Random generator

Abstract

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 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. In one implementation, the random number generator circuit is used to generate a replacement way for a cache.

1. An apparatus comprising:
 a first circuit to generate a first replacement way for a cache when a cache line is to be evicted, the first circuit to exhibit complex harmonics when generating the first replacement way, but in which the first replacement way generated may provide for a way not present in the cache; 
 a second circuit to generate a second replacement way for the cache, in which the second replacement way corresponds to ways present in the cache, but the second replacement way has less randomness than the first replacement way; 
 a detector circuit coupled to receive the first replacement way from the first circuit and to detect if the first replacement way corresponds to a way present in the cache, the detector circuit to generate a select signal in response to the detection; and 
 a select circuit coupled to receive the select signal, the first replacement way and the second replacement way and in response to the select signal, to select the first replacement way for eviction of the cache line if the select signal indicates that the first replacement way corresponds to a way present in the cache, but to select the second replacement way for eviction of a cache line if the select signal indicates that the first replacement way corresponds to a way not present in the cache. 
 
   
   
     2. The apparatus of  claim 1  wherein the first circuit includes a linear feedback shift register (LFSR) to generate the first replacement way. 
   
   
     3. The apparatus of  claim 2  wherein the first circuit further includes a next state circuit coupled to receive preselected bits of the LFSR and to generate a bit value to be shifted into the LFSR for a next state of the LFSR. 
   
   
     4. The apparatus of  claim 3  wherein the second circuit includes a counter to count through values corresponding to the second replacement way. 
   
   
     5. The apparatus of  claim 4  wherein the count changes whenever the select signal selects the second replacement way for eviction of a cache line. 
   
   
     6. An apparatus comprising:
 a first circuit to generate a first replacement way for a cache when a cache line is to be evicted, the first circuit to exhibit complex harmonics when generating the first replacement way, but in which the first replacement way generated may provide for a way not enabled in the cache; 
 a second circuit to generate a second replacement way for the cache, in which the second replacement way corresponds to ways enabled in the cache, but the second replacement way has less randomness than the first replacement way; 
 a detector circuit coupled to receive the first replacement way from the first circuit and to detect if the first replacement way corresponds to a way enabled in the cache, the detector circuit to generate a select signal in response to the detection; and 
 a select circuit coupled to receive the select signal, the first replacement way and the second replacement way and in response to the select signal, to select the first replacement way for eviction of the cache line if the select signal indicates that the first replacement way corresponds to a way enabled in the cache, but to select the second replacement way for eviction of a cache line if the select signal indicates that the first replacement way corresponds to a way not enabled in the cache. 
 
   
   
     7. The apparatus of  claim 6  wherein the first circuit includes a linear feedback shift register (LFSR) to generate the first replacement way. 
   
   
     8. The apparatus of  claim 7  wherein the first circuit further includes a next state circuit coupled to receive preselected bits of the LFSR and to generate a bit value to be shifted into the LFSR for a next state of the LFSR. 
   
   
     9. The apparatus of  claim 8  wherein the second circuit includes a counter to count through values corresponding to the second replacement way. 
   
   
     10. The apparatus of  claim 9  wherein the count changes whenever the select signal selects the second replacement way for eviction of a cache line. 
   
   
     11. A method comprising:
 generating a first replacement way for a cache when a cache line is to be evicted, wherein the first replacement way to exhibit complex harmonics when randomly generated, but in which the first replacement way generated may provide for a way not present or, if present, not enabled in the cache; 
 generating a second replacement way for the cache, in which the second replacement way corresponds to ways present and enabled in the cache, but the second replacement way has less randomness than the first replacement way; 
 detecting if the first replacement way corresponds to a way present and enabled in the cache for the eviction of the cache line; 
 generating a select signal corresponding to the detecting; and 
 selecting the first replacement way for eviction of the cache line if the select signal indicates that the first replacement way corresponds to a way present and enabled for eviction of a cache line in the cache, but selecting the second replacement way for eviction, if the select signal indicates that the first replacement way corresponds to a way not present or not enabled in the cache. 
 
   
   
     12. The method of  claim 11  wherein the generating the first replacement way includes using a linear feedback shift register (LFSR) to obtain a random value. 
   
   
     13. The method of  claim 12  wherein the generating the first replacement way includes obtaining a next state by receiving preselected bits of the LFSR and generating a bit value to be shifted into the LFSR for a next state of the LFSR. 
   
   
     14. The method of  claim 13  wherein the generating the second replacement way includes counting values corresponding to the second replacement way. 
   
   
     15. The method of  claim 14  wherein the counting includes changing a count value whenever the select signal selects the second replacement way for evicting a cache line.