Cache column multiplexing using redundant form addresses

Details Cache column multiplexing using redundant form addresses Cache column multiplexing using redundant form addresses

2000-03-29

2003-01-14

Lebentritt, Michael S. (Department: 2824)

Static information storage and retrieval

Addressing

Multiplexing

C365S230060

Reexamination Certificate

active

06507531

ABSTRACT:

RELATED APPLICATIONS
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.
FIELD OF THE INVENTION
This invention relates generally to decoders for memory, and in particular to decoders for high-speed cache memory.
BACKGROUND OF THE INVENTION
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.


REFERENCES:
patent: 4926385 (1988-05-01), Fujishima et al.
patent: 4804871 (1989-02-01), Walters, Jr.
patent: 4905189 (1990-02-01), Brunolli
patent: 5227997 (1991-05-01), Kikuda et al.
patent: 5315558 (1993-04-01), Hag
patent: 5257236 (1993-10-01), Sharp
patent: 5488583 (1994-09-01), Ong et al.
patent: 5568442 (1995-06-01), Kowalczyk et al.
patent: 5657469 (1995-10-01), Shimizu
patent: 5640339 (1996-03-01), Davis et al.
patent: 5657281 (1996-03-01), Mohan
patent: 5532947 (1996-07-01), Potter et al.
patent: 5956274 (1996-07-01), Elliot et al.
patent: 5555529 (1996-09-01), Hose, Jr. et al.
patent: 5583806 (1996-12-01), Widigen et al.
patent: 5920515 (1997-09-01), Shalik et al.
patent: 5680569 (1997-10-01), Correll
patent: 5710731 (1998-01-01), Ciraula et al.
patent: 5754819 (1998-05-01), Lynch et al.
patent: 5841687 (1998-11-01), Rees
patent: 5854761 (1998-12-01), Patel et al.
patent: 5860092 (1999-01-01), Breid et al.
patent: 5212109 (1999-08-01), Proebsting
patent: 5933376 (1999-08-01), Lee
patent: 5970912 (1999-10-01), Martens et al.
patent: 6373753 (2000-02-01), Proebsting
patent: 6098150 (2000-08-01), Brethour et al.
patent: 6172933 (2001-01-01), Sager
patent: 6181612 (2001-01-01), Wada
patent: 6373758 (2001-02-01), Hughes et al.
patent: 6209076 (2001-03-01), Blomgren
patent: 6212109 (2001-04-01), Proebsting
patent: 6256709 (2001-07-01), Patel et al.
patent: 6341327 (2002-01-01), Sager
patent: 6356485 (2002-03-01), Proebsting
patent: 6363020 (2002-03-01), Shubat et al.
Cortadella et al., “Evaluation of A+B=K Conditions Without Carry Propagation,” IEEE Transactions on Computers, vol. 41, No. 11, pp. 1484-1488, Nov., 1992.
Heald et al., “Sum-Addressed-Memory Cache with 1.6ns Cycle and 2.6nc Latency,” IEEE ISSCC, Paper SP 22.2, Feb. 7, 1998.
Cortadella et al., “Evaluation of A+B=K Conditions in Constant Time,” IEEE ISSCC Paper SP 22.2, Feb. 7, 1998.
Lutz et al., “The Half-Adder Form and Early Branch Condition Resolution,” IEEE ARITH′97, Jul. 6-9, 1997.
Lutz et al., “Early Zero Detection,” IEEE ICCD′96, Oct. 7-9, 1996.

Affiliated with

Also associated with

Rating

Cache column multiplexing using redundant form addresses does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Cache column multiplexing using redundant form addresses, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cache column multiplexing using redundant form addresses will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3064020