Cache column multiplexing using redundant form addresses

Application Ser. No. 09/532,411, titled “Shared Cache Wordline Decoder For Redundant and Regular Addresses,” filed Mar. 22, 2000, pending. Application Ser. No. 09/887,870, titled “Tag Design For Cache Access With Redundant Form Address,” filed Jun. 22, 2001, pending.

This invention relates generally to decoders for memory, and in particular to decoders for high-speed cache memory.

A cache is a fast memory for storing copies of frequently accessed data. As processors become faster, cache access time is often a dominating factor in system performance. Conflicting goals face designers of cache memory systems. Smaller caches provide faster access times, but larger caches provide higher hit ratios thereby reducing penalties associated with accessing slower memory.

Two prior art methods are shown in U. S. Pat. No. 5,555,529. One typical prior art cache is shown in FIG. 1. A wordline decoder 30 receives an address to access memory array 32 . Depending on the address, exactly one wordline, 60 , 61 , 62 , 63 , 64 , or 65 is activated. For example, if wordline 60 is activated, then memory locations 50 , 80 , 85 , and 90 will be accessed. When these memory locations are accessed, two bits of information at each memory location, 50 , 80 , 85 , and 90 will be presented on a pair of bitlines, 35 , 39 , 41 , and 45 to column multiplexers (MUXs) 99 , 101 , 103 , and 105 . This technique is known as column multiplexing. One bit from each pair will be selected by a column selector to be presented to the sense amplifiers 100 , 102 , 104 , and 106 . It should be noted that columns typically supply both true and complemented signal values for each bit stored at a memory location. Other column multiplexing schemes are in ratios of 4:1, 8:1 and 16:1, with 2:1 and 4:1 being most common. Advantages associated with column multiplexing include better area usage since memory read circuits and write circuits can be laid out using a wider pitch, and more room is provided for global routing over memory cells. Disadvantages include higher power usage and slower multiplexers for higher column multiplexing ratios.

A second prior art method is shown in FIG. 2 . In this case, wordline decoder 125 activates either wordlines associated with array 120 or wordlines associated with array 122 , but not both. If for example, wordline 130 is activated then bitline pairs 135 , 137 , 139 and 140 each supply one bit of information comprising both true and complemented signals to sense amplifiers 148 , 144 , 142 , and 145 . On the other hand, if wordline 150 is activated then bitline pairs 152 , 155 , 158 and 160 each supply one bit of information comprising both true and complemented signals to sense amplifiers 162 , 164 , 166 , and 168 . One advantage of this technique is that there is a power savings through discharging only the needed memory locations. Disadvantages include forcing a narrower pitch and greater probability of masked soft errors going undetected.

Another disadvantage with both of these prior methods involves computing large addresses. Since a current trend in processor design is to devote a substantial proportion of chip area to cache memory, much effort has been invested in improving access times for large caches. But for large addresses, the time it takes an adder to propagate a carry signal in computing the address is a significant factor.

In one prior art method, Cortadella et al [“Evaluation of A+B=K Conditions Without Carry Propagation,” IEEE Transactions on Computers, vol. 41, pp. 1484-1488, November, 1992] show that an equality test does not require carry propagation. One representation of a sum A+B, which is suitable for use in a carry nonpropagative equality test, is known as half-adder or carry-sum form. The carry-sum representation uses a carry bit, C i , and a sum bit, S i , to represent a binary digit of a number in the ith digit position. In carry-sum form each number may have multiple valid representations. In a system of numbers, where each number is assigned multiple binary representations, the numbers are said to be in redundant form.

The carry-sum redundant form representation permits numbers to be added together while eliminating the need to propagate carry signals along the length of the address.

Another example, of a redundant form is called sign-digit. Each binary digit is represented as a sign bit, X si , and a magnitude bit, X mi , and can take on values of 1, 0, and −1.

Addresses can be calculated in carry-save or sign-digit redundant forms faster than through traditional adders, and wordline comparisons can be performed to access data without requiring carry propagation. Yet, techniques for cache column multiplexing based on specific address-bit values must be computed from redundant representations that are not unique. Therefore, computing column selectors may become a critical path in accessing cache.

The present invention is illustrated by way of example and not limitation in the figures of the accompanying drawings.

FIG. 1 shows a prior art odd-even cache column multiplexing technique.

FIG. 2 shows a prior art odd-even cache column segregation technique.

FIG. 3 shows a cache wordline decoder for decoding addresses in a carry-sum redundant form.

FIG. 4 shows one embodiment of a pre-decoder component circuit that accepts addresses in a carry-sum redundant form.

FIG. 5 shows one embodiment of a decoder component circuit that combines two-bit subsequences into three-bit subsequences.

FIG. 6 details one embodiment of a cache wordline decoder for decoding four-digit addresses in a carry-sum redundant form.

FIG. 7 a shows one embodiment of circuit that accepts addresses in a sign-digit redundant form and provides addresses in a negated carry-sum redundant form.

FIG. 7 b shows one embodiment of a pre-decoder component circuit that accepts addresses in a sign-digit redundant form.

FIG. 8 shows one embodiment of a cache wordline decoder for sign-digit redundant addresses.

FIG. 9 a shows a circuit for generating four column selectors from carry-sum redundant form addresses using a carry lookahead circuit.

FIG. 9 b shows a half adder circuit for generating carry propagate and carry generate signals from carry-sum redundant form address digits.

FIG. 9 c shows circuits for generating carry out signals from carry-propagate and carry generate signals.

FIG. 10 shows a truth table for generating possible subsequence indicators from carry-save redundant form address digits.

FIG. 11 a shows a grouping of 4-bit addresses according to most significant 2-bit subsequences.

FIG. 11 b shows a grouping of 4-bit addresses according to second most significant 2-bit subsequences.

FIG. 12 shows one embodiment of a cache column multiplexing scheme using a grouping of addresses according to possible 2-bit subsequences.

FIG. 13 details one embodiment of a cache column multiplexing scheme using a grouping of addresses according to possible 2-bit subsequences.

FIG. 14 shows one embodiment of a 2-level column multiplexing scheme using a grouping of addresses according to possible 2-bit subsequences.

FIG. 15 shows one embodiment of a digital computing system that includes a cache column multiplexing scheme using a grouping of addresses according to possible 2-bit subsequences.

FIG. 16 shows one embodiment of a method of accessing data in a cache using redundant addresses.

These and other embodiments of the present invention may be realized in accordance with the following teachings and it should be evident that various modifications and changes may be made in the following teachings without departing from the broader spirit and scope of the invention. The specification and drawings are, accordingly, to be regarded in an illustrative rather than restrictive sense and the invention measured only in terms of the claims.

For one embodiment a cache wordline decoder, herein described, provides carry-nonpropagative pre-decode circuitry to identify possible subsequences from redundant addresses. These identified subsequences are combined to identify wordline sequences and to activate corresponding wordline enable signals. The activated wordline enable signals are used to access data stored in cache memory at corresponding storage locations. A single 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.

For one embodiment, a cache column multiplexing technique, herein described, provides desirable features of column multiplexing and also of column segregation, while reducing undesirable features of both. Such a technique reduces power consumption by segregating columns according to wordlines, improves area usage by permitting memory read circuits and write circuits to be laid out using a wider pitch, and provides more room for global routing over memory cells. Soft error rates are reduced by the limiting proximity of same column storage cells. Column access speed is improved through reduced multiplexer sizes.

It will be appreciated that the techniques herein disclosed could also be used to access storage locations in forms of storage other than cache, including but not limited to dynamic, static, magnetic, read-only, volatile or non-volatile memories.

One method for quickly calculating addresses in a processor is to use a carry nonpropagative arithmetic circuit such as a carry-save adder to sum addressing components, possibly including a base address and an index or a displacement. Results from a carry-save adder can be bypassed to a load-store unit in redundant form, without waiting for carry propagation to complete. In order to access a cache using such an address, a cache wordline decoder for decoding addresses in a carry-sum redundant form is required.

The type of cache wordline decoder required is depicted in FIG. 3 . It accepts addresses in which the binary digits comprise carry bits, C i , and sum bits, S i , produced by a carry-save adder. In order to identify a corresponding wordline, Wordline i , in cache memory, adjacent digits can first be pre-decoded by pre-decoder 301 to identify possible subsequences that could result from completion of carry propagation. According to the identified possible subsequences, subsequence indicators in subsequence indicator sets 302 , 303 , 304 , and 305 , 306 are activated. These subsequence indicators are combined in decoder 307 to identify a unique wordline sequence. According to the wordline sequence identified, one of a set of wordline indicators 308 is activated to access a corresponding location in cache.

Identification of possible subsequences from carry-sum redundant digits can be accomplished using a circuit like the one shown in FIG. 4 . This embodiment of a pre-decoder component circuit 408 comprises pre-decoder component circuit 404 and pre-decoder component circuit 402 . Pre-decoder component circuit 404 accepts, sum bits, S i and S i−1 and carry bits, C i−1 and C i−2 , of an address in carry-sum redundant form and identifies possible two-bit subsequences that could result at positions, i and i−1 when the carry-sum address is converted into two's complement form. The identified possible subsequences are indicated by activating at least one of the four possible subsequence indicator signals, R i 11 , R i 01 , R i 10 and R i 00 . Likewise, sum bits, S i−1 and S i−2 , and carry bits, C i−2 and C i−3 , can be used by pre-decoder component circuit 402 to identify possible two-bit subsequences that could result at positions, i−1 and i−2 when the address is converted to two's complement. The possible subsequences are indicated by activating at least one of the four possible subsequence indicator signals, R i−1 11 , R i−1 01 , R i−1 10 , R i−1 00 .

As shown in FIG. 4, the afore mentioned possible subsequence indicator signals (as shown in pre-decoder component circuit 404 ) for a subsequence with most significant bit at position, i, in a wordline sequence are activated according to the following logic equations or their equivalents:

R i 11 =( S i−1 AND C i−2 ) X OR ( S i X OR C i−1 ),

R i 01 =( S i−1 AND C i−2 ) XN OR ( S i X OR C i−1 ),

R i 10 =( S i−1 OR C i−2 ) X OR ( S i X OR C i−1 ),

and

R i 00 =( S i−1 OR C i−2 ) XN OR ( S i X OR C i−1 ).

The possible three-bit subsequences ending at position, i, can be identified by combining possible two-bit sequences ending at position, i, with the possible two-bit subsequences ending at position, i−1. FIG. 5 shows one embodiment of a decoder component circuit that combines two-bit subsequences into three-bit subsequences in this manner. It should be noted, of course, that one skilled in the art could modify the pre-decoder illustrated in FIG. 4 directly identify possible three-bit subsequences, or to identify possible four-bit subsequences, or to identify possible subsequences of any other size.

As shown in FIG. 5, a 3-bit possible subsequence indicator for a subsequence with most significant bit at position, i, in a wordline sequence is activated according to the following logic equations or their equivalents:

R i 111 =R i 11 AND R i−1 11 ,

R i 110 =R i 11 AND R i−1 10 ,

R i 101 =R i 10 AND R i−1 01 ,

R i 100 =R i 10 AND R i−1 00 ,

R i 011 =R i 01 AND R i−1 11 ,

R i 010 =R i 01 AND R i−1 10 ,

R i 001 =R i 00 AND R i−1 01 ,

and

R i 000 =R i 00 AND R i−1 00 .

In a like manner, longer possible subsequences could be identified by ANDing together additional shorter possible subsequences.

One embodiment of a cache wordline decoder for decoding four-digit binary addresses in a carry-sum redundant form is illustrated in FIG. 6 . Through combining the possible two-bit subsequences ending at position, i, identified by pre-decoder component circuit 608 ; position i−1, identified by pre-decoder component circuit 604 ; and position i−2, identified by pre-decoder component circuit 602 ; position with the one-bit possibilities for the least significant position, identified by pre-decoder component circuit 601 the unique four-bit wordline corresponding to the carry-sum redundant address can be identified without requiring carry propagation.

A unique wordline indicator for a 4-bit wordline sequence is activated by decoder 616 according to the following logic equations or their equivalents:

Word 1111 =R 3 11 AND R 2 11 AND R 1 11 AND R 0 1X ,

Word 1110 =R 3 11 AND R 2 11 AND R 1 10 AND R 0 0X ,

Word 1101 =R 3 11 AND R 2 10 AND R 1 01 AND R 0 1X ,

Word 1100 =R 3 11 AND R 2 10 AND R 1 00 AND R 0 0X ,

Word 1011 =R 3 10 AND R 2 01 AND R 1 11 AND R 0 1X ,

Word 1010 =R 3 10 AND R 2 01 AND R 1 10 AND R 0 0X ,

Word 1001 =R 3 10 AND R 2 00 AND R 1 01 AND R 0 1X ,

Word 1000 =R 3 10 AND R 2 00 AND R 1 00 AND R 0 0X ,

Word 0111 =R 3 01 AND R 2 11 AND R 1 11 AND R 0 1X ,

Word 0110 =R 3 01 AND R 2 11 AND R 1 10 AND R 0 0X ,

Word 0101 =R 3 01 AND R 2 10 AND R 1 01 AND R 0 1X ,

Word 0100 =R 3 01 AND R 2 10 AND R 1 00 AND R 0 0X ,

Word 0011 =R 3 00 AND R 2 01 AND R 1 11 AND R 0 1X ,

Word 0010 =R 3 00 AND R 2 01 AND R 1 10 AND R 0 0X ,

Word 0001 =R 3 00 AND R 2 00 AND R 1 01 AND R 0 1X ,

and

Word 0000 =R 3 00 AND R 2 00 AND R 1 00 AND R 0 0X .

Another redundant representation used to quickly calculate load addresses without carry propagation is the sign-digit redundant form. In the sign-digit redundant form, each digit is represented by sign bit, X si , and a magnitude bit, X mi . FIG. 7 a shows one embodiment of circuit that accepts addresses in a sign-digit redundant form and produces addresses in a negated carry-sum redundant form.

Identification of possible subsequences from sign-digit redundant digits can be accomplished using a circuit like the one shown in FIG. 7 b. This embodiment of a pre-decoder component circuit 728 comprises pre-decoder component circuit 724 and pre-decoder component circuit 722 . Pre-decoder component circuit 724 accepts, sign bits, X si−1 , and X si−2 , magnitude bits, X mi , X mi−1 and X mi−2 of an address in sign-digit redundant form and identifies possible two-bit subsequences that could result at positions, i and i−1 when the sign-digit address is converted into two's complement form. The identified possible subsequences are indicated by activating at least one of the four possible subsequence indicator signals, R i 11 , R i 01 , R i 10 and R i 00 . Likewise, sign bits, X si−2 , and X si−3 ,and magnitude bits, X mi−1 , X mi−2 and X mi−3 , can be used by pre-decoder component circuit 722 to identify possible two-bit subsequences that could result at positions, i−1 and i−2 when the address is converted to two's complement. The possible subsequences are indicated by activating at least one of the four possible subsequence indicator signals, R i−1 11 , R i−1 01 , R i−1 10 , R i−1 00 .

As shown in FIG. 4, the afore mentioned possible subsequence indicator signals (as shown in pre-decoder component circuit 724 ) for a subsequence with most significant bit at position, i, in a wordline sequence are activated according to the following logic equations or their equivalents:

R i 11 =( X mi−1 N OR ( X mi−2 N AND NOT X si−2 )) X OR ( X mi X OR ( X mi−1 N AND NOT X si−1 )),

R i 01 =NOT ( X mi−1 N OR ( X mi−2 N AND NOT X si−2 )) X OR ( X mi X OR ( X mi−1 N AND NOT X si−1 )),

R i 10 =( X mi−1 N AND ( X mi−2 N AND NOT X si−2 )) X OR ( X mi X OR ( X mi−1 N AND NOT X si−1 )),

R i 00 =NOT ( X mi−1 N AND ( X mi−2 N AND NOT X si−2 )) X OR ( X mi X OR ( X mi−1 N AND NOT X si−1 )),

FIG. 8 shows one embodiment of a cache wordline decoder for sign-digit redundant addresses. It accepts addresses in which the binary digits comprise sign bits, X si , and magnitude bits, X mi , produced by a carry-save adder. In order to identify a corresponding wordline, Wordline i , in cache memory, adjacent digits can first be pre-decoded by pre-decoder 801 to identify possible subsequences that could result from completion of carry propagation. According to the identified possible subsequences, subsequence indicators in subsequence indicator sets 802 , 803 , 804 , and 805 , 806 are activated. These subsequence indicators are combined in decoder 807 to identify a unique wordline sequence. According to the wordline sequence identified, one of a set of wordline indicators 808 is activated to access a corresponding location in cache.

There are advantages associated with column multiplexing including better area usage since memory read circuits and write circuits can be laid out using a wider pitch, and more room is provided for global routing over memory cells. Soft error rates are reduced by limiting proximity of same column storage cells. There are also advantages associated with column segregation. The technique reduces power consumption and decoder sizes. A straight forward scheme for generating column selector signals for redundant addresses is to propagate carry signals to a desired position and identify a true bit value at that position then to combine enough possible subsequences indicators with the identified true bit value to completely decode a subsequence of the wordline.

FIG. 9 a shows a circuit for generating four column selectors 910 from carry-sum redundant form addresses using a carry lookahead circuit 911 . Carry lookahead circuit 911 accepts, sum bits, S i−2 through S 0 , and carry bits, C i−3 through C in , of an address in carry-sum redundant form and propagates carry signals to generate a carry output signal, C LA , for position, i−2. Pre-decoder component circuit 914 accepts, sum bits, S i and S i−1 , and carry bits, C i−1 , and C i−2 , of an address in carry-sum redundant form and identifies possible two-bit subsequences that could result at positions, i and i−1 when the carry-sum address is converted into two's complement form. The identified possible subsequences are indicated by activating at least one of the four possible subsequence indicator signals, R i 11 , R i 01 , R i 10 and R i 00 . Pre-decoder component circuit 912 accepts, sum bit, S i−1 , carry bit, C i−2 , of an address in carry-sum redundant form and a carry-lookahead carry signal C LA . It identifies a true two-bit subsequence at positions, i and i−1. The identified subsequence are indicated by activating exactly one of the four column selector signals, R i 11c , R i 01c , R i 10c , and R i 00c .

FIG. 9 b shows a half adder circuit for generating carry propagate, P i , and carry generate signals, G i , from carry-sum redundant form address digits, S i and C i−1 , according to the following logic equations or their equivalents:

P i =S i X OR C i−1

and

G i =S i AND C i−1 .

FIG. 9 c shows carry lookahead circuits for generating a carry out signal, C i , from carry-propagate signals, P 0 through P i−1 , and carry generate signals, G 0 through G i−1 , and carry input signal, C 0 , according to the following logic equations or their equivalents:

C 1 =( C 0 AND P 0 )OR G 0 .

C 2 =( C 0 AND P 0 AND P 1 ) OR ( G 0 AND P 1 ) OR G 1 ,

C 3 =( C 0 AND P 0 AND P 1 AND P 2 ) OR ( G 0 AND P 1 AND P 2 ) OR ( G 1 AND P 2 ) OR G 2 ,

C 4 =( C 0 AND P 0 AND P 1 AND P 2 AND P 3 ) OR ( G 0 AND P 1 AND P 2 AND P 3 ) OR ( G 1 AND P 2 AND P 3 ) OR ( G 2 AND P 3 ) OR G 3 ,

One problem with this approach is that it may reduce the benefits of using nonpropagative circuitry to calculate addresses and decode wordlines by requiring carry propagation to generate column selector signals. It is also limited to the less significant address positions as more significant positions require longer carry propagation delays. Since access speed is crucial to cache design, a better column multiplexing scheme is desired for redundant addresses.

The truth table shown in FIG. 10 is for generating possible subsequence indicators from carry-save redundant form address digits. A similar table can be drawn for sign-digit addresses. It can be noticed that adjacent pairs of possible subsequence indicators (R i 11 , R i 01 ) and (R i 10 , R i 00 ) are mutually exclusive. For example line 1000 shows that if S i =0, C i−1 =0, S i−1 =0, and C i−2 =0; then R i 11 =0, R i 01 =1, R i 10 =0, and R i 00 =1. Similarly for line 1001 , if S i =0, C i−1 =0, S i−1 =0, and C i−2 =1; then R i 11 =0, R i 01 =1, R i 10 =1, and R i 00 =0. Like patterns are shown for the remaining lines 1002 - 1033 . Hence R i 11 is never equal to R i 01 and R i 10 is never equal to R i 00 . Further it can be noticed that an address having an active possible subsequence indicator R i 11 could share a wordline with an address having an active possible subsequence indicator R i 01 and an address having an active possible subsequence indicator R i 10 could share a wordline with an address having an active possible subsequence indicator R i 00 . This can be seen in FIG. 11 a.

FIG. 11 a shows a grouping of 4-bit addresses according to most significant 2-bit subsequences. Since the sequences shown in block 1110 have corresponding sequences in block 1112 , these addresses could be permitted to share a word line generated by the three least significant bits, if the column was selected by the most significant active possible subsequence indicator. Similarly, since the sequences shown in block 1111 have corresponding sequences in block 1113 , these addresses could be permitted to share a word line generated by the three least significant bits, if the column was selected by the most significant active possible subsequence indicator. Further, since a single unique wordline will be activated, there is no danger of contention between block 1110 and block 1111 for example, or between block 1112 and block 1113 . It can also be noticed that similar conditions exist for digit positions other than the most significant digit position.

For instance, FIG. 11 b shows another grouping of 4-bit addresses according to second most significant 2-bit subsequences. Since the sequences shown in blocks 1120 have corresponding sequences in blocks 1122 , these addresses could be permitted to share a word line generated by the most significant bit and the two least significant bits, if the column was selected by the second most significant active possible subsequence indicator. Similarly, since the sequences shown in blocks 1121 have corresponding sequences in blocks 1123 , these addresses could be permitted to share a word line generated by the most significant bit and the two least significant bits, if the column was selected by the second most significant active possible subsequence indicator.

Such a wordline could be generated, for example, by combining R 3 11 and R i 10 through an OR gate prior to decoding through a circuit like the one shown in FIG. 5 . Similarly R 3 01 and R 3 00 could be combined through an OR gate prior to decoding through a circuit like the one shown in FIG. 5 . This guarantees the activation of a unique wordline. Of course, it will be appreciated that one skilled in the art may select to implement such a wordline decoder in a variety of ways, some providing reductions in required circuitry when compared to a literal implementation of the solution disclosed above.

As before, since a single unique wordline is activated, there is no danger of contention between blocks 1120 and blocks 1121 for example, or between blocks 1122 and blocks 1123 . Hence, an address space may be divided into four quarters according to possible subsequence indicators and these four quarters may be multiplexed by directly using possible subsequence indicators as column selectors. This is illustrated in FIG. 12 .

With regard to FIG. 12, one embodiment of a cache column multiplexing scheme using a grouping of addresses according to possible 2-bit subsequences is disclosed. As was previously discussed, a bitline 1220 for a 0th data bit may be shared by quarter 00, illustrated as block 1200 , and quarter 10, illustrated as block 1210 by directly using some ith possible subsequence indicators R i 00 and R i 10 as column selectors in column multiplexer 1240 . Similarly, bitline 1220 for a 0th data bit may be shared by quarter 01, illustrated as block 1201 , and quarter 11 , illustrated as block 1211 by directly using ith possible subsequence indicators R i 01 and R i 11 as column selectors in column multiplexer 1250 . Further considering a wordline W h produced by combining identified possible subsequences as described above but omitting from this combination the ith subsequence, this wordline being directly column selected by ith possible subsequence indicators R i 00 and R i 10 ; such a wordline differs in its i−1 th bit from a similarly produced wordline W k being directly column selected by ith possible subsequence indicators R i 01 and R i 11 and hence accesses a different physical storage location than wordline W k . Therefore bitline 1220 may be shared as a common output of column multiplexer 1240 and column multiplexer 1250 without contention, providing a unique 0th data bit D 0 for line 1230 .

Similarly, bitline 1229 may be shared as a common output of column multiplexer 1249 for an nth data bit shared by quarter 00, illustrated as block 1209 , and quarter 10, illustrated as block 1219 by directly using ith possible subsequence indicators R i 01 and R i 11 as column selectors; and column multiplexer 1259 for an nth data bit shared by quarter 01, illustrated as block 1291 , and quarter 11, illustrated as block 1299 by directly using ith possible subsequence indicators R i 01 and R i 11 as column selectors without contention, providing a unique nth data bit D n for line 1239 .

Details of one embodiment of a cache column multiplexing scheme using a grouping of addresses according to possible 2-bit subsequences is illustrated in FIG. 13. A bitline comprising line 1320 connected with line 1322 through line 1330 , for a 0th data bit is shared by quarter 00, illustrated as block 1300 , and quarter 10, illustrated as block 1310 by directly using some ith possible subsequence indicators R i 00 and R i 10 as column selectors in a column multiplexer comprising pass-gate device 1340 and pass-gate device 1342 . Similarly, a bitline comprising line 1320 connected with line 1322 through line 1330 , is shared by quarter 01, illustrated as block 1301 , and quarter 11, illustrated as block 1311 by directly using ith possible subsequence indicators R i 01 and R i 11 as column selectors in a column multiplexer comprising pass-gate device 1350 and pass-gate device 1352 .

A wordline W h , produced by combining identified possible subsequences while omitting from this combination the ith subsequence, accesses storage cell 1360 to present a stored true logical value on bitline B 00 and a stored complemented logical value on bitline B 00 bar and also accesses storage cell 1362 to present a stored true logical value on bitline B 10 and a stored complemented logical value on bitline B 10 bar. This wordline being directly column selected by ith possible subsequence indicators R i 00 and R i 10 to multiplex either the true logical value on bitline B 00 onto line 1320 or the true logical value on bitline B 02 onto line 1322 , differs in its i−1th bit from similarly produced wordlines W i and W k being directly column selected by ith possible subsequence indicators R i 01 and R i 11 and hence accesses a different physical storage location than wordlines W i or W k . Therefore neither the storage cells 1361 and 1371 of block 1301 nor the storage cells 1363 and 1373 of block 1311 will be accessed and so the bitline comprising line 1320 connected with line 1322 through line 1330 may be shared as a common output of the column multiplexer comprising pass-gate device 1340 and pass-gate device 1342 and the column multiplexer comprising pass-gate device 1350 and pass-gate device 1352 without contention, providing a unique 0th true data bit D 0 for line 1330 .

Similarly wordline W h , being directly column selected by ith possible subsequence indicators R i 00 and R i 10 to multiplex either the complemented logical value on bitline B 00 bar onto line 1325 or the complemented logical value on bitline B 02 bar onto line 1327 , accesses a different physical storage location than wordlines W i or W k . Therefore the bitline comprising line 1325 connected with line 1327 through line 1335 may be shared as a common output of the column multiplexer comprising pass-gate device 1345 and pass-gate device 1347 and the column multiplexer comprising pass-gate device 1355 and pass-gate device 1357 without contention, providing a unique 0th complemented data bit D 0 bar for line 1335 . It will be appreciated that the above description is intended to illustrate rather than restrict, and that real memory typically comprise further complexities such as equilibrium circuitry, cross coupled differential amplifiers, and write circuitry not shown in FIG. 13 . It will also be appreciated that real memory typically involves many more wordlines, storage cells and perhaps more columns than those illustrated in FIG. 13 .

FIG. 14 shows one embodiment of a 2-level column multiplexing scheme using a grouping of addresses according to a first set of possible 2-bit subsequence indicators, (R n 11 , R n 01 ) and (R n 10 , R n 00 ) and according to a second set of possible 2-bit subsequence indicators, (R m 11 , R m 01 ) and (R m 10 , R m 00 ) For example, a wordline W h produced by combining identified possible subsequences as described above but omitting from this combination the nth and mth subsequences, this wordline being directly column selected by nth possible subsequence indicators R n 00 and R n 10 ; such a wordline, differs in its n−1th bit from a similarly produced wordline W i being directly column selected by nth possible subsequence indicators R n 01 and R n 11 and hence accesses a different physical storage location than wordline W i . Hence, a common output 1422 may be shared between column multiplexer 1440 and column multiplexer 1450 without contention, providing a unique 0th data bit D 0 for line 1422 .

Further, wordline W h produced by combining identified possible subsequences as described above but omitting from this combination the nth and mth subsequences, this wordline also being directly column selected by mth possible subsequence indicators R m 00 and R m 10 ; such a wordline differs in its m−1th bit from a similarly produced wordline W k being directly column selected by mth possible subsequence indicators R m 01 and R m 11 and hence accesses a different physical storage location than wordline W k . Hence, a common output 1420 may be shared between column multiplexer 1470 and column multiplexer 1480 without contention, providing a unique 0th data bit D 0 for line 1230 .

One embodiment of a digital computing system is shown in FIG. 15, which comprises a cache 1513 with a decoder for receiving redundant addresses and multiplexing bitlines according to possible subsequence indicators R i 00 corresponding to block 1508 , R i 10 corresponding to block 1510 , R i 01 corresponding to block 1509 , and R i 11 corresponding to block 1511 . For one embodiment, cache 1513 , is the fastest internal cache in a hierarchical plurality of caches including slower external caches and 1513 is resident on the same die as processor, 1512 . In another embodiment, cache 1513 and possibly other internal caches reside on the same die, but there are no external caches. In this context, an internal cache is one that resides on a die or chip with a processor core. An external cache is one that resides off the die, on a separate die or chip.

Instruction decoder, 1501 , receives instructions that may include additions, loads, stores, etc. For example, a first instruction to add a base address in a first register to an index in a second register, writing the result in a third register may be received and decoded. Then a second instruction to load data from the address in the third register may be received and decoded. The first instruction may produce a result by providing operands from a register file, 1505 , to a redundant adder, 1503 . In order to complete the second instruction quickly, the result produced by redundant adder, 1503 , may be bypassed to cache, 1513 , by the bypassing control 1506 . The redundant address received by cache 1513 may be processed by a pre-decoder to identify possible subsequences and activate possible subsequence indicators R i 11 , R i 01 , R i 10 and R i 00 for each ith bit position in the corresponding result address of the first instruction. A mth set of possible subsequence indicators R m 11 , R m 01 , R m 10 , and R m 00 for an mth bit position in the corresponding result address of the first instruction, may be omitted from a combination of possible subsequence indicators to identify a wordline and activate a wordline indicator with which to access a particular wordline of storage locations in memory. The mth set of possible subsequence indicators R m 11 , R m 01 , R m 10 , and R m 00 may instead be used directly as column selectors to multiplex four sets of bitlines corresponding to four 2-bit sequences at positions m and m−1 in the result address of the first instruction, said sets of bitlines being multiplexed into common outputs for presenting data values of each of the bit positions of the data associated with the result address of the first instruction.

FIG. 16 summarizes one embodiment of a method of accessing data in a cache using redundant addresses. The method comprises receiving a redundant address in block 1601 to access a storage location, and processing the redundant address to identify possible subsequences in block 1602 . According to the possible sequences identified, possible subsequence indicators R i 11 , R i 01 , R i 10 , and R i 00 , are activated in block 1603 for each ith digit position in the redundant address. An mth set of possible subsequence indicators R m 11 , R m 01 , R m 10 , and R m 00 for an mth digit position in the redundant address is omitted and remaining sets of possible subsequence indicators are combined to identify a wordline in block 1604 . A wordline indicator with which to access a particular wordline of storage locations in memory is activated according to the wordline identified in block 1605 . The mth set of possible subsequence indicators R m 11 , R m 01 , R m 10 , and R i 00 is used directly as column selectors to multiplex four sets of bitlines into common outputs in block 1606 , the bitlines corresponding to four 2-bit sequences at positions m and m−1 in a binary address corresponding to the redundant address. The common outputs present data values of each of the bit positions of the data stored at the location associated with the redundant address.

The above description is intended to illustrate preferred embodiments of the present invention. From the discussion above it should also be apparent that the invention can be modified in arrangement and detail by those skilled in the art without departing from the principles of the present invention within the scope of the accompanying claims.