Trace victim cache

Details Trace victim cache Trace victim cache

1997-12-16

2001-04-10

Yoo, Do (Department: 2187)

Electrical computers and digital processing systems: memory

Storage accessing and control

Hierarchical memories

C711S003000, C712S230000

Reexamination Certificate

active

06216206

ABSTRACT:

BACKGROUND OF THE INVENTION
1. FIELD OF THE INVENTION
The present invention relates to the field of computer systems. More specifically, the present invention relates to the art of caching decoded micro-operations with trace segments and providing a victim cache for replaced cache lines.
2. DESCRIPTION OF RELATED ART
Historically, cached instructions are stored and organized in an instruction cache in accordance with the instructions' memory addresses. Each cache line stores a number of instructions that are spatially adjacent each other in main memory. This historic approach to caching instructions has at least one disadvantage in that it typically requires multiple cache lines to be accessed when execution of a program necessitates branching from the middle of a cache line or branching into the middle of a cache line.
In a cache organized by instruction address, a full line of adjacent instructions is typically fetched from the main memory and loaded into the cache. If the cache becomes fill, an existing line in the cache memory is replaced to accommodate a new line of instructions required by the microprocessor. The replacement of a particular line does not impact any other lines in the cache.
An alternative approach to organizing cached instructions is known, whereby cached instructions are organized by instruction trace segments. Each cache line stores an instruction trace segment comprising one or more basic blocks of instructions that are predicted to be sequentially executed. For example, in an embodiment where each cache line comprises two basic blocks of instructions, the second basic block of instructions includes instructions to be executed if the branch instruction located at the end of the first basic block is taken. Assuming the branch is predicted taken, the second basic block is included in the same trace segment. A particular trace segment may extend over a number of cache lines. Each trace segment is retrieved based on the memory address of the first instruction in the trace segment.
A cache organized by trace segments is typically operated in one of two modes, an execution mode, and a build mode. Instructions are read from the cache memory during the execution mode and trace segments are built into the cache memory in the build mode. If an instruction required by the microprocessor is not present in the cache memory, a cache miss is generated and the cache memory switches to build mode. A switch to build mode results in a performance penalty due to the latency generated as new instructions must be fetched, decoded, and supplied to the microprocessor.
In a trace cache arrangement, a line replacement is more costly than in a traditional cache arrangement. For example, consider a trace segment occupying six cache lines. The fourth line of the trace segment is replaced. Because the trace segment can only be accessed through the address of the first instruction in the first cache line (i.e. the head of the trace segment), only lines one, two, and three, will be accessible after the replacement of the fourth line. Lines, five and six will be unavailable because they were cut off from the trace segment when the fourth line was replaced.
As a result, when the processor accesses the trace segment to retrieve instructions, a cache miss will occur after the third line. The processor will then switch to build mode to begin a new trace segment including the replaced fourth line and cut off fifth and sixth lines. As a result, the instructions contained in the fifth and sixth lines will be cached twice.
Thus, it is desirable to have a new approach for caching instructions that reduces the performance penalty caused by cache line replacements and reduces the degree of code redundancy present in the cache.
SUMMARY OF THE INVENTION
An aspect of the invention is seen in a cache memory including a data array and a trace victim cache. The data array is adapted to store a plurality of trace segments. Each trace segment includes at least one trace segment member. The trace victim cache is adapted to store plurality of entries. Each entry includes a replaced trace segment member selected for replacement from one of the plurality of trace segments.
Another aspect of the invention is seen in a method for accessing cached instructions. The cached instructions are stored in a data array and organized in trace segments. The trace segment has a plurality of trace segment members. The method includes retrieving a first trace segment member of a first trace segment; identifying an expected location within the data array of at least one subsequent trace segment member of the first trace segment; determining if the subsequent trace segment member is stored in the data array at the expected location; and determining if the subsequent trace segment member is stored in a trace victim cache if the subsequent trace segment member is not stored in the data array at the expected location.


REFERENCES:
patent: 5381533 (1995-01-01), Peleg et al.
patent: 5526510 (1996-06-01), Akkary et al.
patent: 5577227 (1996-11-01), Finnell et al.
patent: 5649154 (1997-07-01), Kumar et al.
patent: 5822755 (1998-10-01), Shippy
patent: 6018786 (2000-01-01), Krick et al.

Affiliated with

Also associated with

Rating

Trace victim cache does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Trace victim cache, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Trace victim cache will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2518769