Method and apparatus for allocating data and instructions within a shared cache

[0002] The present invention relates to cache memories and more specifically to a method and apparatus for allocating data and instructions within a shared cache.

[0003] Processor cache architecture schemes generally follow one of two models: a split cache model or a shared (unified) cache model. In a split cache model, two distinct first level caches are provided, a first cache for data and a second cache for instructions. The disadvantage of this architecture is that some applications are heavily weighted toward either data or instructions. In these situations, a split cache effectively excludes a large portion of the total cache capacity from use (e.g., either the data cache or the instruction cache, depending on the weighting of the application), and therefore makes highly inefficient use of cache resources.

[0004] In a shared cache both data and instructions inhabit a single cache, and the continued residency of data and instructions within the cache is managed by a single replacement algorithm. For example, a commonly employed replacement algorithm is a “least-recently-used” (LRU) algorithm that assigns an “age” to each line within the single data and instruction cache. As new data is loaded into a line of the cache, or as a new cache line is accessed, the cache line is assigned the youngest cache line age while all other lines within the cache are aged. When a cache line needs to be discarded, the cache line having the oldest cache line age associated therewith is replaced.

[0005] In practice, actual implementations of the LRU algorithm rely upon incomplete retained data on actual cache usage (e.g., there are simply too many lines in a typical cache to maintain a complete set of statistics on the use of each cache line and there is too little time available during cache operations to evaluate a complete set of cache line use statistics). Therefore, actual cache line replacements are made on a partially random basis.

[0006] For “distributed statistics” (wherein the shared cache contains a similar number of data and instruction cache lines with similar ages), the LRU algorithm functions well. However, for non-distributed statistics (wherein the shared cache contains a non-similar number of data and instruction cache lines having non-similar ages), the LRU algorithm often maintains a non-optimal balance between the number of data and instruction lines within a shared cache. Accordingly, a need exists for an improved method and apparatus for allocating data and instructions within a shared cache.

[0007] To overcome the needs of the prior art, an inventive method and apparatus are provided for managing cache allocation for a plurality of data types in a unified cache having dynamically allocable lines for first type data (e.g., data/instructions) and for second type data (e.g., instructions/data). Cache allocation is managed by counting misses to first type data and misses to second type data in the unified cache, and by determining when a difference between a number of first type data misses and a number of second type data misses crosses a preselected threshold. A replacement algorithm of the unified cache then is adjusted in response to the detected crossing of the preselected threshold, the adjusting step including increasing a replacement priority of the first type data lines in the cache. The replacement algorithm preferably is an LRU algorithm wherein the adjusting step includes incrementing an age indication of the first type data lines. To re-balance the count of misses to first type data and the count of misses to second type data (e.g., during a new task), preferably the count of misses to first type data and the count of misses to second type data are reset after a predetermined time period or in response to a new task.

[0008] Hardware for implementing the inventive cache allocation management method comprises a miss counter having a first counter input adapted to couple to the control logic of the unified cache and to receive a miss to first type data signal therefrom, a second counter input adapted to couple to the control logic of the unified cache and to receive a miss to second type data signal therefrom and a first counter output. The miss counter is configured to increment its count in response to a miss, to first type data signal on the first counter input and to output a first logic state on the first counter output when its count exceeds a first predetermined count. A priority adjustment circuit is coupled to the first counter output of the miss counter and is adapted to couple to the replacement algorithm logic of the unified cache. The priority adjustment circuit is configured to increase the replacement priority of the first type data relative to the replacement priority of the second type data in response to the first logic state output by the miss counter on the first counter output.

[0009] Preferably the miss counter is further adapted to decrement its count in response to a miss to second type data signal on the second counter input and to output a second logic state on the first counter output when its count is equal to or less than the first predetermined count. The priority adjustment circuit thereby may be configured to increase the replacement priority of the second type data relative to the replacement priority of the first type data in response to the second logic state output by the miss counter on the first counter output. The priority adjustment circuit preferably comprises an LRU priority adjustment circuit configured to inhibit aging of at least a portion of first/second type data within the unified cache by an LRU algorithm of the cache when the second/first logic state is output by the miss counter. Preferably the miss counter's count is resettable and/or presettable, the response rate of the miss counter to misses to first type data and/or misses to second type data is adjustable, and an upper and a lower count threshold may be set to limit the count range of the miss counter.

[0010] By monitoring the ratio of misses to first type data to misses to second type data, and by adjusting the percentage of the unified cache dedicated to each type data based thereon, a unified cache's hit rate is significantly improved. Further, cache hit rate improvement is achieved with a minimal increase in cache circuitry complexity.

[0011] Other objects, features and advantages of the present invention will become more fully apparent from the following detailed description of the preferred embodiments, the appended claims and the accompanying drawings.

[0012] The present invention is described with reference to the accompanying drawings. In the drawings, like reference numbers indicate identical or functionally similar elements. Additionally, the left-most digit of a reference number identifies the drawing in which the reference number first appears.

[0013] FIG. 1 is a flowchart of an inventive method for managing cache allocation between data and instructions in a unified cache in accordance with the present invention;

[0014] FIG. 2 is a schematic diagram of a first cache management circuit for implementing the inventive cache management method of FIG. 1;

[0015] FIG. 3 is a schematic diagram of a unified cache configured for use with the inventive cache management method of FIG. 1;

[0016] FIG. 4 is a schematic diagram of a second cache management circuit for implementing the inventive cache management method of FIG. 1; and

[0017] FIG. 5 is schematic diagram of a third cache management circuit for implementing the inventive cache management method of FIG. 1.

[0018] FIG. 1 is a flowchart of an inventive method for managing cache allocation between data and instructions in a unified cache (“inventive cache management method 100”) in accordance with the present invention. The inventive cache management method 100 begins at step 101.

[0019] In step 102, misses to data and misses to instructions within a unified cache (not shown) are counted.

[0020] Thereafter, in step 103, a determination is made as to whether the difference between the number of misses to data and the number of misses to instructions within the cache crosses (e.g., exceeds or falls below) a predetermined threshold (e.g., a predetermined count as described below with reference to FIG. 2). If so, in step 104, a replacement algorithm that governs the replacement of data and instructions within the unified cache (not shown) is adjusted to increase the replacement priority of instructions within the cache relative to the replacement priority of data within the cache; otherwise if the difference does not cross the predetermined threshold, in step 105, the replacement algorithm is adjusted to increase the replacement priority of data within the cache relative to the replacement priority of instructions within the cache. Following either step 104 or 105, counting of misses to data and misses to instructions continues in step 102 as shown.

[0021] Adjustment of the replacement algorithm for the unified cache may be performed by many techniques. For example, if a least-recently-used (LRU) replacement algorithm is employed, in step 104, the “age” of each instruction cache line may be increased while the age of each data cache line is not increased, or in step 105, the age of each data cache line may be increased while the age of each instruction cache line is not increased. However, when an LRU replacement algorithm is employed, preferably the LRU replacement algorithm is adjusted in step 104 by prohibiting the replacement of data cache lines while allowing the replacement of instruction cache lines, and in step 105 by prohibiting the replacement of instruction cache lines while allowing the replacement of data cache lines as described below with reference to FIG. 2.

[0022] FIG. 2 is a schematic diagram of a first cache management circuit 200 for implementing the inventive cache management method 100 of FIG. 1. The first cache management circuit 200 is configured to operate with a unified cache 300 (shown in FIG. 3) having a plurality of cache lines 302a-k. Each cache line has a plurality of data or instruction bits 304, a plurality of LRU age bits 306 and a data/instruction bit 308 which designates the cache line as either a data line (e.g., by a logic 0) or an instruction line (e.g., by a logic 1) as described further below.

[0023] The first cache management circuit 200 comprises in pertinent part an up-down counter 202 having a first input coupled to a miss to instructions output of control logic 204 (shown in phantom) of the unified cache 300, a second input coupled to a miss to data output of the control logic 204 and an output coupled to a plurality of priority adjustment circuits 206a-k. The up-down counter 202 may comprise any conventional up-down counter 202 such as a National Semiconductor 54AC191 4-bit up/down counter, a Fairchild Semiconductors™ DM74LS469A 8-bit up/down counter, etc.

[0024] Each priority adjustment circuit 206a-kis configured identically to the priority adjustment circuit 206ashown in FIG. 2, but receives its cache line inputs from a corresponding cache line 302a-kof the unified cache 300. For example, priority adjustment circuit 206areceives as inputs information from cache line 302a, priority adjustment circuit 206breceives as inputs information from cache line 302b, etc. For convenience, only the details of priority adjustment circuit 206aare described herein.

[0025] The priority adjustment circuit 206acomprises a first AND gate 208 having a first input coupled to the output of the up-down counter 202, a second input coupled to a miss output of the control logic 204 and an output coupled to a first input of a second AND gate 210. The second AND gate 210 has a second input configured to receive the data/instruction bit 308 of cache line 302a(of the unified cache 300) via a first inverter 212, a third input coupled to an output of a third AND gate 214 and an output coupled to a first input of an OR gate 216. The third AND gate 214 has a plurality of inputs configured to receive the LRU age bits 306 from the cache line 302aof the unified cache 300.

[0026] The priority adjustment circuit 206afurther comprises a fourth AND gate 218 having a first input coupled to the output of the up-down counter 202 via a second inverter 220, a second input coupled to the miss output of the control logic 204 and an output coupled to a first input of a fifth AND gate 222. The fifth AND gate 222 has a second input configured to receive the data/instruction bit 308 of the cache line 302aof the unified cache 300, a third input coupled to the output of the third AND gate 214 and an output coupled to a second input of the OR gate 216. The output of the OR gate 216 is coupled to LRU cache support logic 224.

[0027] The LRU cache support logic 224 is configured to replace the data or instructions stored in the cache line 302aof the unified cache 300 with new data or instructions in response to an appropriate logic level output by the OR gate 216. The LRU cache support logic 224 also is configured to replace the data or instructions stored in each cache line 302b-kwith new data or instructions in response to an appropriate logic level output by an OR gate (not shown) of each priority adjustment circuit 206b-k. Note that LRU cache support logic (such as the LRU cache support logic 224) for replacing data or instructions stored in cache lines is well known in the art and is not described further herein.

[0028] In operation, the up-down counter 202 is set to a predetermined count (e.g., 64 for a 128 count counter), and thereafter counts the number of misses to data and the number of misses to instructions generated as the unified cache 300 is accessed. Specifically, for each miss to data signal generated by the control logic 204, the up-down counter 202's count is decremented and for each miss to instruction signal generated by the control logic 204, the up-down counter 202's count is incremented. Thus, the count of the up-down counter 202 effectively measures the difference between the number of misses to data and the number of misses to instructions associated with the unified cache 300.

[0029] The up-down counter 202 is provided with a count threshold (e.g., preferably selectable/programmable as described below) such that when the count of the up-down counter 202 exceeds the count threshold, a first logic state (e.g., a logic 1) is output by the up-down counter 202. When the count of the up-down counter 202 is equal to or less than the count threshold, a second logic state (e.g., a logic 0) is output by the up-down counter 202. Accordingly, if more misses to instructions occur than misses to data, the up-down counter 202 outputs a high logic level, and if more misses to data occur than misses to instructions, the up-down counter 202 outputs a low logic level.

[0030] In a conventional LRU algorithm for managing cache allocation, each time a miss to cache occurs, the control logic 204 generates a miss to cache signal and either a miss to instructions or a miss to data signal, and the age of the cache lines within the unified cache 300 are aged (e.g., by adjusting the LRU age bits 306) as is known in the art. To determine which cache line or lines to replace, the age of each cache line 302a-kis examined, and the oldest cache line is replaced (e.g., a cache line having high logic levels for each LRU age bit). However, in accordance with the inventive cache management method 100, when a miss to cache occurs, the particular cache line or lines replaced within the unified cache 300 depends on the count of the up-down counter 202.

[0031] Assuming more misses to instructions than misses to data have occurred, the up-down counter 202 outputs a high logic level. In response thereto the first AND gate 208 of each priority adjustment circuit 206a-koutputs a high logic level (a “REPLACE LRU DATA” signal) to the second AND gate 210, and the fourth AND gate 218 outputs a low logic level to the fifth AND gate 222.

[0032] With reference to the priority adjustment circuit 206a, if the LRU bits 306 of the cache line 302aare other than all high logic levels, the third AND gate 214 outputs a low logic level, as do the second AND gate 210, the fifth AND gate 222 and the OR gate 216 so as to prevent the LRU cache support logic 224 from replacing the cache line 302a. However, if the LRU bits 306 of the cache line 302aare all high logic levels, the cache line 302amay be eligible for replacement. For example, if the first cache line 302acontains data (e.g., as indicated by a low logic level for the data/instruction bit 308 of the first cache line 302a), with the output of the first AND gate 208 high (due to more misses to instructions than misses to data occurring so as to generate a high logic level at the output of the up-down counter 202 as described), the second AND gate 210 outputs a high logic level. In response thereto, the OR gate 216 outputs a high logic level to the LRU cache support logic 224, and the LRU cache support logic 224 treats the cache line 302aas replaceable.

[0033] Note that with the output of the up-down counter 202 high, the fifth AND gate 222 is effectively disabled so that if the cache line 302ais an instruction cache line (as indicated by a high logic level value for the data/instruction bit 308) having all high logic level LRU age bits 306 (e.g., the oldest age), the OR gate 216 is unable to generate a high logic level and the LRU cache support logic 224 is precluded from replacing the cache line 302a. The allocation of cache resources of the unified cache 300 thereby is biased toward instructions. The priority adjustment circuits 206b-koperate similarly to determine the replaceability of cache lines 302b-k, respectively.

[0034] If more misses to data occur than misses to instructions, the count of the up-down counter 202 falls below the count threshold and the up-down counter 202 outputs a low logic level. In response thereto, the first AND gate 208 of each priority adjustment circuit 206a-koutputs a low logic level to the second AND gate 210 while the fourth AND gate 218 of each priority adjustment circuit 206a-koutputs a high logic level (a “REPLACE LRU INSTRUCTIONS” signal) to the fifth AND gate 222. With the output of the first AND gate 208 low, the output of the second AND gate 210 is forced low so that data cache lines (e.g., cache lines having a low logic level for data/instruction bit 308) may not be replaced by the LRU cache support logic 224. However, with the output of the fourth AND gate 218 high, instruction cache lines (e.g., cache lines having a high logic level for data/instruction bit 308) that have high logic level LRU age bits 306 are designated as replaceable via a high logic level output by the fifth AND gate 222 to the OR gate 216 and by the OR gate 216 to the LRU cache support logic 224. In this manner, allocation of the unified cache 300's resources is biased toward data.

[0035] FIG. 4 is a schematic diagram of a second cache management circuit 400 for implementing the inventive cache management method 100 of FIG. 1. The second cache management circuit 400 is identical to the first cache management circuit 200 of FIG. 2 with the exception that the up-down counter 202 is replaced with an up-down counter 402 having a preset input coupled to task switching logic 404 of a microprocessor (not shown) employing the unified cache 300 of FIG. 3. The task switching logic 404 generates a new task signal in response to each new task performed within the microprocessor (as is known in the art) and supplies the new task signal to the preset input of the up-down counter 402. In response thereto, the count of the up-down counter 402 is preset to a default condition, such as 50% of the full scale value of the counter. Any other default count may be employed, and the up-down counter 402 preferably is configured to allow any default value to be programmably provided via the preset input. Alternatively, the up-down counter 402 may be preset automatically after a predetermined time period. Old hit/miss statistics for data and instructions which typically are in applicable or undesirably skew cache allocation for new applications thereby are reset at least periodically, but preferably at the beginning of each new task.

[0036] FIG. 5 is a schematic diagram of a third cache management circuit 500 for implementing the inventive cache management method 100 of FIG. 1. The third cache management circuit 500 is similar to the first cache management circuit 200 of FIG. 2 and to the second cache management circuit 400 of FIG. 4. However, unlike the first cache management circuit 200 and the second cache management circuit 400, the third cache management circuit 500 comprises an up-down counter 502 having a plurality of preset inputs 504a-c, a plurality of upper-count threshold taps 506a-c, a plurality of mid-count threshold taps 508a-cand a plurality of lower-count threshold taps 510a-c. The third cache management circuit 500 further comprises a first adjustable divide-by circuit 512 coupled between the control logic 204 and a count increment input of the up-down counter 502, a second adjustable divide-by circuit 514 coupled between the control logic 204 and a count decrement input of the up-down counter 502 and an adjustable preset circuit 516 coupled between the task switching logic 404 and the preset inputs 504a-c. A first adjustable stop circuit 518 is coupled to the upper-count threshold taps 506a-cand to the count increment input of the up-down counter 502, a second adjustable stop circuit 520 is coupled between the lower-count threshold taps 510a-cand to the count, decrement input of the up-down counter 502, and an adjustable tap selection circuit 522 is coupled between the mid-count threshold taps 508a-cof the up-down counter 502 and the priority adjustment circuits 206a-k.

[0037] In operation, the first adjustable divide-by circuit 512 divides the miss to instructions signal output by the control logic 204 by a predetermined divide-by value stored within registers 512a. Preferably, the predetermined divide-by value is programmable by writing the binary equivalent of the desired divide-by value to the registers 512a. The response rate of the up-down counter 502 to the miss to instructions signal from the control logic 204 thereby is adjustable. The second adjustable divide-by circuit 514 operates similarly with regard to the miss to data signal output by the control logic 204, allowing the response rate of the up-down counter 502 to the miss to data signal to be adjusted by a predetermined and preferably programmable divide-by value stored within registers 514aof the second adjustable divide-by circuit 514.

[0038] The preset circuit 516 supplies the up-down counter 502 with user selectable values for the plurality of upper, mid and lower count thresholds of the up-down counter 502 in response to a new task signal from the task switching logic 404. Specifically, the preset circuit 516 contains a register file 516athat stores “sets” of preset values for the upper, mid and lower count thresholds of the up-down counter 502, and the particular set of threshold values loaded into the up-down counter 502 (in response to a new task signal from the task switching logic 404) is selected by the contents of registers 516bof the preset circuit 516.

[0039] Preferably both the register file 516aand the registers 516bare programmable to allow any desired count threshold values to be loaded into the up-down counter 502. AND gates 516c-eare provided to prevent the contents of the register file 516afrom affecting the up-down counter 502's count thresholds when a new task signal is not present.

[0040] The first adjustable stop circuit 518 detects when the count of the up-down counter 502 reaches one of its upper-count thresholds and in response thereto generates a stop signal that gates off the miss to instructions signal from the control logic 204 so as to prevent further increases of the up-down counter 502's count. In this manner, the count of the up-down counter 502 is prevented from reaching a level during “heavy” instructions cycles that altogether eliminates cache allocation for data.

[0041] The first adjustable stop circuit 518 comprises registers 518acoupled to a first AND gate 518band to a second AND gate 518cthat select which of the upper-count threshold taps to monitor. For example, if the registers 518acontain (0,0), the first AND gate 518bgates off the first upper-count threshold tap 506a, the second AND gate 518cgates off the second upper-count threshold tap 506band the third upper-count threshold tap 506c(e.g., the tap having the highest upper-count threshold) controls the operation of the first adjustable stop circuit 518. Likewise, if a high logic level is supplied to either the first AND gate 518bor to the second AND gate 518c, the first upper-count threshold tap 506bor the second upper-count threshold tap 506c, respectively, will control the operation of the first adjustable stop circuit 518. That is, when the up-down counter 502 reaches the upper-count threshold associated with the selected upper-count threshold tap, a high logic level is generated on the tap and is supplied to a NOR gate 518d. In response thereto, the NOR gate 518dgenerates a low logic level that gates off the miss to instructions signal (supplied from the control logic 204) via a third AND gate 518e. Preferably the registers 518aare programmable.

[0042] The second adjustable stop circuit 520 functions similarly to the first adjustable stop circuit 518 by selecting one of the lower-count thresholds of the up-down counter 502 and by preventing the count of the up-down counter 502 from falling below the selected count threshold. The second adjustable stop circuit 520 employs registers 520a, first AND gate 520band second AND gate 520cto select which of the lower-count threshold taps 510a-cwill control the second adjustable stop circuit 520; and the selected lower-count threshold tap supplies a high logic level to a NOR gate 520dso as to gate the miss to data signal (supplied from the control logic 204) via a third AND gate 520e.

[0043] The adjustable tap selection circuit 522 employs similar register/gate logic (e.g., registers 522aand first and second AND gates 522b, 522c) to select which of the mid-count threshold taps 508a-cpasses a high logic level (via an OR gate 522d) to the priority adjustment circuits 206a-kwhen the selected tap's mid-count threshold is exceeded. In this manner, the count threshold that determines whether to weight cache allocation toward instructions or data is adjustable (and preferably programmable).

[0044] The foregoing description discloses only the preferred embodiments of the invention, modifications of the above disclosed apparatus and method which fall within the scope of the invention will be readily apparent to those of ordinary skill in the art. For instance, the specific type of logic gates described herein are merely preferred and any functionally equivalent logic gates may be similarly employed.

[0045] Accordingly, while the present invention has been disclosed in connection with the preferred embodiments thereof, it should be understood that other embodiments may fall within the spirit and scope of the invention, as defined by the following claims.