Designing a cache using an LRU-LFU array

A system, comprising:

• a processor;
• and
• a memory unit coupled to said processor, wherein said memory unit is operable for storing a computer program for designing a cache;
• wherein said processor, responsive to said computer program, comprises:
• circuitry operable for receiving requests forming a workload;
• circuitry operable for performing a trace of said workload;
• circuitry operable for analyzing said trace of said workload;
• and
• circuitry operable for designing one or more stacks of cache entries based on said analysis of said trace of said workload;
• wherein said cache comprises a plurality of logical sections, wherein one of said plurality of logical sections comprises information, wherein one of said plurality of logical sections comprises a cache directory;
• wherein said cache directory in said cache comprises a logical time stamp associated with each cache entry in said cache;
• wherein each of said one or more one or more stacks comprises cache entries ordered from most recently used to least recently used based on said logical time stamps of said cache entries;
• wherein a cache entry at a least recently used stack position in a particular stack is evicted upon the storing of a new cache entry at a most recently used stack position in said particular stack;
• wherein said evicted cache entry is stored at said most recently used stack position of a next higher level stack except when said particular stack is a highest level stack.

A method for designing a cache comprising the steps of:

• receiving requests forming a workload;
• performing a trace of said workload;
• analyzing said trace of said workload;
• and
• logically ordering a plurality of stacks of cache entries based on said analysis of said trace of said workload;
• wherein said plurality of stacks are ordered in an array based on a frequency count of said cache entries, wherein said plurality of stacks are ordered from most frequently used to least frequently used.

A computer program product embodied in a machine readable medium for designing a cache comprising the programming steps of:

• receiving requests forming a workload;
• performing a trace of said workload;
• analyzing said trace of said workload;
• and
• logically ordering a plurality of stacks of cache entries based on said analysis of said trace of said workload;
• wherein said plurality of stacks are ordered in an array based on a frequency count of said cache entries, wherein said plurality of stacks are ordered from most frequently used to least frequently used.

A system, comprising:

• a processor;
• and
• a memory unit coupled to said processor, wherein said memory unit is operable for storing a computer program for designing a cache;
• wherein said processor, responsive to said computer program, comprises:
• circuitry operable for receiving requests forming a workload;
• circuitry operable for performing a trace of said workload;
• circuitry operable for analyzing said trace of said workload;
• and
• circuitry operable for logically ordering a plurality of stacks of cache entries based on said analysis of said trace of said workload;
• wherein said plurality of stacks are ordered in an array based on a frequency count of said cache entries, wherein said plurality of stacks are ordered from most frequently used to least frequently used.