Computer Organization and Architecture - Pipelining

Parallel Processing

• Parallel processing systems perform concurrent data processing to achieve faster execution times.
• The purpose is to speed up computer processing capability and increase throughput (the amount of processing accomplished during a given interval).
• Parallel processing increases hardware amount and system cost.
• Parallel processing can be classified based on:
  • Internal organization of processors
  • Interconnection structure between processors
  • Flow of information through the system

Flynn's Classification

• M.J. Flynn classified computer systems by the number of instructions and data items manipulated simultaneously.
• Instruction stream: Sequence of instructions read from memory.
• Data stream: Operations performed on data in the processor.
• Flynn's classification divides computers into four major groups:
  • Single Instruction stream, Single Data stream (SISD)
  • Single Instruction stream, Multiple data stream (SIMD)
  • Multiple Instruction stream, Single Data stream (MISD)
  • Multiple Instruction stream, Multiple Data stream (MIMD)

SISD

• Represents a single computer with a control unit, a processor unit, and a memory unit.
• Instructions are executed sequentially.
• The system may or may not have internal parallel processing capabilities, achieved by multiple functional units or pipeline processing.

SIMD

• Includes many processing units under a common control unit.
• All processors receive the same instruction but operate on different data items.
• The shared memory unit must contain multiple modules for simultaneous communication with all processors.

MISD

• Structure is only of theoretical interest, as no practical system has been constructed using this organization.

MIMD

• Refers to a computer system capable of processing several programs at the same time.
• Most multiprocessor and multicomputer systems are classified in this category.

Pipelining

Pipelining – Analogy (Laundry)

Non-Pipelined Laundry

1. Place one dirty load of clothes in the washer.
2. When the washer is finished, place the wet load in the dryer.
3. When the dryer is finished, place the dry load on a table and fold.
4. When folding is finished, put the clothes away. Start over with the next dirty load.

Pipelined Laundry

1. Place one dirty load of clothes in the washer.
2. When the washer is finished, place the first wet load in the dryer. Also, load the washer with the second dirty load.
3. When the dryer is finished, place the first dry load on a table and fold. Place the second wet load in the dryer. Also, load the washer with the third dirty load.
4. When folding is finished, put the first set of clothes away. Place the second dry load on a table and fold. Place the third wet load in the dryer. Also, load the washer with the fourth dirty load.

• All steps (stages in pipelining) operate concurrently.
• Separate resources for each stage enable pipelining.
• Pipelining improves throughput of the laundry system.
• Pipelining does not decrease the time to complete one load but improves throughput when multiple loads are processed.

Definition

• Pipelining is a technique of decomposing a sequential process into sub-operations.
• Each sub-process is executed in a special dedicated segment that operates concurrently with all other segments.
• Any operation that can be decomposed into a sequence of sub-operations of about the same complexity can be implemented by a pipeline processor.
• The technique is efficient for applications that need to repeat the same task many times with different sets of data.

Pipelining Idealism

• Uniform Suboperations: The operation to be pipelined can be evenly partitioned into uniform-latency suboperations.
• Repetition of Identical Operations: The same operations are to be performed repeatedly on a large number of different inputs.
• Repetition of Independent Operations: All the repetitions of the same operation are mutually independent, i.e., no data dependence and no resource conflicts.

Pipelining Characteristics

• Pipelining doesn’t reduce latency of a single task; it improves the throughput of the entire workload.
• Pipeline rate is limited by the slowest pipeline stage.
• Potential speedup = Number of pipe stages.
• Unbalanced lengths of pipe stages reduce speedup.
• Time to fill the pipeline and time to drain it reduces speedup.

Pipelining in Circuits

• Increases throughput with little increase in hardware.
• Bandwidth or Throughput = Performance.
• Pipelining partitions the system into multiple independent stages with added buffers between the stages.
• Pipelining can increase the throughput of a system.
• Bandwidth (BW) = no. of tasks/unit time.
• For a system that operates on one task at a time: $BW = \frac{1}{\text{latency}}$.
• BW can be increased by pipelining if many operands exist which need the same operation, i.e., many repetitions of the same task are to be performed.

Four Segment Pipeline

• The operands pass through all four segments in a fixed sequence.
• Each segment consists of a combinational circuit S; that performs a suboperation over the data stream flowing through the pipe.
• The segments are separated by registers Ri that hold the intermediate results between the stages.
• Information flows between adjacent stages under the control of a common clock applied to all the registers simultaneously.
• A task is defined as the total operation performed going through all the segments in the pipeline.

Space-Time Diagram for Pipeline

• Consider a k-segment pipeline with a clock cycle time $t_p$ used to execute n tasks.
• The first task $T<em>1$ requires a time equal to $kt</em>p$ to complete its operation since there are k segments in the pipe.
• The remaining n - 1 tasks emerge from the pipe at the rate of one task per clock cycle and they will be completed after a time equal to $(n - 1)t_p$.
• Therefore, to complete n tasks using a k-segment pipeline requires $k + (n - 1)$ clock cycles.
• A non-pipeline unit performs the same operation and takes a time equal to tn to complete each task.
• The total time required for n tasks is $n*t_n$.
• The speedup of a pipeline processing over an equivalent non-pipeline processing is defined by the ratio
• The time required for the pipeline processing is $k + (n - 1)t_p$, where:
  • k is the number of stages in the pipeline
  • n is the number of tasks
  • $t_p$ is the clock cycle time
• The first task ($T<em>1$) will take $kt</em>p$ clock cycles to complete, since it has to pass through all k stages of the pipeline.
• The second task ($T<em>2$) will take k-1 clock cycles to complete since it can start executing in the second stage of the pipeline while $T</em>1$ is still executing in the first stage.
• The third task ($T_3$) will take k-2 clock cycles to complete, and so on.
• The nth task ($T_n$) will take only one clock cycle to complete, since it can start executing in the kth stage of the pipeline while all the other tasks are already in their respective stages.

Example Calculation

• Suppose we have a 4-stage pipeline with a clock cycle time of 1 ns. We want to execute 5 tasks.
• The total time required for the pipeline processing is $4 + (5 - 1) * 1 \text{ ns} = 9 \text{ ns}$.
• Pipelining is a very effective technique for improving the performance of computer systems. By pipelining the execution of tasks, computer systems can process tasks faster and more efficiently.

Example with Specific Values

• Let the time it takes to process a suboperation in each segment be equal to $t_p = 20 \text{ ns}$. Assume that the pipeline has $k = 4$ segments and executes $n = 100$ tasks in sequence.
• The pipeline system will take $(k + n - 1)t_p = (4 + 99) \times 20 = 2060 \text{ ns}$ to complete.
• Assuming that $t<em>n = kt</em>p = 4 \times 20 = 80 \text{ ns}$, a non pipeline system requires $nkt_p = 100 \times 80 = 8000 \text{ ns}$ to complete the 100 tasks.
• The speedup ratio is equal to $8000/2060 = 3.88$.
• As the number of tasks increases, the speedup will approach 4, which is equal to the number of segments in the pipeline.
• If we assume that $t_n = 60 \text{ ns}$, the speedup becomes $6000/2060 = 3$.

Instruction Pipeline

• An instruction pipeline reads consecutive instructions from memory while previous instructions are being executed in other segments.
• This causes the instruction fetch and execute phases to overlap and perform simultaneous operations.
• The pipeline is divided into stages, and these stages are connected with one another to form a pipe-like structure. Instructions enter from one end and exit from another end. Pipelining increases the overall instruction throughput.

Instruction Division

An instruction in a process is divided into 5 subtasks:

• Instruction Fetch
• Instruction Decode
• Operand Fetch
• Execute (ALU operation)
• Write Back

Instruction Pipeline Operation

Once the instruction fetch operation of the first instruction is completed in the next clock cycle, the instruction fetch of the second instruction gets started. This way the hardware never sits idle; it is always busy performing some or other operation. But, no two instructions can execute their same stage at the same clock cycle.

Pipelining Issues

• Ideal Case: Independent computations, where all instructions are mutually independent.
• Reality: Pipeline stalls – cannot proceed when a later computation may require the result of an earlier computation.
  • Impact of ISA
    • Reduce Memory addressing modes - dependency detection
    • Use register addressing mode - easy dependencies check

Limits to Pipelining

• Hazards: Circumstances that would cause incorrect execution if the next instruction is fetched and executed.
• There are mainly three types of hazards possible in a pipelined processor:
  • Structural hazards
  • Data hazards
  • Control hazards

Structural Hazards

Attempting to use the same hardware to do two different things at the same time. Structural hazards arise because there is not enough duplication of resources.

• Resolving structural hazards:
  • Solution 1: Wait
  • Solution 2: Avoid structural hazards by duplicating resources

Data Hazards

Instruction depends on the result of a prior instruction still in the pipeline

Control Hazards

Caused by delay between the fetching of instructions and decisions about changes in control flow (branches)

Structural Hazard Details

• This situation arises mainly when two instructions require a given hardware resource at the same time, and hence for one of the instructions, the pipeline needs to be stalled.
• The most common case is when memory is accessed at the same time by two instructions. One instruction may need to access the memory as part of the Execute or Write back phase, while the other instruction is being fetched. In this case, if both the instructions and data reside in the same memory, both the instructions can’t proceed together, and one of them needs to be stalled till the other is done with the memory access part. Thus, in general, sufficient hardware resources are needed for avoiding structural hazards.
• Solution for structural dependency
  • To minimize structural dependency stalls in the pipeline, use a hardware mechanism called Renaming.
  • Renaming: Divide the memory into two independent modules used to store the instruction and data separately, called Code memory(CM) and Data memory(DM) respectively. CM will contain all the instructions, and DM will contain all the operands that are required for the instructions.

Example

Unport Memory

Illustrates structural hazard when memory access conflicts occur between instruction fetch and data memory access, causing stalls.

Detecting & Resolving Structural Hazard

Stalling an instruction to resolve a structural hazard, inserting bubbles into the pipeline to maintain correct execution.

Control Hazard Details

• The instruction fetch unit of the CPU is responsible for providing a stream of instructions to the execution unit. The instructions fetched by the fetch unit are in consecutive memory locations, and they are executed.
• However, the problem arises when one of the instructions is a branching instruction to some other memory location. Thus, all the instructions fetched in the pipeline from consecutive memory locations are invalid now and need to be removed (also called flushing of the pipeline). This induces a stall till new instructions are again fetched from the memory address specified in the branch instruction.
• Thus, the time lost as a result of this is called a branch penalty. Often, dedicated hardware is incorporated in the fetch unit to identify branch instructions and compute branch addresses as soon as possible, reducing the resulting delay as a result.

Handling Conditional Branches

• One way of handling a conditional branch is to prefetch the target instruction in addition to the instruction following the branch. Both are saved until the branch is executed. If the branch condition is successful, the pipeline continues from the branch target instruction. An extension of this procedure is to continue fetching instructions from both places until the branch decision is made. At that time, control chooses the instruction stream of the correct program flow.
• Another possibility is the use of a branch target buffer or BTB. The BTB is an associative memory included in the fetch segment of the pipeline. Each entry in the BTB consists of the address of a previously executed branch instruction and the target instruction for that branch. It also stores the next few instructions after the branch target instruction. When the pipeline decodes a branch instruction, it searches the associative memory BTB for the address of the instruction. If it is in the BTB, the instruction is available directly, and prefetch continues from the new path. If the instruction is not in the BTB, the pipeline shifts to a new instruction stream and stores the target instruction in the BTB. The advantage of this scheme is that branch instructions that have occurred previously are readily available in the pipeline without interruption.

Example

Illustrates a branch instruction scenario with comparison, branching, and sequential instructions, followed by a branch target.

Branch Prediction and Delayed Branch

• Branch prediction: A pipeline with branch prediction uses some additional logic to guess the outcome of a conditional branch instruction before it is executed. The pipeline then begins prefetching the instruction stream from the predicted path. A correct prediction eliminates the wasted time caused by branch penalties.
• Delayed branch: Compiler rearranges instructions in order to keep the pipeline full. (Insert NOP or some other useful instruction after each branch.) Used by most RISC processors. In this procedure, the compiler detects the branch instructions and rearranges the machine language code sequence by inserting useful instructions that keep the pipeline operating without interruptions. An example of delayed branch is the insertion of a no-operation instruction after a branch instruction. This causes the computer to fetch the target instruction during the execution of the no-operation instruction, allowing a continuous flow of the pipeline.

Data Hazards

add r1,r2,r3

sub r4,r1,r3

and r6,r1,r7

or r8,r1,r9

xor r10,r1,r11

Data hazards may be classified as one of three types, depending on the order of read and write accesses in the instructions:

Read After Write (RAW)

Considering two instructions i and j, instruction j reads the data before i writes it.

I : add r1,r2,r3

J : sub r4,r1,r3

Add modifies r1 and then Sub should read it.

• Caused by a data dependence.
• Can actually be solved relatively easily – with forwarding.
• Forwarding occurs when a result is passed directly to the functional unit that requires it.
• Result goes from the output of one unit to the input of another.

Operand Forwarding to Avoid Data Hazard

Illustrates operand forwarding to avoid data hazards, where results are directly passed to subsequent instructions, reducing stalls.

Write After Write (WAW)

Corresponds to an output dependence. Occurs when there are multiple writes or a short integer pipeline and a longer floating-point pipeline or when an instruction proceeds when a previous instruction is stalled.

• WAW (write after write)
  • This is caused by a name dependence. There is no actual data transfer. It is the same name that causes the problem
• Considering two instructions i and j, instruction j should write after instruction i has written the data
  • i: SUB R1, R4, R3
  • j: ADD R1, R2, R3
• Instruction i has to modify register R1 first, and then j has to modify it. Otherwise, there is a WAW hazard. There is a problem because of R1. If some other register had been used, there will not be a problem
• Solution is register renaming, that is, use some other register. The hardware can do the renaming or the compiler can do the renaming

Write After Read (WAR)

• Arises from an anti-dependence
• Cannot occur in most static issue pipelines
• Occurs either when there are early writes and late reads, or when instructions are re-ordered
• There is no actual data transfer. It is the same name that causes the problem
• Considering two instructions i and j, instruction j should write after instruction i has read the data.
  • i: SUB R4, R1, R3
  • j: ADD R1, R2, R3
• Instruction i has to read register R1 first, and then j has to modify it. Otherwise, there is a WAR hazard. There is a problem because of R1. If some other register had been used, there will not be a problem
• Solution is register renaming, that is, use some other register. The hardware can do the renaming or the compiler can do the renaming
• WAR and WAW happens in out of order pipes

Instruction Level Parallelism(ILP)

• ILP: The simultaneous execution of multiple instructions from a program. Pipelining is a form of ILP.
• Instruction-level parallelism (ILP) of a program—a measure of the average number of instructions in a program that a processor might be able to execute at the same time. Mostly determined by the number of true (data) dependencies and procedural (control) dependencies in relation to the number of other instructions
• A dependence is a property of the instructions in a program; for example, a true dependence arises when one instruction uses the value produced by an earlier instruction.
• A hazard is a potential problem in a pipeline that may arise from a dependence.
• dependence: fixed property of instruction stream – (i.e., program)
• hazard: property of program and processor organization

Dependences and Hazards

• In order to achieve parallelism, we should not have dependences among instructions
• A dependence results in a hazard, and the hazard causes a stall
• To exploit instruction-level parallelism, determine which instructions can be executed in parallel. If two instructions are data dependent, they cannot execute simultaneously
• If 2 instructions are:
  • (independent) parallel, they can execute simultaneously in a pipeline
  • dependent, they are not parallel and must be executed in order
• In order to achieve parallelism, we should not have dependences among instructions which are executing in parallel. Why is dependence bad? A dependence results in a hazard, and the hazard causes a stall. Pipeline stalls increase CPI which in turn reduces pipeline performance.

Types of Dependences

• Data dependences
• Name dependences
• Control dependences

Data Dependence

• Read-after-Write (RAW)

• Anti-dependence (Write-after-Read)

• Output dependence (Write-after-Write)

• Control dependence

Types of Dependencies

• Dependencies are a property of programs
• There are two types of data dependence- true data dependences and name dependences
  • True Data dependence
    • An instruction j is data dependent on instruction i if either of the following holds:
      • Instruction i produces a result that may be used by instruction j, or
      • Instruction j is data dependent on instruction k, and instruction k is data dependent on instruction i
  • Name dependencies
    • A name dependence occurs when two instructions use the same register or memory location, called a name, but there is no flow of data between the instructions associated with that name
      • Output dependence
        • An output dependence occurs when instruction i and instruction j write the same register or memory location. The ordering between the instructions must be preserved.
      • Anti-dependence
        • An anti-dependence between instruction i and instruction j occurs when instruction j writes a register or memory location that instruction i reads. The original ordering must be preserved.
• Control Dependence

True Data Dependences

• An instruction j is data dependent on instruction i if either of the following holds:
  • instruction i produces a result that may be used by instruction j , or
  • instruction j is data dependent on instruction k, and instruction k is data dependent on instruction i

```
LOOP LD F0, 0(R1)

ADD F4, F0, F2

SD F4, 0(R1)

ADD R1, R1, 8

BNE R1, R2, LOOP```

Name Dependences

• Anti-dependence (Corresponds to WAR)
  • When instruction j writes a register or memory location that instruction i reads, the ordering must be preserved to ensure that i reads the correct value.
  • i: add r6,r5,r4
  • j: sub r5,r8,r11
• Output dependence (Corresponds to WAW)
  • When instruction i and j write the same register or memory location. The ordering must be preserved to leave the correct value in the register
  • i: add r7,r4,r3
  • j: div r7,r2,r8
  • Since this is not a true dependence, renaming can be more easily done for register operands, where it is called register renaming
  • Register renaming can be done either statically by a compiler or dynamically by the hardware

Data Hazard

• Read After Write (RAW)
  • InstrJ tries to read operand before InstrI writes it
  • Caused by a “True Data Dependence”
    • I: add r1,r2,r3
    • J: sub r4,r1,r3

Data Hazard Write After Read (WAR)

• InstrJ tries to write operand before InstrI reads
  • InstrI gets wrong operand
  • Caused by “anti-dependence”
    • I: sub r4,r1,r3
    • J: add r1,r2,r3
    • K: mul r6,r1,r7

Data Hazard Write After Write (WAW)

• InstrJ tries to write operand before InstrI writes it
  • Leaves wrong result
  • Caused by “output dependence”
    • I: sub r1,r4,r3
    • J: add r1,r2,r3
    • K: mul r6,r1,r7

Data Dependency (Data Hazard)

• Data hazards occur when instructions that exhibit data dependence, modify data in different stages of a pipeline. Hazard cause delays in the pipeline. There are mainly three types of data hazards:
  • 1) RAW (Read after Write) [Flow/True data dependency]
  • 2) WAR (Write after Read) [Anti-Data dependency]
  • 3) WAW (Write after Write) [Output data dependency]
• Let there be two instructions I and J, such that J follow I. Then,
  • RAW hazard occurs when instruction J tries to read data before instruction I writes it. Eg:
    • I: R2 <- R1 + R3
    • J: R4 <- R2 + R3
  • WAR hazard occurs when instruction J tries to write data before instruction I reads it. Eg:
    • I: R2 <- R1 + R3
    • J: R3 <- R4 + R5
  • WAW hazard occurs when instruction J tries to write output before instruction I writes it. Eg:
    • I: R2 <- R1 + R3
    • J: R2 <- R4 + R5
• WAR and WAW hazards occur during the out-of-order execution of the instructions.

Data Dependence