Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
2001-05-15
2004-06-08
Sparks, Donald (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C711S128000, C711S134000, C711S136000, C711S159000, C711S160000
Reexamination Certificate
active
06748495
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention is related to random number generator circuits and pseudo-random number generator circuits and, more particularly, to a random number generator circuit for generating a random replacement way for a cache.
2. Description of the Related Art
Random number generator circuits have a variety of uses in various circuits, such as integrated circuits. For example, random number generator circuits may be used, in a set associative cache, to select a random replacement way from which to evict data in order to store a newly fetched cache line (in response to a cache miss). A random number generator circuit could be addressable via instructions in a processor to provide a random number for software use. For example, various games and other applications may benefit from being able to read a random number generator circuit rather than using a complex software routine to generate a random number. Other hardware uses may include random selection of one of several eligible units to execute an instruction, random translation lookaside buffer entry replacement, random branch history buffer or target address buffer replacement in a branch predictor, etc.
The random number generator circuits are typically pseudo-random circuits, in which the circuits attempt to generate a relatively unpredictable sequence of numbers over time (when viewed from the consumer of the numbers) using some sort of deterministic algorithm. However, for brevity herein, these circuits will be referred to as random number generator circuits. Generally, it is desirable that the algorithm produce a long sequence of numbers before any repeated patterns are experienced, either in the values used in the algorithm or in the output random number values. The number of values produced before a repeat is referred to as a harmonic of the random number generator, and producing one or more long sequences (high harmonics) may be referred to as complex harmonics. It may generally be desirable to produce large, odd numbered harmonics, prime number harmonics, etc. to improve the apparent randomness of the generated numbers.
Algorithms having complex harmonics tend to reduce the occurrence of degenerative cases in which the same random number is generated repeatedly over a relatively short period of time, or the same random number is generated with a short, consistent frequency over a short period of time. For example, in the cache replacement scheme mentioned above, if a cache miss in a given set occurs with a frequency that matches a harmonic of the random number generator, then the same way would be replaced in the set each time where it may be desirable, in general, to replace different ways in the set for each miss to replace less recently accessed data in the set with the more recently accessed data. In a simple example, if a miss within a given set occurs every fourth miss (or frequently the fourth miss) during a certain period of time and every fourth value of the random number generator is the same during the period (or mostly the same), then the same way is replaced in that set during the time period.
Generally, the random number generator circuit may produce a random number within a range of integers. For example, a four way set associative cache having random replacement may include a random number generator circuit which produces a way value (an integer in the range from 0 to 3). A three way set associative cache would have a random number generator which produces an integer in the range of 0 to 2. Thus, the range required of a given random number generator circuit may be arbitrary.
SUMMARY OF THE INVENTION
A random number generator circuit includes a primary circuit configured to generate a value within a first range and a secondary circuit configured to generate a value within a second range. A detector circuit detects whether or not the value from the primary circuit is within the desired output range for the random number generator circuit, and selects either the value from the primary circuit or the value from the secondary circuit in response. The second range (from which the value from the secondary circuit is generated) is the desired output range and the first range encompasses the second range.
In one embodiment, the primary circuit has complex harmonics but may generate values outside the desired range. The secondary circuit may have less complex harmonics, but may generate values only within the desired range. The combination of the primary circuit and the secondary circuit may have complex harmonics and may generate values only within the desired range. In one specific implementation, the primary circuit may generate values within a range of a power of two. For example, a linear feedback shift register (LFSR) may be the primary circuit and a counter may be the secondary circuit.
In one implementation, the random number generator circuit is used to generate a replacement way for a cache. The cache may have a number of ways which is not a power of two, or may be programmable to disable one or more ways. In either case, the random number generator may be used to generate replacement ways with complex harmonics.
Broadly speaking, a circuit is contemplated comprising a first circuit, a second circuit, and a detector circuit. The first circuit is configured to generate a first value within a first predetermined range of values. The second circuit is configured to generate a second value within a second range of values, wherein the second range is encompassed by the first predetermined range. The detector circuit is coupled to receive the first value, wherein the detector circuit is configured to detect whether or not the first value is within the second range. The detector circuit is configured to select the first value as an output of the circuit unless the first value is out of the second range. Furthermore, the detector circuit is configured to select the second value as the output if the first value is out of the second range.
Additionally, a cache is contemplated comprising a memory array and a replacement circuit. The memory array is arranged in an N way set associative configuration, N being a positive integer greater than 1. Coupled to select a replacement way of the N ways, the replacement circuit comprises a first circuit configured to generate a first value indicative of a first way, a second circuit configured to generate a second value indicative of one of the N ways, and a detector circuit coupled to receive the first value. The one of the N ways indicated by the second value is selectable as a replacement way. The detector circuit is configured to detect whether or not the first way is within the range of ways selectable as the replacement way. In response, the detector circuit is configured to select the first value as an output of the replacement circuit unless the first way is out of the range, and to select the second value as the output if the first value is out of the range.
Moreover, a method is contemplated. A first value within a first predetermined range of values is generated. A second value within a second range of values is generated. The second range is encompassed by the first predetermined range. Whether or not the first value is within the second range is detected. The first value is selected unless the first value is out of the second range. The second value is selected if the first value is out of the second range.
REFERENCES:
patent: 3693165 (1972-09-01), Reiley et al.
patent: 4044338 (1977-08-01), Wolf
patent: 4453212 (1984-06-01), Gaither et al.
patent: 4511994 (1985-04-01), Webb et al.
patent: 4575792 (1986-03-01), Keeley
patent: 4633440 (1986-12-01), Pakulski
patent: 4654778 (1987-03-01), Chiesa et al.
patent: 4807115 (1989-02-01), Torng
patent: 4833642 (1989-05-01), Ooi
patent: 4858105 (1989-08-01), Kuriyama et al.
patent: 4907278 (1990-03-01), Cacinati et al.
patent: 4996641 (1991-02-01), Talgam et al.
patent: 5113514 (1992-05-01), Albonesi et al.
patent: 5125083 (1992-06-01), Fite et al.
patent: 5163142 (1992-11
Ning Chun H.
Rowlands Joseph B.
Broadcom Corporation
Dinh Ngoc V
Merkel Lawrence J.
LandOfFree
Random generator 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 generator, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Random generator will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3335765