Handling virtual memory address synonyms in a multi-level cache hierarchy structure

Patent metadata

Field	Value
Publication number	US-9274959-B2
Application number	US-201414335230-A
Country	US
Kind code	B2
Filing date	Jul 18, 2014
Priority date	Jul 24, 2013
Publication date	Mar 1, 2016
Grant date	Mar 1, 2016

Abstract

Handling virtual memory address synonyms in a multi-level cache hierarchy structure. The multi-level cache hierarchy structure having a first level, L1 cache, the L1 cache being operatively connected to a second level, L2 cache split into a L2 data cache directory and a L2 instruction cache. The L2 data cache directory including directory entries having information of data currently stored in the L1 cache, the L2 cache being operatively connected to a third level, L3 cache. The first level cache is virtually indexed while the second and third levels are physically indexed. Counter bits are allocated in a directory entry of the L2 data cache directory for storing a counter number. The directory entry corresponds to at least one first L1 cache line. A first search is performed in the L1 cache for a requested virtual memory address, wherein the virtual memory address corresponds to a physical memory address tag at a second L1 cache line.

First claim

What is claimed is:

1. A method for handling virtual memory address synonyms in a multi-level cache hierarchy structure, the multi-level cache hierarchy structure comprising a first level, L1 cache, the L1 cache being operatively connected to a second level, L2 cache split into a L2 data cache directory and a L2 instruction cache, wherein the L2 data cache directory comprises directory entries comprising information of data currently stored in the L1 cache, the L2 cache being operatively connected to a third level, L3 cache, the method comprising:
allocating counter bits in a directory entry of the L2 data cache directory for storing a counter number, wherein the directory entry corresponds to at least one first L1 cache line, and wherein the first level cache is virtually indexed while the second and third levels are physically indexed;
performing a first search in the L1 cache for a requested virtual memory address, wherein the requested virtual memory address corresponds to a physical memory address tag at a second L1 cache line;
based on the first search resulting in a cache miss, performing a second search in the L2 cache to locate a synonym index of a synonym L1 cache line corresponding to the requested virtual memory address, wherein the synonym L1 cache line is the at least one first L1 cache line;
based on the second search resulting in a cache hit:
sending a fetch request to the L3 cache for fetching contents of the synonym L1 cache line from the L3 cache, wherein the counter number is incremented;
invalidating the synonym L1 cache line in the directory entry and in a L1 directory entry of the L1 cache corresponding to the synonym L1 cache line; and
copying the fetched contents to the second L1 cache line; and

based on a determination that the counter number is equal to a predetermined maximum number of synonyms:
copying the contents of the synonym L1 cache line to the L2 instruction cache of the L2 cache, wherein a subsequent fetch request is redirected to the L2 instruction cache for fetching the contents of the synonym L1 cache line from the L2 instruction cache and for subsequently executing the invalidating the synonym L1 cache line and copying the fetched contents to the second L1 cache line.

2. The method of claim 1 , wherein the directory entry further comprises least recently used (LRU) bits indicative of a least recently used cache line for data replacement, wherein the copying the fetched contents of the second L1 cache line comprises modifying the LRU bits of the directory entry for indicating the synonym L1 cache line as a replacement cache line.

3. The method of claim 1 , wherein the copying the contents of the synonym L1 cache line comprises modifying LRU bits of the directory entry for indicating a cache line of the L2 instruction cache as a replacement cache line.

4. The method of claim 1 , wherein the copying the fetched contents to the second L1 cache line further comprises:
updating the directory entry with a synonym index of the second L1 cache line; and
creating a L1 directory entry in the L1 cache corresponding to the second L1 cache line.

5. The method of claim 1 , wherein the synonym index comprises at least one bit, b, of a virtual part of the requested virtual memory address, wherein the maximum number of synonyms is determined based on the synonym index.

6. The method of claim 1 , wherein the counter bits comprise at least two bits.

7. The method of claim 1 , wherein the fetching comprises incrementing the counter number by one.

8. The method of claim 1 , wherein the counter number is set to zero when the synonym L1 cache line is first copied from the L3 cache.

9. A multi-level cache system comprising a first level, L1 cache being operatively connected to a second level, L2 cache split into a L2 data cache directory and a L2 instruction cache, wherein the L2 data cache directory comprises directory entries comprising information of data currently stored in the L1 cache, the L2 cache being operatively connected to a third level, L3 cache, the multi-level cache system comprising:
a L1 controller in the L1 cache configured to perform a first search in the L1 cache for a requested virtual memory address, wherein the requested virtual memory address corresponds to a physical memory address tag at a second L1 cache line, wherein the first level cache is virtually indexed while the second and third levels are physically indexed;
a L2 controller in the L2 cache configured to:
allocate counter bits in a directory entry of the L2 data cache directory for storing a counter number, wherein the directory entry corresponds to at least one first L1 cache line;
based on the first search resulting in a cache miss, performing a second search in the L2 cache to locate a synonym index of a synonym L1 cache line corresponding to the requested virtual memory address, wherein the synonym L1 cache line is the at least one first L1 cache line; and
based on the second search resulting in a cache hit:
sending a fetch request to the L3 cache for fetching contents of the synonym L1 cache line from the L3 cache, wherein the counter number is incremented;
invalidating the synonym L1 cache line in the directory entry and in a L1 directory entry of the L1 cache corresponding to the synonym L1 cache line; and
copying the fetched contents to the second L1 cache line; and

based on a determination that the counter number is equal to a predetermined maximum number of synonyms:
copying the contents of the synonym L1 cache line to the L2 instruction cache of the L2 cache, wherein a subsequent fetch request is redirected to the L2 instruction cache for fetching the contents of the synonym L1 cache line from the L2 instruction cache and for subsequently executing the invalidating the synonym L1 cache line and copying the fetched contents to the second L1 cache line.

10. The multi-level cache system of claim 9 , wherein the L2 cache comprises a fetch control register for storing and incrementing the counter number, wherein the fetching comprises loading the incremented counter number of the fetch control register and storing said counter number in the allocated counter bits.

11. The multi-level cache system of claim 9 , wherein the L2 data cache directory comprises at least 2 counter bits.

12. The multi-level cache system of claim 9 , wherein the directory entry further comprises least recently used (LRU) bits indicative of a least recently used cache line for data replacement, wherein the copying the fetched contents of the second L1 cache line comprises modifying the LRU bits of the directory entry for indicating the synonym L1 cache line as a replacement cache line.

13. A computer program product for handling virtual memory address synonyms in a multi-level cache hierarchy structure, the multi-level cache hierarchy structure comprising a first level, L1 cache, the L1 cache being operatively connected to a second level, L2 cache split into a L2 data cache directory and a L2 instruction cache, wherein the L2 data cache directory comprises directory entries comprising information of data currently stored in the L1 cache, the L2 cache being operatively connected to a third level, L3 cache, the computer program product comprising:
a non-transitory computer readable storage medium readable by a processing circuit and storing instructions for execution by the processing circuit for performing a method comprising:
allocating counter bits in a directory entry of the L2 data cache directory for storing a counter number, wherein the directory entry corresponds to at least one first L1 cache line, and wherein the first level cache is virtually indexed

Assignees

• Globalfoundries Inc

Inventors

• Habermann Christian
• Jacobi Christian
• Koch Gerrit
• Recktenwald Martin
• Tast Hans-Werner

Classifications

• G06F12/0848 Primary

  Partitioned cache, e.g. separate instruction and operand caches · CPC title

• G06F2212/1024

  Latency reduction · CPC title

• G06F12/0897

  with two or more cache hierarchy levels (with multilevel cache hierarchies G06F12/0811) · CPC title

• G06F12/1063

  the data cache being concurrently virtually addressed · CPC title

• G06F12/0811 Primary

  with multilevel cache hierarchies · CPC title