Method and means for dynamically partitioning cache into a global and data type subcache hierarchy from a real time reference trace
First Claim
1. In a data processing system having a host processor, an external storage system, and a cache management system wherein said cache management system comprises a cache hierarchy and a cache manager, a method for dynamically partitioning a least recently used (LRU) ordered cache hierarchy as a function of a real time reference trace, said cache hierarchy being positioned in a data path coupling said processor to said external storage subsystem, said cache hierarchy including a global and at least one local subcache, said cache hierarchy being operative in a global to local subcache to external storage subsystem destaging direction among referenced objects defined over a plurality of data types, said cache hierarchy being partitioned as to storage space between said global and destaging local caches, each local cache being bound to objects having the same data type, a "hit" being denominated as a comparison match between a reference request and location of the object within a subcache while a "miss" being denominated as the absence of an object within a subcache, comprising the steps of:
- (a) recursively, using said cache management system, creating and maintaining LRU lists of referenced objects located in the counterpart subcaches;
(b) recursively, using said cache management system, creating and maintaining a multi-planar array of partition distribution data obtained from said real time reference trace and said LRU lists, each plane in said array having at least the integer dimensions of global subcache size, local subcache size, and data type; and
(c) optimally, using said cache management system, resizing the global and local subcache partitions after a predetermined number of cycles in said real time reference trace according to a deterministic dynamic program operated over said array to reflect expected improved performance in said cache hierarchy.
0 Assignments
0 Petitions
Accused Products
Abstract
A method and means is disclosed for dynamically partitioning an LRU cache partitioned into a global cache storing referenced objects of k different data types and k local caches storing objects of a single type. Referenced objects are stored in the MRU position of the global cache and overflow is managed by destaging the LRU object from the global to the local cache having the same data type. Dynamic partitioning is accomplished by recursively creating and maintaining from a trace of objects an LRU list of referenced objects and associated data structures for each subcache, creating and maintaining a multi-planar array of partition distribution data from the lists and the trace as a collection of all possible of maximum and minimum subcache sizing, optimally resizing the subcache partitions by applying a dynamic programming heuristic to the multiplanar array, and readjusting the partitions accordingly.
152 Citations
9 Claims
-
1. In a data processing system having a host processor, an external storage system, and a cache management system wherein said cache management system comprises a cache hierarchy and a cache manager, a method for dynamically partitioning a least recently used (LRU) ordered cache hierarchy as a function of a real time reference trace, said cache hierarchy being positioned in a data path coupling said processor to said external storage subsystem, said cache hierarchy including a global and at least one local subcache, said cache hierarchy being operative in a global to local subcache to external storage subsystem destaging direction among referenced objects defined over a plurality of data types, said cache hierarchy being partitioned as to storage space between said global and destaging local caches, each local cache being bound to objects having the same data type, a "hit" being denominated as a comparison match between a reference request and location of the object within a subcache while a "miss" being denominated as the absence of an object within a subcache, comprising the steps of:
-
(a) recursively, using said cache management system, creating and maintaining LRU lists of referenced objects located in the counterpart subcaches; (b) recursively, using said cache management system, creating and maintaining a multi-planar array of partition distribution data obtained from said real time reference trace and said LRU lists, each plane in said array having at least the integer dimensions of global subcache size, local subcache size, and data type; and (c) optimally, using said cache management system, resizing the global and local subcache partitions after a predetermined number of cycles in said real time reference trace according to a deterministic dynamic program operated over said array to reflect expected improved performance in said cache hierarchy. - View Dependent Claims (2, 3, 8)
-
-
4. A CPU implemented method for dynamically adjusting portions of a LRU referenceable memory space partitioned among a global subcache storing objects having k different data types and k local subcaches each bound to store objects of a single data type, applications executing on said CPU invoking a supervisory process to manage the subcache referencing, comprising the steps of:
-
(a) determining, using said supervisory process, an optimal space allocation among the global and local subcaches responsive to a trace of references to objects stored among the subcaches by (1) recursively, using said supervisory process, creating and maintaining LRU lists of said objects located in counterpart subcaches; (2) recursively, using said supervisory process, creating and maintaining a multi-planar array of partition distribution data obtained from said reference trace and said LRU lists, each plane in said array having at least the integer dimensions of global subcache size, local subcache size, and data type; and (3) optimally, using said supervisory process, resizing the global and local subcache partitions after processing a predetermined number of references in said reference trace according to a deterministic dynamic program operating over said array; (b) responsive, using said supervisory process, to each reference in said reference trace, LRU ordering the objects in the global subcache and adjusting for overflow in the global to local subcache direction such that an object referenced among the subcaches is placed in the most recently used (MRU) position in the global subcache, and in the event of a subcache full condition, the LRU object in the global subcache is destaged to the local subcache having the same data type; and (c) repeating, using said supervisory process, steps (a) and (b) for request traces of different lengths. - View Dependent Claims (5, 6, 7)
-
-
9. In a system having a processor, an external store, and means for establishing a path to data between said processor and external store, said means including a cache management system, said cache management system comprising a cache and a cache manager for maintaining objects referenced in said cache in least recently used (LRU) order,
said cache being partitioned into a global cache for storing referenced objects in LRU order over k different data types and k local caches for storing referenced objects in LRU order over a single one of the k data types, said global and local subcaches forming a hierarchy operative in the global to local destaging direction such that any currently referenced object is inserted in the most recently used order in the global subcache, in the event of a cache full condition, overflow is managed by destaging the LRU object in the global subcache to the local subcache having the same data type, wherein the improvement in said means for establishing a path to data comprises: -
(a) a plurality of counters arranged into 2*k disjoint sets such that the counters in each of the disjoint sets form a matrix of r rows and c columns where r is the number of different allowable global subcache sizes and c is the number of different allowable local subcache sizes for a given data type, thereby defining two matrices of counter values for each of the k data types, a first matrix for recording minimum count values and a second matrix for recording maximum count values; (b) said cache management system comprising means responsive to a real time reference trace for recursively creating and maintaining LRU lists of said objects and associated data structures representing inverted sorted orders of subsets of the lists, said lists and structures being counterpart to each of the subcaches; (c) said cache management system comprising means for recursively creating and maintaining a multiplanar array of partition distribution data obtained from said real time reference trace and said LRU lists and structures data in said counter matrices; and (d) said cache management system comprising means for optimally resizing the global and local subcache partitions after processing a predetermined number of references in said real time reference trace according to a deterministic dynamic program operating over said array.
-
Specification