Method and means for dynamically partitioning cache into a global and

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.