Method and apparatus for constant stride accessing to memories in vector processor

• US 5,134,695 A
• Filed: 11/21/1990
• Issued: 07/28/1992
• Est. Priority Date: 03/13/1987
• Status: Expired due to Fees

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Ikeda, Masayuki
• Primary Examiner(s): Bowler, Alyssa H.
• Assistant Examiner(s): LANE, JOHN A
• Application Number:
  US07/616,738
• Time in Patent Office: 615 Days
• Field of Search: 364/200, 364/900
• US Class Current: 711/5
• CPC Class Codes: G06F 12/0207 with multidimensional access, e.g. row/column, matrix
• CPC Class Codes: G06F 12/0607 Interleaved addressing
• CPC Class Codes: G06F 9/3455 using stride

Abstract

A method and apparatus for generating addresses for a constant stride vector addressed memory device. An address generator generates address indices following an equation

c.D=1(mod B)

where B is the bank number of the memory device, D is the stride of the vector addressed memory device and c is a positive integer corresponding in a delta index. By doing so, the requested addresses are successively generated in order of bank addresses of the memory device and, the waiting time of prior constant stride vector access methods is eliminated. And the throughput of the memory device is improved.

Claims

1. An apparatus for accessing a constant stride vector addressed memory device that stores a vector having a starting address and a stride D in a number of memory locations and that includes a number of interleaved memory banks (B) that are consecutively accessed and that have respective bank indexes, said apparatus including:

a distance register connected to store distance signals representing the stride D;

a delta index register connected to store delta signals representing a value c satisfying cD=1(mod B);

index generating means for generating, based on the distance signals and the delta signal, index signals respectively identifying the memory locations of the vector in order of the consecutively accessed bank is; and

adding means for providing the address signals to the constant stride vector addressed memory device based on the index signals.

2. An apparatus according to claim 1, further comprising:

a start address register connected to store starting address signals representing the starting address, and wherein said adding means includes means for providing the address signals based on combining the index signals and the starting address signals.

3. An apparatus according to claim 2, wherein said index generating means includes:

means for generating the index signals representing a value satisfying R (mod Bx D).

4. An apparatus according to claim 3, wherein said correction means comprises:

means for providing first signals representing a value satisfying B×

D;

means for providing second signals representing a value satisfying B×

D×

C;

first and second divider means, each having x any y input terminals and Q and R output terminals, for performing the operation of

space="preserve" listing-type="equation">x+y=Q and R

wherein x, y, Q and R are integers representing signals received at the x and y terminals and provided at the Q and R output terminals, and Q is a quotient and R is a remainder and,

said first divider means having its x terminal connected to receive the index signals, and having its y terminal connected to receive the first signals;

said second divider means having its x terminal connected to receive the index signals, and having its y terminal connected to receive the second signals; and

means, operatively connected to the Q output terminal of said second divider means and to the R output terminal of said first divider means, for multiplying the first signals and the signals from the Q output terminal of said second divider means, and for adding the result of this multiplication to the signals from the R output terminal of said first divider means.

5. An apparatus according to claim 3, wherein said index generating means further comprises correction means for changing the signals outputted from said adding means to signals corresponding to values of an equation

6. An apparatus according to claim 5, wherein said correction means comprises:

means for providing first signals representing a value satisfying B×

D;

means for providing second signals representing a value satisfying B×

D×

C;

means for providing a signal representing a value corresponding to B;

first and second divider means, each having x and y input terminals and Q and R output terminals, for performing the operation of

space="preserve" listing-type="equation">x+y=Q and r

where x, y, Q and R are integers representing signals received at the x and y terminals and provided at the Q and R output terminals, and Q is a quotient and R is a remainder and,

said first divider means having its x terminal connected to receive the index signals, and having its y terminal connected to receive the signal representing B;

said second divider means having its x terminal connected to receive the index signals, and having its y terminal connected to receive the first signals; and

means, operatively connected to the Q output terminals of said second divider means and to the R output terminal of said first divider means, for multiplying the signal representing B and for adding the result of this multiplication to the and the signals from the Q output terminal of said second divider means, signal from the R output terminal of said first divider means.

7. A method of accessing a constant stride vector addressed memory device that stores a vector having a starting address and a stride D in a number of memory locations that includes a number of interleaved memory banks (B) that are consecutively accessed and that have respective bank indexes, said method comprising the steps of:

(a) providing distance signals representing the stride D;

(b) providing delta signals (c) representing a value c satisfying c.D=1(mod B);

(c) generating index signals using the distance signals and the delta signals so that the index signals represent memory locations in consecutively addressed memory banks; and

(d) generating address signals for the constant stride vector addressed memory device based on the index signals.

8. A method for accessing a constant stride vector addressed memory device according to claim 7, further comprising the steps of:

providing staring address signals; and

wherein step (d) includes the substep of;

generating the address signals based on combining the starting address signals and the index signals;

9. A method of accessing a constant stride vector addressed memory device according to claim 8, further comprising the steps of:

generating a signal I_n based on multiplying the delta signal (c) and the distance signals (D);

modifying the signals I_n based on the multiplication of the delta signals (c), the distance signals (D) and the number of consecutively addressed memory banks (B) such that the modified signals I_n have a value representing a value expressed by I_n =R_n (mod B×

c×

D); and

adding a signal having a value representing R_n to the starting address.

10. A method of accessing a constant stride vector addressed memory device according to claim 8, further comprising the steps of:

generating a signal I_n based on multiplying the delta signal (c) and the distance signals (D)

modifying the signals [I_'"'"'n ] I'"'"'_n based on the multiplication of the delta signals (c), the distance signals (D) and the number of consecutively addressed memory banks (B) such that the modified signals I'"'"'_n have a value representing a value expressed by I'"'"'_n =[R_'"'"'n ]R'"'"'_n (mod B); and

multiplying the signals representing R'"'"'_n by the distance signals and adding the resultant value to the starting address.