High-performance interleaved memory system comprising a prime number of memory modules

In a prime-way interleaved memory system comprising:

• a) a prime number P of memory modules, wherein P=2.sup.k -.DELTA. and wherein k and .DELTA. are any integers;
• b) 2.sup.m memory banks in each of said memory modules, each of said memory banks being indexed from 0 to 2.sup.m-1, wherein m is any integer .gtoreq.0;
• c) 2.sup.l-m memory locations in each of said memory banks, for a total of P(2.sup.l) memory locations in said memory system, wherein 1 is any integer .gtoreq.m, each of said memory locations being capable of storing a single datum or word, and each of said P(2.sup.l) memory locations being identified by a memory address A in the form of an n-bit binary string A=A.sub.n-1 . . .A.sub.0, wherein n=l+k;
• THE IMPROVEMENT COMPRISING
• d) means for mapping each said memory address A to a unique location L/2.sup.m of a unique memory bank L mod 2.sup.m of a unique memory module A mod P;
• wherein L is generated as a function of A according to any one of a family of bijective mappings equivalent to ##EQU12##

In a prime-way interleaved memory system comprising:

• a) a prime number P of memory modules, wherein P=2.sup.k +.DELTA. and wherein k and .DELTA. are any integers;
• b) 2.sup.m memory banks in each of said memory modules, each of said memory banks being indexed from 0 to 2.sup.m- 1, wherein m is any integer .gtoreq.0;
• c) 2.sup.l-m memory locations in each of said memory banks, for a total of P(2.sup.l) memory locations in said memory system, wherein 1 is any integer .gtoreq.m, each of said memory locations being capable of storing a single datum or word, and each of said P(2.sup.l) memory locations being identified by a memory address A in the form of an n-bit binary string A=A.sub.n-1 . . .A.sub.0, wherein n=l+k+1;
• THE IMPROVEMENT COMPRISING
• d) means for mapping each said memory address A to a unique location L/2.sup.m of a unique memory bank L mod 2.sup.m of a unique memory module A mod P;
• wherein L is generated as a function of A according to any one of a family of bijective mappings equivalent to ##EQU13##

A method for minimizing memory access conflicts among concurrent access of multiple vectors to a multi-port interleaved memory system having a prime number P of memory modules, comprising the steps of:

• a) generating memory addresses A.sub.0, A.sub.1, . . . , A.sub.VL-1 for a vector of length VL with a starting address SA and a stride S in an optimized address sequence of the .alpha.-type at each memory port , where .alpha. is an integer in the range from 1 to P-1 and is fixed for all memory ports of said memory system by
• i) setting A.sub.0 :=SA;
• ii) computing s:=.vertline.S.vertline. mod P;
• iii) obtaining I(.alpha.), from a set I(.alpha.), wherein I(.alpha.) is a set of P precomputed integers I(.alpha.)={I(.alpha.).sub.s .vertline.0.ltoreq.s.ltoreq.P-1} where I(.alpha.).sub.s is an integer in the range from 1 to P-1 such that I(.alpha.).sub.s .times.s=.alpha. (modulo P) and I(.alpha.).sub.s =1 if s=0;
• iv) obtaining CV (.alpha.) from a set CV (.alpha.) , wherein CV (.alpha.) is a set of P precomputed control vectors CV(.alpha.)={CV(.alpha.).sub.s .vertline.0.ltoreq.s.ltoreq.P-1} where CV(.alpha.).sub.s is a control vector of P bits indexed from 0 to P-1;
• v) setting R1:=I (.alpha.).sub.s s.times.S;
• vi) setting R0:=(P-i (.alpha.).sub.s).times.S;
• vii) generating A.sub.i+1 for i=0, 1, . . . , VL-(VL mod P)-1 by
• vii-a) setting A.sub.i+l :=A.sub.i +R1 if bit (i mod P) of CV(.alpha.).sub.s is 1;
• vii-b) setting A.sub.i+1 :=A.sub.i -R0 if bit (i mod P) of CV(.alpha.).sub.s is 0;
• viii) generating A.sub.i+1 for i=VL-(VL mod P), . . . , VL-2 by setting A.sub.i+1 :=Ai+S;
• and
• b) ordering each memory port to access words of said vector in the order in which their addresses appear in said optimized address sequence of the .alpha.-type.