US5377340A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for memory interleaving using an improved hashing scheme
Assignee: HP Inc
•
Filing: 1991-06-18
•
Granted: 1994-12-27
•
Expires: 2011-06-18
Abstract
Abstract A novel memory hashing system is disclosed. The system converts an address into a hashed address of the form (B,C) where B is a module number in a multi-module memory system and C is an offset in the module. The system can be shown to have no pathological cases for any stride value less than some predetermined value. An apparatus according to the present invention is conveniently implemented in a pipelined architecture which allows one address value to be calculated each memory cycle. The present invention utilizes a special matrix calculated from a primitive polynomial for calculating the hashed addresses. The conversion of any given address requires one row of the matrix. The entries of the matrix may be stored in ROM. Alternatively, the required row of the matrix may be calculated in response to receiving the address which is to be convened to the hashed address.
Inventors
- 👤 Gadiel Seroussi
- 👤 Abraham Lempel
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-01 05:38
CPC Classifications
G; G06; G06F; G06F12/00; G06F12/02; G06F12/06; G06F12/0607
Claims Analysis
Total Claims: 8
Claim 1
Independent Claim
150 words
An apparatus for assigning a memory address having a value of A. where A is a positive integer, to a memory module B comprising one of 2 m memory modules in an interleaved memory, said apparatus comprising: means for receiving an l-bit binary representation of A; means for computing a reduced address value, r, equal to (A mod p), where p=2 n -1, and n is a positive integer satisfying m≦n≦l; means for generating the entries of a binary mapping matrix comprising p rows and n columns, each said row being assigned a unique row number between 0(p-1); and means for generating a binary representation of B, said binary representation comprising m predetermined bits of one of said rows of said binary mapping matrix having the assigned row number equal to r, said row being referred to as the r th one of said rows of said binary mapping matrix.
Claim 2
Independent Claim
150 words
An apparatus for assigning a memory address having a value of A. where A is a positive integer, to a memory module B comprising one of 2 m memory modules in an interleaved memory, said apparatus comprising: means for receiving an l-bit binary representation of A; means for computing a reduced address value, r, equal to (A mod p), where p=2 n -1, and n is a positive integer satisfying m≦n≦l; means for generating the entries of a binary mapping matrix comprising p rows and n columns, each said row being assigned a unique row number between 0(p-1); and means for generating a binary representation of B, said binary representation comprising m predetermined bits of one of said rows of said binary mapping matrix having the assigned row number equal to r, said row being referred to as the r th one of said rows of said binary mapping matrix.
Claim 3
Dependent Claim
65 words
The apparatus of claim 1 further comprising means for computing an offset address within said memory module B, the bits of the binary representation of said offset address being determined by the n-m bits of said r th row of said binary mapping matrix that were not used in generating said binary representation of B, and the binary representation of the integer part of A/p.
Claim 4
Dependent Claim
225 words
The apparatus of claim 2 wherein said means for generating said binary mapping matrix comprises a plurality of stages including a primary stage and one or more secondary stages. each said primary and secondary stages comprising: means for receiving clock signals; an n-bit input means for receiving the binary representation of an n-bit number; means for scaling a binary representation of the n-bit number to generate a plurality of scaled inputs, each said scaled input comprising said binary representation of the n-bit number multiplied by a constant having a value equal to one or to a number whose binary representation comprises one row of said binary mapping matrix; multiplexer means for selecting one of said scaled inputs in response to predetermined bits of r; and register means comprising means for storing a selected one of said scaled inputs and output means for outputting a stored scaled input; and said means for generating the entries of said binary mapping matrix further comprising means for generating the value one at an input of said primary stage, said one or more secondary stages being connected in series such that the m-bit input means of each stage is connected to the output means of the register means in the previous stage, an output of the last said secondary stage comprising the r th row of said binary mapping matrix.
Claim 5
Dependent Claim
54 words
The apparatus of claim 3 wherein said multiplexer means in said secondary stages further comprise means for delaying the arrival of said predetermined bits of r by a number of clock pulses dependent on the position of one of said secondary stages in said means for generating the entries of said binary mapping matrix.
Claim 6
Dependent Claim
204 words
The apparatus of claim 3 wherein said means for computing said reduced address value, r, comprises: first and second registers, said first register comprising means for storing the l-n most significant bits of A, and said second register comprising means for storing the n least significant bits of A; first adder means for adding the contents of said first and second registers and generating an (n+1)-bit value representing the sum of said first and second registers, said first adder means including a first sum register for storing the most significant bit of said (n+1)-bit value and a second sum register for storing the least significant n-bits of said (n+1)-bit value; means for generating a signal having a first value if the contents of said first sum register is a one or if the contents of said second sum register are all ones, and a second value otherwise; and means for assigning the contents of said second sum register plus one as said reduced address value, r, if said for generating a signal means generates said first value and for assigning the contents of said second sum register as said reduced address value, r, if said for generating a signal means generates said second value.
Claim 7
Dependent Claim
58 words
The apparatus of claim 5 wherein said means for computing the integer part of A/p comprises means for assigning said integer part the contents of said first register if said for generating a signal means generates said value and the contents of said first register plus one if said for generating a signal means generates said second value.
Claim 8
Dependent Claim
22 words
The apparatus of claim 1 wherein said means for generating said binary mapping matrix comprises memory means for storing said mapping matrix.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1997-12-26 | 1998-06-27 | 1998-12-27 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2001-12-26 | 2002-06-27 | 2002-12-27 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2005-12-26 | 2006-06-27 | 2006-12-27 | $7700.00 | Window Closed / Lapsed |