Advanced computer architectures notes

ACAIndex

• Cap 2 - Recall on Basic Architecture, Multithreading
• Cap 3 - Branch Hazards and Static Branch Prediction Techniques
• Cap 4 – Dynamic Branch Prediction
• Cap 5 - ILP, Complex Pipelining and introduction to scheduling
• Cap 6 - Static Scheduling and very long instruction words (VLIW)
• Cap 7 – Dynamic scheduling, Scoreboard
• Cap 8 - Dynamic Scheduling, Tomasulo
• Cap 9 – Exception handling
• Cap 10 – Hardware-based speculation
• Cap 11 – Explicit Register Renaming
• Cap 12 - ILP Limits and Superscalar Architecture
• Cap 13 - Parallel architectures: SIMD and intro to MIMD
• Cap 14 - GPU
• Cap 15 – Review Mem hierarchy, MIMD machines and Cache Coherency

1L2 - Recall on basic architecture, multithreading

Recall about our reference architecture: MIPS.

RISC (Reduced Instruction Set Computer) are architectures based on the concept of executing only simple instructions in a reduced basic cycle to optimize the performances of CISC CPUs.

Load/Store Architecture use dedicated instructions to load data from memory to registers and store data from registers to memory.

Pipeline architecture are performance optimization technique based on the overlapping of the execution of multiple instructions derived from a sequential execution flow (Instruction-level parallelism ILP).

Data path: storage, FU, that interconnect sufficient parts to perform the desired functions.

Controller: state machine used to orchestrate operation on the data path. 2

Figure 2: MIPS Data path

Figure 3: Pipeline Execution of MIPS instructions

Figure 4: implementation of MIPS pipeline 3

Figure 5: visualizing pipeline

Hazards

• Structural Hazards: attempt to use the same resource from different instructions simultaneously (es: single memory for instructions and data).
• Data Hazards: attempt to use a result before it is ready (es: instruction depending on a result of a previous instruction still in the pipeline).
• Control Hazards: attempt to make a decision on the next instruction to execute before the condition is evaluated (es: conditional branch execution).

Figure 6: Types of DATA Hazards 4

Classes of parallelism

• Data-level parallelism (DLP): arises because there are many data items that can be operated on at the same time.
• Task-level parallelism: arises because tasks of work are created that can operate independently and largely in parallel.
• Instruction-level parallelism (ILP): exploits data-level parallelism at modest levels with compiler help using ideas like pipelining and at medium levels using ideas like speculative execution.
• Thread-level parallelism (TLP): exploits either data-level parallelism or task-level parallelism in a tightly coupled hardware model that allows for interaction among parallel threads.
• Request-level parallelism (RLP): exploits parallelism among largely decoupled tasks specified by the programmer or the operating system.

Explicit Parallel programming implies structuring the applications into concurrent and communicating tasks. OS offer support for different types of tasks, like processes and threads. The OS implement multitasking differently based on the characteristics of the processor: single core, single core with multithreading support or multicore.

A Thread is an instruction stream with own PC (program counter) and data. It may be a process part of a parallel program or an independent. Each thread has all the state necessary to allow it to execute. 5

Figure 7: multiplicity of processes/threads

Multithreading

Fine-grained multithreading: it switches from one thread to the other at each instruction. The CPU must be able to change thread at every clock cycle: it’s necessary to duplicate the hardware resources. It can hide short and long stalls. It slows down the execution of individual threads, since thread ready to execute will be delayed by instructions from other threads.

Coarse grained multithreading: switching from one thread to another occurs only when there are long stalls. In normal conditions the single thread is not slowed down, but for long stalls does not reduce the throughput loss.

SMT: the system is dynamically adapted to the environment, allowing that the instructions of a single thread use all the functional units. 6

Flynn Taxonomy

• SISD: single instruction single data, for uniprocessor systems.
• MISD: multiple instruction single data, not used.
• SIMD: single instruction multiple data, for simple programming models.
• MIMD: multiple instruction multiple data, very scalable and fault tolerant. 7

Figure 9: AI accelerators 8

L3 - Branch Hazards and static branch prediction techniques

Conditional Branch Instruction: the branch is taken only if the condition is satisfied. The Branch Target Address (BTA) is stored in the Program Counter (PC) instead of the address of the next instruction in the sequential instruction stream.

In the 5-stage MIPS pipeline an instruction like beq $x, $y, offset is managed in the following way:

1. The instruction is fetched and the PC increments.
2. The register reads $x and $y from the Register File.
3. The ALU compares the register $x and $y to derive the branch outcome (taken or not).
4. The result of the registers’ comparison is used to derive the value to be stored in the PC (PC+4 or PC+4+offset).

The branch outcome and the branch target address are ready at the end of stage 3 (the EX stage); conditional branches are solved when the PC is updated at the end of the memory access (ME) stage (stage 4). 9

The performances of conditional branches are:

To feed the pipeline we need to fetch a new instruction at each clock cycle, but the branch decision is taken at the MEM stage, this is called Control Hazard or Conditional Branch Hazard.

When a branch changes the PC to its target address, it’s a taken branch, otherwise it’s a branch not taken. 10

As we can see in the two examples, without forwarding we stall for three clock cycles, with forwarding we stall for two clock cycles.

If the branch is not taken the two or three stall cycles are not justified and we have a throughput reduction. We can flush instructions only if the branch is not taken.

One solution can be the early evaluation of the PC: in MIPS processors the comparison between the registers, the computation of the branch target address and the update of the PC is done during the ID stage. So each branch costs only one stall to fetch the correct instruction flow. 11

Also with the branch decision made during the ID stage there is one clock cycle of stall that yields to a performance loss of 10/30%. In order to solve this problem we can use different methods:

• Static branch prediction techniques: the actions for a branch are fixed for each branch during the entire execution. The actions are fixed at compile time.
• Dynamic Branch Prediction Techniques: the decision causing the branch prediction can change during the program execution.

Static branch prediction techniques are used in processors where the expectation is that the branch behavior is highly predictable at compile time or to assist the dynamic predictors. They are: 12

• Branch Always Not Taken (Predicted-Not-Taken)
• Branch Always Taken (Predicted-Taken)
• Backward Taken Forward Not Taken (BTFNT)
• Profile-Driven Prediction
• Delayed Branch

Branch Always Not Taken: we assume the branch will not take. If the condition stage will result not satisfied the prediction is correct � and we can preserve performance. If not we need to flush the next instruction already fetched and we restart the execution by fetching the instruction at the branch target address, so we have one-cycle penalty.

Branch Always Taken: we assume that every branch is taken. This makes sense for pipelines where the branch target is known before the branch outcome. In MIPS pipeline we don’t know it, so there is no advantage in this approach for this pipeline.

Backward Taken Forward Not Taken (BTFNT): backward-going branches are predicted as taken (like branches at the end of loops) and forward-going branches as not taken.

Profile-Driven Prediction: the branch prediction is based on profiling information collected from earlier runs. This method can use compiler hints.

Delayed Branch Techniques: the compiler statically schedules an independent instruction in the branch delay slot of 1 cycle, that is executed whether or not the branch is taken. If the branch is untaken the execution continues with the instruction after the branch, if it is taken the execution continues at the branch target.

The branch delay slot can be scheduled in three ways:

• From Before: the branch delay slot is scheduled with an independent instruction from before the branch. 13
• From Target: the branch delay slot is scheduled from the target of the branch. Usually the target instruction will need to be copied. This strategy is preferred when the branch is taken with high probability, such as loop branches (backward branches).
• From Fall-Through: the branch delay slot is scheduled from the not-taken fall-through path. This strategy is used when the branch is not taken with high probability, such as forward branches.

L4 - Dynamic Branch Prediction

The basic idea is to use the past branch behavior to predict the future. The prediction will depend on the behavior of the branch at 14 run time and will change if the branch changes its behavior during execution. It’s based on two mechanisms:

• Branch Outcome Predictor: to predict the direction of a branch (taken or not).
• Branch Target Predictor: to predict the branch target address in case of taken branch.

These modules are used in the Instruction Fetch Unit: if the branch is not taken we increment the PC, if it’s taken the BTP gives the target address.

Branch target buffer (or predictor): is a cache storing the predicted branch target address for the next instruction after a branch.

Branch History Table (or branch prediction buffer): is a table containing 1 bit for each entry that says whether the branch was 15 recently taken or not. The table is indexed by the lower portion of the address of the branch instruction. We assume that the hint is correct, but if it’s not we invert the prediction bit.

In the graph 1 means taken and 0 not taken.

Mispredictions occur when the prediction is incorrect for that branch or the same index has been referenced by two different branches and the previous history refers to the other branch (if we increase the number of rows of the BHT, or we add an hash function we solve that problem).

If we consider a 2-bit branch history table the finite state machine changes in the following way: 16

In the case of 11 and 10 we take the branch, for 00 and 01 we don’t.

The generalization of this is the n-bit branch history table, so the counter can take values between 0 and 2^n – 1, we consider the branch taken when the counter is greater than or equal ½ the max value, that is 2^n – 1. The counter is as always incremented on a taken branch or decremented on a untaken branch.

Performances of 2-bit BHT is very similar to the ones of n-bit BHT and go from 82% to 99%.

Correlating Branch Predictor (2-level predictors): the idea of this method is that the behavior of recent branches are correlated, so also the recent behavior of other branches can influence the prediction of the current branch.

A (1,1) correlating predictor is a 1-bit predictor with 1-bit of correlation, so the behavior of the last branch is used to choose among a pair of 1-bit branch predictors. 17

The (m,n) correlating branch predictors records the last m branches m to choose from 2 BHTs, that are all n-bit predictors. The branch prediction buffer uses the global history of the most recent m branches.

In the (2,2) correlating predictor we have 64 total entries Each BHT has 16 entries of 2-bit each. The 4-bit branch address is used to choose four entries a row and the 2-bit global history is used to choose one of four entries in a row.

The (2,2) predictor outperforms the simply 2-bit predictor (is a (0,2) predictor) also if this last has an unlimited number of entries.

Two-level adaptive branch predictors: the first level history is recorder in one or more k-bit shift register called Branch History Register (BHR), that records the outcomes of the k most recent branches; the second level history is recorder in one or more tables called Pattern History Table (PHT)of 2-bit saturating counters.

The BHR is used to index the PHT, that is used to select which 2-bit counter to use. Then the prediction is made as before.

The BHT is a local predictor that is indexed by the low-order bits of the PC (branch address).

The GAs are local and global predictors (2-level), where the PHT is indexed by the content of BHR (global history).

The GShare is a local XOR global information that is indexed by the exclusive OR of the low-order bits of PC and the content of BHR. 18

L5 - ILP, complex pipelining and introduction to scheduling

When we have Instruction Level Parallelism (ILP) we want to overlap the execution of unrelated instructions. This is possible if there are no structural hazards, no RAW, WAR or WAW stalls and no control stalls. 19

As we know hazards limit performances: for structural we need more HW resources, for Data we need forwarding or compiler scheduling and for control we need early evaluation, delayed branch or predictors. Increasing the length of pipe increases impact of hazards. Pipelining helps instruction bandwidth, but not latency.

The complex pipeline is used because we want high performances with multiple function and memory units, we have memory systems with variable access time and exceptions. 20

The issue stage manages the separate registers file and pick up the proper functional unit. It also handles conflicts at the write-back stage due to the latencies of the different functional units.

To solve the oversubscription of the write ports and the exception implementation we can delay the write back so that all the operations have the same latency, but that means that an integer operation may have the same duration of a floating division (es: 30 clock cycles instead of 1), and that’s not good.

A solution, but not good enough is forwarding. Another is instruction scheduling, so using an out-of-order scheduling of independent instructions:

We can do better, using hardware solution, instead of the compile-time solution just seen.

Before the issue stage can dispatch an instruction he has to check if: the functional is available, the input data are available (RAW), is safe to write the destination (WAR, WAW), there is a structural conflict at the WB stage.

Now also name dependencies become a problem and can cause race condition.

We have to make also some assumptions:

• All functional units are pipelined; 21
• Register are read in the issue stage (they are written in the first half of the clock cycle and read in the second);
• No forwarding;
• ALU operations take 1 clock cycle and memory operations and FP ALU operations 2 clock cycles;
• WB has a single write port;
• Instruction are fetched, decoded and issued in order;
• Instructions enter in the issue stage if they don’t cause WAR or WAW hazards;
• Only one instruction can be issued at a time and if multiple are available only the oldest will go first.

To get higher performances we need more parallelism, so we need to order instructions (scheduling) in order to reach the highest parallelism possible.

If two instructions are dependent we can’t execute them in parallel.

There are 3 types of dependences: name, data and control.

Name dependences: they occur when 2 instructions use the same register or memory location (called name). They can be of 2 types:

• Anti dependence: when an instruction writes on a memory location or register where another one is reading. We must preserve the order to ensure that we read the right value;
• Output dependence: when two instructions write on the same register or memory location. 22

Name dependences are not true data dependences because there is no value being transmitted between instructions. Register renaming can be easily done and can solve the problem.

Dependences can generate hazards. In particular RAW hazards correspond to true data dependences; WAW to output dependences and WAR to antidependences. The difference is that the dependences are a property of the program, while hazards are properties of the pipeline.

Control dependences: is not a critical property but must be preserved and is a simple way to preserve the program order. They determine the ordering of instructions. They check that an instruction before a branch is executed before it and not after and that an instruction is not executed until the branch direction is known (control hazard).

Two properties critical for the program correctness are: