US5479624A
Expired / Lapsed
US
⏱️ 0.0 years remaining
High-performance interleaved memory system comprising a prime number of memory modules
Assignee: Lee Res Inc
•
Filing: 1992-10-14
•
Granted: 1995-12-26
•
Expires: 2012-10-14
Abstract
Abstract A method for implementation of muti-port interleaved memory systems comprising any prime number P of memory modules each of which contains a power of two memory banks. Each memory bank comprises a power of two memory locations. In this method, sequential addresses are mapped into sequential memory modules, and the addresses mapped into a given module are mapped into distinct memory locations within the module without explicit and implicit operations of division by the prime number P. The method embodies families of functions any one of which can be used for the bijective mapping of addresses into memory locations within a memory module. Furthermore, any of the functions is computable in O(1) gate delays employing O(log 2 P) logic gates. A multi-port interleaved memory system with P memory modules can serve multiple requests for vectors of data, where each memory port is used to serve a request for a vector of data. Disclosed is also a method for generating memory addresses for words of a vector in optimized address sequence of the α-type, where α is a fixed integer in the range 1≦α≦P-1. Serving a request for a vector of data at each memory port by accessing words of the vector in optimized sequence of the α-type minimizes memory access conflicts among the concurrent access of multiple vectors when the value of α is fixed at the same value for all memory ports.
Inventors
- 👤 De-Lei Lee
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-06 08:56
CPC Classifications
G; G06; G06F; G06F12/00; G06F12/02; G06F12/06; G06F12/0607
Claims Analysis
Total Claims: 17
Claim 1
Independent Claim
299 words
In a prime-way interleaved memory system for use in a computing system which requests access of one or more vectors of data, comprising: a) a prime number P of memory modules arranged into K sections, wherein P=2 k ±Δ and wherein k and Δ are any integers; b) 2 m memory banks in each of said memory modules, each of said memory banks being indexed from 0 to 2 m-1 , wherein m is any integer ≧0, each one of said memory banks having 2 l-m memory locations, for a total of P(2 l ) memory locations in said memory system, wherein 1 is any integer ≧m, each of said memory locations being capable of storing a single datum or word, each of said P(2 l ) memory locations being identified by a memory address of the form A=A n-1 . . . A 0 , wherein n=l+k when P=2 k -Δ and n=l+k+1 when P=2 k +Δ; c) a plurality of memory ports for access by said computing system; d) switching means for connecting one of said memory ports to one of said memory banks within one of said memory modules within one of said sections in response to access to said memory location A of said one of said memory banks; THE IMPROVEMENT COMPRISING e) index generating means associated with each of said plurality of memory ports for generating a set of indices for locating a unique memory location L/2 m of a unique memory bank L mod 2 m of a unique memory module A mod P of a unique Section (A mod P) mod K, as a function of said memory address A to be accessed, wherein L is in the form of an l-bit binary string L=L l-1 . . . L 0 .
Claim 2
Dependent Claim
299 words
In a prime-way interleaved memory system for use in a computing system which requests access of one or more vectors of data, comprising: a) a prime number P of memory modules arranged into K sections, wherein P=2 k ±Δ and wherein k and Δ are any integers; b) 2 m memory banks in each of said memory modules, each of said memory banks being indexed from 0 to 2 m-1 , wherein m is any integer ≧0, each one of said memory banks having 2 l-m memory locations, for a total of P(2 l ) memory locations in said memory system, wherein 1 is any integer ≧m, each of said memory locations being capable of storing a single datum or word, each of said P(2 l ) memory locations being identified by a memory address of the form A=A n-1 . . . A 0 , wherein n=l+k when P=2 k -Δ and n=l+k+1 when P=2 k +Δ; c) a plurality of memory ports for access by said computing system; d) switching means for connecting one of said memory ports to one of said memory banks within one of said memory modules within one of said sections in response to access to said memory location A of said one of said memory banks; THE IMPROVEMENT COMPRISING e) index generating means associated with each of said plurality of memory ports for generating a set of indices for locating a unique memory location L/2 m of a unique memory bank L mod 2 m of a unique memory module A mod P of a unique Section (A mod P) mod K, as a function of said memory address A to be accessed, wherein L is in the form of an l-bit binary string L=L l-1 . . . L 0 .
Claim 3
Dependent Claim
34 words
The memory system of claim 1, wherein P=2 k -Δ and said index generating means' generates said l-bit binary string L according to any one of a family of bijective mappings equivalent to ##EQU10##
Claim 4
Dependent Claim
202 words
The memory system of claim 2, wherein said index generating means further comprises: i) means for partitioning said address A into a first segment of k bits, a second segment of (l-k) bits and a third segment of k bits such that the first k-bit segment comprises the address bits A n-1 . . . A 1 , the second (l-k)-bit segment comprises the address bits A l-1 . . . A k and the third k-bit segment comprises the address bits A l-1 . . . A 0 ; ii) sensor means for detecting whether A mod 2 k <Δ is true; iii) means for concatenating said first k-bit segment with said second (l-k) bit segment in the event A mod 2 k <Δ is not true, thereby generating said l-bit binary string L of the form A n-1 . . . A l A l-1 . . . A k ; and iv) means for concatenating the bitwise complement of said third k-bit segment with said second (l-k) bit segment in the event A mod 2 k <Δ is true, thereby generating said l-bit binary string L of the form A.sub.k-1 . . . A.sub.0 A.sub.l-1 . . . A.sub.k.
Claim 5
Dependent Claim
34 words
The memory system of claim 1, wherein P=2 k +Δ and said index generating means generates said l-bit binary string L according to any one of a family of bijective mappings equivalent to ##EQU11##
Claim 6
Dependent Claim
201 words
The memory system of claim 4, wherein said index generating means further comprises: i) means for partitioning said address A into a first segment of k+1 bits, a second segment of (l-k-1) bits and a third segment of k+1 bits such that the first (k+1)-bit segment comprises the address bits A n-1 . . . A 1 , the second (l-k-1)-bit segment comprises the address bits A l-1 . . . A k+1 and the third (k+1)-bit segment comprises the address bits A k . . . A 0 ; ii) sensor means for detecting whether A mod 2 k+1 <P-2Δ is true; iii) means for concatenating said first (k+1)-bit segment with said second (l-k-1)-bit segment in the event A mod 2 k+1 <P-2Δ is not true, thereby generating said l-bit binary string L of the form A n-1 . . . A 1 , A l-1 . . . A k+1 ; and iv) means for concatenating the bitwise complement of said third (k+1)-bit segment with said second (l-k-1)-bit segment in the event A mod 2 k+1 <P-2Δ is true, thereby generating said l-bit binary string L of the form A.sub.k . . . A.sub.0 A.sub.l-1 . . . A.sub.k+1.
Claim 7
Dependent Claim
191 words
In a prime-way interleaved memory system comprising: a) a prime number P of memory modules, wherein P=2 k -Δ and wherein k and Δ are any integers; b) 2 m memory banks in each of said memory modules, each of said memory banks being indexed from 0 to 2 m-1 , wherein m is any integer ≧0; c) 2 l-m memory locations in each of said memory banks, for a total of P(2 l ) memory locations in said memory system, wherein 1 is any integer ≧m, each of said memory locations being capable of storing a single datum or word, and each of said P(2 l ) memory locations being identified by a memory address A in the form of an n-bit binary string A=A n-1 . . .A 0 , wherein n=l+k; THE IMPROVEMENT COMPRISING d) means for mapping each said memory address A to a unique location L/2 m of a unique memory bank L mod 2 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##
Claim 8
Dependent Claim
191 words
In a prime-way interleaved memory system comprising: a) a prime number P of memory modules, wherein P=2 k -Δ and wherein k and Δ are any integers; b) 2 m memory banks in each of said memory modules, each of said memory banks being indexed from 0 to 2 m-1 , wherein m is any integer ≧0; c) 2 l-m memory locations in each of said memory banks, for a total of P(2 l ) memory locations in said memory system, wherein 1 is any integer ≧m, each of said memory locations being capable of storing a single datum or word, and each of said P(2 l ) memory locations being identified by a memory address A in the form of an n-bit binary string A=A n-1 . . .A 0 , wherein n=l+k; THE IMPROVEMENT COMPRISING d) means for mapping each said memory address A to a unique location L/2 m of a unique memory bank L mod 2 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##
Claim 9
Dependent Claim
191 words
In a prime-way interleaved memory system comprising: a) a prime number P of memory modules, wherein P=2 k +Δ and wherein k and Δ are any integers; b) 2 m memory banks in each of said memory modules, each of said memory banks being indexed from 0 to 2 m- 1, wherein m is any integer ≧0; c) 2 l-m memory locations in each of said memory banks, for a total of P(2 l ) memory locations in said memory system, wherein 1 is any integer ≧m, each of said memory locations being capable of storing a single datum or word, and each of said P(2 l ) memory locations being identified by a memory address A in the form of an n-bit binary string A=A n-1 . . .A 0 , wherein n=l+k+1; THE IMPROVEMENT COMPRISING d) means for mapping each said memory address A to a unique location L/2 m of a unique memory bank L mod 2 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##
Claim 10
Dependent Claim
191 words
In a prime-way interleaved memory system comprising: a) a prime number P of memory modules, wherein P=2 k +Δ and wherein k and Δ are any integers; b) 2 m memory banks in each of said memory modules, each of said memory banks being indexed from 0 to 2 m- 1, wherein m is any integer ≧0; c) 2 l-m memory locations in each of said memory banks, for a total of P(2 l ) memory locations in said memory system, wherein 1 is any integer ≧m, each of said memory locations being capable of storing a single datum or word, and each of said P(2 l ) memory locations being identified by a memory address A in the form of an n-bit binary string A=A n-1 . . .A 0 , wherein n=l+k+1; THE IMPROVEMENT COMPRISING d) means for mapping each said memory address A to a unique location L/2 m of a unique memory bank L mod 2 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##
Claim 11
Independent Claim
124 words
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 0 , A 1 , . . . A VL-1 for a vector of length VL with a starting address SA and a stride S in an optimized address sequence of the α-type at each memory port, where a is an integer in the range from 1 to P-1 and is fixed for all memory ports of said memory system, 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 α-type.
Claim 12
Independent Claim
124 words
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 0 , A 1 , . . . A VL-1 for a vector of length VL with a starting address SA and a stride S in an optimized address sequence of the α-type at each memory port, where a is an integer in the range from 1 to P-1 and is fixed for all memory ports of said memory system, 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 α-type.
Claim 13
Dependent Claim
209 words
The method of claim 8, wherein said step of generating memory addresses A 0 , A 1 , . . . , A VL-1 in said optimized address sequence of the α-type for said vector comprises executing the steps of: a) setting A 0 :=SA; b) computing s:=|S| mod P; c) obtaining I(α), from a set I(α), wherein I(α) is a set of P precomputed integers I(α)={I(α) s |0≦s≦P-1} where I(α) s is an integer in the range from 1 to P-1 such that I(α) s ×s=α(modulo P) and I(α) s =1 if s=0; d) obtaining CV (α) from a set CV (α), wherein CV (α) is a set of P precomputed control vectors CV(α)={CV(α) s |0≦s≦P-1} where CV(α)s is a control vector of P bits indexed from 0 to P-1; e) setting R1:=I(α) s ×S; f) setting R0:=(P-i(α) s )×S; g) generating A i+1 for i=0, 1, . . . , VL-(VL mod P)-1 by i) setting A i+1 :=A i +R1 if bit (i mod P) of CV(α) s is 1; ii) setting A i+1 :=A i -R0 if bit (i mod P) of CV(α) s is 0; h) generating A i+1 for i=VL-(VL mod P) , . . . , VL-2 by setting A i+1 :=Ai+S.
Claim 14
Dependent Claim
125 words
A method for constructing the set of P precomputed control vectors CV(α) as set forth in claim 9 including a procedure, which uses the set of integers I (α) as set forth in claim 9, to construct control vector CV(α) s , in said set for any given s in the range from 1 to P-1, comprising the steps of: a) initializing a variable A to 0; b) computing bit i of CV(α) s for i=0, 1, . . . P-1 by executing i) if A≦(P-I(α) s )×s, setting bit i of CV(α) s to 1 and replacing A by A+I (α) s ×s ii) if A>(P-I(α) s )×s, setting bit i of CV(α) s to 0 and replacing A by A-(P-I (α) s )×s.
Claim 15
Independent Claim
300 words
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 0 , A 1 , . . . , A VL-1 for a vector of length VL with a starting address SA and a stride S in an optimized address sequence of the α-type at each memory port , where α 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 0 :=SA; ii) computing s:=|S| mod P; iii) obtaining I(α), from a set I(α), wherein I(α) is a set of P precomputed integers I(α)={I(α) s |0≦s≦P-1} where I(α) s is an integer in the range from 1 to P-1 such that I(α) s ×s=α (modulo P) and I(α) s =1 if s=0; iv) obtaining CV (α) from a set CV (α) , wherein CV (α) is a set of P precomputed control vectors CV(α)={CV(α) s |0≦s≦P-1} where CV(α) s is a control vector of P bits indexed from 0 to P-1; v) setting R1:=I (α) s s×S; vi) setting R0:=(P-i (α) s )×S; vii) generating A i+1 for i=0, 1, . . . , VL-(VL mod P)-1 by vii-a) setting A i+l :=A i +R1 if bit (i mod P) of CV(α) s is 1; vii-b) setting A i+1 :=A i -R0 if bit (i mod P) of CV(α) s is 0; viii) generating A i+1 for i=VL-(VL mod P), . . . , VL-2 by setting A 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 α-type.
Claim 16
Independent Claim
300 words
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 0 , A 1 , . . . , A VL-1 for a vector of length VL with a starting address SA and a stride S in an optimized address sequence of the α-type at each memory port , where α 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 0 :=SA; ii) computing s:=|S| mod P; iii) obtaining I(α), from a set I(α), wherein I(α) is a set of P precomputed integers I(α)={I(α) s |0≦s≦P-1} where I(α) s is an integer in the range from 1 to P-1 such that I(α) s ×s=α (modulo P) and I(α) s =1 if s=0; iv) obtaining CV (α) from a set CV (α) , wherein CV (α) is a set of P precomputed control vectors CV(α)={CV(α) s |0≦s≦P-1} where CV(α) s is a control vector of P bits indexed from 0 to P-1; v) setting R1:=I (α) s s×S; vi) setting R0:=(P-i (α) s )×S; vii) generating A i+1 for i=0, 1, . . . , VL-(VL mod P)-1 by vii-a) setting A i+l :=A i +R1 if bit (i mod P) of CV(α) s is 1; vii-b) setting A i+1 :=A i -R0 if bit (i mod P) of CV(α) s is 0; viii) generating A i+1 for i=VL-(VL mod P), . . . , VL-2 by setting A 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 α-type.
Claim 17
Dependent Claim
125 words
A method for constructing the set of P precomputed control vectors CV(α) as set forth in claim 11 including a procedure, which uses the set of integers I (α) as set forth in claim 11, to construct control vector CV(α) s , in said set for any given s in the range from 1 to P-1, comprising the steps of: a) initializing a variable A to 0; b) computing bit i of CV(α) s for i=0, 1, . . . P-1 by executing i) if A≦(P-I(α) s )×s, setting bit i of CV(α) s to 1 and replacing A by A+I (α) s ×s ii) if A>(P-I(α) s )×s, setting bit i of CV(α) s to 0 and replacing A by A-(P-I (α) s )×s.
References Cited (Backward Citations)
US4051551A
Cited
US4101960A
Cited
US4334285A
Cited
US4400768A
Cited
US5111389A
Cited
US5276826A
Cited
US4918600A
Cited
US5123095A
Cited
US5247645A
Cited
US5323489A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1998-12-25 | 1999-06-26 | 1999-12-26 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2002-12-25 | 2003-06-26 | 2003-12-26 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2006-12-25 | 2007-06-26 | 2007-12-26 | $7700.00 | Window Closed / Lapsed |