Back to results
US 5,293,607 AGranted
Flexible N-way memory interleaving
AssigneeHewlett-Packard Company
InventorsRussell C. Brockmann, William S. Jaffe, William R. Bryg
Life of this patent
Estimating the term…
Abstract
The invention comprises methods and apparatuses for interleaving a number of memory cards of different sizes. A restricted range modulo-N adder for identifying and selecting the correct interleave card is provided. Another aspect of the invention provides a computer system with flexible memory interleaving capability.
Claims9
A method of interleaving a plurality of N memory blocks of size S using translated M-bit data addresses, said memory blocks having lines of size L, and N, M, S and L being integers, the method comprising the steps:
- computing the values:
- A=log.sub.2 (S), B=M-A, and I=truncate(log.sub.2 (N);
- defining a first group of bits (B.sub.-- bits) as the B MSBs of the address being translated;
- defining a second group of bits (A.sub.-- bits) as the A LSBs of the address being translated;
- defining a third group of bits (I.sub.-- bits) as the I LSBs of A.sub.-- bits after first stripping away the log.sub.2 (L) LSBs of A.sub.-- bits;
- computing an unadjusted sum (SUM) and an adjusted sum (ADJ.sub.-- SUM) in accordance with the following definitions;
- SUM=B.sub.-- bits+I.sub.-- bits, (i)
- and
- ADJ.sub.-- SUM=B.sub.-- bits+I.sub.--bits-N;
- defining a block number corresponding to the address being translated, said bock number being a function of at least one of the values of SUM or ADJ.sub.-- SUM;
- and
- addressing a memory in accordance with said block number.
9 more elements
A method of interleaving a plurality of N memory blocks of size S using translated M-bit data addresses, said memory blocks having lines of size L, and N, M, S and L being integers, the method comprising the steps:
- identifying a first group of bits (B.sub.-- bits) of an address being translated;
- identifying a second group of bits (I.sub.-- bits) defining an interleave index corresponding to the address being translated;
- assigning said memory blocks to a plurality of groups, each group being identified by a number GS;
- computing an unadjusted sum (SUM) and an adjusted sum (ADJ.sub.-- SUM) in accordance with the following definitions;
- SUM=B.sub.-- bits+I.sub.-- bits-GS, (i)
- and
- ADJ.sub.-- SUM=B.sub.-- bits+I.sub.-- bits-(N+GS);
- defining a block number corresponding to the address being translated, said block number being a function of at least one of the values of SUM or ADJ.sub.-- SUM;
- and
- addressing a memory in accordance with said block number.
7 more elements
A digital system, comprising:
- (a) a computer;
- (b) memory means, coupled to the computer and comprising N memory blocks of size S, N and S being integers, for storing a list of data values in associated storage locations, each storage location being identifiable by an associated M-bit address, M being an integer;
- (c) addressing means for reading/writing said data values from/to said memory means in an interleaved fashion, said addressing means comprising:
- (i) means for identifying a first group of bits (B.sub.-- bits) of an address being translated;
- (ii) means for identifying a second group of bits (I.sub.-- bits) defining an interleave index corresponding to the address being translated;
- (iii) means for computing an unadjusted sum (SUM) and an adjusted sum (ADJ.sub.-- SUM) in accordance with the following definitions;
- SUM=B.sub.-- bits+I.sub.-- bits,
- and
- ADJ.sub.-- SUM=B.sub.-- bits+I.sub.-- bits-N;
- and
- (iv) means for defining a block number corresponding to the address being translated, comprising means for selecting as the block number the value of SUM when ADJ.sub.-- SUM is less than zero, and selecting as the block number the value of ADJ.sub.-- SUM when ADJ.sub.-- SUM is greater than or equal to zero;
- (d) means for dividing said memory means into a plurality of groups, each group being identified by a number GS;
- and
- (e) means for subtracting said number GS identifying each group from the sums computed by said means for computing an unadjusted sum and an adjusted sum.
11 more elements
A digital system, comprising:
- a computer;
- memory means, coupled to the computer and comprising N memory blocks of size S, N and S being integers, for storing a list of data values in associated storage locations, each storage location being identifiable by an associated M-bit address, M being an integer;
- and
- addressing means for reading/writing said data values from/to said memory means in an interleaved fashion, sad addressing means comprising:
- means for identifying a first group of bits (B.sub.-- bits) of an address being translated;
- means for identifying a second group of bits (I.sub.-- bits) defining an interleave index corresponding to the address being translated;
- means for computing an unadjusted sum (SUM) and an adjusted sum (ADJ.sub.-- SUM) in accordance with the following definitions:
- SUM=B.sub.-- bits+I.sub.-- bits,
- and
- ADJ.sub.-- SUM=B.sub.-- bits+I.sub.-- bits-N;
- and
- means for defining a block number corresponding to the address being translated, said block number being a function of at least one of the values of SUM or ADJ.sub.-- SUM;
- means for computing the values:
- A=log.sub.2 (S), B=M-A, and I=truncate(log.sub.2 (N));
- means for defining B.sub.-- bits as the B MSBs of the address being translated;
- means for defining A.sub.-- bits as the A LSBs of the address being translated;
- and
- means for defining I.sub.-- bits as the I LSBs of A.sub.-- bits after first stripping away the log.sub.2 (L) LSBs of A.sub.-- bits.
15 more elements
A digital system, comprising:
- (a) a computer;
- (b) memory means, coupled to the computer and comprising N memory blocks of size S, N and S being integers, for storing a list of data values in associated storage locations, each storage location being identifiable by an associated M-bit address, M being an integer;
- and
- (c) addressing means for reading/writing said data values from/to said memory means in an interleaved fashion, said addressing means comprising:
- (i) means for identifying a first group of bits (B.sub.-- bits), comprising means for computing the values A=log.sub.2 (S), B=M-A, and I=truncate(log.sub.2 (N)), and means for defining B.sub.-- bits as the B MSBs of the address being translated;
- (ii) means for identifying a second group of bits (I.sub.-- bits) defining an interleave index corresponding to the address being translated, comprising means for identifying the A LSBs of the address being translated (A.sub.-- bits), and means for defining I.sub.-- bits as the I LSBs of A.sub.-- bits after first stripping away the log.sub.2 (L) LSBs of A.sub.-- bits;
- (iii) means for dividing said memory means into a plurality of groups, each group being identified by a number GS;
- (iv) summing means for computing an unadjusted sum (SUM) and an adjusted sum (ADJ.sub.-- SUM) in accordance with the following definitions;
- SUM=B.sub.-- bits+I.sub.-- bits-GS,
- and
- ADJ.sub.-- SUM=B.sub.-- bits+I.sub.-- bits-(GS+N);
- and
- (v) means for defining a block number corresponding to the address being translated, said block number being selected as the value of SUM when ADJ.sub.-- SUM is less than zero and as the value of ADJ.sub.-- SUM when ADJ.sub.-- SUM is greater than or equal to zero.
10 more elements
Dependencies are inferred from the claim text.