Method and system for exclusive two-level caching in a chip-multiprocessor

• US 6,912,624 B2
• Filed: 02/02/2004
• Issued: 06/28/2005
• Est. Priority Date: 06/09/2000
• Status: Expired due to Term

• Current Assignee: SK Hynix Inc.
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Barroso, Luiz Andre, Nowatzyk, Andreas, Gharachorloo, Kourosh
• Primary Examiner(s): Anderson, Matthew
• Assistant Examiner(s): Li, Zhuo H.
• Application Number:
  US10/769,824
• Publication Number:
  US 20040260879A1
• Time in Patent Office: 512 Days
• Field of Search: 711/141, 711117-118, 711/119, 711/122, 711/130, 711/143, 711/145
• US Class Current: 711/141
• CPC Class Codes: G06F 12/0811 with multilevel cache hierarchies
• CPC Class Codes: G06F 12/0826 Limited pointers directories; State-only directories without pointers
• CPC Class Codes: G06F 2212/621 Coherency control relating to peripheral accessing, e.g. from DMA or I/O device

Abstract

To maximize the effective use of on-chip cache, a method and system for exclusive two-level caching in a chip-multiprocessor are provided. The exclusive two-level caching in accordance with the present invention involves method relaxing the inclusion requirement in a two-level cache system in order to form an exclusive cache hierarchy. Additionally, the exclusive two-level caching involves providing a first-level tag-state structure in a first-level cache of the two-level cache system. The first tag-state structure has state information. The exclusive two-level caching also involves maintaining in a second-level cache of the two-level cache system a duplicate of the first-level tag-state structure and extending the state information in the duplicate of the first tag-state structure, but not in the first-level tag-state structure itself, to include an owner indication. The exclusive two-level caching further involves providing in the second-level cache a second tag-state structure so that a simultaneous lookup at the duplicate of the first tag-state structure and the second tag-state structure is possible. Moreover, the exclusive two-level caching involves associating a single owner with a cache line at any given time of its lifetime in the chip-multiprocessor.

Claims

1. A method for maximizing the use of on-chip cache memory capacity in a chip-multiprocessors, comprising:

forming a two-level cache system with an exclusive cache hierarchy in order to minimize cache line replication and on-chip traffic, the two-level cache system including a first level cache dedicated to each processor in the chip-multiprocessor and a second-level cache shared by all the processors;

associating cache lines with an indication of ownership so that among one or more than one instances of each cache line present in the two-level cache system, there is only one instance that is an owner instance, the indication of ownership being provided only in a second-level cache;

associating the cache lines with state information that includes the indication of ownership, the state information for cache lines present in the first-level cache being maintained in the second-level cache; and

administering cache line ownership and write-backs based on a predetermined guideline.

2. A method as in claim 1, wherein based the predetermined guideline a first-level cache miss that finds no other copy of a requested cache line becomes an owner of the cache line.

3. A method as in claim 1, wherein based the predetermined guideline a first-level cache miss that does not find a copy of a cache line in the second-level cache but finds it in one or more than one of the first-level caches receives that cache line from a previous owner and becomes a new owner.

4. A method as in claim 1, wherein based the predetermined guideline a first-level cache that replaces a cache line, is informed by the second-level cache whether it is owner, in which case it issues a second level cache fill.

5. A method as in claim 1, wherein based the predetermined guideline whenever the second-level cache has a copy of a cache line, the second-level cache is the owner, and wherein a first-level cache miss that hits in the second-level cache without invalidating it by a write miss does not steal ownership from the second-level cache.

6. A method as in claim 1, wherein based the predetermined guideline whenever the second-level cache needs to evict a cache line that is additionally present in one or more first-level caches the second-level cache arbitrarily selects one of these first-level caches as the new owner.

7. A two-level cache system in a chip-multiprocessor for maximizing the use of on-chip cache memory capacity in the chip multiprocessor, comprising:

means for forming a two-level cache system with an exclusive cache hierarchy in order to minimize cache line replication and on-chip traffic, the two-level cache system including a first-level cache dedicated to each processor in the chip-multiprocessor and a second-level cache shared by all the processors;

means for associating cache lines with an indication of ownership so that among one or more than one instances of each cache line present in the two-level cache system, there is only one instance that is an owner instance, the indication of ownership being provided only in a second-level cache;

means for associating the cache lines with state information that includes the indication of ownership, the state information for cache lines present in the first-level cache being maintained in the second-level cache; and

means for administering cache line ownership and write-backs based on a predetermined guideline.

8. A two-level cache as in claim 7, wherein the system can be implemented in hardware or software or a combination of both.