User:Rmathiv/sandbox

Trace Cache

Working of a trace Cache

Trace Cache (also known as execution trace cache) is a very specialized cache which stores the dynamic stream of instructions know as trace. It helps in increasing the instruction fetch bandwidth and decreasing power consumption (in the case of Intel Pentium 4 ) by storing traces of instructions that have already been fetched and decoded. Trace Processor is an architecture designed around the Trace Cache and processes the instructions at trace level granularity.

Background

The earliest academic publication of trace cache was "Trace Cache: a Low Latency Approach to High Bandwidth Instruction Fetching". This widely acknowledged paper was presented by Eric Rotenberg, Steve Bennett, and Jim Smith at 1996 MICRO conference. An earlier publication is (US patent 5381533) , by Alex Peleg and Uri Weiser of Intel Corp., "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

Wider superscalar processors demand 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 of branch and jump instructions. So processors need additional logic and hardware support to fetch and align such instructions from non-contiguous basic blocks. If multiple branches are predicted as not-taken, then processors can fetch instructions from multiple contiguous basic blocks in a single cycle. However, if any of the branches is predicted as taken, then processor should fetch instructions from the taken path in that same cycle. This limits the fetch capability of a processor.

Basic Blocks of a simple if-else loop

Consider these four basic blocks (A, B, C, D) as shown in the figure that correspond to a simple if-else loop. These blocks will be stored contiguously as ABCD in the memory. If the branch D is predicted not-taken, the fetch unit can fetch the basic blocks A,B,C which are placed contiguously. However, if D is predicted taken, the fetch unit has to fetch A,B,D which are non-contiguously placed. Hence, fetching these blocks which are non contiguously places, in a single cycle will be very difficult. So, in situations like these trace cache comes in aid to the processor.

Once fetched, trace cache stores the instructions in their dynamic sequence. This allows the instruction fetch unit of a processor to fetch several basic blocks from the trace cache, when they have encountered again, without having to worry about branches in the execution flow. Instructions will be stored in 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

Trace, also called as dynamic instruction sequence, is an entry in the trace cache. It can be characterized by maximum no of instructions and maximum basic blocks. Traces can start at any dynamic instruction. Multiple traces can have same starting instruction i.e. same starting 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 terminates when one of the following occurs:

1. Trace got filled with allowable maximum no of instructions
2. Trace has allowable maximum basic blocks
3. Return Instructions
4. Indirect branches
5. System calls

Trace Control Information:

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 - no of branches in the trace and whether trace ends in a branch or not
• Trace Fall through - Next PC if last instruction is not-taken branch or not a branch
• Trace Target - Address of last branch's taken target

Trace Cache Design

Following are the factors that need to be considered while designing a trace cache.

• Trace Selection Policies - maximum no of instructions and maximum basic blocks in a trace

• Associativity - no of ways a cache can have
• Cache indexing Method - Concatenation or XOR with PC bits
• Path associativity - traces with same starting PC but with different basic blocks can be mapped to different sets
• Trace Cache Fill choices -
  1. After decode stage (Speculative)
  2. After retire stage

A trace cache is not on the critical path of instruction fetch

Hit/Miss Logic

Trace lines are stored in the trace cache based on the program counter 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 assosiativity to the trace cache. Other method can include having only starting PC as tag in trace cache. In the instruction fetch stage of a pipeline, the current program counter along with a set of branch predictions is checked in the trace cache for a hit. If there is a hit, a trace line is supplied to fetch 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 a misprediction in the pipeline. If there is a miss, a new trace starts to be built.

The Pentium 4's trace cache stores micro-operations resulting from decoding x86 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.

See Also

CPU cache

Instruction cycle