Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
1997-12-22
2001-10-23
Yoo, Do Hyun (Department: 2185)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C711S123000, C711S003000, C712S001000, C712S220000, C710S052000, C710S053000
Reexamination Certificate
active
06308241
ABSTRACT:
FIELD OF THE INVENTION
The invention relates to an electronic circuit comprising a CPU with a cache. The invention also relates to a method of supplying an information item, such as data or an instruction, to an execution unit of a CPU.
BACKGROUND ART
A CPU typically has one or more cache memories arranged between the data and instruction inputs of its execution unit on the one hand and the port for connection to main memory. The caches compensate for the difference in speed between the processing in the CPU and the fetching of data and instructions from main memory. The successful operation of the cache relies on the locality principle: program references to memory tend to be clustered in time and in logical space. Temporal clustering relates to the tendency to reference the same address more than once within a specific period of time. Spatial clustering relates to the tendency to fetch data or instructions from logically consecutive memory addresses. The data and instructions in the main memory are mapped into the cache in blocks of logically coherent addresses. Below, the term “information item” is used to refer to either data or an instruction within this context.
A cache read miss occurs when the CPU requests an information item that is not present in its cache. The cache has thereupon to retrieve the appropriate block from the main memory or the secondary cache and store it. During this cache refill, the execution unit is stalled. Various techniques are in use to minimize the number of clock cycles that the execution unit has to idle as a result of a cache refill.
For example, European patent application 0 543 487 A1 discusses the early-restart technique. As soon as the requested item arrives from main memory it is sent to the execution unit without waiting for completion of the writing of the entire block to the cache. A refinement of this early-restart is the out-of-order fetch. The out-of-order fetch lets the main memory skip all information items located at addresses logically preceding the requested item in the relevant block. The requested item is sent directly to the execution unit upon retrieval while the remainder of the block is being retrieved looping around to fetch the items previously skipped.
European patent application 0 543 487 A1 also discusses an alternative technique that involves the following steps. If the CPU fetches data during a data cache fill and the requested data being fetched is part of the memory block being currently filled, the data is retrieved and returned to the execution unit simultaneously with its writing into the cache, if the data has not been written into the cache. If the data has been written into the cache, the data is retrieved and returned to the execution unit at the next read cycle.
Also see, e.g., “MIPS RISC Architecture”, Gerry Kane and Joe Heinrich, Prentice Hall, 1992, notably Chapter 5, page 5-5. In the implementations of MIPS processor architectures, e.g., the R2000 and R3000, a typical sequence of events occurring after a cache miss are the following. On a cache miss, the processor reads one word from memory and stalls while the designated blocks in the cache are refilled. After the refill has been completed, missed information items are retrieved from the cache and are supplied to the processor's execution unit to resume processing. For general background information on the MIPS architecture, also see, e.g., “Structured Computer Organization”, A. S. Tanenbaum, Prentice Hall International Editions, third edition, 1990, especially pp. 472-487.
OBJECT OF THE INVENTION
The advantages of early restart are limited if the execution unit processes the requested item faster than the cache can complete the refill. In the latter case, the execution has to idle after processing the item that was received directly until the cache has been refilled.
The alternative technique in the prior art reference discussed above addresses the problem of reducing the number of idle cycles of the execution unit while the cache is being refilled. This prior art reference does not address the problem of reducing the number of idle cycles when the refill has been, or nearly has been, completed. It is an object of the invention to increase performance of the processor by reducing the number of idle cycles substantially near completion of the cache refill.
SUMMARY OF THE INVENTION
To this end, the invention provides an electronic circuit comprising a CPU, an input for receipt of an information item, and a cache between the input and an execution unit of the CPU. The execution unit is operative to process the item. The circuit further comprises a buffer between the input and the execution unit, and a controller connected to the buffer. The controller controls the storing of the information item in the buffer and the supply of the item to the execution unit substantially near completion of a cache refill.
The inventor proposes to use a temporary buffer in order to prevent the CPU from idling at least during the step wherein an item is being retrieved from the cache upon completion of the refill. The item is provided from the buffer instead of from the cache near completion of the refill. In this way, at least one clock cycle is saved per cache miss, since the buffer register is not address-controlled like a cache.
The circuit of the invention can use the buffer in combination with a main memory capable of early-restart and out-of-order fetch as mentioned above. The early restart/out-of-order fetch allows reducing the number of CPU idling cycles preceding the cache refill, and the buffer register in the invention reduces the number of CPU idling cycles after the cache has been refilled or has nearly completed refilling.
REFERENCES:
patent: 5179679 (1993-01-01), Shoemaker
patent: 5353426 (1994-10-01), Patel et al.
patent: 5386526 (1995-01-01), Mitra et al.
patent: 5671444 (1997-09-01), Akkary et al.
patent: 5752263 (1998-05-01), Kranich
patent: 5765190 (1998-06-01), Circello et al.
patent: 5854914 (1998-12-01), Bodas et al.
patent: 0543487A1 (1993-05-01), None
“MIPS RISC Architecture”, Gerry Kane and Joe Heinrich, Prentice Hall, 1992, chapter 5.
“Structured Computer Organization”, A.S. Tanenbaum, Prentice Hall International Editions, thi 1990, pp.472-487.
“MIPS RISC Architecture”, Gerry Kane and Joe Heinrich, Prentice Hall, 1992, chapter 1.
Eltman Brad E.
Simovich Slobodan
McLean Kimberly
U.S. Philips Corporation
Verdonk Peter
Yoo Do Hyun
LandOfFree
On-chip cache file register for minimizing CPU idle cycles... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with On-chip cache file register for minimizing CPU idle cycles..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On-chip cache file register for minimizing CPU idle cycles... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2606874