Cache column multiplexing using redundant form addresses

• US 6,507,531 B1
• Filed: 03/29/2000
• Issued: 01/14/2003
• Est. Priority Date: 03/29/2000
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Zhang, Kevin X.
• Primary Examiner(s): Lebentritt, Michael S.
• Assistant Examiner(s): Nguyen, Tuan T.
• Application Number:
  US09/538,553
• Time in Patent Office: 1,021 Days
• Field of Search: 365/230.02, 365/230.06
• US Class Current: 365/230.02
• CPC Class Codes: G11C 15/00 Digital stores in which information comprising one or more characteristic parts is written into the store and in which information is read-out by searching for one or more of these characteristic parts, i.e. associative or content-addressed stores
• CPC Class Codes: G11C 8/10 Decoders

Abstract

A method and apparatus uses possible wordline subsequence identifiers to multiplex columns for addresses received in redundant form, including addresses received from a bypass circuit. A cache wordline decoder uses carry-nonpropagative pre-decode circuitry to identify possible subsequences from redundant addresses. Identified subsequences are combined to identify wordline sequences and to activate corresponding wordline enable signals to access data stored in cache memory. A wordline may correspond to storage locations for multiple addresses. Identified possible subsequences are used to directly multiplex cache columns and the columns are organized so as to guarantee mutual exclusivity.

Claims

1. An apparatus comprising:

a plurality of storage locations associated with a plurality of bitlines;

a pre-decoder to receive an address in redundant form and to identify one or more possible subsequences of bit values corresponding to each of a plurality of digit positions in the redundant address; and

a first column multiplexer having a first bitline output, the first column multiplexer to receive a first plurality of data values on a first portion of the plurality of bitlines, and to select a first bitline having a first data value in response to a first identifier of the one or more possible subsequences of bit values identified.

2. The apparatus recited in claim 1 further comprising:

a wordline decoder, from one or more of the identified possible subsequences of bit values, to identify a wordline and to access a first portion of the plurality of storage locations associated with the first portion of the plurality of bitlines.

3. The apparatus recited in claim 2 wherein the first identifier of the one or more possible subsequences of bit values identified is excluded from said one or more of the identified possible subsequences of bit values used to identify the wordline.

4. The apparatus recited in claim 1 wherein the address in redundant form is in a carry-sum redundant form.

5. The apparatus recited in claim 4 wherein the one or more possible subsequences of bit values identified include a subsequence of length two or more bits.

6. The apparatus recited in claim 5 wherein the one or more possible subsequences of bit values are identified according one or more of a plurality of logical relations equivalent to or including:

7. The apparatus recited in claim 1 wherein the address in redundant form is in a sign-digit redundant form.

8. The apparatus recited in claim 7 wherein the one or more possible subsequences of bit values identified include a subsequence of length two or more bits.

9. The apparatus recited in claim 8 wherein the one or more possible subsequences of bit values are identified according to one or more of a plurality of logical relations equivalent to or including:

10. The apparatus recited in claim 1 wherein the first identifier of the one or more possible subsequences of bit values identified corresponds to an identified possible subsequence having a length of two or more bits.

11. The apparatus recited in claim 10 wherein the first column multiplexer is coupled with the pre-decoder to receive a second identifier of the one or more possible subsequences of bit values identified, which is mutually exclusive of the first identifier of the one or more possible subsequences of bit values identified, and which indicates a bit value that is the same as a corresponding bit value indicated by the first identifier, the indicated bit value occurring in a least significant bit position of the possible subsequence identified by the second identifier.

12. The apparatus recited in claim 1 further comprising:

a second column multiplexer having a second bitline output, to receive a second plurality of data values on a second portion of the plurality of bitlines, and to select a second bitline having a second data value in response to a second identifier of the one or more possible subsequences of bit values identified.

13. The apparatus recited in claim 12 wherein the second column multiplexer is coupled to receive data from the first bitline output of the first column multiplexer.

14. The apparatus recited in claim 13 wherein the second identifier of the one or more possible subsequences of bit values identified indicates a bit value occurring in a bit position that does not correspond to a bit position in the possible subsequence identified by the first identifier.

15. The apparatus recited in claim 12 further comprising:

a common bitline output coupled with the first bitline output to receive the first data value from the first column multiplexer and coupled with the second bitline output to receive the second data value from the second column multiplexer.

16. The apparatus recited in claim 15 wherein the second identifier of the one or more possible subsequences of bit values identified indicates a bit value that is the same as a corresponding bit value indicated by the first identifier, the indicated bit value occurring in a most significant bit position of the possible subsequence identified by the second identifier.

17. The apparatus recited in claim 15 wherein the first data value and the second data value are not received as inverted signals.

18. A digital computing system comprising:

a processor core;

an internal cache having a first plurality of storage locations and a first plurality of corresponding bitlines including a first bitline on which to transmit a first data value;

a pre-decoder to receive an address in redundant form from the processor core and to identify one or more possible subsequences of bit values corresponding to each of a plurality of digit positions in the redundant address;

a first column multiplexer having a first bitline output, the first column multiplexer to receive a first plurality of data values on the first plurality of bitlines, and to select the first bitline in response to a first identifier of the one or more possible subsequences of bit values identified; and

an external cache having a second plurality of storage locations including a storage location to store a second data value, the external cache coupled with the internal cache, to transmit the second data value to the internal cache.

19. The digital computing system recited in claim 18 further comprising:

a wordline decoder to identify a wordline from one or more of the identified possible subsequences of bit values and to access the first plurality of storage locations of the internal cache.

20. The digital computing system recited in claim 19 wherein the first identifier of the one or more possible subsequences of bit values identified is excluded from said one or more of the identified possible subsequences of bit values used to identify a wordline.

21. A method comprising:

receiving an address in redundant form;

identifying a possible subsequence of bit values corresponding to the address received;

activating one or more possible subsequence indicators corresponding to the possible subsequence of bit values identified;

using a first possible subsequence indicator of the one or more possible subsequence indicators activated to select from a plurality of data sources a first data source from which to receive a first data value;

transmitting a data output value in response to the first data value received from the selected first data source.

22. The method recited in claim 21 further comprising:

activating a plurality of possible subsequence indicators associated with a plurality of digit positions in the address received;

combining the plurality of possible subsequence indicators activated to identify a wordline, the combined plurality of possible subsequence indicators excluding the first possible subsequence indicator;

in accordance with the identified wordline, activating the plurality of data sources to supply data values.

23. A cache memory system comprising:

a plurality of lines and columns for storing copies of memory storage locations having corresponding addresses;

means for decoding a first portion of an address to access a line of the cache memory system responsive to an access request that includes an address represented in a redundant form; and

means for decoding a second portion of the address represented in the redundant form into one or more indicators of possible subsequences of bit values to access a column of the cache memory system.

24. An apparatus comprising:

a pre-decoder to receive an address in a redundant form and to identify, from the redundant form of the address, one or more possible subsequences of values for bit positions in the address;

a wordline decoder, responsive to one or more of the identified possible subsequences of values, to identify a wordline to enable a plurality of bitlines associated with a plurality of storage locations; and

a first selector coupled with the pre-decoder and identified with a first one of the one or more possible subsequences of values for bit positions in the address to select a first bitline of the plurality of enabled bitlines when the first one of the one or more possible subsequences of values for bit positions in the address is identified by the pre-decoder.

25. The apparatus recited in claim 24 further comprising:

a second selector coupled with the pre-decoder, which is mutually exclusive of the first selector, and which indicates a value for a bit position in the address that is the same as a corresponding value indicated by the first selector, the second selector to select a second bitline of the plurality of enabled bitlines when a second one of the one or more possible subsequences of values for bit positions in the redundant address is identified by the pre-decoder.

26. The apparatus recited in claim 25 further comprising:

a first column multiplexer to receive data on the plurality of enabled bitlines, and coupled with the pre-decoder to output data from the first bitline responsive to the first selector and to output data from the second bitline responsive to the second selector.

27. The apparatus recited in-claim 26 further comprising:

a second column multiplexer coupled to an output of the first column multiplexer, and coupled with the pre-decoder to select the output of the first column multiplexer responsive to a third selector identified with a third one of the one or more possible subsequences of values for bit positions in the address.