Pipelining.
Pipeline hazards
Sabina Batyrkhanovna
What is pipelining?
• A technique used in advanced microprocessors where the
microprocessor begins executing a second instruction before the first
has been completed
• Multiple instructions are overlapped in execution
• Process of instruction execution is divided into two or more steps, called pipe stages
or pipe segments
• Different stage are completing different parts of different instructions in parallel
• The stages are connected one to the next to form a pipe
• Instructions enter at one end, progress through the stages, and exit at the other end
• Unlike some speedup techniques, it is not visible to the programmer/compiler.
Characteristics of pipelining
• Hardware or software implementation – pipelining can be implemented in either software
or hardware.
• Large or Small Scale – Stations in a pipeline can range from simplistic to powerful, and a
pipeline can range in length from short to long.
• Buffered or unbuffered flow – One stage of pipeline sends data directly to another one or
a buffer is place between each pairs of stages.
• Synchronous or asynchronous flow – A synchronous pipeline operates like an assembly
line: at a given time, each station is processing some amount of information. A
asynchronous pipeline, allow a station to forward information at any time.
• Automatic Data Feed Or Manual Data Feed – Some implementations of pipelines use a
separate mechanism to move information, and other implementations require each stage
to participate in moving information
Types of pipelining
• Software Pipelining
• Can Handle Complex Instructions
• Allows programs to be reused
• Hardware Pipelining
• Help designer manage complexity – a complex task can be divided into smaller, more
manageable pieces.
• Hardware pipelining offers higher performance
Effects of pipelining
• Time in ns per instruction goes up
• Number of cycles per instruction goes up (note the increase in clock
speed)
• Total execution time goes down, resulting in lower time per instruction
• Average cycles per instruction increases slightly
• Under ideal conditions:
• speedup = ratio of elapsed times between successive instruction completions
= number of pipeline stages = increase in clock speed
Instruction pipelining
• An instruction pipeline increases the performance of a processor by overlapping the
processing of several different instructions
• Consists of five stages:
• Instruction fetch (IF): the instruction is fetched from memory and placed in the
instruction register (IR)
• Instruction decode (ID): identification of the operation to be performed
• Execution (EX): the instruction is executed
• Memory read/write (ME): stage is responsible for storing and loading values to and
from memory. It also responsible for input or output from the processor.
• Write back (WB): The results of the operation are written to the destination register.
Timings
• Estimated timing for each stage of instruction:
• Instruction fetch – 2ns
• Instruction decode – 1ns
• Execution – 2ns
• Memory and I/O – 2ns
• Write Back – 1ns
Hazards
• There are three types of hazards that can happen while pipelined
execution:
• Structural hazards
• Data hazards
• Control hazards
Hazards (cont.)
• Structural hazards
• different instructions in different stages (or the same stage) conflicting for the
same resource
• Data hazards
• an instruction cannot continue because it needs a value that has not yet been
generated by an earlier instruction
• Control hazards
• fetch cannot continue because it does not know the outcome of an earlier
branch – special case of a data hazard
Data hazard
• Data hazard caused by data dependences
• There are three data dependences:
• Read-After-Write (RAW)
• Write-After-Write (WAW)
• Write-After-Read (WAR)
Read-After-Write
Read R2 and R3 Add R2 and R3 Write result to R1
ADD R1, R2, R3 IF ID EX M WB
SUB R4, R1, R5 IF ID EX M WB
Read R1 and R5
Next instruction tries to read an operand before previous instruction writes it Extremely common hazard
Write-After-Write
Read R2 and R3 Add R2 and R3 Write result to R1
ADD R1, R2, R3 IF ID EX M M1 M2 M3 WB
SUB R1, R4, R5 IF ID EX M WB
Write result to R1
Next instruction tries to write an operand before previous instruction writes it
Write-After-Read
Read R2 and R3 Write result to R1
ADD R1, R2, R3 IF ID EX M WB
SUB R2, R1, R5 IF ID EX M WB
Write result to R2
Next instruction tries to write an operand before previous instruction reads it. Happens if pipeline is out-order
Dealing with data hazard
• We can solve data hazard problem with stalling
• Stalling
• halting the flow of instructions until the required result is ready to be used
• wastes processor time by doing nothing while waiting for the result.
ADD R1, R2, R3
IF ID EX M WB
STALL IF ID EX M WB
STALL IF ID EX M WB
STALL IF ID EX M WB
IF ID EX M WB
SUB R4, R1, R5
Performance of pipelines
𝐴𝑣𝑔 𝑖𝑛𝑠𝑡𝑢𝑐𝑡𝑖𝑜𝑛 𝑡𝑖𝑚𝑒 𝑢𝑛𝑝𝑖𝑝𝑒𝑙𝑖𝑛𝑒𝑑
𝑆𝑝𝑒𝑒𝑑𝑢𝑝 𝑓𝑟𝑜𝑚 𝑝𝑖𝑝𝑒𝑙𝑖𝑛𝑖𝑛𝑔 = =
𝐴𝑣𝑔 𝑖𝑛𝑠𝑡𝑟𝑢𝑐𝑡𝑖𝑜𝑛 𝑡𝑖𝑚𝑒 𝑝𝑖𝑝𝑒𝑙𝑖𝑛𝑒𝑑
𝐶𝑃𝐼 𝑢𝑛𝑝𝑖𝑝𝑒𝑙𝑖𝑛𝑒𝑑 × 𝐶𝑙𝑜𝑐𝑘 𝑐𝑦𝑐𝑙𝑒 𝑡𝑖𝑚𝑒 𝑢𝑛𝑝𝑖𝑝𝑒𝑙𝑖𝑛𝑒𝑑
𝐶𝑃𝐼 𝑝𝑖𝑝𝑒𝑙𝑖𝑛𝑒𝑑 × 𝐶𝑙𝑜𝑐𝑘 𝑐𝑦𝑐𝑙𝑒 𝑡𝑖𝑚𝑒 𝑝𝑖𝑝𝑒𝑙𝑖𝑛𝑒𝑑
𝐶𝑃𝐼 𝑝𝑖𝑝𝑒𝑙𝑖𝑛𝑒𝑑 = 𝐼𝑑𝑒𝑎𝑙 𝐶𝑃𝐼 + 𝑃𝑖𝑝𝑒𝑙𝑖𝑛𝑒 𝑠𝑡𝑎𝑙𝑙 𝑐𝑙𝑜𝑐𝑘 𝑐𝑦𝑐𝑙𝑒𝑠 𝑝𝑒𝑟 𝑖𝑛𝑠𝑡𝑟𝑢𝑐𝑡𝑖𝑜𝑛
On a pipelined processor Ideal CPI is 1
𝐶𝑃𝐼 𝑝𝑖𝑝𝑒𝑙𝑖𝑛𝑒𝑑 = 1 + 𝑃𝑖𝑝𝑒𝑙𝑖𝑛𝑒 𝑠𝑡𝑎𝑙𝑙 𝑐𝑙𝑜𝑐𝑘 𝑐𝑦𝑐𝑙𝑒𝑠 𝑝𝑒𝑟 𝑖𝑛𝑠𝑡𝑟𝑢𝑐𝑡𝑖𝑜𝑛
𝐶𝑃𝐼 𝑢𝑛𝑝𝑖𝑝𝑒𝑙𝑖𝑛𝑒𝑑
𝑆𝑝𝑒𝑒𝑑𝑢𝑝 𝑓𝑟𝑜𝑚 𝑝𝑖𝑝𝑒𝑙𝑖𝑛𝑖𝑛𝑔 =
1 + 𝑃𝑖𝑝𝑒𝑙𝑖𝑛𝑒 𝑠𝑡𝑎𝑙𝑙 𝑐𝑙𝑜𝑐𝑘 𝑐𝑦𝑐𝑙𝑒𝑠 𝑝𝑒𝑟 𝑖𝑛𝑠𝑡𝑟𝑢𝑐𝑡𝑖𝑜𝑛
CPI unpipelined = depth of pipeline
IF ID EX M WB
IF ID EX M WB
IF ID EX M WB
Pipeline depth
𝑷𝒊𝒑𝒆𝒍𝒊𝒏𝒆 𝒅𝒆𝒑𝒕𝒉
𝑺𝒑𝒆𝒆𝒅𝒖𝒑 𝒇𝒓𝒐𝒎 𝒑𝒊𝒑𝒆𝒍𝒊𝒏𝒊𝒏𝒈 =
𝟏 + 𝑷𝒊𝒑𝒆𝒍𝒊𝒏𝒆 𝒔𝒕𝒂𝒍𝒍 𝒄𝒍𝒐𝒄𝒌 𝒄𝒚𝒄𝒍𝒆𝒔 𝒑𝒆𝒓 𝒊𝒏𝒔𝒕𝒓𝒖𝒄𝒕𝒊𝒐𝒏
Advantages and disadvantages
• Advantages:
• More efficient use of processor
• Quicker time of execution of large number of instructions
• Disadvantages:
• Pipelining involves adding hardware to the chip
• Inability to continuously run the pipeline at full speed because of pipeline
hazards which disrupt the smooth execution of the pipeline.
