Method and apparatus for predicting hot spots in cache memories

One embodiment of the present invention provides a system for predicting hot spots in a cache memory. Upon receiving a memory operation at the cache, the system determines a target location within the cache for the memory operation. Once the target location is determined, the system increments a counter associated with the target location. If the counter reaches a pre-determined threshold value, the system generates a signal indicating that the target location is a hot spot in the cache memory.

RELATED APPLICATION

The subject matter of this application is related to the subject matter in a co-pending non-provisional application by the same inventors as the instant application and filed on the same day as the instant application entitled, “Method and Apparatus for Reducing the Effects of Hot Spots in Cache Memories,” having Ser. No. 10/354,327, and filing date 29 Jan. 2003.

BACKGROUND

1. Field of the Invention

The present invention relates to the design of cache memories within computer systems. More specifically, the present invention relates to a method and an apparatus for predicting the occurrence of hot spots in cache memories.

2. Related Art

Microprocessors use cache memories to store frequently used data closer to the computing engines. This helps to speed up applications because it takes considerably less time to access data in cache than it does to access data in main memory. Caches, however, are not without their limitations. Caches cannot be made infinitely large due to chip area and timing considerations. Typically, caches use a hashing scheme based on a target address of the data to allocate space in the cache memory for the data. Since caches are much smaller than main memory, multiple addresses in main memory will map to the same address in cache memory. The hashing scheme controls how many lines of main memory map to the same location in cache.

“Hot spots” in cache memories result from multiple blocks of data competing for the same location in cache. When a second piece of data gets allocated to the same location in cache as a first piece of data, the first piece of data is evicted from cache. If the first piece of data is subsequently requested by the application, the application typically has to wait for the first piece of data to be retrieved again from a lower level of the memory hierarchy, thus resulting in a much longer wait than if the first piece of data was still in cache.

Typically, microprocessor designers rely on multiple levels of cache to deal with this problem. However, each new level of cache is typically further away from the processing units and thus takes longer to access than the first-level cache. While these additional levels of cache help to speed up applications, they are not that effective when dealing with hot spots. Hot spots are typically small areas in the cache that are constantly being toggled between multiple sets of data. While additional levels of cache help to reduce the time needed for each lookup, they do not completely solve the problem.

In order to deal with the problem of hot spots, it is first necessary to identify which portions of a cache memory are hot spots. Since program behavior is extremely hard to predict beforehand, this identification process must take place at run time.

Hence, what is needed is a method and an apparatus that predicts the occurrence of hot spots in cache memories to facilitate reducing the effects of the hot spots.

SUMMARY

One embodiment of the present invention provides a system for predicting hot spots in a cache memory. Upon receiving a memory operation at the cache, the system determines a target location within the cache for the memory operation. Once the target location is determined, the system increments a counter associated with the target location. If the counter reaches a pre-determined threshold value, the system generates a signal indicating that the target location is a hot spot in the cache memory.

In a variation on this embodiment, if the target location is a hot spot and if a line is evicted from the cache during the memory operation, the system saves the evicted line to a hot spot cache that operates in parallel with the cache, so that the evicted line can be subsequently retrieved from the hot spot cache without having to access lower levels of the memory hierarchy.

In a variation on this embodiment, the counter stops incrementing when the counter reaches a maximum counter value.

In a variation on this embodiment, the pre-determined threshold is reached when the counter reaches the maximum counter value.

In a variation on this embodiment, the system resets the counter for each target location every n cycles. Resetting the counter in this way prevents every target location in the cache from eventually indicating a hot spot.

In a variation on this embodiment, the system uses a predictor RAM to store the counter values for the target locations in the cache.

In a variation on this embodiment, the system performs a function on the index bits of the address associated with the memory operation to determine which counter to increment for the memory operation. In this way, the system maps multiple target locations to a single counter.

DETAILED DESCRIPTION

Hot Spot Cache

FIG. 1illustrates hot spot cache104in accordance with an embodiment of the present invention.FIG. 1illustrates computer system100. Computer system100can generally include any type of computer system, including, but not limited to, a computer system based on a microprocessor, a mainframe computer, a digital signal processor, a portable computing device, a personal organizer, a device controller, and a computational engine within an appliance.

Computer system100contains data cache102, hot spot cache104, and hot spot predictor106. Note that data cache102can include any level of cache within computer system100, such a level-one (L1) cache or a level-two (L2) cache. Data cache102can also include any type of cache, such an instruction cache or a data cache. Data cache102contains decode unit108which decodes memory addresses to select their corresponding locations in tag RAM110and data RAM112. The output of tag RAM110is compared against the tag of the target address to determine if a data line for the target address is located within data cache102. Note that if data cache102is a set associative cache, each lookup returns multiple tags that are compared in parallel against the tag for the target address. If the tag for the target address matches a tag retrieved from tag RAM110, there is a cache hit. This means that the memory operation can be performed on the corresponding data line from data RAM112.

Hot spot cache104stores cache lines that have been evicted from “hot spots” in data cache102. Hot spot cache104contains tag RAM114and data RAM116, which store tags and data for lines that have been evicted from hot spots in data cache102. In this way, hot spot cache104effectively increases the associativity of data cache102for lines associated with hot spots by storing additional lines for the hot spots. Note that lines that are retrieved from hot spot cache104can be bypassed directly to the register file and can also be stored into data cache102for subsequent retrieval. In one embodiment of the present invention, hot spot cache104is a fully associative cache.

Hot spot predictor107determines whether or not a block in data belongs to a hot spot. If hot spot predictor107determines that a block in data cache102belongs to a hot spot, and if the block is being evicted from data cache102, hot spot predictor107sends a save victim signal108to hot spot cache104. This causes hot spot cache104to save the tag and data from victim line118in hot spot cache104. Note that victim line118contains the tag and data being evicted from data cache102.

Hot Spot Predictor

FIG. 2illustrates hot spot predictor106in accordance with an embodiment of the present invention. Hot spot predictor106contains index hash unit202, which performs a many-to-one mapping on the index portion of a target address for the current memory operation and uses the resulting modified index to perform a lookup into predictor RAM204. In this way multiple entries in data cache102can map into a single location in predictor RAM104. This saves on the amount of memory required to implement predictor RAM204at the cost of occasional aliasing problems.

Each entry in predictor RAM204contains a counter indicating how many times corresponding entries in data cache102have been written to. Upon receiving a modified index from index hash202, predictor RAM204sends the count for the corresponding entries in data cache102to compute threshold unit208and increment unit210. Increment unit210increments the count for the memory location and writes that count back to predictor RAM204if cache miss signal203is asserted. (Note that cache miss signal203is asserted if there is a miss in both data cache102can hot block cache104). Compute threshold unit208determines if the count for the memory location is above a pre-determined threshold, and if so, determines that the cache line is “hot” and sends a save victim signal to hot spot cache104if cache miss signal203is asserted.

Hot spot predictor106also contains reset logic206. Over time, the count for each memory location in predictor RAM204eventually becomes saturated. Hence, it is necessary to perform housekeeping on predictor RAM204to prevent it from sending a save victim signal for every memory operation in data cache102. Reset logic206can send a signal to predictor RAM204every n cycles which instructs predictor RAM204to clear all counters. In one embodiment of the present invention, reset logic206is configured to clear predictor RAM204every 10,000 cycles.

Process of Implementing a Hot Spot Cache

FIG. 3presents a flow chart illustrating the operation of a hot spot cache104in accordance with an embodiment of the present invention. The system starts when a memory operation is received at data cache102(step300). Upon receiving the memory operation, the system performs a lookup for the memory operation in data cache102and hot spot cache104in parallel (step302). The system then determines if the memory operation produces a hit or a miss in each cache (step304). Next, the system uses the hit or miss information to determine what actions to take (step306).

If the memory operation results in a hit in data cache102and a miss in hot spot cache104, the system bypasses the data from data cache102to the register file (step308). If the memory operation results in a miss in data cache102and a hit in hot spot cache104, the system bypasses the data from hot spot cache104to the register file (step310). In this situation, the system also fills the data line from hot spot cache104into data cache102, and also evicts the data line from hot spot cache104(step312).

If the memory operation results in a miss in both data cache102and hot spot cache104, the system tests to see if the entry in data cache102that corresponds to the memory operation is a hot spot (step314), and if so, data fills the victim line from data cache102into hot spot cache104(step316). Otherwise, if the memory operation is not directed to a hot spot in hot spot cache104, the system writes back the victim line to main memory (step318).