Formula sheet: Instruction Pipelining | Digital Circuits - Electronics and Communication Engineering (ECE) PDF Download

 Page 1


Digital Circuits: Instruction Pip elining F orm ula
Sheet for GA TE
Basic Concepts
• Instruction Pip elining : T ec hnique to o v erlap the execution of m ultiple instructions
b y dividing the pro cess in to stages (e.g., F etc h, Deco de, Execute, Memory , W rite-
bac k).
• Pip eline Stages : T ypically 5 stages (IF, ID, EX, MEM, WB).
• Pip eline Throughput : Num b er of instructions completed p er unit time.
P erformance Metrics
• Clo c k Cycle Time : Time for one pip eline stage (determined b y the slo w est stage).
T
cycle
=max(T
stage
i
)
where T
stage
i
is the time for stage i .
• Instruction Execution Time (Non-Pip elined) : T otal time for one instruction.
T
non-pip elined
= n·T
stage
where n is the n um b er of stages, T
stage
is the stage time.
• Instruction Execution Time (Pip elined) : Time p er instruction in steady state.
T
pip elined
= T
cycle
• T otal Execution Time (Pip elined) : F or k instructions with n stages.
T
total
= T
cycle
·(k+n-1)
• Sp eedup : Ratio of non-pip elined to pip elined execution time.
S =
T
non-pip elined
T
pip elined
=
k·n·T
stage
k·T
cycle
˜ n ( for large k)
• Throughput : Instructions p er unit time.
Throughput=
k
T
total
=
k
T
cycle
·(k+n-1)
Pip eline Hazards
• T yp es of Hazards :
– Structural : Resource conflicts (e.g., same hardw are needed b y m ultiple stages).
1
Page 2


Digital Circuits: Instruction Pip elining F orm ula
Sheet for GA TE
Basic Concepts
• Instruction Pip elining : T ec hnique to o v erlap the execution of m ultiple instructions
b y dividing the pro cess in to stages (e.g., F etc h, Deco de, Execute, Memory , W rite-
bac k).
• Pip eline Stages : T ypically 5 stages (IF, ID, EX, MEM, WB).
• Pip eline Throughput : Num b er of instructions completed p er unit time.
P erformance Metrics
• Clo c k Cycle Time : Time for one pip eline stage (determined b y the slo w est stage).
T
cycle
=max(T
stage
i
)
where T
stage
i
is the time for stage i .
• Instruction Execution Time (Non-Pip elined) : T otal time for one instruction.
T
non-pip elined
= n·T
stage
where n is the n um b er of stages, T
stage
is the stage time.
• Instruction Execution Time (Pip elined) : Time p er instruction in steady state.
T
pip elined
= T
cycle
• T otal Execution Time (Pip elined) : F or k instructions with n stages.
T
total
= T
cycle
·(k+n-1)
• Sp eedup : Ratio of non-pip elined to pip elined execution time.
S =
T
non-pip elined
T
pip elined
=
k·n·T
stage
k·T
cycle
˜ n ( for large k)
• Throughput : Instructions p er unit time.
Throughput=
k
T
total
=
k
T
cycle
·(k+n-1)
Pip eline Hazards
• T yp es of Hazards :
– Structural : Resource conflicts (e.g., same hardw are needed b y m ultiple stages).
1
– Data : Data dep endencies b et w een instructions (e.g., RA W, W AR, W A W).
– Con trol : Branc h instructions causing pip eline flushes.
• Stall (Bubble) : Idle cycle in tro duced to resolv e hazards.
T
stall
= T
cycle
· Num b er of stalls
• Branc h P enalt y : Extra cycles due to branc h misprediction.
T
branc h p enalt y
= T
cycle
·( Num b er of flushed stages )
Data Hazards and Resolution
• Read After W rite (RA W) : Dep enden t instruction reads data b efore it is written.
• W rite After Read (W AR) : W rite o ccurs b efore read of same register.
• W rite After W rite (W A W) : Multiple writes to the same register.
• Resolution T ec hniques :
– F orw arding (Bypassing) : P ass data directly b et w een pip eline stages.
– Stalling : Insert bubbles to w ait for data a v ailabilit y .
Con trol Hazards and Resolution
• Branc h Prediction : Predict branc h outcome to reduce flush p enalt y .
• Dela y ed Branc hing : Execute instructions in dela y slot b efore branc h.
• Pip eline Flush : Clear pip eline stages on branc h misprediction.
T
flush
= T
cycle
·( Num b er of stages flushed )
Key Notes
• Ideal sp eedup is equal to the n um b er of pip eline stages for large k .
• Hazards reduce pip eline e?iciency; fo cus on iden tifying hazard t yp es for GA TE.
• F orw arding reduces data hazard stalls but requires additional hardw are.
• Branc h p enalt y dep ends on pip eline depth and misprediction rate.
• F or GA TE, practice n umericals on sp eedup, total execution time, and stalls.
2