# US 2016/0253259 A1 · Mixed cache management

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

- Number: US 2016/0253259 A1
- Document ID: US20160253259A1
- Status: Published application
- Kind: A1
- Application number: 15/032,636
- Filed: 2013-10-29
- Published: 2016-09-01
- Earliest claimed: 2013-10-29
- Assignees: Hua Zhong University of Science Technology
- Applicants: Hua Zhong University of Science Technology
- Inventors: Hai JIN; Xuanhua SHI; Song WU; Xin YU
- Web page: https://patentgrep.com/patent/US20160253259A1

## CPC

- G06F 12/084: with a shared cache
- G06F 12/0811: with multilevel cache hierarchies
- G06F 12/0891: using clearing, invalidating or resetting means
- G06F 12/1009: using page tables, e.g. page table structures
- G06F 12/1054: {the data cache being concurrently physically addressed}
- G06F 12/123: with age lists, e.g. queue, most recently used [MRU] list or least recently used [LRU] list
- G06F 2212/604: Details relating to cache allocation
- G06F 2212/653: Page colouring
- Y02D 10/00: Energy efficient computing, e.g. low power processors, power management or thermal management
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- Y02D: CLIMATE CHANGE MITIGATION TECHNOLOGIES IN INFORMATION AND COMMUNICATION TECHNOLOGIES [ICT], I.E. INFORMATION AND COMMUNICATION TECHNOLOGIES AIMING AT THE REDUCTION OF THEIR OWN ENERGY USE

## Abstract

A mixed cache is indexed to main memory and page coloring is applied to map main memory to virtual memory. A nursery array and a mature array are indexed to virtual memory. An access to a virtual page from the mixed cache is recorded by determining an index and a tag of an array address based on a virtual address, following the index to corresponding rows in the nursery and the mature arrays, and determining if the tag in the array address matches any tag in the rows. When there is a match to a tag in the rows, an access count in a virtual page entry corresponding to the matched tags is incremented. When there is no match, a virtual page entry in the row in the nursery array is written with the tag in the array address and an access count in the entry is incremented.

## Claims

### Claim 1

A method for a computing system to migrate virtual pages between cache regions of different memory types in a mixed cache, the mixed cache being indexed to a main memory comprising physical pages so each physical page in the main memory is mapped to one group of contiguous cache sets in the mixed cache, a nursery array and a mature array being indexed to a virtual memory comprising virtual pages so each virtual page is mapped to one row in the nursery array and one row in the mature array, the method comprising:
applying page coloring to map the virtual memory to the main memory so that physical pages mapped to different groups of contiguous cache sets are assigned to adjacent virtual pages; and
recording access to a particular virtual page of the virtual memory from the mixed cache, wherein recording comprises:
receiving a virtual address for the particular virtual page;
from the received virtual address, determining an index and a tag of an array address to the nursery array and the mature array;
following the determined index of the array address to a row in the nursery array and a row in the mature array, the row in the nursery array and the row in the mature array comprising virtual page entries;
determining whether or not the determined tag of the array address matches any tag in the virtual page entries of the row in the nursery array and the row in the mature array;
in response to a non-match between the determined tag of the array address and any tag in the virtual page entries of the row in the nursery array and the row in the mature array, writing a virtual page entry of the row in the nursery array with the determined tag of the array address and an access count; and
in response to a match between the determined tag of the array address and the tag in in the virtual page entry, incrementing the access count in the virtual page entry corresponding to the matched tags.

### Claim 2 (depends on 1)

The method of claim 1, wherein writing the virtual page entry of the row in the nursery array with the determined tag of the array address and the access count comprises, in response to the row in the nursery array being full, selecting the virtual page entry based on a replacement policy and writing over data in the virtual page entry.

### Claim 3 (depends on 1)

The method of claim 1, wherein the mixed cache is a last level cache, every nth access from the mixed cache is recorded, and n is greater than or equal to 1.

### Claim 4 (depends on 1)

The method of claim 1, further comprising:
moving the virtual page entry from the nursery array to the mature array, wherein moving comprises:
determining whether or not an access pattern of the particular virtual page is greater than a first threshold based on the access count in the virtual page entry in the nursery array; and
in response to the access pattern of the particular virtual page being greater than the first threshold, moving the virtual page entry from the row in the nursery array to the row in the mature array.

### Claim 5 (depends on 4)

The method of claim 4, wherein moving the virtual page entry from the row in the nursery array to the row in the mature array comprises, in response to the row in the mature array being full, selecting another virtual page entry from the row in the mature array based on a replacement policy and swapping the virtual page entry from the row in the nursery array with the selected virtual page entry from the row in the mature array.

### Claim 6 (depends on 4)

The method of claim 4, further comprising:
migrating the particular virtual page from being mapped to a first cached region in the mixed cache to being mapped to a second cache region in the mixed cache, wherein migrating comprises:
determining whether or not the access pattern of the particular virtual page is greater than a second threshold based on the access count in the virtual page entry from the row in the mature array; and
in response to the access pattern of the virtual page being greater than the second threshold, remapping the particular virtual page from a first physical page of the main memory that is mapped to the first cache region to a second physical page of the main memory that is mapped to the second cache region.

### Claim 7 (depends on 6)

The method of claim 6, wherein remapping the particular virtual page from the first physical page mapped to the first cache region to the second physical page mapped to the second cache region comprises:
selecting a free physical page or an allocated physical page of the main memory having a different hybrid bit in its physical address so that underlying cache sets are located in the second cache region; and
migrating data from first cache sets corresponding to the first physical page to second cache sets corresponding to the second physical page.

### Claim 8 (depends on 7)

The method of claim 7, wherein:
selecting the free physical page comprises selecting the free physical page from a linked list of free physical pages from linked lists of free physical pages of different colors based on a round-robin scheduling; and
selecting the allocated physical page is based on a replacement policy.

### Claim 9 (depends on 6)

The method of claim 6, further comprising:
moving the virtual page entry from the mature array to the nursery array, comprising:
determining whether or not the access pattern of the particular virtual page is less than a third threshold based on the access count in the virtual page entry in the mature array; and
in response to the access pattern of the virtual page being less than the third threshold, moving the virtual page entry from the row in the mature array to the row in the nursery array.

### Claim 10 (depends on 9)

The method of claim 9, wherein moving the virtual page entry from the row in the mature array to the row in the nursery array comprises, in response to the row in the nursery array being full, selecting another virtual page entry from the row in the nursery array based on a replacement policy and swapping the virtual page entry from the row in the mature array with the selected virtual page entry from the row in the nursery array.

### Claim 11 (depends on 9)

The method of claim 9, further comprising:
migrating the particular virtual page from being mapped to the second cached region to being mapped to the first cache region, comprising:
determining whether or not the access pattern of the particular virtual page is less than a fourth threshold based on the access count in the virtual page entry in the nursery array; and
in response to the access pattern of the virtual page being less than the fourth threshold, remapping the particular virtual page from the second physical page mapped to the second cache region to a third physical page mapped to the first cache region.

### Claim 12 (depends on 11)

The method of claim 11, wherein remapping the particular virtual page from the second physical page mapped to the second cache region to the third physical page mapped to the first cache region comprises:
selecting a free physical page or an allocated physical page of the main memory having a different hybrid bit in its physical address so that underlying cache sets are located in the first cache region; and
migrating data from second cache sets corresponding to the second physical page to third cache sets corresponding to the third physical page.

### Claim 13 (depends on 12)

The method of claim 12, wherein:
selecting the free physical page comprises selecting the free physical page from a link list of free physical pages from linked lists of free physical pages of different colors based on a round-robin scheduling; and
selecting the allocated physical page is based on a replacement policy.

### Claim 14 (depends on 10)

The method of claim 10, wherein the access count comprises a read count, a write count, or a read-write ratio.

### Claim 15

A computing system, comprising:
a processor;
a mixed cache coupled to the processor and comprising a first cache region and a second cache region of different memory types, the mixed cache being indexed to a main memory comprising physical pages so that one group of contiguous cache sets in the mixed cache is mapped to a physical page of the main memory;
a nursery array and a mature array indexed to a virtual memory comprising virtual pages so that each virtual page of the virtual memory is mapped to one row in the nursery array and one row in the mature array;
wherein the processor is configured to control operation of:
a page partition module to implement page coloring to map the virtual memory to the main memory so that physical pages mapped to different groups of contiguous cache sets are assigned to adjacent virtual pages;
a sampler to record access to a particular virtual page from the mixed cache, the sampler being configured to:
receive a virtual address for the particular virtual address access;
from the received virtual address, determine an index and a tag of an array address to the nursery array and the mature array;
follow the determined index of the array address to a row in the nursery array and a row in the mature array, the row in the nursery array and the row in the mature array comprising virtual page entries;
determine whether or not the determined tag of the array address matches any tag in the virtual page entries of the row in the nursery array and the row in the mature array;
in response to a non-match between the determined tag of the array address and any tag in the virtual page entries of the row in the nursery array and the row in the mature array, write a virtual page entry of the row in the nursery array with the determined tag of the array address and an access count; and
in response to a match between the determined tag of the array address and the tag in the virtual page entry, increment the access count in the virtual page entry corresponding to the matched tags.

### Claim 16 (depends on 15)

The computing system of claim 15, wherein the mixed cache is the last level cache, the sampler is configured to record every nth access from the mixed cache, and n is greater than or equal to 1.

### Claim 17 (depends on 15)

The computing system of claim 15, wherein the sampler is configured to:
move the virtual page entry from the nursery array to the mature array, wherein to move the virtual page entry, the sampler is configured to:
determine whether or not an access pattern of the particular virtual page is greater than a first threshold based on the access count in the virtual page entry in the nursery array; and
in response to the access pattern of the virtual page being greater than the first threshold, move the virtual page entry from the row in the nursery array to the row in the mature array.

### Claim 18 (depends on 17)

The computing system of claim 17, wherein the processor is configured to control operation of:
a page migration module to migrate the particular virtual page from being mapped to a first cached region in the mixed cache to being mapped to a second cache region in the mixed cache, the page migration module being configured to:
determine whether or not the access pattern of the particular virtual page is greater than a second threshold based on the access count in the virtual page entry in the mature array; and
in response to the access pattern of the virtual page being greater than the second threshold, remap the particular virtual page from a first physical page of the main memory that is mapped to the first cache region to a second physical page of the main memory that is mapped to the second cache region.

### Claim 19 (depends on 18)

The computing system of claim 18, wherein to remap the virtual page from a first physical page mapped to the first cache region to a second physical page mapped to the second cache region, the sampler is configured to:
select a free physical page or an allocated physical page of the main memory having a different hybrid bit in its physical address so that underlying cache sets are located in the second cache region; and
migrate data from first cache sets corresponding to the first physical page to second cache sets corresponding to the second physical page.

### Claim 20 (depends on 18)

The computing system of claim 18, wherein the sampler is configured to:
move the virtual page entry from the mature array to the nursery array, wherein to move the virtual page entry, the sampler is configured to:
determine whether or not the access pattern of the particular virtual page is less than a third threshold based on the access count in the virtual page entry in the mature array; and
in response to the access pattern of the virtual page being less than the third threshold, move the virtual page entry from the row in the mature array to the row in the nursery array.

### Claim 21 (depends on 20)

The computing system of claim 20, wherein the page migration module is configured to:
migrate the particular virtual page from being mapped to the second cached region to being mapped to the first cache region, wherein to migrate the virtual page, the page migration module is configured to:
determine whether or not the access pattern of the virtual page is less than a fourth threshold based on the access count in the virtual page entry in the nursery array; and
in response to the access pattern of the virtual page being less than the fourth threshold, remap the virtual page from the second physical page mapped to the second cache region to a third physical page mapped to the first cache region.

### Claim 22 (depends on 21)

The computing system of claim 21, wherein the processor is configured to control operation of:
one or more modules to receive a performance target and convert the performance target into:
the first, the second, the third, and the fourth thresholds, each of the first, the second, the third, and the fourth thresholds comprising a read count, a write count, or a read-write ratio; and
frequencies for storing accesses to virtual pages in the nursery and the mature arrays, moving virtual page entries between the nursery and the mature arrays, and migrating virtual pages between the first and the second cache regions.

### Claim 23

A non-transitory, computer-readable storage medium encoded with instructions executable by a processor to:
apply page coloring to map a virtual memory comprising virtual pages to a main memory comprising physical pages so that physical pages mapped to different groups of contiguous cache sets in a mixed cache are assigned to adjacent virtual pages, the mixed cache being indexed to the main memory so each physical page in the main memory is mapped to one group of contiguous cache sets in the mixed cache; and
record access to a particular virtual page of the virtual memory from the mixed cache, comprising to:
receive a virtual address for the particular virtual page;
from the received virtual address, determine an index and a tag of an array address to a nursery array and a mature array, the nursery array and the mature array being indexed to the virtual memory so each virtual page is mapped to one row in the nursery array and one row in the mature array;
follow the determined index of the array address to a row in the nursery array and a row in the mature array, the row in the nursery array and the row in the mature array comprising virtual page entries;
determine whether or not the determined tag of the array address matches any tag in the virtual page entries of the row in the nursery array and the row in the mature array;
in response to a non-match between the determined tag of the array address and any tag in the virtual page entries of the row in the nursery array and the row in the mature array, write a virtual page entry of the row in the nursery array with the determined tag of the array address and an access count; and
in response to a match between the determined tag of the array address and the tag in in the virtual page entry, incrementing the access count in the virtual page entry corresponding to the matched tags.

### Claim 24 (depends on 23)

The non-transitory, computer-readable storage medium of claim 23, wherein the mixed cache is a last level cache, every nth access from the mixed cache is recorded, and n is greater than or equal to 1.

### Claim 25 (depends on 23)

The non-transitory, computer-readable storage medium of claim 23, wherein the instructions further include instructions executable by the processor to:
move the virtual page entry from the nursery array to the mature array, comprising to:
determine whether or not an access pattern of the particular virtual page is greater than a first threshold based on the access count in the virtual page entry in the nursery array; and
in response to the access pattern of the particular virtual page being greater than the first threshold, move the virtual page entry from the row in the nursery array to the row in the mature array.

### Claim 26 (depends on 25)

The non-transitory, computer-readable storage medium of claim 25, wherein the instructions further include instructions executable by the processor to:
migrate the particular virtual page from being mapped to a first cached region in the mixed cache to being mapped to a second cache region in the mixed cache, comprising to:
determine whether or not the access pattern of the particular virtual page is greater than a second threshold based on the access count in the virtual page entry from the row in the mature array; and
in response to the access pattern of the virtual page being greater than the second threshold, remap the particular virtual page from a first physical page of the main memory that is mapped to the first cache region to a second physical page of the main memory that is mapped to the second cache region.

### Claim 27 (depends on 26)

The non-transitory, computer-readable storage medium of claim 26, wherein the instructions further include instructions executable by the processor to:
move the virtual page entry from the mature array to the nursery array, comprising to:
determine whether or not the access pattern of the particular virtual page is less than a third threshold based on the access count in the virtual page entry in the mature array; and
in response to the access pattern of the virtual page being less than the third threshold, move the virtual page entry from the row in the mature array to the row in the nursery array.

### Claim 28 (depends on 27)

The non-transitory, computer-readable storage medium of claim 27, wherein the instructions further include instructions executable by the processor to:
migrate the particular virtual page from being mapped to the second cached region to being mapped to the first cache region, comprising to:
determine whether or not the access pattern of the particular virtual page is less than a fourth threshold based on the access count in the virtual page entry in the nursery array; and
in response to the access pattern of the virtual page being less than the fourth threshold, remap the particular virtual page from the second physical page mapped to the second cache region to a third physical page mapped to the first cache region.
