# US 2022/0027160 A1 · Out of order memory request tracking structure and technique

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

- Number: US 2022/0027160 A1
- Document ID: US20220027160A1
- Status: Published application
- Kind: A1
- Application number: 16/940,363
- Filed: 2020-07-27
- Published: 2022-01-27
- Earliest claimed: 2020-07-27
- Assignees: NVIDIA Corporation
- Applicants: NVIDIA Corporation
- Inventors: Michael A. FETTERMAN; Mark GEBHART; Shirish GADRE; Mitchell HAYENGA; Steven HEINRICH; Ramesh JANDHYALA; Raghavan MADHAVAN; Omkar PARANJAPE; James ROBERTSON; Jeff SCHOTTMILLER
- Web page: https://patentgrep.com/patent/US20220027160A1

## CPC

- G06F 9/3836: {Instruction issuing, e.g. dynamic instruction scheduling or out of order instruction execution}
- G06F 12/0895: of parts of caches, e.g. directory or tag array
- G06F 5/065: {Partitioned buffers, e.g. allowing multiple independent queues, bidirectional FIFO's}
- G06F 9/30047: {Prefetch instructions; cache control instructions}
- G06F 9/3867: {using instruction pipelines}
- G06F 9/546: {Message passing systems or structures, e.g. queues}
- G06F 12/084: with a shared cache
- G06F 12/0842: for multiprocessing or multitasking
- G06F 12/0846: Cache with multiple tag or data arrays being simultaneously accessible
- G06F 12/0873: Mapping of cache memory to specific storage devices or parts thereof
- G06F 2212/1021: Hit rate improvement
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

In a streaming cache, multiple, dynamically sized tracking queues are employed. Request tracking information is distributed among the plural tracking queues to selectively enable out-of-order memory request returns. A dynamically controlled policy assigns pending requests to tracking queues, providing for example in-order memory returns in some contexts and/or for some traffic and out of order memory returns in other contexts and/or for other traffic.

## Claims

### Claim 1

A memory request tracking circuit for use with a streaming cache memory, the memory request tracking circuit comprising:
a tag check configured to detect cache misses;
plural tracking queues; and
a queue mapper coupled to the tag check and the plural tracking queues, the queue mapper being configured to distribute request tracking information to the plural tracking queues to enable in-order and out-of-order memory request returns.

### Claim 2 (depends on 1)

The memory request tracking circuit of claim 1 wherein the queue mapper is programmable to preserve in-order memory request return handling for a first type of memory requests and to enable out-of-order memory request return handling for a second type of memory requests different from the first type of memory requests.

### Claim 3 (depends on 1)

The memory request tracking circuit of claim 1 wherein the first and second types of memory requests are selected from the group consisting of loads from local or global memory; texture memory/storage; and acceleration data structure storage.

### Claim 4 (depends on 1)

The memory request tracking circuit of claim 1 wherein the plural tracking queues comprise first through N tracking queues, and the queue mapper allocates a first tracking queue to a particular warp and distributes certain types of memory requests evenly across second through N tracking queues.

### Claim 5 (depends on 1)

The memory request tracking circuit of claim 1 wherein the plural tracking queues each comprise a first-in-first-out storage.

### Claim 6 (depends on 1)

The memory request tracking circuit of claim 1 further includes a pipelined checker picker that selects tracking queue outputs for application to a check in response to cache miss fill indications, the pipelined checker picker being dynamically configured to perform the selection.

### Claim 7 (depends on 6)

The memory request tracking circuit of claim 6 wherein the check comprises tracking structures that indicate memory system return data needed by the head of each tracking queue and are configured to track when the memory system has returned all sectors needed by the head of each tracking queue.

### Claim 8 (depends on 7)

The memory request tracking circuit of claim 7 wherein the checks are configured to provide plural sector valid bits for each of plural tag banks.

### Claim 9 (depends on 1)

The memory request tracking circuit of claim 1 further including a first commit picker configured to process a first traffic type.

### Claim 10 (depends on 9)

The memory request tracking circuit of claim 9 further including a second commit picker configured to process a second traffic type different from the first traffic type.

### Claim 11 (depends on 1)

The memory request tracking circuit of claim 1 configured to provide a first mode that provides in-order allocation and deallocation of tracking resources and a second mode that provides out-of-order allocation and deallocation of tracking resources.

### Claim 12 (depends on 1)

The memory request tracking circuit of claim 1 further including a state packet queue configured to hold state packets and further configured to restrict out-of-order state packet processing so state packets remain in program order relative to memory access requests that reference the state packets.

### Claim 13 (depends on 1)

The memory request tracking circuit of claim 1 further including an indicator encoder that encodes an indicator of a last packet in a commit group.

### Claim 14 (depends on 13)

The memory request tracking circuit of claim 13 further including a commit picker configured to selecting tracked memory request entries for moving to a commit queue in response to the indicator indicating that all memory request entries in a commit group have been serviced and are in the cache.

### Claim 15 (depends on 1)

The memory request tracking circuit of claim 1 further including:
first and second traffic paths, wherein the first path bypasses the plural tracking queues and the second path is through at least one of the plural tracking queues; and
an interlock circuit that guarantees the first path is always faster than the second path.

### Claim 16 (depends on 15)

The memory request tracking circuit of claim 15 wherein the interlock circuit includes a comparator configured to compare the age of traffic in the fast path with the age of traffic in the slow path.

### Claim 17 (depends on 1)

The memory request tracking circuit of claim 1 further including reference counters that count a number of inflight references to a memory slot, reference counter outputs and/or operations being configured to adapt to out of order processing.

### Claim 18

A streaming cache comprising:
a tag pipeline including a coalescer, a tag memory and a tag processor, the tag pipeline detecting cache misses;
a commit FIFO;
an evict FIFO; and
an out-of-order memory request tracking circuit comprising plural tracking queues.

### Claim 19 (depends on 18)

The streaming cache of claim 18 further including a queue mapper coupled to the tag pipeline and the plural tracking queues, the queue mapper being configured to distribute request tracking information to the plural tracking queues to selectively enable out-of-order memory request returns.

### Claim 20

A memory request tracking method for use with a streaming cache memory, the memory request tracking method comprising:
detecting cache misses;
providing plural tracking queues; and
distributing request tracking information to the plural tracking queues to support either in-order and out-of-order memory request returns.

### Claim 21 (depends on 20)

The memory request tracking method of claim 20 further including programming a queue mapper to preserve in-order memory request return handling for a first type of memory requests and to enable out-of-order memory request return handling for a second type of memory requests different from the first type of memory requests.

### Claim 22 (depends on 20)

The memory request tracking circuit of claim 20 wherein the first and second types of memory requests are each selected from the group consisting of local or global memory load requests, texture memory requests, surface memory requests, and acceleration data structure memory requests.

### Claim 23 (depends on 20)

The memory request tracking circuit of claim 20 wherein the plural tracking queues comprise first through N tracking queues, and distributing includes allocating a first tracking queue to a particular warp and distributing certain types of memory requests evenly across second through N tracking queues.

### Claim 24 (depends on 20)

The memory request tracking circuit of claim 20 wherein the plural tracking queues each comprise a first-in-first-out storage.

### Claim 25 (depends on 20)

The memory request tracking circuit of claim 20 further including selecting tracking queue outputs for application to a check in response to cache miss fill indications.

### Claim 26 (depends on 25)

The memory request tracking circuit of claim 25 further comprising using tracking structures to indicate memory system return data needed by the head of each tracking queue and tracking when the memory system has returned all sectors needed by the head of each tracking queue.

### Claim 27 (depends on 26)

The memory request tracking circuit of claim 26 further including providing plural sector valid bits for each of plural tag banks.

### Claim 28 (depends on 20)

The memory request tracking circuit of claim 20 further including configuring a first commit picker to process a first traffic type.

### Claim 29 (depends on 28)

The memory request tracking circuit of claim 28 further including configuring a second commit picker process a second traffic type different from the first traffic type.

### Claim 30 (depends on 20)

The memory request tracking circuit of claim 20 further including providing both in-order and out-of-order allocation and deallocation of tracking resources.

### Claim 31 (depends on 20)

The memory request tracking circuit of claim 20 further including configuring a state packet queue to hold state packets, and restricting out-of-order state packet processing so state packets remain in program order relative to memory access requests that reference the state packets.

### Claim 32 (depends on 20)

The memory request tracking circuit of claim 20 further including encoding an indicator of a last packet in a commit group.

### Claim 33 (depends on 32)

The memory request tracking circuit of claim 32 further including selecting tracked memory request entries for moving to a commit queue in response to the indicator indicating that all memory request entries in a commit group have been serviced and are in the cache.

### Claim 34 (depends on 20)

The memory request tracking circuit of claim 20 further including:
using a first traffic path to bypass the plural tracking queues;
using a second traffic path through at least one of the plural tracking queues; and
guaranteeing the first path is always faster than the second path.

### Claim 35 (depends on 34)

The memory request tracking circuit of claim 34 further including comparing the age of traffic in the fast path with the age of traffic in the slow path.

### Claim 36 (depends on 20)

The memory request tracking circuit of claim 20 further including counting a number of inflight references to a memory slot, reference counter outputs and/or operations being configured to adapt to out of order processing.
