# US 6,732,236 B2 · Cache retry request queue

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

- Number: US 6,732,236 B2
- Document ID: US6732236B2
- Status: Granted
- Kind: B2
- Application number: 09/740,658
- Filed: 2000-12-18
- Published: 2002-06-20
- Granted: 2004-05-04
- Earliest claimed: 2000-12-18
- Assignees: Redback Networks Inc.
- Inventors: John G. Favor
- Web page: https://patentgrep.com/patent/US6732236B2

## CPC

- G06F 12/0857: {by multiple requestors}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

In accordance with one aspect of the present invention, an access request associated with a cache miss to a single cache line having a pending cache fill can be handled in a non-blocking manner by storing the cache miss in a retry queue while the cache fill is pending. The retry queue then detects the return of the cache fill and inserts the access request associated with the cache miss onto the cache pipeline for processing.

## Claims

### Claim 1

A method for handling a cache miss to a single cache line having a pending cache fill in a non-blocking manner, comprising the steps of:
storing an access request associated with the cache miss in a retry queue until the pending cache fill returns to the cache;
detecting the return of the cache fill to the cache;
determining if the access request is eligible for retry; and
processing an access request if it is determined to be eligible for retry.

### Claim 2 (depends on 1)

The method of claim 1, wherein the retry queue comprises an entry.

### Claim 3 (depends on 2)

The method of claim 2, wherein the entry comprises an address tag field, a valid bit field, and a retry bit field.

### Claim 4 (depends on 3)

The method of claim 3, wherein the storing step further comprises the steps of:
receiving the access request associated with the cache miss in the retry queue from an address lookup module;
storing an address tag associated with the access request in the address tag field of the entry;
initializing the valid bit field of the entry to valid; and
initializing the retry bit of the entry to ineligible.

### Claim 5 (depends on 4)

The method of claim 4, wherin the determining step further comprises the steps of:
receiving an address tag associated with the cache fill in the retry queue from the address lookup module;
comparing the cache fill address tag against the address tags associated with each cache miss located in the retry queue; and
changing the retry bit of each access request address tag that matches the cache fill address tag from ineligible to eligible.

### Claim 6 (depends on 1)

The method of claim 1, wherein the access request associated with the cache miss is initially stored in a tail end of the retry queue, and further wherein the access request is shifted toward a head of the retry queue as other access requests associated with other cache misses are removed from the retry queue.

### Claim 7

A method for handling a cache miss to a single cache line having a pending cache fill in a non-blocking manner, comprising the steps of:
receiving the access request associated with the cache miss in the retry queue from an address lookup module;
storing an address tag associated with the access request in the address tag field of the entry;
initializing the valid bit field of the entry to valid;
initializing the retry bit of the entry to ineligible;
detecting the return of the cache fill to the cache;
determining if the access request is eligible for retry; and
processing the access request if it is determined to be eligible for retry.

### Claim 8 (depends on 7)

The method of claim 7, wherein the retry queue comprises an entry.

### Claim 9 (depends on 8)

The method of claim 8, wherein the entry comprises an address tag field, a valid bit field, and a retry bit field.

### Claim 10 (depends on 7)

The method of claim 7, wherein the access request associated with the cache miss is initially stored in a tail end of the retry queue, and further wherein the access request is shifted toward a head of the retry queue as other access requests associated with other misses are removed from the retry queue.

### Claim 11 (depends on 7)

The method of claim 7, wherin the determining step further comprises the steps of:
receiving an address tag associated with the cache fill in the retry queue from the address lookup module;
comparing the cache fill address tag against the address tags associated with each cache miss located in the retry queue; and
changing the retry bit of each access request address tag that matches the cache fill address tag from ineligible to eligible.

### Claim 12

An apparatus for handling a cache miss to a single cache line having a pending cache fill in a non-blocking manner, comprising:
an entry configured to store an access request associated with the cache miss in a retry queue until the pending cache fill returns to the cache; and
a control logic module configured to detect the return of the cache fill to the cache and process the access request after detecting the return of the cache line for the cache.

### Claim 13 (depends on 12)

The apparatus of claim 12, wherein the entry further comprises an address tag field, a valid bit field, and a retry bit field.

### Claim 14 (depends on 12)

The apparatus of claim 12, wherein the access request associated with the cache miss is initially stored in a tail end of the retry queue, and further wherein the access request is shifted toward a head of the retry queue as other access requests associated with other cache misses are removed from the retry queue.

### Claim 15 (depends on 12)

The apparatus of claim 12, wherein the control logic module is configured to:
receive the access request associated with the cache miss from an address lookup module;
store an address tag associated with the access request in the address tag field of the entry;
initialize the valid bit field of the entry to valid; and
initialize the retry bit of the entry to ineligible.

### Claim 16 (depends on 12)

The apparatus of claim 12, wherein the control logic module further configured to:
receive an address tag associated with the cache fill in the retry queue from the address lookup module;
compare the cache fill address tag against the address tags associated with each cache miss located in the retry queue; and
change the retry bit of each access request address tag that matches the cache fill address tag from ineligible to eligible.

### Claim 17

An apparatus for handling a cache miss to a single cache line having a pending cache fill in a non-blocking manner, comprising the steps of:
means for storing an access request associated with the cache miss in a retry queue until the pending cache fill returns to the cache;
means for detecting the return of the cache fill to the cache;
means for determining if the access request is eligible for retry; and
means for processing the access request if it is determined to be eligible for retry.

### Claim 18 (depends on 17)

The apparatus of claim 17, wherein the retry queue comprises an entry.

### Claim 19 (depends on 18)

The apparatus of claim 18, wherein the entry comprises an address tag field, a valid bit field, and a retry bit field.

### Claim 20 (depends on 19)

The apparatus of claim 19, wherein the means for storing further comprises:
means for receiving the access request associated with the cache miss in the retry queue from an address lookup module;
means for storing an address tag associated with the access request in the address tag field of the entry;
means for initializing the valid bit field of the entry to valid; and
means for initializing the retry bit of the entry to ineligible.

### Claim 21 (depends on 20)

The apparatus of claim 20, wherin the means for determining further comprises:
means for receiving an address tag associated with the cache fill in the retry queue from the address lookup module;
means for comparing the cache fill address tag against the address tags associated with each cache miss located in the retry queue; and
means for changing the retry bit of each access request address tag that matches the cache fill address tag from ineligible to eligible.

### Claim 22 (depends on 17)

The apparatus of claim 17, wherein the access request associated with the cache miss is initially stored in a tail end of the retry queue, and further wherein the access request is shifted toward a head of the retry queue as other access requests associated with other cache misses are removed from the retry queue.
