Canonical Method for Cache Design
Original Publication Date: 2005-Mar-18
Included in the Prior Art Database: 2005-Mar-18
A canonical cache design method is disclosed. The method models the fundamental rules of caching to facilitate the design of a cache with some sense of optimal results: if a canonical cache structure can be defined, then certain operations can be applied to derive other forms of cache structure with behaviors that can be considered optimal in some sense. For example, the smallest cache implemented satisfying a certain minimum hit ratio for a low cost optimization, or with the highest hit ratio possible satisfying a certain largest amount of logic for a high performance optimization. These caches are formed when restrictions are applied to the canonical form based on the specified design constrains. The constrains are the traditional constrains applied in design optimization: performance, cost and complexity. The canonical design method, because of its nature (i.e., described by rules), is at a level of description higher than other methods in the art such as the LRU replacement algorithm. By that I mean that starting with the canonical array description it is possible to explain other methods if certain extensions, restrictions and/or modifications are applied. However, there is no set of equations in closed form that can be applied. Instead, the procedures to this optimization are captured in heuristics that take as input the design constrains for the cache and a trace of the workload that the cache is expected to handle.
Canonical Method for Cache Design
Two complementary canonical stack arrays are described, the canonical R-Stack array and the canonical F-Stack array. Starting with a cache structure in one of these forms, design constrains are applied according to the heuristics of the method to derive a cache design that can be considered optimal in some sense. The canonical stack array subsumes a wide range of cache entry replacement methods based on the locality of reference characteristics of both recency of reference (LRU) and frequency of reference (LFU). A design space is defined by both the R-stack and the F-stack arrays that include design parameters for array configuration such as stack size, the number of stacks, cache size, and a partitioning criteria. The basic metric for cache performance is the cache hit ratio. However, in practice, that metric does not provide enough measure to make decisions on the values used for the various design parameters in a dynamic way. We need performance metric(s) that get down into the performance of the individual stacks in order to have an effective cache management algorithm. The cache management algorithm controls the relative size of the various LRU stacks for the R-stack array. There are two sets of algorithms used for method described here, one describes the simulation done to establish the parameters of the design, such as the size of the cache. The others are used by the cache manager to track the changes in the workload dynamically and change the cache configuration adaptively in order to have an optimal solution. The dynamic cache management algorithms track the workload adaptively to reconfigure the cache through a continuum of configurations in a design space that spans both the R-stack array and the F-stack array and the specific design points in that design space depend on the real time changes of the workload. There is no specific design point defined by this disclosure. Instead, the design flows from one design point to another as it tracks the real time changes of the workload.
A diagram of the F-stack array is shown in Figure 1 below. An LRU stack keeps the entries ordered from most recently used (MRU) to least recently used (LRU). An LFU stack keeps the entries ordered from most frequently used (MFU) to least frequently used (LFU). A canonical array keeps the entries ordered in both recency of use and frequency of use in expanded form. A canonical expression is described, based on a recency organized stack, or R-stack, that is represented by an n by i array consisting ofn R-stacks of lengthi, where each stack is dedicated to a range of frequency counts and each entry in the R-stack is determined by the recency of the entries (by means of a time stamp). In the present invention, a second canonical expression is introduced based on a frequency organized stack or F-stack, that is represented by an n by i array consisting of n F-stacks of length i, where each stack is dedicated to a r...