Cache with selective least frequently used or most frequently used cache line replacement

Methods and apparatus allowing a choice of Least Frequently Used (LFU) or Most Frequently Used (MFU) cache line replacement are disclosed. The methods and apparatus determine new state information for at least two given cache lines of a number of cache lines in a cache, the new state information based at least in part on prior state information for the at least two given cache lines. Additionally, when an access miss occurs in one of the at least two given lines, the methods and apparatus (1) select either LFU or MFU replacement criteria, and (2) replace one of the at least two given cache lines based on the new state information and the selected replacement criteria. Additionally, a cache for replacing MFU cache lines is disclosed. The cache additionally comprises MFU circuitry (1) adapted to produce new state information for the at least two given cache lines in response to an access to one of the at least two given cache lines, and (2) when a cache miss occurs in one of the at least two given cache lines, adapted to determine, based on the new state information, which of the at least two given cache lines is the most frequently used cache line.

FIELD OF THE INVENTION

This invention relates to computer systems, and, more particularly, relates to caches used by processors in computer systems.

BACKGROUND OF THE INVENTION

Caches are used to speed up accesses to recently accessed information. During a read from main memory, a copy of the read information will also be stored in the cache. When the processor next accesses the information, the cache will generally supply the information (assuming that the information is still in the cache), instead of having a read performed of main memory to determine the information. This speeds access time to the information, as the memory used in a cache will typically be on the order of ten to hundreds of times faster than the memory used in the main memory of a computer system. With increased speed generally also comes increased cost, area, complexity, and power demands. Consequently, caches are highly optimized to work efficiently in the intended computer environment.

Caches are generally organized into two portions, namely a cache data array and a directory. The cache data array stores information from main memory, while the directory contains items such as the main memory addresses to which the information belongs.

A “hit” in the cache occurs when the information being addressed from main memory already exists in the cache. A hit means that the information can be read from the cache and no read is performed to main memory. A “miss” occurs when the information being addressed from main memory is not in the cache. A read is performed to main memory to obtain the information, and a copy of the information is also stored in the cache.

The cache memory generally contains “lines” of information. Each line typically contains information from more than one memory address in main memory. Caches are created this way because it is commonly assumed that if information at one main memory address is used, information at addresses near the original address will also be used. Therefore, lines in the cache contain information from multiple main memory addresses.

Caches generally use some cache line replacement technique to lessen the likelihood that main memory will be accessed. A common cache line replacement technique is called a Least Recently Used (LRU) technique. The LRU cache line replacement technique attempts to determine which line in a cache is the least recently used and to replace the least recently used information with information being read from main memory. The directory typically contains data which is used to determine which lines in the cache are the least recently used.

Although LRU cache line replacement techniques are beneficial in order to update lines in a cache, a need still exists for additional cache line replacement techniques.

SUMMARY OF THE INVENTION

The present invention provides techniques for cache line replacement that selectively allow Least Frequently Used (LFU) or Most Frequently Used (MFU) cache line replacement. Additionally, a cache having MFU cache line replacement techniques is disclosed.

In an exemplary aspect of the invention, methods and apparatus allowing a choice of LFU or MFU cache line replacement are disclosed. The methods and apparatus determine new state information for at least two given cache lines of a number of cache lines in a cache, the new state information based at least in part on prior state information for the at least two given cache lines. Additionally, when an access miss occurs in one of the at least two given lines, the methods and apparatus (1) select either LFU or MFU replacement criteria, and (2) replace one of the at least two given cache lines based on the new state information and the selected replacement criteria.

In another exemplary aspect of the invention, a cache for replacing MFU cache lines is disclosed. The cache comprises a number of cache lines and state information for at least two given cache lines. The cache additionally comprises MFU circuitry (1) adapted to produce new state information for the at least two given cache lines in response to an access to one of the at least two given cache lines, and (2) when a cache miss occurs in one of the at least two given cache lines, adapted to determine, based on the new state information, which of the at least two given cache lines is the most frequently used cache line. The cache also comprises replacement circuitry coupled to the MFU circuitry and to the number of cache lines, the replacement circuitry adapted to replace the given cache line determined as the most frequently used.

DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS

The present invention provides techniques for cache line replacement allowing choice of LFU or MFU cache line replacement. In an exemplary embodiment, an LFU cache line replacement or MFU cache line replacement may be performed depending on a selection that can be predetermined or determined during real time. Methods and apparatus are disclosed herein that allow choice of LFU or MFU cache line replacement.

For ease of reference, the present detailed description is divided into an Introduction section and an Exemplary Embodiments section.

Introduction

This section presents reasons why choice of LFU or MFU cache line replacement might be beneficial for an embedded system. Although embedded systems are used as the examples herein, the present invention is in no way limited to embedded systems and may be applied to any system using a cache line replacement technique.

An embedded system is, for example, a computer system that contains one or more processors that each perform a specialized function or set of functions. Embedded systems may be contained within a more general computer system, e.g., a Digital Signal Processor (DSP) contained in a cell phone, a controller contained in a set-top box, or a graphics accelerator card contained in a general purpose computer system. The “code space” for an embedded system is the space used to store executable statements (e.g., called “code”). On an embedded system, the code space also typically contains data.

Typical embedded systems (e.g., DSPs and controllers) do not use cache memories for several reasons: the code space is often small enough that a small to medium sized, one level memory can contain it; the processors work in real-time and may not be able to tolerate any unexpected delays, which can be introduced by a cache miss; and power is often a major issue, so no components can be added that might consume additional power. Such embedded systems are typically a System on One Chip (SOC) and as such, the associated memory is generally a “macro” that fits on the same chip. This limits the code space to that of a fast Static Random Access Memory (SRAM), in the range of 64 KiloBytes (KBytes) or less, more often 16 KBytes.

As systems and applications increase in size, the code space increases and is already extending into regions where 16 to 64 KBytes is not sufficient. Adding additional one-level memory macros on other chips can incur undesirable delays and thus makes caches, such as a first-level (L1) cache, attractive. As is known in the art, an L1cache is typically formed on the same chip as the processor, while second-level (L2) or third-level (L3) caches are typically formed outside the package containing the chip and its processor. Thus the use of a cache for embedded systems is becoming more attractive, and eventually might be necessary. As described below, embedded processors have particular code execution characteristics which allow and in fact would make good use of a cache, such as an L1cache.

As described above, in cache systems in common use, cache lines are generally replaced based on an LRU algorithm. Also, typical cache systems will be divided into a number of “congruence classes,” each of which has a number of cache lines. Congruence classes are a way of organizing a cache.

There are two different nomenclatures used with respect to cache architecture. The one used herein is as follows. The “congruence class” determines a degree of set-associativity, which is the number of cache lines that simultaneously require a compare for determining a hit. Thus, a four-way set associative cache has four lines per congruence class and requires four compares on a virtual address to determine if a line is present in the cache. Each such congruence class contains four sets, A B, C, and D. So the total cache has a number of lines equal to A+B+C+D.

In more recent nomenclature, a “set” is the same as the congruence class defined above. Additionally, the sets defined above are called “ways” in the more recent nomenclature.

Each congruence class requires a small register to keep track of the ordering of the cache lines in each congruence class. For a four-way set associative cache, using a Least Recently Used (LRU) replacement technique, each congruence class of four cache lines requires six stored bits to maintain the LRU order. An introduction to congruence classes and set associativity is described in Matick, “Computer Storage Systems and Technology,” J. Wiley, 595–599 (1977), the disclosure of which is hereby incorporated by reference. LRU replacement algorithms are usually inadequate for the types of code encountered in embedded systems. Techniques based on frequency of use are more desirable, as will be discussed below. Thus, LFU or MFU cache line replacement strategies are more desirable, but were previously considered to be more difficult and expensive to implement.

In the past, an LFU type of cache line replacement technique has been used in large storage systems for databases. Such techniques keep track of the frequency of use of disk pages and replace those which are least frequently used. These technique are more complex than that disclosed herein, require and use large, stored “tables of frequencies” that are updated and processed by a special stored program, and require typically microseconds to milliseconds to process. See, for example, N. Megiddo and D. S. Modha, “ARC: A self-tuning, low overhead replacement cache,” Proc. of FAST'03: 2nd USENIX Conf. on File and Storage Techniques, 115–130 (2003), the disclosure of which is hereby incorporated by reference. Such algorithms and implementations are generally unsuitable for an L1cache, or even L2or L3caches. However, the present invention provides LFU or MFU cache line replacement techniques that are suitable for a variety of levels of cache.

FIG. 1shows an example of a cache105that has a number cache blocks115. The caches blocks are broadly divided into two sections: a kernel section140and a control code section160. Two cache blocks115are frontend kernels120. Four cache blocks115are backend kernels130. The kernel section140is therefore divided into the frontend kernels120and backend kernels130. A number of additional cache blocks115are control code blocks150-1through150-N (collectively, “control code 150”). The control code section160is therefore divided into N control code blocks150-1through150-N. The different types of information in the cache blocks115will be examined to see why it can be beneficial to choose between LFU and MFU cache line replacement techniques depending on the type of code being executed.

Typically, code in an embedded system such as a DSP comprises three types of frames:

1. Control code150having short, typically sequentially executed instructions that seldom have much immediate reuse (e.g., no looping) but are re-executed on a long time scale. This control code150is invoked to start and control the kernel segments which do the real signal processing. Control code takes 20 percent of CPU time, but 80 percent of program code address space. If a cache line has only four Long Instruction Words (LIWs) and control lines only get sequential access, on average, then this would be a frequency of use-count of three or four accesses per line.

2. Frontend kernels120that will typically process 64 samples at a time. Frontend kernels120might be, for example, equalizers, digital filters, interpolators, decimators, and echo cancellers. Assuming all LIWs of a cache line get used, then 64 samples require 64 loops through the code. If cache lines are four LIW long (e.g., where one LIW is eight bytes) then each cache line will get used (e.g., accessed) 4*64=256 times.

3. Backend kernels130that will typically process 512 samples at a time, requiring 512 loops through the code. Backend kernels130could be, e.g., Fast Fourier Transforms (FFTs), Reed Solomon decoders, Quadrature Amplitude Modulation (QAM) decoders and Viterbi decoders. Again assuming each LIW gets used, then a cache line of four LIWs will be accessed 4*512=2048 times.

A typical application might have the following code stored in the cache: 16 frontend kernels120(at eight LIWs or 64 bytes per kernel) and one backend kernel130of 128 LIW or 1 Kbytes. At 32 bytes per cache line, this represents 16 frontend kernels120occupying two cache lines per kernel, and one backend kernel130occupying 32 cache lines plus about 8 Kbytes or more of control and Operating System (OS) code.

This code, stored as lines in a cache might look and behave as shown inFIG. 1. The control code section160takes up 80 percent of the memory space, but since it is used mainly sequentially with no looping, it takes only about 20 percent of the processing time. The control code150is reused but only on a long time scale. However, having it resident when needed can be important for performance in order to get kernels started quickly.

The kernel section140, which occupies about 20 percent of the memory space, will typically take 80 percent of the processing time. Typically, this code stored in a cache105would only have one backend kernel130, which would be executed to completion, and would not be used again for a long time and thus should be replaced in the cache by another backend kernel130. Frontend kernels120are generally much smaller, so many can reside in the cache105at one time. Since part of or even the entire group of frontend kernels120, are likely to be reused sometime relatively soon, they should be maintained in the cache.

Depending on the application, the backend kernels130should be replaced whenever a cache miss occurs, and sometimes the control code150. The feature of such DSP, or any similar code which allows this is as follows.

A typical application scenario would be something as follows.

Assume code in the frontend kernel120is executing: all four LIWs of all 32 lines are used and the code loops through all these 64 times (e.g., for 64 samples). So each cache line is accessed 4 LIW*64 loops=256 times. If the processor executes, on average, one LIW each cycle, this full frontend kernel120takes 4*32*64=8K cycles. At five nanoseconds (ns) per cycle, this is 40 microseconds (μs) of processor time.

In between each frontend kernel120, some control code150is executed to set up the next frontend kernel120. This is typically all sequential, with little or no looping, so each control code150cache line is used four times maximum. When the frontend kernel120is done executing, the control code150sets up the backend kernel130.

Code in the backend kernel130executes all four LIWs of all 32 cache lines but redoes this entire process 512 times (maybe not in order, but on average covers all LIWs this way) So each cache line of the backend kernel130is accessed 4*512=2K times. The entire single backend kernel130of 32 lines requires a total of 4*32*512=64K cycles or 320 μs at five ns per LIW.

So the frequencies between “fast” (e.g., 40 μs) frontend kernels120and “slow” (320 μs) backend kernels130is 256 versus 2K, a factor of eight as per the length of samples making up the loops in each of the types of kernels.

When the first backend kernel130is completed, one or several other different, large backend kernels130will typically be executed before this first backend kernel130will be needed again. However, in the meantime, the same 16 small frontend kernels120will likely be repeatedly reused, possibly even multiple times while the first backend kernel130is running.

Various replacement policies are possible, and the choice depends on the particular application with its details of behavior. For the above scenario of a cache105with 16 small, fast, frontend kernels120and one large, slow backend kernel130, the set of 16 frontend kernels120can be invoked multiple times while the backend kernel130is running, and this set of frontend kernels120and backend kernels130is reused many times. Thus, for this case, it is desirable to maintain the set of 16 frontend kernels in the cache and replace the backend kernel130while keeping any already present frontend kernels120and control code130. For the implementation to be described below, the backend kernels130can be made to be the MFU cache lines, with some small exceptions. Thus this case would use a MFU cache line replacement technique.

In other applications, or under different conditions, the control code150needed at any time can change significantly even while the same backend kernel130is executing. In such cases, it would be desirable to replace the control code150while keeping any already present frontend kernels120and backend kernels130. For the implementation to be described below, the control code150can be made to be the LFU cache lines, with possibly some small exceptions. Thus this case would use a LFU cache line replacement techniques.

Either of these cache line replacement policies is possible within the realm of exemplary embodiments herein. In one embodiment, choice of either LFU or MFU cache line replacement is achieved by keeping a limited frequency count of each cache line useage, and a separate count of the total usage of each congruence class within a cache directory, for a set associative cache organization, where the set associativity can be any value.

Exemplary Embodiments

This section describes exemplary implementations for achieving a dynamic, partitioned cache having selectable LFU or MFU cache line replacement techniques.

Turning now toFIG. 2, a computer system205is shown. Computer system205comprises a processor215, an LFU/MFU cache220, and a main memory240, each of which is interconnected through bus260. LFU/MFU cache220comprises LFU/MFU circuitry225, directory230, and cache data array235. Main memory240comprises one or more applications250, which comprise selection information255.

LFU/MFU circuitry225is used to perform the LFU or MFU cache line replacement technique. The LFU/MFU circuitry225, as described below, has selection circuitry that can take input from, for instance, main memory240in order to determine which of the LFU or MFU cache line replacement techniques should be used for kernels or executable statements in main memory240. Directory230has information (not shown) such as addresses for cache lines in cache data array235and certain counters (described, e.g., in reference toFIG. 3below) used during LFU and MFU calculations. Cache data array235contains cache lines (not shown).

The application250is an application executed by the processor215. The selection information255is information that marks a portion (not shown) of application250or even single executable statements (not shown) in application250to indicate which of the LFU or MFU cache line replacement technique should be used. The application250may also be an OS. The portion of application250could be, for example, a frontend kernel, backend kernel, or control code, as described above. Additionally, the application250may be multiple applications250, where each application is typically assigned either an LFU or MFU cache line replacement technique. Furthermore, selection information255may be stored outside of application250or could be an instruction that places LFU/MFU circuitry225in either an LFU cache line replacement technique or an MFU cache line replacement technique.

In a simple system, a user, through techniques such as selection of an input parameter or choice of a particular operating system, at time of starting the system (called Initial Program Load, or IPL), would specify which cache line replacement technique to use. Then the cache line replacement technique is fixed until changed as above.

In a more complex system, the compiler would determine the best cache line replacement technique and set one or more parameters, which the system OS reads to set the proper cache line replacement technique. This could be done separately for each separate application run on the system.

An even more complex system could dynamically keep a running score of the effectiveness of the “current” cache line replacement technique setting and change the setter during real-time if performance sags. This is rather complex and requires some way to measure performance, but the present invention would allow the complex system to change cache line replacement techniques during operation.

Referring now toFIG. 3, an LFU/MFU cache220is shown. In this example, the LFU/MFU cache220is a four-way set-associative cache, with sets A through D. Cache data array235comprises N+1 congruence classes310-0through310-N. Each congruence class310comprises four sets315-1through315-4, each set of each congruence class310being a cache line. InFIG. 3, “Line XYY” refers to congruence class X and Set YY, where YY is written in binary. It should be noted that the term “cache line” indicates any portion of a cache that may be replaced. For example, cache lines may be called “blocks” in certain cache implementations. Directory230comprises a one line use (LUse) counter320for each line in cache data array235. Consequently, there are 4*(N+1) LUse counters320. Directory230also comprises one congruence class use (CCUse) counter330for each of the congruence classes310.

The LFU/MFU cache220replaces cache lines which are either least frequently used or most frequently used based on, for example, the criteria described below.

The LUse counters320keep count of the number of times a cache line has been used within some arbitrary period (to be discussed later) by including, for example, 4 to 7 bits (allowing counts of 16 to 128) corresponding to each cache line. This adds 4× Number of Cache Lines or 7× Number of Cache Line bits to the directory, which is not very large for most cases. For instance, for a 16 Kbyte cache, the extra bits for four bit counters amount to 512×4=2 K BITS for 32 byte cache lines or 4×256=1 K Bits for 64 byte cache lines. Additional bits for 7 bit counters in a 16K byte cache with 32 byte cache lines would be 7×512=3584, and 1792 bits for 64 byte cache lines.

In addition, each congruence class310has, in this exemplary embodiment, one additional counter, the CCUse counter330. This CCUse counter330will typically have one to three more bits than the LUse counters320. If eight bits are used for each CCUse counter330, then the directory230for a 16K, four-way set associative cache using 32 byte cache lines will require an additional 8*512/4=1K bits, and only 512 additional bits for 64 byte cache lines.

Turning now toFIG. 4, LFU/MFU cache220is shown in a different view. In this example, the LFU/MFU cache220is a two-way set-associative cache. The LFU/MFU cache220comprises, in this figure, the directory230, the LFU/MFU circuitry225, and replacement circuitry480. The directory230comprises LUse counters420-1,420-2and a CCUse count430for the congruence class405to which the cache lines (not shown), corresponding to the LUse counters420, belong. The directory230also comprises other stored data415(such as addressing information corresponding to the cache lines, which correspond to the LUse counters420). For simplicity, only one congruence class405is shown.

The LFU/MFU circuitry225comprises maximum (max.) value detectors433,432, and431, a data register440, multiplexers (MUXs)455,460, and445, an LFU detector465, selection circuitry450, and one-bit adders446and470. An LFU/MFU calculator is comprised of the MUX455and LFU detector465. The LFU/MFU calculator485is an example of a device used to perform either a LFU calculation or an MFU calculation. The data register440comprises non-inverted versions441,444of the LUse counters420-1and420-2and inverted versions442,443of the LUse counters420-1,420-2. The data register440is adapted to invert the data from the LUse counters420-1and420-2. The data register440is also adapted to shift the data from the LUse counters420-1,420-2, for reasons described below.

In the example ofFIG. 4, exemplary LFU or MFU cache line replacement techniques make use of the LFU counters420in the following way. Each time a cache line experiences a hit access, the LUse counter420corresponding to that cache line has a one added to its value. This is performed via MUX460, which is enabled via enables for Set A or Set B. The one-bit adder470increases the value of the LUse counter420-1or420-2corresponding to the cache line experiencing the hit. The resultant value then passes through the MUX445back to either LUse counter420-1or LUse counter420-2. When the LUse counter420of any accessed congruence class405reaches its maximum value (e.g., a value of 15 for 4 bit counter; or a value of 127 for 7 bit counter), then all LUse counters420in this congruence class405are divided in half (e.g., a right shift by one) to ensure the correct order of “use frequency” is maintained. In general, the division can be any integer division. The data register440is adapted to shift the data from LUse counters420when either Max. value detector433or Max. value detector432enables the data register440. The shifted data is then stored back to LUse counters420-1,420-2.

If a miss occurs, which requires replacing a cache line, the LUse counters420of the accessed congruence class405are searched for the entry with the smallest (LFU) or largest (MFU) count value.

In order to perform the LFU or MFU cache line replacement, the selection circuitry450selects which set of data from LUse counters420is to be used. The selected set of data will be A and B or Ā and {overscore (B)}. The selection circuitry450will enable the MUX455to select the set A and B when LFU cache line replacement is desired. Conversely, when MFU cache line replacement is desired, the selection circuitry450will enable the MUX455to select the set Ā and {overscore (B)}.

The LFU detector465performs a least frequently used calculation on one of the sets A and B or Ā and {overscore (B)}. When the LFU cache line replacement technique is selected, the LFU detector465performs the least frequently used calculation on the set A and B. The least frequently used calculation will select the LUse counter420with the smallest value. Thus, the output of the LFU detector465will be an indication as to which of the LUse counters420is the smallest, and the smallest LUse counter420corresponds to the least frequently used cache line. When the MFU cache line replacement technique is selected, the LFU detector465performs the least frequently used calculation on the set Ā and {overscore (B)}. The least frequently used calculation will select the largest LUse counter420. Thus, the output of the LFU detector465will be an indication as to which of the LUse counters420is the largest, and the largest LUse counter420corresponds to the most frequently used cache line.

In order to ensure the eventual replacement of a cache line that reaches a high count value and is not accessed anymore while the other cache lines in the same congruence class405are all used a fewer number of times, the count value of all entries may be reset to one-half of their values at some predetermined period. This period may be determined as follows: each congruence class405increments and makes use of its own CCUse counter430as previously indicated. The CCUse counter430starts at zero and is incremented by one (via one-bit adder446) each time a hit or miss occurs in its corresponding congruence class405. When any CCUse counter430in a currently accessed congruence class405reaches some predetermined value (as determined, e.g., by Max. value detector431), all LUse counters420in that congruence class405are divided in half and the CCUse counter430is reset to zero. As a result, any non-active cache lines, and thus non-changing LUse counters420, which initially have a high count value will reduce to one in three such periods, and to zero in four such periods, assuming a four bit counter. A seven bit counter with a higher maximum value will reduce to one in six such periods and zero in seven such periods. The cache line will likely be replaced before this, assuming the other cache lines are active.

Replacement circuitry480replaces the cache line indicated by the LFU detector465. Replacement circuitry480is well known in the art.

The LFU/MFU calculator485can also include inverters to create Ā and {overscore (B)}, if desired. The LFU/MFU calculator485is one implementation for calculating, by using the LUse counters420, which cache line is the least or most frequently used.

Selection circuitry450can be as simple as an input having a logic zero or logic one placed thereon. Selection circuitry450could be circuitry that determines, by using a bit or bits stored in an executable statement in the cache lines to which the LUse counters420correspond, whether a LFU or MFU cache line replacement technique should be used. As another example, the selection circuitry450could select a LFU or MFU cache line replacement technique based on address ranges corresponding to cache lines for the congruence class405or based on other criteria.

In a broad sense, the LFU/MFU circuitry225can perform a state-determination process. The “state” may be saved in the LUse counters420and in the CCUse counters430. New state is the new counts stored in LUse counter420and CCUse counters430, after incrementing by 1 or shifting (e.g., dividing in half). State-determination processing can be considered as two different processes: (1) State updating, which updates state via Max value detectors433,432, and431, enable shift/storeback, two 1-bit addresses (446&470), MUX460, MUX445, plus some simple logic (not shown) such as “Enable Shift” logic; and (2) state detection on miss, which uses the LFU detector465plus selection circuitry450to select either LFU or MFU cache line replacement with MUX455and based on LFU or MFU cache line criteria (such as that provided by the selection information255ofFIG. 2).

One reason for considering a state-determination process is the following. Suppose the cache is using an LFU replacement, and assume one congruence class is active, and has two cache lines (e.g., set associativity=2). Starting from a cold start (i.e., no previous cache line replacement), all use counters, both LUse set A counter420-1, LUse set B counter420-2, and CCUse counter430for this congruence class405are zero. Now suppose some cache access occurs to this congruence class405. This will be a miss, one of the two cache lines (e.g., empty slots), say from set A, will get filled and its LUse counter420-1will be incremented by one. The LUse counter420-2of set B of the second cache line of this same congruence class is not processed (e.g., remains at 0). Now suppose another access occurs to this same congruence class and is a miss. The LFU line to be changed which is a cache line of set B, whose LUse counter420-2(e.g., state) has not been processed, i.e., has not been changed. In this case the state has not been updated for the LUse counter420-2, but a state-determination process can still modify the LFU cache line.

It should be noted that LFU/MFU circuitry225can be modified to solely perform either LFU cache line replacement or MFU cache line replacement. For instance, always providing inverted versions of LUse counters420to the MUX455will select MFU cache line replacement. Similarly, always providing non-inverted versions of LUse counters420to the MUX455will select LFU cache line replacement.

Turning now toFIG. 5, a method500is shown that allows choice of LFU or MFU cache line replacement. Method500is generally performed by LFU/MFU circuitry225of the LFU/MFU cache220. In step520, a cache access occurs. If a hit occurs, steps515,520and525are performed. If a miss occurs, steps530and535are performed.

In step530, a replaceable cache line is found. The LUse counters of the missed congruence class are compared in order to determine the LUuse counter with minimum value if LFU cache line replacement is in effect. If MFU cache line replacement is in effect, the complemented values of the LUse counters are compared in order to determine the minimum value. In step535, the cache line that is the least or most frequently used for the congruence class is reloaded and the LUse counter for the replaced cache line is set to one. If CCUse=CCMax, then set CCUse to zero and right shift all LUse counters in this congruence class. Otherwise, increment CCUse.

It should be noted that different locations in method500could result in CCUse with the maximum value. For example, CCUse could be a maximum value before step515or after step535. Testing could be performed, if desired, at these points to ensure that CCUse does not exceed its maximum value without a corresponding reset.

The examples shown inFIG. 6illustrate the use of the LUse and CCUse counters. A typical scenario of cache usage and filling or resetting of the LUse and CCUse counters might be as follows. Assume the LUse counters are all 7 bits (e.g., counting from zero to 127) and the CCUse counter is 8 bits.

It is assumed that the cache line use counters were all initially zero, then some control code and frontend code is executed to complete one full set of 16 frontend kernels. The final state of all counters of one congruence class is shown as State I.

Next, a backend kernel begins processing and completes 128 samples (e.g., loops) resulting in a state of all counters that is shown as State II. The same backend kernel processes one more sample (e.g., loop), causing its LUse counter to reach 127+1, which exceeds the maximum count value and causes all LUse counters to be divided in half. The new state is State III.

Backend kernel continues processing 55 more loops, resulting in a state as shown in State IV. In this state, the CCUse counter is at its maximum value.

Backend kernel processes another loop, causing the CCUse counter to exceed its maximum value, thereby causing all LUse counters to be divided in half and resetting the CCUse counter itself to zero. This results in the new state shown as State V.

Examination of the four LUse counters shows that, with the exception of State I, the backend code lines are the MFU for all other cases. Thus, if the architecture or application dictates replacement of backend lines, the hardware only has to select the complements of the LUse counters to the LFU detector. By use of the complements, the counter values are effectively reversed so the MFU count becomes the LFU value. On rare occasions (e.g., if a miss occurs to the congruence which happens to be in state State I), the wrong line will be replaced. This will occur infrequently and only constitutes a minor degradation in performance, if any at all (this could, in fact, be the correct line to replace due to circumstances).

If the application or architecture specifies the replacement of control code, then the hardware only has to select the “true” values of the LUse counters to the LFU detector. Thus, the system only needs one LFU detector and can perform either MFU or LFU replacement. In fact, the choice can be made dynamically, since the only delay is a selection via a MUX in an exemplary embodiment shown above. Thus, if a compiler or other means (e.g., such as the programmer) can specify which choice is more desirable for any given application, the replacement policy is easily adjusted to suit this choice, and can be varied from application to application, or even from cycle to cycle.

The additional circuits required for the techniques of the present invention have been sized for one technology and implementation, and are relatively quite small in area and power consumption. Thus, the use of an off-chip main memory feeding a small cache on-chip with a processor, rather than an on-chip larger non-cached memory, can significantly reduce overall chip-power while maintaining performance. Exemplary embodiments of the present invention also allow fine tuning of the replacement policy to the application, either statically, at initial program load, or dynamically, while executing.