Cache memory system and method for managing streaming-data

• US 6,578,111 B1
• Filed: 09/29/2000
• Issued: 06/10/2003
• Est. Priority Date: 09/29/2000
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Guzovskiy, Aleksandr, Shanahan, Patricia, Damron, Peter C.
• Primary Examiner(s): Verbrugge, Kevin
• Application Number:
  US09/677,093
• Time in Patent Office: 984 Days
• Field of Search: 711/133, 711/134
• US Class Current: 711/133
• CPC Class Codes: G06F 12/0862 with prefetch
• CPC Class Codes: G06F 12/0897 with two or more cache hierarchy levels with multilevel cache hierarchies G06F12/0811
• CPC Class Codes: G06F 2212/6028 Prefetching based on hints or prefetch instructions

Abstract

A system and method are provided for efficient handling of streaming-data in a cache memory system (105) having a cache with several cache-lines (160) capable of storing data. In one aspect, a method is provided for determining before storing data to a cache-line if the storing of data will replace earlier data already stored in cache (135). If the storing of data will replace data in the cache (135), it is determined if the data that will be replaced is streaming-data. If the data to be replaced is not streaming-data, it is stored into victim cache (155). However, if the data to be replaced is streaming-data, it is not stored into the victim cache, thereby improving system efficiency by eliminating the copying of data to be replaced and avoiding replacing other earlier data in victim cache (155) that may be needed in the future.

Claims

1. A method for operating a cache memory system having a cache with a plurality of cache-lines each capable of storing data, wherein the cache has the plurality of cache-lines grouped into a plurality of sets, the method comprising the steps of:

storing data in at least one of the plurality of cache-lines;

storing a sequence of numbers identifying the cache-lines in a particular one of the sets accessed in a first predetermined number, n, of preceding references to the set; and

setting a streaming-data-bit to identify data in a particular cache-line as streaming-data if the cache-line has been accessed less than a second predetermined number, k, times in the preceding n references to the set.

2. A method according to claim 1 wherein the cache memory system further comprises a victim cache between a lower level memory and the cache, and wherein the method further comprises the initial steps of:

determining prior to the step of storing data if the storing of data will replace data already stored in the cache-line;

if the storing of data will replace data in the cache-line, determining if the data to be replaced is streaming-data;

if the data is to be replaced is not streaming-data, storing the data to be replaced in the victim cache; and

if the data is to be replaced is streaming-data, not storing the data to be replaced in the victim cache.

3. A method for operating a cache memory system having a cache with a plurality of cache-lines each capable of storing data, wherein the cache is a set associative cache with the plurality of cache-lines grouped into a plurality of sets, the method comprising the steps of:

storing data in at least one of the plurality of cache-lines; and

determining if the data is streaming-data, the determining operation comprising the steps of;

providing a plurality of history queues, each of the history queues being associated with one of the plurality of sets and each of the history queues being adapted to hold a sequence of numbers identifying the cache-lines in the associated set accessed in a first predetermined number, n, of preceding references to the set; and

setting a streaming-data-bit to identify data in the cache-line as streaming-data if the cache-line has been accessed less than a second predetermined number, k, times in the preceding n references to the set.

4. A cache memory system comprising:

a cache having a plurality of cache-lines capable of storing data, each cache-line having associated therewith a streaming-data-bit capable of indicating whether data stored in the cache-line is streaming-data;

a cache controller configured to store data in one of the plurality of cache-lines, the cache controller further configured to determine if the data is streaming-data; and

a plurality of history queues, each of the history queues being adapted to hold a sequence of numbers identifying the cache-lines in the associated set accessed in a first predetermined number, n, of preceding references to the set.

5. A cache memory system according to claim 4 wherein the cache memory system further comprises a victim cache between a lower level memory and the cache, and wherein the cache controller is configured to:

determine prior to storing of data in one of the plurality of cache-lines if the storing of data will replace data already stored in the cache-line;

if the storing of data will replace data in the cache-line, determine if the data to be replaced is streaming-data;

if the data is to be replaced is not streaming-data, store the data to be replaced in the victim cache; and

if the data is to be replaced is streaming-data, not store the data to be replaced in the victim cache.

6. A cache memory system comprising:

a cache having a plurality of cache-lines capable of storing data, each cache-line having associated therewith a streaming-data-bit capable of indicating whether data stored in the cache-line is streaming-data, wherein the cache is a set associative cache with the plurality of cache-lines grouped into a plurality of sets;

a cache controller configured to store data in one of the plurality of cache-lines, the cache controller further configured to determine if the data is streaming-data; and

a plurality of history queues, each of the history queues being associated with one of the sets and each of the history queues being adapted to hold a sequence of numbers identifying the cache-lines in the associated set accessed in a first predetermined number, n, of preceding references to the set.

7. A cache memory system according to claim 6 wherein the cache controller is configured to set the streaming-data-bit to identify data in a cache-line in one of the plurality of sets as streaming-data if data in the cache-line has been accessed less than a second predetermined number, k, times in the preceding n references to the set.

8. A cache memory system for storing data, the cache memory system comprising:

a cache having a plurality of cache-lines capable of storing data, wherein the cache is a set associative cache with the plurality of cache-lines grouped into a plurality of sets;

a cache controller configured to store data to a way in one of the plurality of cache-lines; and

means for determining if the data stored in the way is streaming data, wherein the means for determining if data stored in the way is streaming-data comprises a plurality of history queues, each of the history queues being associated with one of the plurality of cache-lines and each of the history queues being adapted to hold a sequence of numbers identifying the cache-lines in the associated set accessed in a first predetermined number, n, of preceding references to the set.

9. A cache memory system according to claim 8 wherein the cache controller is further configured to set a streaming-data-bit associated with each way in each of the plurality of cache-lines to identify data as streaming-data if data in the cache-line has been accessed less than a second predetermined number, k, of times in the preceding n references to the set as recorded in the history queue.