5.1 Linear Instruction Pipeline Execution & Performance Speedup Proofs

Back to DBMS Notes

📚05Topic 5.1⏱️18 min

🎯High-Yield For:Instruction pipelining is the single most transformative microarchitectural optimization in modern computing, transforming multi-cycle instruction execution into a continuous, high-throughput assembly line.

💡 Core Intuition:

🍳 The Everyday Analogy:

Imagine an industrial commercial laundry business that handles hundreds of client loads every week. Each load requires four consecutive operations:

1. Washing Machine: $30\text{ minutes}$
2. Dryer Machine: $40\text{ minutes}$
3. Folding Table: $20\text{ minutes}$
4. Ironing & Packaging Station: $30\text{ minutes}$

• Under a Sequential (Non-Pipelined) Strategy: The laundry operator washes Load 1, moves it to the dryer, folds it, and irons it—taking a full $120\text{ minutes}$ ($2\text{ hours}$) before ever putting Load 2 into the washer! In this scheme, three out of the four machines sit completely cold and idle at any given moment. Processing $100\text{ loads}$ requires: $T_{\text{seq}} = 100 \times 120\text{ minutes} = 12,000\text{ minutes} = 200\text{ hours}$

• Under an Overlapped (Pipelined) Strategy: The moment Load 1 finishes washing and enters the dryer, the operator immediately drops Load 2 into the washer! When Load 1 advances to the folding table, Load 2 enters the dryer, and Load 3 enters the washer. Because the slowest station (the Dryer) requires $40\text{ minutes}$, a new completed basket rolls off the packaging station every $40\text{ minutes}$ in steady state! $T_{\text{pipe}} = \text{Initial Fill (4 stages)} + (99 \times 40\text{ min}) = 120\text{ min} + 3,960\text{ min} = 4,080\text{ minutes} = 68\text{ hours}$

The total operational time drops from $200\text{ hours}$ to $68\text{ hours}$—achieving a near $3\times$ speedup—without speeding up the physical washing or drying motors by even a single second!

💻 Bridging to Computer Science:

In a microprocessor, an instruction does not execute instantaneously. It traverses multiple physical hardware subsystems: instruction cache, decoding ROM, register files, arithmetic logic units (ALU), data caches, and writeback buses.

In a non-pipelined CPU, only one functional unit is active at any instant; the rest of the expensive silicon sits dormant. Instruction Pipelining partitions the CPU datapath into distinct, synchronized combinational stages separated by intermediate buffer registers. By overlapping instructions across these functional units, the processor achieves a steady-state throughput of one instruction per clock cycle!

---

📑Table of Contents

• Sequential vs. Pipelined Architecture Comparison
• The Classic 5-Stage RISC Pipeline Microarchitecture
  • The Critical Role of Pipeline Buffer Registers
• Mathematical Formulation of Pipeline Timing & Clock Period
  • Derivation of Processor Clock Period (\tau)
  • Total Execution Time for n Instructions
• The Space-Time Reservation Matrix
• Quantitative Performance Metrics: Speedup, Efficiency & Throughput
  • Mathematical Proof of Speedup (S)
• Stage Balancing & Splitting Slow Bottleneck Stages
• 🏭 Real-World Production Context:
• 📐 Numerical Applications & Worked Examples
  • Example 1: 4-Stage Pipeline Timing & Speedup with Latch Overhead
  • Example 2: Performance Gain via Bottleneck Stage Splitting
  • Example 3: Clock Frequency Reduction vs. Pipeline Depth Trade-off
• 🎯 Exam & Interview Pitfall Check

---

Sequential vs. Pipelined Architecture Comparison

The fundamental microarchitectural divergence between non-pipelined and pipelined processors centers on hardware utilization and concurrency.

Non-Pipelined Sequential vs. Pipelined Overlapped Execution

Comparing single-instruction monopolization against concurrent multi-stage overlapping

Sequential Execution

Non-Pipelined Architecture

🐢

Dominant Architecture / DomainEarly Microprocessors, Low-Power Microcontrollers

• •Instructions execute strictly one after another; next fetch begins only after current instruction retires.
• •Over 80% of execution hardware sits idle at any given instant during a clock cycle.
• •Clock cycle period equals the entire sum of all operational delays: T = Σ(t_i).
• •Throughput is locked at exactly 1 instruction per k clock cycles (CPI = k).

"One instruction monopolizes the entire CPU datapath from fetch to writeback."

Overlapped Execution

Pipelined Architecture

⚡

Dominant Architecture / DomainAll Modern General-Purpose CPUs (x86-64, ARM, RISC-V)

• •Multiple instructions occupy different datapath stages concurrently on the same clock edge.
• •Hardware functional units (ALU, decoders, memory interfaces) operate with near 100% utilization.
• •Clock period equals the slowest stage delay plus latch overhead: τ = max(t_i) + t_r.
• •In steady-state, one completed instruction retires every single clock cycle (Ideal CPI = 1).

"Hardware concurrency maximizes instruction throughput without altering single-task latency."

---

The Classic 5-Stage RISC Pipeline Microarchitecture

In modern reduced instruction set computer (RISC) architectures—such as classic MIPS, DLX, and basic RISC-V—instruction execution is partitioned into five distinct, balanced combinational stages.

The 5 Canonical RISC Pipeline Execution Stages

Micro-architectural datapath progression from instruction fetch to register writeback

1

Instruction Fetch (IF)

Read instruction from L1 Instruction Cache using Program Counter (PC).

2

Instruction Decode & Register Read (ID)

Decode 32-bit opcode and read source register values from the Register File.

3

Execution & Address Calculation (EX)

ALU performs arithmetic/logical operation or computes effective memory address.

4

Memory Access (MEM)

Read or write data operand to/from L1 Data Cache.

5

Register Writeback (WB)

Commit the final computation result back to destination register in Register File.

The Critical Role of Pipeline Buffer Registers

Notice that between every adjacent pair of combinational stages sits an intermediate synchronous storage element:

• IF/ID Register: Holds the fetched instruction word and current PC.
• ID/EX Register: Holds decoded control signals, source register values, and sign-extended immediate offset.
• EX/MEM Register: Holds ALU computation result, zero flag, and memory write-data.
• MEM/WB Register: Holds data read from memory and ALU output destined for writeback.

[!IMPORTANT] Why are Pipeline Registers Mathematically Mandatory?
Combinational logic gates continuously propagate electrical signals. Without pipeline registers, an electrical change in the IF stage would ripple uncontrollably into the ID and EX stages before the clock cycle completes, destroying data from previously running instructions. Pipeline registers act as synchronous electrical firewalls, capturing and freezing state at every rising clock edge.

---

Mathematical Formulation of Pipeline Timing & Clock Period

Let a pipeline consist of $k$ distinct combinational stages, where stage $i$ exhibits a combinational propagation delay of $t_i$ ($1 \le i \le k$).
Let $t_r$ denote the intermediate register/latch setup, propagation, and clock-skew overhead.

Derivation of Processor Clock Period ($\tau$)

In a synchronous pipeline, a single master clock drives every pipeline register simultaneously. For an instruction to transition safely from stage $i$ to stage $i+1$ without timing violations: $\tau \ge t_i + t_r \quad \forall i \in \{1, 2, \dots, k\}$

Therefore, the processor clock period $\tau$ is strictly constrained by the maximum combinational delay among all stages:

$\tau = t_p = \max(t_1, t_2, \dots, t_k) + t_r$

$\text{Processor Clock Frequency } f_{\text{clk}} = \frac{1}{\tau} = \frac{1}{\max(t_i) + t_r}$

Total Execution Time for $n$ Instructions

Suppose $n$ independent instructions are executed on a $k$-stage pipeline without stalls or branches:

1. Pipeline Fill Phase: The first instruction ($I_1$) enters an empty pipeline at clock cycle 1. It must traverse all $k$ distinct stages sequentially. Hence, $I_1$ requires exactly $k$ clock cycles to complete.
2. Steady-State Retirement Phase: At the end of cycle $k$, the pipeline is completely full. Because every subsequent instruction ($I_2, I_3, \dots, I_n$) is exactly one stage behind the preceding one, one completed instruction retires at every single clock cycle thereafter!
3. The remaining $(n - 1)$ instructions require exactly $(n - 1)$ clock cycles.

📐Total Pipelined Execution Time Formulaformula

$\text{Total Clock Cycles } C_{\text{total}} = k + (n - 1)$

$\text{Total Execution Time } T_{\text{pipe}} = [k + (n - 1)] \cdot \tau$

Where:

• $k$ = Total number of pipeline stages
• $n$ = Total number of instructions / tasks
• $\tau = t_p$ = Clock period duration (nanoseconds / picoseconds)

---

The Space-Time Reservation Matrix

The spatial progression of 5 independent instructions ($I_1 \dots I_5$) across a 5-stage pipeline ($IF, ID, EX, MEM, WB$) over time is represented below:

Instruction	Cycle 1	Cycle 2	Cycle 3	Cycle 4	Cycle 5	Cycle 6	Cycle 7	Cycle 8	Cycle 9
$I_1$	IF	ID	EX	MEM	WB	—	—	—	—
$I_2$	—	IF	ID	EX	MEM	WB	—	—	—
$I_3$	—	—	IF	ID	EX	MEM	WB	—	—
$I_4$	—	—	—	IF	ID	EX	MEM	WB	—
$I_5$	—	—	—	—	IF	ID	EX	MEM	WB

• Total Clock Cycles: $k + (n - 1) = 5 + (5 - 1) = 9\text{ cycles}$.
• Under Non-Pipelined Execution: $5 \times 5 = 25\text{ cycles}$ would be required!

---

Quantitative Performance Metrics: Speedup, Efficiency & Throughput

To mathematically evaluate the engineering return of a pipelined processor, architects rely on four standardized metrics:

The 4 Fundamental Pipeline Performance Metrics

Mathematical metrics governing throughput, efficiency, and hardware acceleration

⏱️

Clock Period (τ)

Cycle Constraint

• Determined by slowest bottleneck stage delay: τ = max(t_i) + t_r.
• Register overhead t_r limits the maximum practical number of stages.
• Defines processor clock frequency: f = 1 / τ.

Key Abstractions / Calls

τ = max(t_i) + t_rf = 1 / τ

🚀

Speedup Ratio (S)

Acceleration Factor

• Ratio of non-pipelined execution time to pipelined execution time.
• Under ideal conditions and large n: S approaches k (number of stages).
• S = (n · t_seq) / ([k + n - 1] · τ).

Key Abstractions / Calls

S = T_seq / T_pipeS_max = k

📊

Pipeline Efficiency (η)

Hardware Utilization

• Measures percentage of time pipeline functional units perform productive work.
• Direct ratio of actual speedup to maximum theoretical speedup: η = S / k.
• Approaches 1.0 (100%) as instruction count n becomes very large.

Key Abstractions / Calls

η = S / kη = n / (k + n - 1)

⚡

Throughput (TP)

Instruction Flow Rate

• Number of instructions completed per unit of time (instructions/second).
• TP = n / T_pipe = n / ([k + n - 1] · τ).
• Maximum steady-state throughput is 1 / τ instructions per second.

Key Abstractions / Calls

TP = n / T_pipeTP_max = 1 / τ

Mathematical Proof of Speedup ($S$)

🔍Theorem 5.1: Derivation of Pipeline Speedup Limitproof

Let $T_{\text{seq}}$ be the time required to execute $n$ instructions on an equivalent non-pipelined processor.
In a non-pipelined system, each instruction passes through the total combinational logic:

$t_{\text{seq}} = \sum_{i=1}^k t_i$

$T_{\text{seq}} = n \cdot t_{\text{seq}} = n \cdot \sum_{i=1}^k t_i$

Under pipelined execution: $T_{\text{pipe}} = [k + (n - 1)] \cdot \tau = [k + (n - 1)] \cdot [\max(t_i) + t_r]$

The Speedup ($S$) is defined as: $S = \frac{T_{\text{seq}}}{T_{\text{pipe}}} = \frac{n \cdot \sum_{i=1}^k t_i}{[k + (n - 1)] \cdot [\max(t_i) + t_r]}$

Case 1: Ideal Perfectly Balanced Pipeline ($t_1 = t_2 = \dots = t_k = t$) with Zero Latch Delay ($t_r = 0$): Here, $\sum t_i = k \cdot t$, and $\max(t_i) = t$. The speedup becomes: $S = \frac{n \cdot k \cdot t}{[k + (n - 1)] \cdot t} = \frac{n \cdot k}{k + n - 1}$

Taking the limit as the number of instructions $n \to \infty$: $\lim_{n \to \infty} S = \lim_{n \to \infty} \frac{k}{1 + \frac{k - 1}{n}} = \mathbf{k}$

$\blacksquare$

[!NOTE] Why Can Real-World Speedup Never Reach $k$?

1. Intermediate Register Overhead ($t_r > 0$): Every latch consumes setup and hold time ($5\text{–}20\text{ ps}$). As $k$ increases, latch delay accumulates, consuming an increasing fraction of the cycle time.
2. Stage Imbalance: Real-world circuits cannot be divided into identically equal time slices. A slow cache read ($200\text{ ps}$) forces fast ALU operations ($60\text{ ps}$) to wait.
3. Pipeline Hazards & Stalls: Data dependencies, branch mispredictions, and cache misses inject bubbles ($CPI > 1$).

---

Stage Balancing & Splitting Slow Bottleneck Stages

Because clock period $\tau$ is constrained by $\max(t_i) + t_r$, an imbalanced pipeline wastes tremendous performance. If four stages take $10\text{ ns}$ each, but the fifth stage takes $30\text{ ns}$, the entire processor must run at $\tau = 30\text{ ns} + t_r$, leaving four stages idle for $20\text{ ns}$ in every single cycle!

To eliminate this bottleneck, architects apply Stage Splitting:

📐The Bottleneck Splitting Ruleprinciple

If stage $X$ exhibits delay $t_X \gg t_{\text{avg}}$, partition stage $X$ across multiple sub-stages: $\text{Stage } X \implies X_1 (t_{X1}) + X_2 (t_{X2})$ Such that: $t_{X1} \approx t_{X2} \approx \frac{t_X}{2}$

Consequence: The new clock period drops to: $\tau_{\text{new}} = \max(t_1, \dots, t_{X1}, t_{X2}, \dots) + t_r$ Although the pipeline depth increases from $k$ to $k+1$ (adding 1 cycle to initial fill latency), the operating frequency $f = 1 / \tau$ increases dramatically, drastically boosting overall system throughput!

---

🏭 Real-World Production Context:

Modern production microarchitectures demonstrate the practical engineering limits of instruction pipelining:

1. Intel NetBurst (Pentium 4 Prescott): Pushed pipelining to its theoretical extreme with 31 pipeline stages to reach $3.8\text{ GHz}$ clock frequencies. However, the extreme branch misprediction penalty ($31\text{+ cycles lost}$) and massive dynamic power dissipation ($P = C V^2 f$) caused severe thermal runaway, leading Intel to abandon ultra-deep pipelines.
2. Modern Intel Core (Golden Cove / Raptor Cove): Settles on a balanced 14 to 16 stage pipeline for integer execution, achieving $5.8\text{ GHz}$ frequencies with high instructions-per-cycle (IPC) efficiency.
3. Apple Silicon (M1/M2/M3 Firestorm & Avalanche): Utilizes a wider, shorter 14-stage out-of-order execution pipeline coupled with an unprecedented 8-wide decode engine and massive 630-entry Reorder Buffer (ROB), prioritizing IPC efficiency and low power over raw gigahertz scaling.

---

📐 Numerical Applications & Worked Examples

Example 1: 4-Stage Pipeline Timing & Speedup with Latch Overhead

Problem Statement:
A 4-stage instruction pipeline has stage delays of $150\text{ ns}$, $120\text{ ns}$, $160\text{ ns}$, and $140\text{ ns}$ respectively. The intermediate buffer registers between stages introduce a propagation delay of $5\text{ ns}$ each.

1. Determine the minimum clock period ($\tau$) and maximum clock frequency of the pipelined processor.
2. Calculate the total time required to execute $1,000$ instructions on this pipeline.
3. Calculate the speedup achieved over an equivalent non-pipelined processor.

Step-by-Step Solution:

1. Calculate the Clock Period ($\tau$): The pipeline cycle time is dictated by the slowest stage plus the register delay: $\tau = \max(t_1, t_2, t_3, t_4) + t_r$ $\tau = \max(150, 120, 160, 140) + 5 = 160\text{ ns} + 5\text{ ns} = \mathbf{165\text{ ns}}$ $\text{Clock Frequency } f = \frac{1}{\tau} = \frac{1}{165 \times 10^{-9}\text{ s}} \approx \mathbf{6.06\text{ MHz}}$

2. Calculate Total Execution Time ($T_{\text{pipe}}$): For $k = 4$ stages and $n = 1,000$ instructions: $T_{\text{pipe}} = [k + (n - 1)] \cdot \tau$ $T_{\text{pipe}} = [4 + (1,000 - 1)] \times 165\text{ ns} = 1,003 \times 165\text{ ns} = \mathbf{165,495\text{ ns}} \approx \mathbf{165.50\text{ }\mu\text{s}}$

3. Calculate Non-Pipelined Time ($T_{\text{seq}}$) & Speedup ($S$): In a non-pipelined processor, an instruction passes through all combinational logic without intermediate registers: $t_{\text{seq}} = \sum_{i=1}^4 t_i = 150 + 120 + 160 + 140 = 570\text{ ns}$ $T_{\text{seq}} = n \cdot t_{\text{seq}} = 1,000 \times 570\text{ ns} = 570,000\text{ ns} = 570\text{ }\mu\text{s}$ $\text{Speedup } S = \frac{T_{\text{seq}}}{T_{\text{pipe}}} = \frac{570,000\text{ ns}}{165,495\text{ ns}} \approx \mathbf{3.444\times}$

---

Example 2: Performance Gain via Bottleneck Stage Splitting

Problem Statement:
Instruction execution in a processor is divided into 5 stages: Instruction Fetch (IF), Instruction Decode (ID), Operand Fetch (OF), Execute (EX), and Writeback (WB). The combinational delays are $5\text{ ns}$, $4\text{ ns}$, $20\text{ ns}$, $10\text{ ns}$, and $3\text{ ns}$ respectively. Intermediate registers introduce a delay of $2\text{ ns}$.
Two implementations are evaluated for executing $20$ independent instructions:

• Implementation A (Naive Pipeline - NP): The standard 5-stage pipeline.
• Implementation B (Efficient Pipeline - EP): The bottleneck $OF$ stage ($20\text{ ns}$) is divided into two balanced sub-stages: $OF_1 = 12\text{ ns}$ and $OF_2 = 8\text{ ns}$, creating a 6-stage pipeline.
  Calculate the speedup achieved by the Efficient Pipeline (EP) over the Naive Pipeline (NP).

Step-by-Step Solution:

1. Analyze Implementation A (NP - 5 stages, $k = 5$):

   • Bottleneck stage delay: $\max(5, 4, 20, 10, 3) = 20\text{ ns}$ ($OF$ stage).
   • Clock period: $\tau_{\text{NP}} = 20\text{ ns} + 2\text{ ns} = 22\text{ ns}$.
   • Total execution time for $n = 20$ instructions: $T_{\text{NP}} = [k + (n - 1)] \cdot \tau_{\text{NP}} = [5 + (20 - 1)] \times 22\text{ ns} = 24 \times 22\text{ ns} = \mathbf{528\text{ ns}}$

2. Analyze Implementation B (EP - 6 stages, $k = 6$):

   • Stages: $IF (5)$, $ID (4)$, $OF_1 (12)$, $OF_2 (8)$, $EX (10)$, $WB (3)$.
   • New bottleneck stage delay: $\max(5, 4, 12, 8, 10, 3) = 12\text{ ns}$ ($OF_1$ stage).
   • Clock period: $\tau_{\text{EP}} = 12\text{ ns} + 2\text{ ns} = 14\text{ ns}$.
   • Total execution time for $n = 20$ instructions: $T_{\text{EP}} = [k + (n - 1)] \cdot \tau_{\text{EP}} = [6 + (20 - 1)] \times 14\text{ ns} = 25 \times 14\text{ ns} = \mathbf{350\text{ ns}}$

3. Calculate Relative Speedup ($S_{\text{EP / NP}}$): $S = \frac{T_{\text{NP}}}{T_{\text{EP}}} = \frac{528\text{ ns}}{350\text{ ns}} \approx \mathbf{1.51\times}$ Splitting the single bottleneck stage yields an immediate $51\%$ net performance acceleration, even for a tiny batch of 20 instructions!

---

Example 3: Clock Frequency Reduction vs. Pipeline Depth Trade-off

Problem Statement:
A non-pipelined processor operates at a clock frequency of $2.5\text{ GHz}$ ($f_1 = 2.5\times 10^9\text{ Hz}$) with an average Cycles Per Instruction of $CPI_{\text{non-pipe}} = 4.0$.
The processor architecture is upgraded to a 5-stage pipeline ($k = 5$). Due to internal clock distribution and intermediate latch delays, the maximum clock frequency of the pipelined processor drops to $2.0\text{ GHz}$ ($f_2 = 2.0\times 10^9\text{ Hz}$). Assuming an ideal instruction stream with zero stalls ($CPI_{\text{pipe}} = 1.0$), calculate the effective speedup achieved by the pipelined processor.

Step-by-Step Solution:

1. Calculate Average Instruction Execution Time on Non-Pipelined Processor: $\text{Clock Period } \tau_{\text{non-pipe}} = \frac{1}{f_1} = \frac{1}{2.5\text{ GHz}} = 0.4\text{ ns}$ $\text{Time per instruction } t_{\text{non-pipe}} = CPI_{\text{non-pipe}} \times \tau_{\text{non-pipe}} = 4.0 \times 0.4\text{ ns} = \mathbf{1.6\text{ ns}}$

2. Calculate Average Instruction Execution Time on Pipelined Processor: In steady state with zero stalls, the pipelined processor completes 1 instruction every clock cycle ($CPI_{\text{pipe}} = 1.0$): $\text{Clock Period } \tau_{\text{pipe}} = \frac{1}{f_2} = \frac{1}{2.0\text{ GHz}} = 0.5\text{ ns}$ $\text{Time per instruction } t_{\text{pipe}} = CPI_{\text{pipe}} \times \tau_{\text{pipe}} = 1.0 \times 0.5\text{ ns} = \mathbf{0.5\text{ ns}}$

3. Calculate Effective Speedup ($S$): $S = \frac{t_{\text{non-pipe}}}{t_{\text{pipe}}} = \frac{1.6\text{ ns}}{0.5\text{ ns}} = \mathbf{3.2\times}$ Even though the raw clock frequency decreased from $2.5\text{ GHz}$ to $2.0\text{ GHz}$, the reduction in CPI from $4.0$ to $1.0$ delivers a net $3.2\times$ performance improvement!

---

🎯 Exam & Interview Pitfall Check

Core Conceptual Questions

• Why does pipelining improve instruction throughput without reducing individual instruction execution latency?
  Pipelining does not accelerate the speed of light or the physical propagation delay through transistors. An individual instruction must still travel through all $k$ stages sequentially, taking $k \times \tau$ nanoseconds from start to finish. However, by overlapping multiple independent instructions across separate functional units, the processor retires one instruction every single cycle in the steady state, multiplying overall program throughput by up to $k\times$.

• Why can pipeline depth ($k$) not be increased indefinitely to achieve infinite speedup?
  As the number of stages $k$ increases, the combinational delay per stage ($t_i = t_{\text{total}} / k$) shrinks. However, the intermediate latch setup and hold time ($t_r$) remains constant. Eventually, $t_r$ dominates the cycle time ($t_r > t_i$), creating diminishing returns. Furthermore, deeper pipelines dramatically increase branch misprediction penalties and data hazard stall cycles, causing actual CPI to degrade severely. Modern high-performance CPUs cap pipeline depth around 12 to 19 stages.

Common Interview Traps

• Trap 1: Assuming $n$ instructions on a $k$-stage pipeline take $n \times k$ clock cycles.
  Candidates frequently multiply $n \times k$. Remember the pipeline overlap principle: only the first instruction takes $k$ cycles to fill the pipe; the remaining $(n - 1)$ instructions retire at 1 cycle each: $C = k + n - 1$. For $n = 10,000$ and $k = 5$, the total cycles is $10,004$, NOT $50,000$!

• Trap 2: Forgetting intermediate register delay ($t_r$) when calculating clock frequency.
  If stages have delays of $10\text{ ns}, 15\text{ ns}, 12\text{ ns}$ and latch delay is $2\text{ ns}$, candidates incorrectly state $\tau = 15\text{ ns}$ ($f = 66.7\text{ MHz}$). The clock period must account for the latch: $\tau = 15 + 2 = 17\text{ ns}$ ($f = 58.8\text{ MHz}$). Missing $t_r$ produces incorrect cycle times in all subsequent speedup calculations.

• Trap 3: Calculating non-pipelined time as $k \times \max(t_i)$.
  In a true non-pipelined processor, an instruction passes through the combinational logic without stopping at pipeline registers: $t_{\text{seq}} = \sum_{i=1}^k t_i$. Only in the special case of an already-clocked single-cycle multi-stage processor does $t_{\text{seq}} = k \times \tau$. Read the problem statement carefully to see if stage delays are given individually!

---

🗺️View Complete COA Roadmap & Syllabus

← Previous Topic4.3 Direct Memory Access (DMA) Controllers & Cycle Stealing MechanicsNext Topic →5.2 Pipeline Hazards: Structural, Data Hazards & Operand Forwarding