Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
2001-07-18
2004-02-24
Elmore, Reba I. (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C711S144000, C711S159000
Reexamination Certificate
active
06697918
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention is related to caches and, more particularly, to evicting blocks of data from caches.
2. Description of the Related Art
Generally, caches are used to reduce the effective latency of memory accesses. A cache is a memory into which copies of data from an underlying memory are stored. Generally, a block of contiguous data is allocated/deallocated from the cache as a unit (i.e. a cache block is the smallest unit of allocation/deallocation of storage space in the cache). The term cache line is also frequently used as a synonym for cache block. The cache typically has a latency less than that of the underlying memory, and thus accesses for which the corresponding data is stored in the cache may occur with a lower latency than accesses to the underlying memory. Thus, the average latency of memory accesses may be less than the latency of the underlying memory.
Caches attempt to store the most recently accessed blocks and/or the most frequently accessed blocks. In some cases, prefetch strategies are employed to speculatively load blocks which may be accessed in the future into the cache. However, since caches are usually significantly smaller in capacity than the underlying memory, data for an access may not be stored in the cache when the access occurs (referred to as a cache miss, or simply a miss). When a cache miss occurs, the missing cache block is generally loaded into the cache. Since the cache has a finite capacity, in many cases a valid cache block in the cache is replaced by the newly loaded cache block. If the cache block being replaced (referred to as the evicted cache block or the victim cache block) is modified with respect to the copy stored in memory, the evicted cache block is read from the memory before replacement by the newly loaded cache block. The evicted cache block may then be written back to memory.
Unfortunately, the hardware for reading the evicted cache block from the cache for writing back to memory may impact the amount of time for performing accesses. Typically, such hardware must be integrated into the hardware for performing cache accesses. Since cache accesses are often the critical timing path in a semiconductor device, increasing the path length may negatively impact the overall operating frequency of the device. Alternatively, the critical path may have to be pipelined, which may reduce the performance of the device.
SUMMARY OF THE INVENTION
A cache is configured to select a cache block for eviction in response to detecting a cache miss. The cache transmits the address of the cache block as a write transaction on an interface to the cache, and the cache captures the address from the interface and reads the cache block from the cache memory in response to the address. The read may occur similar to other reads in the cache, detecting a hit in the cache (in the cache storage location from which the cache block is being evicted). In this manner, the eviction may be provided for without additional hardware (e.g. an added port, or another path to the same port) for supporting the eviction. Thus, the timing of the path may not be impacted to perform evictions. The path through the cache for accesses from other agents and for evictions may be the same.
Using the initiating of the write transaction to write the evicted cache block to memory to read the evicted cache block from the cache may be viewed as effectively creating a break in the requests to the cache for reading the evicted cache block from the cache. The write transaction is initiated before the corresponding data is available for transfer, and the use of the bus bandwidth to initiate the transaction provides an open access time into the cache for reading the evicted cache block. Viewed in another way, the access to the cache to read the evicted cache block may be effectively free, reusing the hardware already used to perform cache accesses for transactions initiated by other agents.
Broadly speaking, an apparatus is contemplated comprising an interface and cache coupled thereto. The cache is configured to transmit an address of a cache block to be evicted from the cache on the interface. The cache includes a memory configured to store a plurality of cache blocks including the cache block, and the memory is coupled to receive the address from the interface. The memory is configured to access the cache block in response to the address for transmission on the interface.
Additionally, a cache is contemplated comprising a memory configured to store a plurality of cache blocks and a control circuit. The control circuit is configured to transmit an address of a cache block to be evicted from the cache on an interface to which the cache is couplable. The memory is coupled to receive the address from the interface and is configured to access the cache block in response to the address for transmission on the interface.
Moreover, a method is contemplated. A cache transmits an address of a cache block to be evicted from the cache on an interface. In response to the transmitting, the cache block is read from a data memory of the cache for transmission on the interface.
REFERENCES:
patent: 5860117 (1999-01-01), Cherabuddi
patent: 5883826 (1999-03-01), Wendell et al.
patent: 6038645 (2000-03-01), Nanda et al.
patent: 6047357 (2000-04-01), Bannon et al.
patent: 6240487 (2001-05-01), Liu et al.
patent: 6393529 (2002-05-01), Keller
patent: 2002/0147889 (2002-10-01), Kruckemyer et al.
patent: 2003/0023814 (2003-01-01), Barroso et al.
SiByte, “Target Applications,” http://sibyte.com/mercurian/applications.htm, Jan. 15, 2001, 2 pages.
SiByte, “SiByte Technology,” http://sibyte.com/mercurian/technology.htm, Jan. 15, 2001, 3 pages.
SiByte, “The Mercurian Processor,” http://sibyte.com/mercurian, Jan. 15, 2001, 2 pages.
SiByte, “Fact Sheet,” SB-1 CPU, Oct. 2000, rev. 0.1, 1 page.
SiByte, “Fact Sheet,” SB-1250, Oct. 2000, rev. 0.2, 10 pages.
Stepanian, SiByte, SiByte SB-1 MIPS64 CPU Core, Embedded Processor Forum 2000, June 13, 2000, 15 pages.
Jim Keller, “The Mercurian Processor: A High Performance, Power-Efficient CMP for Networking,” Oct. 10, 2000, 22 pages.
Tom R. Halfhill, “SiByte Reveals 64-Bit Core For NPUs; Independent MIPS64 Design Combines Low Power, High Performances,” Microdesign Resources, Jun. 2000, Microprocessor Report, 4 pages.
Patterson and Hennessy, “Computer Architecture A Quantitative Approach,” Second Edition, Morgan Kaufmann Publishers, Inc., 1990/1996, pp. 375-378.
Broadcom Corporation
Elmore Reba I.
Merkel Lawrence J.
LandOfFree
Cache configured to read evicted cache block responsive to... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Cache configured to read evicted cache block responsive to..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cache configured to read evicted cache block responsive to... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3340192