Advanced Computer Architecture CSE 8383 January 26 2006 Session 4 Copyright by Hesham El Rewini Computer Science and Engineering Pipelining Copyright by Hesham El Rewini Computer Science and Engineering Contents Introduction Linear Pipelines Nonlinear pipelines Copyright by Hesham El Rewini Computer Science and Engineering Basic Idea Assembly Line Divide the execution of a task among a number of stages A task is divided into subtasks to be executed in sequence Performance improvement compared to sequential execution Copyright by Hesham El Rewini Computer Science and Engineering Pipeline n 2 1 Sub tasks Task Stream of Tasks 1 2 n Pipeline Copyright by Hesham El Rewini Computer Science and Engineering 5 Tasks on 4 stage pipeline Time 1 2 3 4 5 6 7 8 Task 1 Task 2 Task 3 Task 4 Task 5 Copyright by Hesham El Rewini Computer Science and Engineering Speedup Stream of m Tasks t t 1 2 t n Pipeline T Seq n m t T Pipe n t m 1 t Speedup n m n m 1 Copyright by Hesham El Rewini Computer Science and Engineering Linear Pipeline Processing Stages are linearly connected Perform fixed function Synchronous Pipeline Clocked latches between Stage i and Stage i 1 Equal delays in all stages Asynchronous Pipeline Handshaking Copyright by Hesham El Rewini Computer Science and Engineering Latches S1 S2 L1 S3 L2 Slowest stage determines delay Equal delays clock period Copyright by Hesham El Rewini Computer Science and Engineering Reservation Table Time S1 S2 S3 S4 Copyright by Hesham El Rewini X X X X Computer Science and Engineering 5 tasks on 4 stages Time S1 S2 X X X X X X X X X X X X X X X X X X X S3 S4 Copyright by Hesham El Rewini X Computer Science and Engineering Non Linear Pipelines Variable functions Feed Forward Feedback Copyright by Hesham El Rewini Computer Science and Engineering 3 stages 2 functions Y X S1 Copyright by Hesham El Rewini S2 S3 Computer Science and Engineering Reservation Tables for X Y S1 X X X S2 S1 X Y X Y Y S2 S3 X X S3 X Y Copyright by Hesham El Rewini Y Y Computer Science and Engineering Linear Instruction Pipelines Assume the following instruction execution phases Fetch F Decode D Operand Fetch O Execute E Write results W Copyright by Hesham El Rewini Computer Science and Engineering Pipeline Instruction Execution F D I1 I2 I3 I1 I2 I3 I1 I2 I3 I1 I2 I3 I1 I2 O E W Copyright by Hesham El Rewini I3 Computer Science and Engineering Dependencies Data Dependency Operand is not ready yet Instruction Dependency Branching Will that Cause a Problem Copyright by Hesham El Rewini Computer Science and Engineering Data Dependency I1 Add R1 R2 R3 I2 Sub R4 R1 R5 F I1 1 I2 2 D O E W Copyright by Hesham El Rewini I1 3 4 5 6 I2 I1 I2 I1 I2 I1 I2 Computer Science and Engineering Solutions STALL Forwarding Write and Read in one cycle Copyright by Hesham El Rewini Computer Science and Engineering Instruction Dependency I1 Branch o I2 F 1 I1 1 1 D O E W Copyright by Hesham El Rewini 2 I2 2 3 3 I1 I2 I1 4 4 5 5 6 6 I2 I1 I2 I1 I2 Computer Science and Engineering Solutions STALL Predict Branch taken Predict Branch not taken Copyright by Hesham El Rewini Computer Science and Engineering Floating Point Multiplication Inputs Mantissa1 Exponenet1 Mantissa2 Exponent2 Add the two exponents Exponent out Multiple the 2 mantissas Normalize mantissa and adjust exponent Round the product mantissa to a single length mantissa You may adjust the exponent Copyright by Hesham El Rewini Computer Science and Engineering Linear Pipeline for floating point multiplication Add Exponents Add Exponents Multiply Mantissa Partial Products Normalize Accumulator Normalize Round Round Re normalize Copyright by Hesham El Rewini Computer Science and Engineering Linear Pipeline for floating point Addition Subtract Exponents Partial Shift Add Mantissa Find Leading 1 Round Copyright by Hesham El Rewini Partial Shift Re normalize Computer Science and Engineering Combined Adder and Multiplier Partial Products F A Exponents Subtract ADD Partial Shift Copyright by Hesham El Rewini B G C H Partial Shift Find Leading 1 Add Mantissa Round Re normalize E D Computer Science and Engineering Reservation Table for Multiply 1 A 2 3 X X 4 5 6 7 X B C D E X X X X X F G H Copyright by Hesham El Rewini Computer Science and Engineering Reservation Table for Addition 1 A 2 3 4 5 6 7 8 9 Y B C Y D Y E F G H Copyright by Hesham El Rewini Y Y Y Y Y Y Computer Science and Engineering Nonlinear Pipeline Design Latency The number of clock cycles between two initiations of a pipeline Collision Resource Conflict Forbidden Latencies Latencies that cause collisions Copyright by Hesham El Rewini Computer Science and Engineering Nonlinear Pipeline Design cont Latency Sequence A sequence of permissible latencies between successive task initiations Latency Cycle A sequence that repeats the same subsequence Collision vector C Cm Cm 1 C2 C1 m n 1 n number of column in reservation table Ci 1 if latency i causes collision 0 otherwise Copyright by Hesham El Rewini Computer Science and Engineering Mul Mul Collision launch after 1 cycle A 1 2 X Z B C D E X 3 4 X Z Z X X Z 5 6 7 Z X X Z Z X F G H Copyright by Hesham El Rewini Computer Science and Engineering Mul Mul Collision lunch after 2 cycles 1 A 2 X B C D E 3 4 5 X Z Z X X Z 6 7 Z X Z X XZ X F G H Copyright by Hesham El Rewini Computer Science and Engineering Mul Mul Collision launch after 3 cycles 1 A 2 3 X B C D E 4 5 6 Z Z 7 Z X X X X Z X Z X X F G H Copyright by Hesham El Rewini Computer Science and Engineering Collision Vector for Multiply after Multiply Forbidden Latencies 1 2 Collision vector 0 0 0 0 1 1 11 Maximum forbidden latency 2 m 2 Copyright by Hesham El Rewini Computer Science and Engineering