# US 2016/0259689 A1 · Managing reuse information in caches

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2016/0259689 A1
- Document ID: US20160259689A1
- Status: Published application
- Kind: A1
- Application number: 14/638,266
- Filed: 2015-03-04
- Published: 2016-09-08
- Earliest claimed: 2015-03-04
- Assignees: Cavium, Inc.
- Applicants: Cavium, Inc.
- Inventors: Shubhendu Sekhar Mukherjee
- Web page: https://patentgrep.com/patent/US20160259689A1

## CPC

- G06F 11/1402: {Saving, restoring, recovering or retrying}
- G06F 12/0802: Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
- G06F 12/0895: of parts of caches, e.g. directory or tag array
- G06F 12/1045: associated with a data cache
- G06F 2201/805: Real-time
- G06F 2212/608: Details relating to cache mapping
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Address translation and caching is managed using a processor that includes at least one CPU configured to run a hypervisor and at least one guest operating system. The managing includes: translating from virtual addresses to intermediate physical addresses; translating from the intermediate physical addresses to physical addresses; determining reuse information for memory pages based on estimated reuse of cache lines of data stored within the memory pages; storing the determined reuse information independently from: (1) any bits used to indicate virtual addresses, (2) any bits used to indicate intermediate physical addresses, and (3) any bits used to indicate physical addresses; and using the stored reuse information to store cache lines in a selected group of multiple groups of cache lines of a first cache.

## Claims

### Claim 1

A method for managing address translation and caching, the method comprising:
retrieving a first memory page from a storage device in response to a page fault issued after an attempt to retrieve data in the first memory page from a physical address space of a main memory of an external memory system;
issuing the attempt to retrieve the data in the first memory page in response to a cache miss issued after an attempt to retrieve the data in the first memory page from a first cache line of a first cache of the external memory system; and
managing address translation and caching from a processor that includes (1) at least one memory management unit coupled to the external memory system, and (2) at least one central processing unit configured to run a hypervisor and at least one guest operating system, the managing including:
translating from virtual addresses in a virtual address space to intermediate physical addresses in an intermediate physical address space;
translating from the intermediate physical addresses to physical addresses in the physical address space of the main memory;
determining reuse information for memory pages based on estimated reuse of cache lines of data stored within the memory pages;
storing the determined reuse information independently from: (1) any bits used to indicate virtual addresses, (2) any bits used to indicate intermediate physical addresses, and (3) any bits used to indicate physical addresses; and
using the stored reuse information to store cache lines in a selected group of multiple groups of cache lines of the first cache.

### Claim 2 (depends on 1)

The method of claim 1, wherein the first cache comprising a set associative cache having multiple sets of cache lines, each set of cache lines having multiple ways.

### Claim 3 (depends on 2)

The method of claim 2, wherein using the stored reuse information to store cache lines in a selected group of multiple groups of cache lines of the first cache comprises using the stored reuse information to store cache lines in a selected way of the multiple ways of the multiple sets of cache lines of the first cache.

### Claim 4 (depends on 3)

The method of claim 3, wherein a first way of the multiple ways is selected to store cache lines of data stored within a memory page having a first value of the reuse information, and a second way of the multiple ways is selected to store cache lines of data stored within a memory page having a second value of the reuse information different from the first value.

### Claim 5 (depends on 1)

The method of claim 1, wherein the first cache comprises multiple independent storage regions, each independent storage region being addressed by portions of physical addresses in the physical address space.

### Claim 6 (depends on 5)

The method of claim 5, wherein using the stored reuse information to store cache lines in a selected group of multiple groups of cache lines of the first cache comprises using the stored reuse information to store cache lines in a selected storage region of the multiple independent storage regions.

### Claim 7 (depends on 1)

The method of claim 1, wherein the reuse information comprises one or more bits stored within a page table entry cached in a translation lookaside buffer.

### Claim 8 (depends on 1)

The method of claim 1, wherein the estimated reuse of cache lines of data stored within the memory pages comprises an estimated miss rate for blocks of data that are attempted to be retrieved from corresponding cache lines of the first cache.

### Claim 9 (depends on 1)

The method of claim 1, wherein determining the reuse information includes: (1) determining first reuse information by the guest operating system, and (2) determining second reuse information by the hypervisor.

### Claim 10 (depends on 9)

The method of claim 9, wherein using the stored reuse information to store cache lines in a selected group of multiple groups of cache lines of the first cache includes processing the first reuse information and the second reuse information and using a result of the processing to store cache lines in a selected group of multiple groups of cache lines of the first cache.

### Claim 11 (depends on 1)

The method of claim 1, wherein the first cache comprises a last level cache.

### Claim 12

An apparatus comprising:
a storage device configured to store memory pages including a first memory page retrieved from the storage device in response to a page fault issued after an attempt to retrieve data in the first memory page from a physical address space, where the attempt to retrieve the data in the first memory page from the physical address space is issued in response to a cache miss;
an external memory system including: (1) a main memory controller coupled to main memory having the physical address space, and (2) a first cache configured to store a plurality of cache lines and to issue the cache miss after an attempt to retrieve the data in the first memory page from at least one of the cache lines; and
a processor that includes (1) at least one memory management unit coupled to the external memory system, and (2) at least one central processing unit configured to run a hypervisor and at least one guest operating system;
wherein the processor is configured to:
translate from virtual addresses in a virtual address space to intermediate physical addresses in an intermediate physical address space;
translate from the intermediate physical addresses to physical addresses in the physical address space of the main memory;
determine reuse information for memory pages based on estimated reuse of cache lines of data stored within the memory pages;
store the determined reuse information independently from: (1) any bits used to indicate virtual addresses, (2) any bits used to indicate intermediate physical addresses, and (3) any bits used to indicate physical addresses; and
use the stored reuse information to store cache lines in a selected group of multiple groups of cache lines of the first cache.

### Claim 13 (depends on 12)

The apparatus of claim 12, wherein the first cache comprising a set associative cache having multiple sets of cache lines, each set of cache lines having multiple ways.

### Claim 14 (depends on 13)

The apparatus of claim 13, wherein using the stored reuse information to store cache lines in a selected group of multiple groups of cache lines of the first cache comprises using the stored reuse information to store cache lines in a selected way of the multiple ways of the multiple sets of cache lines of the first cache.

### Claim 15 (depends on 14)

The apparatus of claim 14, wherein a first way of the multiple ways is selected to store cache lines of data stored within a memory page having a first value of the reuse information, and a second way of the multiple ways is selected to store cache lines of data stored within a memory page having a second value of the reuse information different from the first value.

### Claim 16 (depends on 12)

The apparatus of claim 12, wherein the first cache comprises multiple independent storage regions, each independent storage region being addressed by portions of physical addresses in the physical address space.

### Claim 17 (depends on 16)

The apparatus of claim 16, wherein using the stored reuse information to store cache lines in a selected group of multiple groups of cache lines of the first cache comprises using the stored reuse information to store cache lines in a selected storage region of the multiple independent storage regions.

### Claim 18 (depends on 12)

The apparatus of claim 12, wherein the reuse information comprises one or more bits stored within a page table entry cached in a translation lookaside buffer.

### Claim 19 (depends on 12)

The apparatus of claim 12, wherein the estimated reuse of cache lines of data stored within the memory pages comprises an estimated miss rate for blocks of data that are attempted to be retrieved from corresponding cache lines of the first cache.

### Claim 20 (depends on 12)

The apparatus of claim 12, wherein determining the reuse information includes: (1) determining first reuse information by the guest operating system, and (2) determining second reuse information by the hypervisor.

### Claim 21 (depends on 20)

The apparatus of claim 20, wherein using the stored reuse information to store cache lines in a selected group of multiple groups of cache lines of the first cache includes processing the first reuse information and the second reuse information and using a result of the processing to store cache lines in a selected group of multiple groups of cache lines of the first cache.

### Claim 22 (depends on 12)

The apparatus of claim 12, wherein the first cache comprises a last level cache.