Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Utility Patent
1999-11-22
2001-01-02
Lane, Jack A. (Department: 2751)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C711S003000, C712S230000
Utility Patent
active
06170038
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 instruction caching.
2. Background Information
Historically, cached instructions are stored and organized in an instruction cache in accordance with the instructions' spatial relationship. Typically, each cache line stores instructions that are located spatially adjacent to each other in main memory. This spatial approach to caching instructions has at least one disadvantage in that it typically requires multiple cache lines to be accessed whenever execution of a program necessitates branching out from the middle of a cache line or branching into the middle of a cache line.
In U.S. Pat. No. 5,381,533, Peleg and Weiser disclosed an alternative approach to organizing cached instructions that overcome the above discussed and other disadvantages of the spatial approach. Under Peleg and Weiser's approach, cached instructions are stored and organized in accordance with the predicted order of execution. Basic blocks of instructions that are predicted to be sequentially executed are organized into trace segments and stored in the cache lines, one trace segment per cache line. The successor basic blocks stored into a cache line to form a trace segment are the branch target basic blocks if the branch instructions located at the end of the corresponding predecessor basic blocks are predicted to be taken; otherwise the successor basic blocks are the fall through basic blocks. The successive basic blocks within a cache line are retrieved sequentially by way of the first instruction of the first basic block, upon locating the first instruction.
Because the Peleg and Weiser approach does not provide for trace segments to span multiple cache lines, address matching to locate the next cache line must be performed each time the instruction supply stored in a cache line is exhausted. As a result, the Peleg and Weiser approach has at least the disadvantage of being limiting in the amount of instructions that can be supplied to the execution units of a processor over a period of time. This limitation is especially undesirable for modern processors with very high instruction execution rates.
Melvin et al., in their article entitled Hardware Support for Large Atomic Units in Dynamically Scheduled Machines, Proceedings of the 21st Annual Workshop on Microprogramming and Microarchitecture, Nov. 30-Dec. 2, 1988, San Diego, Calif., have proposed storing and organizing cached instructions by execution atomic units. Each cache entry (presumably, a cache line) is to comprise an execution atomic unit. An execution atomic unit is a smallest group of micro-ops that the processor can issue as an indivisible unit. Micro-ops are micro-instructions employed by the processor to implement macro-instructions. A fill unit is proposed for building the execution atomic units. The fill unit is to receive the micro-ops from a pre-fetch buffer and micro-op generator. There are at least two conditions under which the building of an execution atomic unit would terminate. The first is when a change of flow control is detected, and the second is when there are no longer enough empty micro-op slots in the fill unit for the next macro-instruction.
The Melvin approach suffers from a number of disadvantages including at least the disadvantages of allowing basically only one basic block per atomic execution unit, and having to cache all decoded micro-ops of a marco-instruction. The later is especially undesirable if the macro-instruction set includes complex macro-instructions that decode into a large number of micro-ops.
Thus, it is desirable to have a new approach for storing and organizing cached instructions, including decoded micro-ops, that has the advantages of Peleg et al., and Melvin et al., but without their disadvantages.
SUMMARY OF THE INVENTION
A cache memory is constituted with a data array and control logic. The data array includes a number of data lines, and the control logic operates to store a number of trace segments of instructions in the data lines, including trace segments that span multiple data lines.
In one embodiment, each trace segment includes one or more trace segment members having one or more instructions, with each trace segment member occupying one data line, and the data lines of a multi-line trace segment being sequentially associated (logically). Retrieval of the trace segment members of a multi-line trace segment is accomplished by first locating the data line storing the first trace segment member of the trace segment, and then successively locating the remaining data lines storing the remaining trace segment members based on the data lines' logical sequential associations. In one embodiment, the instructions are micro-ops of macro-instructions.
In one embodiment, a location address is maintained for each data line storing the first trace segment member of a trace segment. The data line storing the first trace segment member of a trace segment is located by address matching an access address against the location addresses maintained. In one embodiment, the address matching is performed using a subset of the address bits, and a matching data line is validated as to whether the data line indeed contains the first trace segment member being sought. In an N ways of S sets embodiment, storing of trace segment members is further qualified with a criteria of ensuring the address matching subset of the location addresses maintained in association with the various ways of a data line set, if any, is unique.
In one embodiment, at least partial control information sequentially associating each data line of a trace segment with its predecessor as well its successor data line in a logical manner is maintained, where applicable. The successive data lines of a multi-line trace segment are located, relying at least in part on the partial sequential association control information maintained. In one N ways of S sets embodiment, for each data line of a trace segment, a way index indexing into a way of the set of the predecessor data line, as well as a way index indexing into a way of the set of the successor data line is maintained, when applicable. Additionally, a predetermined set relationship between the successive data lines of a multi-line trace segment is maintained.
In one embodiment, a number of data line terminating conditions are employed to terminate caching of instructions of a trace segment in one data line, and continue caching of the instructions of the trace segment in another data line. In one embodiment, a number of trace segment terminating conditions are also employed to terminate caching of instructions as one trace segment, and continue caching of instructions as a new trace segment.
In one embodiment, the control logic includes two state machines operating the cache memory in an execution mode and a trace segment build mode. Each mode includes a number of operating states. Trace segments are built under the trace segment build mode, and their members are subsequently located and retrieved under the execution mode.
REFERENCES:
patent: 5381533 (1995-01-01), Peleg et al.
Melvin et al., “Hardware Support for Large Atomic Units in Dynamically Scheduled Machines,” Computer Science Division, University of California Berkeley, 1988 IEEE, pp. 60-63.
Rotenberg et al., “Trace Cache: a Low latency Approach to High Bandwidth Instruction Fetching,” dated Apr. 11, 1996, 48 pages.
PCT International Search Report, International application No. PCT/US99/00959, Jan. 15, 1999, 5 pages.
Hinton Glenn J.
Krick Robert F.
Lee Chan W.
Sager David J.
Upton Michael D.
Blakely , Sokoloff, Taylor & Zafman LLP
Intel Corporation
Lane Jack A.
LandOfFree
Trace based instruction caching 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 based instruction caching, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Trace based instruction caching will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2464777