Shared cache protocol for parallel search and replacement

Patent metadata

Field	Value
Publication number	US-10002076-B2
Application number	US-201514868477-A
Country	US
Kind code	B2
Filing date	Sep 29, 2015
Priority date	Sep 29, 2015
Publication date	Jun 19, 2018
Grant date	Jun 19, 2018

Abstract

A method includes generating least-recently-used location information for a shared set-associative multi-access cache and next-to least-recently-used location information for the shared set-associative multi-access cache. The method includes concurrently accessing a shared set-associative multi-access cache in response to a first memory request from a first memory requestor and a second memory request from a second memory requestor based on the least-recently-used location information and the next-to least-recently-used location information. The method may include updating the least-recently-used location information and the next-to least-recently-used location information in response to concurrent access to the shared set-associative multi-access cache according to the first memory request and the second memory request. The method may include independently handling the first and second memory accesses concurrently in response to first and second set fields being different and cooperatively handling the first and second memory access concurrently in response to first and second set fields identifying a target set.

First claim

What is claimed is:

1. A method comprising:
generating least-recently-used location information for a shared set-associative multi-access cache and next-to least-recently-used location information for the shared set-associative multi-access cache; and
concurrently accessing a shared set-associative multi-access cache in response to a first memory request from a first memory requestor and a second memory request from second memory requestor, the concurrently accessing being based on the least-recently-used location information and the next-to least-recently-used location information, wherein the concurrently accessing further comprises
comparing a first set field of a first address of the first memory access to a second set field of a second address of the second memory access,
independently handling the first memory access concurrently with the second memory access in response to the first set field being different from the second set field, and
cooperatively handling the first memory access concurrently with the second memory access in response to the first set field and the second set field identifying a target set.

2. The method, as recited in claim 1 , further comprising:
updating the least-recently-used location information and the next-to least-recently-used location information in response to concurrent access to the shared set-associative multi-access cache according to the first memory request and the second memory request.

3. The method, as recited in claim 1 , wherein the independently handling comprises:
accessing contents of the shared set-associative multi-access cache by the first memory requestor via a first bus based on first least-recently-used location information for a first set; and
accessing contents of the shared set-associative multi-access cache by the second memory requestor via a second bus based on second least-recently-used location information for a second set; and
updating the first least-recently-used location information and first next-to least-recently-used location information for the first set and updating the second least-recently-used location information and second next-to least-recently-used location information for the second set.

4. The method, as recited in claim 1 , wherein the cooperatively handling comprises:
comparing a first tag field of the first address to a second tag field of the second address;
in response to the first tag field being different from the second tag field:
concurrently accessing a first cache element of the target set and a second cache element of the target set; and
updating the least-recently-used location information for the target set and the next-to least-recently-used location information for the target set in response to concurrently accessing the first cache element and the second cache element.

5. The method, as recited in claim 4 , wherein the concurrently accessing the first cache element of the target set and a second cache element of the target set comprises:
in response to the first tag field resulting in a first cache hit and the second tag field resulting in a second cache hit:
accessing contents of a first location of the target set associated with the first cache hit; and
accessing contents of a second location of the target set associated with the second cache hit.

6. The method, as recited in claim 4 , wherein the concurrently accessing the first cache element of the target set and a second cache element of the target set comprises:
in response to a first tag field resulting in a first cache miss and a second tag field resulting in a second cache miss:
replacing contents of a least-recently-used location of the target set with information associated with the first memory request; and
replacing contents of a next-to least-recently-used location of the target set with information associated with the second memory request.

7. The method, as recited in claim 4 , wherein the concurrently accessing the first cache element of the target set and a second cache element of the target set comprises:
in response to a first tag field resulting in a first cache hit and a second tag field resulting in a first cache miss:
accessing contents of a location of the target set associated with the first cache hit; and
replacing contents of a least-recently-used location of the target set in response to the first cache miss.

8. The method, as recited in claim 1 , wherein the cooperatively handling comprises:
comparing a first tag field of the first address to a second tag field of the second address;
in response to the first tag field and the second tag field being the same and identifying a target location of the first set:
accessing the target location according to the first and second memory requests; and
in response to the first tag field and the second tag field resulting in a cache miss:
replacing contents of a least-recently-used location of the target set in response to accessing the target location; and
updating the least-recently-used location information for the target set and the next-to least-recently-used location information for the target set in response to replacing contents of the least-recently-used location.

9. The method, as recited in claim 1 , wherein the cooperatively handling comprises:
comparing a first tag field of the first address to a second tag field of the second address;
in response to the first tag field and the second tag field being the same and identifying a target location of the first set:
accessing the target location according to the first and second memory requests; and
in response to the first tag field and the second tag field resulting in a cache hit updating the least-recently-used location information for the target set and the next-to least-recently-used location information for the target set in response to the accessing the target location.

10. The method, as recited in claim 1 , wherein a determination of the least-recently-used location information and the next-to least-recently-used location information excludes any locked locations of the set-associative multi-access cache.

Assignees

• Freescale Semiconductor Inc
• Nxp Usa Inc

Inventors

• Mccarthy Daniel M

Classifications

• G06F12/123

  with age lists, e.g. queue, most recently used [MRU] list or least recently used [LRU] list · CPC title

• G06F12/128

  adapted to multidimensional cache systems, e.g. set-associative, multicache, multiset or multilevel · CPC title

• G06F12/0844 Primary

  Multiple simultaneous or quasi-simultaneous cache accessing · CPC title

• G06F12/0855

  Overlapped cache accessing, e.g. pipeline (G06F12/0846 takes precedence) · CPC title

• G06F12/0815 Primary

  Cache consistency protocols · CPC title