Trace cache
![](https://upload.wikimedia.org/wikipedia/commons/thumb/d/d3/TraceCache.png/456px-TraceCache.png)
Incomputer architecture,atrace cacheorexecution trace cacheis a specializedinstruction cachewhich stores the dynamic stream ofinstructionsknown astrace.It helps in increasing the instruction fetchbandwidthand decreasing power consumption (in the case ofIntelPentium 4) by storing traces of instructions that have already been fetched and decoded.[1]Atrace processor[2]is an architecture designed around the trace cache and processes the instructions at trace level granularity. The formal mathematical theory of traces is described bytrace monoids.
Background
[edit]The earliest academic publication of trace cache was "Trace Cache: a Low Latency Approach to High Bandwidth Instruction Fetching".[1]This widely acknowledged paper was presented by Eric Rotenberg, Steve Bennett, and Jim Smith at 1996International Symposium on Microarchitecture(MICRO) conference. An earlier publication is US patent 5381533,[3]by Alex Peleg and Uri Weiser of Intel, "Dynamic flow instruction cache memory organized around trace segments independent of virtual address line", a continuation of an application filed in 1992, later abandoned.
Necessity
[edit]Widersuperscalar processorsdemand multiple instructions to be fetched in a single cycle for higher performance. Instructions to be fetched are not always in contiguous memory locations (basic blocks) because ofbranchandjumpinstructions. So processors need additional logic and hardware support to fetch and align such instructions from non-contiguous basic blocks. If multiple branches are predicted asnot-taken,then processors can fetch instructions from multiple contiguous basic blocks in a single cycle. However, if any of the branches is predicted astaken,then processor should fetch instructions from the taken path in that same cycle. This limits the fetch capability of a processor.
![](https://upload.wikimedia.org/wikipedia/commons/thumb/8/84/BasicBlocks.png/240px-BasicBlocks.png)
Consider these four basic blocks (A
,B
,C
,D
) as shown in the figure that correspond to a simpleif-elseloop. These blocks will be storedcontiguouslyasABCD
in the memory. If the branchD
is predictednot-taken,the fetch unit can fetch the basic blocksA
,B
,C
which are placed contiguously. However, ifD
is predictedtaken,the fetch unit has to fetchA
,B
,D
which are non-contiguously placed. Hence, fetching these blocks which are non contiguously placed, in a single cycle will be very difficult. So, in situations like these, the trace cache comes in aid to the processor.
Once fetched, the trace cache stores the instructions in their dynamic sequence. When these instructions are encountered again, the trace cache allows the instruction fetch unit of a processor to fetch several basic blocks from it without having to worry about branches in the execution flow. Instructions will be stored in the trace cache either after they have been decoded, or as they are retired. However, instruction sequence is speculative if they are stored just after decode stage.
Trace structure
[edit]A trace, also called a dynamic instruction sequence, is an entry in the trace cache. It can be characterized bymaximum number of instructionsandmaximum basic blocks.Traces can start at any dynamic instruction. Multiple traces can have same starting instruction i.e., same startingprogram counter(PC) and instructions from different basic blocks as per the branch outcomes. For the figure above, ABC and ABD are valid traces. They both start at the same PC (address of A) and have different basic blocks as per D's prediction.
Traces usually terminate when one of the following occurs:
- Trace got filled with allowablemaximum number of instructions
- Trace has allowable maximum basic blocks
- Return instructions
- Indirect branches
- System calls
Trace control information
[edit]A single trace will have following information:
- Starting PC - PC of the first instruction in trace
- Branch flag - (maximum basic blocks -1) branch predictions
- Branch mask - number of branches in the trace and whether trace ends in a branch or not
- Trace fall through - Next PC if last instruction isnot-takenbranch or not a branch
- Trace target - address of last branch's taken target
Trace cache design
[edit]Following are the factors that need to be considered while designing a trace cache.
- Trace selection policies -maximum number of instructionsandmaximum basic blocks in a trace
- Associativity- number of ways a cache can have
- Cache indexing method - concatenation orXORwith PC bits
- Path associativity - traces with same starting PC but with different basic blocks can be mapped to different sets
- Trace cache fill choices -
- After decode stage (speculative)
- After retire stage
A trace cache is not on the critical path of instruction fetch[4]
Hit/miss logic
[edit]Trace lines are stored in the trace cache based on the PC of the first instruction in the trace and a set of branch predictions. This allows for storing different trace paths that start on the same address, each representing different branch outcomes. This method of tagging helps to provide path associativity to the trace cache. Other method can include having only starting PC as tag in trace cache. In the instruction fetch stage of apipeline,the current PC along with a set of branch predictions is checked in the trace cache for ahit.If there is a hit, a trace line is supplied to fetch unit which does not have to go to a regular cache or to memory for these instructions. The trace cache continues to feed the fetch unit until the trace line ends or until there is amispredictionin the pipeline. If there is a miss, a new trace starts to be built.
The Pentium 4's execution trace cache storesmicro-operationsresulting from decodingx86 instructions,providing also the functionality of a micro-operation cache. Having this, the next time an instruction is needed, it does not have to be decoded into micro-ops again.[5]
Disadvantages
[edit]The disadvantages of trace cache are:
- Redundant instruction storage between trace cache and instruction cache and within trace cache itself.[6]
- Power inefficiency and hardware complexity[4]
Execution trace cache
[edit]Within the L1 cache of theNetBurstCPUs, Intel incorporated its execution trace cache.[7][8]It stores decodedmicro-operations,so that when executing a new instruction, instead of fetching and decoding the instruction again, the CPU directly accesses the decoded micro-ops from the trace cache, thereby saving considerable time. Moreover, the micro-ops are cached in their predicted path of execution, which means that when instructions are fetched by the CPU from the cache, they are already present in the correct order of execution. Intel later introduced a similar but simpler concept withSandy Bridgecalledmicro-operation cache(UOP cache).
See also
[edit]References
[edit]- ^abRotenberg, Eric; Bennett, Steve; Smith, James E.; Rotenberg, Eric (1996-01-01)."Trace Cache: a Low Latency Approach to High Bandwidth Instruction Fetching".In Proceedings of the 29th International Symposium on Microarchitecture:24–34.
- ^Eric Rotenberg, Quinn Jacobson, Yiannakis Sazeides, and James E. Smith.Trace Processors.Proceedings of the30th IEEE/ACM International Symposium on Microarchitecture (MICRO-30),pp. 138-148, December 1997
- ^Peleg, Alexander; Weiser, Uri (Jan 10, 1995),Dynamic flow instruction cache memory organized around trace segments independent of virtual address line,retrieved2016-10-18
- ^abLeon Gu; Dipti Motiani (October 2003)."Trace Cache"(PDF). Retrieved2013-10-06.
- ^Agner Fog(2014-02-19)."The microarchitecture of Intel, AMD and VIA CPUs: An optimization guide for assembly programmers and compiler makers"(PDF).agner.org.Retrieved 2014-03-21.
- ^Co, Michele."Trace Cache".www.cs.virginia.edu.Retrieved2016-10-21.[dead link]
- ^Carmean, Doug (Spring 2002)."The Intel® Pentium® 4 Processor"(PDF).Archived fromthe original(PDF)on 19 April 2018.[unreliable source?]
- ^"X-bit labs - Print version".www.xbitlabs.com.Archived fromthe originalon 6 March 2016.Retrieved12 January2022.