Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
2001-07-30
2003-11-04
Verbrugge, Kevin (Department: 2188)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
Reexamination Certificate
active
06643740
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to a digital cache and to a random replacement generator for use in a digital cache. The invention is especially suitable for implementation in an associative cache.
BACKGROUND TO THE INVENTION
A cache is a circuit which includes its own internal memory, and control logic for controlling whether the internal memory can be used to service (buffer) a read or write access supplied to the cache, or whether this access is passed through the cache to a downstream device. When a certain address is already buffered by the cache, then an access to that address is referred to as a cache-hit. When a certain address is not already buffered, then an access to that address is referred to as a cache-miss.
In the event of a cache-miss, then a portion of the memory is, or can be, newly allocated to buffer the data for a future access. This is referred to herein as a “miss with allocation”. Generally, if the cache-miss is a result of a read-access (a “read-miss”), then the miss does result in new allocation, so that the data is buffered. If the cache-miss is a result of a write-access (a “write-miss”), then allocation depends more on the particular write-strategy implemented in the cache. Since the internal memory of the cache is typically several orders of magnitude smaller than the range of addresses it has to service, the internal memory rapidly fills, and each new allocation has to replace (i.e. overwrite) an existing allocation.
A known type of cache is a so-called associative cache, in which the control logic and the internal memory are configured such that there are several internal addresses (so called “ways”) available for each external memory location which is serviced by the cache. In other words, each serviced address can be associated with a plurality of internal addresses for data storage. The number of ways (i.e. the number of possible locations available) for each external address is limited by the design or programming of the cache. In a so-called fully-associative cache, each external address can be mapped anywhere in the internal memory. In a so-called set-associative cache, sets or groups of addresses are mapped statically to an external address, and each set has several ways that represent the associativity.
Whenever a new allocation takes place for which all of the possible ways have already been allocated, then it is necessary for the control logic to implement a replacement algorithm to decide which currently occupied way will be overwritten with new data (and hence replaced in the cache). Various replacement algorithms are known in the art, for example:
Least Recently Used—the algorithm determines which of the ways was accessed the least recently, and selects that way to be overwritten. This usually leads to a very good performance of the cache, but requires additional memory overhead to record time usage, is complicated to implement, and is slow in use.
Random—a random number is generated that determines which way to replace. Random algorithms are commonly used, as they are relatively easy to implement and normally result in good cache performance.
Round Robin—the ways are accessed in a fixed sequence, by using a pointer to record which way was accessed most recently, and then accessing the next way in sequence. This can be applied on a global scale or locally with a set. However, round-robin algorithms are generally avoided as they mostly lead to poor cache performance.
The present invention relates to a random replacement generator. The most common technique for implementing this is as a free running counter, e.g. as a simple incremental counter or a sequential code counter (such as a gray code generator). The count value is modified with every clock-period. When a replacement is necessary, the current count value (or certain bits of the value) is read as the random number. Since replacements occur with irregular frequency (due to varying access-series in a program, waitstates, actions of other bus masters, interrupts, etc) this results in pretty good random behaviour.
The main disadvantage of a free running counter is that it wastes power. As the counter value changes on every clock cycle, parasitic capacitances have to be charged or discharged with logic level changes during each clock period. As a result, a free running counter contributes undesirably to the power consumption of the cache, since the counter keeps running even if the cache is not currently servicing a read or write access.
Clock gating has been used to try to reduce the power consumption by advancing the counter only during an access (or only during certain types of access) to the cache. During other periods, the counter is paused. Although this can reduce the power consumption, it drastically affects the “randomness” of the number generated by the counter, since the counter value is no longer independent. In some cases, depending on a particular sequence of read and write access types to the cache, the counter may turn into a round-robin generator, which results in low cache performance. It is also highly undesirable that the cache performance be dependent on a particular sequence of access types to the cache.
The fundamental problem with a counter is that its “randomness” depends on the counter being able to run for a period which is independent of the “reads” of the random numbers. However, such running results in increased power consumption.
In a different field, namely the communications field, pseudo-noise generators are known for encrypting CDMA signals based on a secret code. The output is a signal which resembles noise, but which can be decrypted based on the secret code. The pseudo-noise generators operate continuously based on an input signal.
SUMMARY OF THE INVENTION
The present invention concerns a cache. The cache may comprise a memory and control logic. The memory may be configured for storing data buffered by the cache. The control logic may be configured for controlling accesses to the memory. The control logic may comprise a pseudo-noise generator and a trigger device. The pseudo-noise generator may be configured for generating a pseudo-random number representing, for a miss access requiring allocation, which of a plurality of possible addresses in the memory to use for the allocation. The trigger device may be configured for controlling a cycle of the pseudo-noise generator to output the pseudo-random number therefrom.
The objects, features and advantages of the invention include (i) providing a high degree of “randomness” and/or (ii) reducing the power consumption of the cache.
REFERENCES:
patent: 5568632 (1996-10-01), Nelson
patent: 5701431 (1997-12-01), Whittaker
patent: 5875465 (1999-02-01), Kilpatrick et al.
patent: 6223256 (2001-04-01), Gaither
patent: 6374341 (2002-04-01), Nijhawan et al.
patent: 6405287 (2002-06-01), Lesartre
patent: 6446168 (2002-09-01), Normoyle et al.
patent: 2002/0174160 (2002-11-01), Gatto et al.
patent: 2002/0188808 (2002-12-01), Rowlands et al.
patent: 2002/0199064 (2002-12-01), Kim et al.
Maiorana PC Christopher P.
Verbrugge Kevin
LandOfFree
Random replacement generator for a cache circuit does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Random replacement generator for a cache circuit, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Random replacement generator for a cache circuit will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3118432