# US 12,117,939 B2 · Stochastic optimization of surface cacheability in parallel processing units

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

- Number: US 12,117,939 B2
- Document ID: US12117939B2
- Status: Granted
- Kind: B2
- Application number: 17/557,475
- Filed: 2021-12-21
- Published: 2023-06-22
- Granted: 2024-10-15
- Earliest claimed: 2021-12-21
- Assignees: Advanced Micro Devices, Inc.
- Applicants: Advanced Micro Devices, Inc.
- Inventors: Saurabh Sharma; Jeremy Lukacs; Hashem Hashemi; Gianpaolo Tommasi; Christopher J. Brennan
- Web page: https://patentgrep.com/patent/US12117939B2

## CPC

- G06F 12/0893: Caches characterised by their organisation or structure
- G06F 12/0895: of parts of caches, e.g. directory or tag array
- G06F 12/084: with a shared cache
- G06F 12/0888: using selective caching, e.g. bypass
- G06F 12/0897: with two or more cache hierarchy levels (with multilevel cache hierarchies G06F12/0811)
- G06F 2212/1021: Hit rate improvement
- G06F 2212/302: In image processor or graphics adapter
- G06F 2212/455: Image or video data
- G06F 2212/502: using adaptive policy
- G06F 2212/604: Details relating to cache allocation
- G06F 2212/6042: Allocation of cache space to multiple users or processors
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A processing system selectively allocates storage at a local cache of a parallel processing unit for cache lines of a repeating pattern of data that exceeds the storage capacity of the cache. The processing system identifies repeating patterns of data having cache lines that have a reuse distance that exceeds the storage capacity of the cache. A cache controller allocates storage for only a subset of cache lines of the repeating pattern of data at the cache and excludes the remainder of cache lines of the repeating pattern of data from the cache. By restricting the cache to store only a subset of cache lines of the repeating pattern of data, the cache controller increases the hit rate at the cache for the subset of cache lines.

## Claims

### Claim 1

A method comprising:
responsive to a pattern of repeating data in which a single instance of the pattern of repeating data spans a number of cache lines that exceeds a storage capacity of a cache in which the pattern of repeating data is to be stored, allocating storage for only a subset of cache lines of the single instance at the cache.

### Claim 2 (depends on 1)

The method of claim 1, further comprising:
bypassing storing a remainder of cache lines of the single instance at the cache.

### Claim 3 (depends on 2)

The method of claim 2, wherein allocating storage for only the subset comprises: selecting cache lines of the pattern of repeating data that exceed the maximum number of cache lines that the cache can store as the remainder.

### Claim 4 (depends on 1)

The method of claim 1, comprising determining that a reuse distance of a cache line of the single instance is greater than the number of cache lines that can be stored at the cache; and limiting the subset to the number of cache lines that can be stored at the cache.

### Claim 5 (depends on 4)

The method of claim 4, further comprising:
iteratively selecting cache lines of the pattern of repeating data to exclude from the cache by:
determining a hit rate for the subset of cache lines of the pattern of repeating data that are not excluded from the cache; and
selecting cache lines of the pattern of repeating data to exclude from the cache based on the hit rate.

### Claim 6 (depends on 4)

The method of claim 4, further comprising:
partitioning the cache into two or more portions; and
assigning a first portion of the cache to the pattern of repeating data; and
wherein determining that the reuse distance of a cache line of the single instance is greater than the number of cache lines that can be stored at the cache comprises determining that the reuse distance of a cache line of the single instance is greater than the number of cache lines that can be stored at the first portion of the cache.

### Claim 7 (depends on 1)

The method of claim 1, wherein the pattern of repeating data comprises a texture.

### Claim 8

A method comprising:
determining that a single instance of a pattern of repeating data spans a number of cache lines that exceed a storage capacity of a cache, the pattern of repeating data to be stored in cache lines of the cache; and
in response to the determining, allocating cache lines of the cache to only a subset of cache lines of the single instance.

### Claim 9 (depends on 8)

The method of claim 8, further comprising:
bypassing storing a remainder of cache lines of the single instance at the cache.

### Claim 10 (depends on 9)

The method of claim 9, wherein selecting the subset comprises:
selecting cache lines of the pattern of repeating data that exceed the maximum number of cache lines that the cache can store as the remainder.

### Claim 11 (depends on 8)

The method of claim 8, further comprising:
determining that a reuse distance of a cache line of the single instance is greater than a number of cache lines that can be stored at the cache; and
limiting the subset to the number of cache lines that can be stored at the cache.

### Claim 12 (depends on 11)

The method of claim 11, further comprising:
iteratively selecting cache lines of the pattern of repeating data to exclude from the cache by:
determining a hit rate for cache lines of the pattern of repeating data that are not excluded from the cache; and
selecting cache lines of the pattern of repeating data to exclude from the cache based on the hit rate.

### Claim 13 (depends on 11)

The method of claim 11, further comprising:
partitioning the cache into two or more portions; and
assigning a first portion of the cache to the pattern of repeating data;
wherein determining that the reuse distance of a cache line of the single instance is greater than the number of cache lines that can be stored at the cache comprises determining that the reuse distance of a cache line of the single instance is greater than the number of cache lines that can be stored at the first portion of the cache.

### Claim 14 (depends on 8)

The method of claim 8, wherein the pattern of repeating data comprises a texture.

### Claim 15

A device comprising:
a parallel processing unit comprising a cache in which a pattern of repeating data is to be stored; and
a cache controller to:
responsive to a single instance of the pattern of repeating data having a number of cache lines that exceeds a storage capacity of the cache, allocate storage for only a subset of cache lines of the single instance at the cache.

### Claim 16 (depends on 15)

The device of claim 15, wherein the cache controller is to:
bypass storing a remainder of cache lines of the pattern of repeating data at the cache.

### Claim 17 (depends on 16)

The device of claim 16, wherein the cache controller is to:
select cache lines of the pattern of repeating data that exceed the maximum number of cache lines that the cache can store as the remainder.

### Claim 18 (depends on 15)

The device of claim 15, wherein the cache controller is to:
determine whether a reuse distance of a cache line of the single instance is greater than the number of cache lines that can be stored at the cache; and
limit the subset to the number of cache lines that can be stored at the cache.

### Claim 19 (depends on 18)

The device of claim 18, wherein the cache controller is to:
determine a hit rate for cache lines of the pattern of repeating data that are not excluded from the cache; and
select cache lines of the pattern of repeating data to exclude from the cache based on the hit rate.

### Claim 20 (depends on 18)

The device of claim 18, wherein the cache controller is to:
partition the cache into two or more portions;
assign a first portion of the cache to the pattern of repeating data; and determine that the reuse distance of a cache line of the
single instance is greater than the number of cache lines that can be stored at the cache by determining that the reuse distance of a cache line of the single instance is greater than the number of cache lines that can be stored at the first portion of the cache.