PIPELINE HAZARDS

In pipelining, there are situations in which the next instruction cannot execute in the
next clock cycle. These events are called hazards, and there are three different types.
Hazards

• Structural Hazards

• Data Hazards

• Control Hazards

STRUCTURAL HAZARD

❖
Structural Hazard occurs when a planned instruction cannot execute in the proper
clock cycle because the hardware does not support the combination of instructions
that are set to execute.

❖
A structural hazard in the laundry room would occur if we used a washer-dryer
combination instead of a separate washer and dryer, or if our roommate was busy doing
something else and wouldn’t put clothes away. Our carefully scheduled pipeline plans would
then be foiled.
FIGURE 1 Single-cycle, non-pipelined execution in top versus pipelined execution in
bottom.
As we said above, the MIPS instruction set was designed to be pipelined, making it fairly easy for
designers to avoid structural hazards when designing a pipeline. Suppose, however, that we had a
single memory instead of two memories. If the pipeline in Figure 1 had a fourth instruction, we would
see that in the same clock cycle the first instruction is accessing data from memory while the fourth
instruction is fetching an instruction from that same memory. Without two memories, our pipeline
could have a structural hazard.

DATA HAZARDS

❖
It is also called a pipeline data hazard. When a planned instruction cannot execute in
the proper clock cycle because data that is needed to execute the instruction is not yet
available.
❖
Data hazards occur when the pipeline must be stalled because one step must wait
for another to complete.

❖
In a computer pipeline, data hazards arise when one instruction depends on an earlier
instruction that is still in the pipeline. For example, suppose we have an add
instruction followed immediately by a subtract instruction that uses the sum ($s0):

add $s0, $t0, $t1

sub $t2, $s0, $t3

❖
Without intervention, a data hazard could severely stall the pipeline. The add
instruction doesn’t write its result until the fifth stage, meaning that we would have to
waste three clock cycles in the pipeline.
❖
To resolve the data hazard, for the code sequence above, as soon as the ALU creates
the sum for the add operation, we can supply it as an input for the subtract. This is
done by adding extra hardware to retrieve the missing item early from the internal
resources is called forwarding or bypassing.
❖
Figure below shows the connection to forward the value in $s0 after the
execution stage of the add instruction as input to the execution stage of the sub
instruction
 Fig 3.2: Graphical representation of forwarding

❖ Forwarding paths are valid only if the destination stage occurs later than the source

stage. For example, there cannot be a valid forwarding path from the output of the
memory access stage in the first instruction to the input of the execution stage of the
following, since that would mean going backwards in time.

❖ Forwarding cannot prevent all pipeline stalls. Suppose the first instruction was a load of

$s0 instead of an add, so the desired data would be available only after the fourth stage of
the first instruction in the dependence, which is too late for the input of the third stage of
the sub instruction.

CONTROL HAZARDS

❖
It is also called as branch hazard. When the proper instruction cannot be executed in
the proper pipeline clock cycle because the fetched instruction is not the one needed,
that is, the flow of instruction addresses is not what the pipeline expected.
❖
A control hazard arises when a decision must be made based on the results of one
instruction while others are executing.

❖
Even with this extra hardware, the pipeline involving conditional branches would look
like that shown in Figure 3.3. The lw instruction, executed if the branch fails, is stalled
for one extra 200 ps clock cycle before starting.
❖
The equivalent decision task in a computer is the branch instruction. Notice that we
must begin fetching the instruction following the branch on the very next clock cycle.
Nevertheless, the pipeline cannot possibly know what the next instruction should be,
since it only just received the branch instruction from memory.
 ❖
One possible solution is to stall immediately after we fetch a branch, waiting until the
pipeline determines the branch outcome and knows which instruction address to fetch
next. Let’s assume we add enough extra hardware so we can test registers, calculate
the branch address, and update the PC during the second stage of the pipeline.

Pipeline showing stalling on every conditional branch as a solution to control hazards.

BRANCH PREDICTION

A method of resolving a branch hazard that assumes a given outcome for the branch and
proceeds from that assumption rather than waiting to ascertain the actual outcome.
Static branch prediction

A more sophisticated version of branch prediction would predict some branches as

taken and others as untaken. In the case of programming, at the bottom of loops are branches
that jump back to the top of the loop. Since they are likely to be taken and they branch
backwards, we could always predict taken for branches that jump to an earlier address.

Dynamic branch prediction

Dynamic hardware predictors, in stark contrast, make their guesses depending on the
behavior of each branch and may change predictions for a branch over the life of a program.
Following our analogy, in dynamic prediction, a person would look at how dirty the uniform
was and guess at the formula, adjusting the next prediction depending on the success of
recent guesses. One popular approach to dynamic prediction of branches is keeping a history
for each branch as taken or untaken and then using the recent past behavior to predict the
future.
 Reduced Instruction Set Computer (RISC)
RISC (Reduced Instruction Set Computer) is a CPU design strategy focused on simplifying the
Instructions executed by a computer. The idea is to use a small set of simple instructions that
can execute in a single clock cycle, allowing for faster and more efficient processing. Here are
some key features and principles of RISC architecture:

1. Simplified Instruction Set

RISC processors have a limited set of instructions, each designed to perform a small, specific
operation. By keeping instructions simple, RISC processors avoid complex and multi-step
instructions, aiming to complete each operation in a single clock cycle.

2. Single-Cycle Execution
One of the main principles of RISC is that each instruction is executed in a single clock cycle,
which increases efficiency and speed.

3. Load and Store Architecture

RISC uses a load/store model, meaning it separates memory access and arithmetic
operations. Only the LOAD and STORE instructions access memory, while all other operations
work directly with the CPU registers, reducing memory access time and improving speed.

4. Large Number of Registers

RISC architecture often includes a larger number of general-purpose registers, allowing more
data to be stored within the CPU itself. This minimises the need to access slower memory,
which further enhances processing speed.

5. Pipelining
Pipelining is widely used in RISC architectures. It allows multiple instructions to be processed
simultaneously, with each part of the CPU handling a different stage of execution for a set of
instructions. This leads to more efficient use of the CPU and a faster overall instruction
execution.

6. Fixed-Length Instructions
RISC instructions are usually of fixed length, which simplifies decoding and aligns better with
pipelining. This uniformity in instruction length helps streamline the instruction cycle and
contributes to the processor's overall efficiency.
7. Optimised Compiler Design
RISC relies on compilers to translate high-level code into optimised machine code, ensuring
that the code can be executed efficiently by the processor. Compilers play a crucial role in
converting complex operations into simpler RISC instructions, thereby offloading some of the
complexity from the CPU.

8. Advantages of RISC
High Speed: Simplified instructions and single-cycle execution make RISC processors faster.
Efficiency in Power and Area: Reduced instructions and simpler circuitry can make RISC
processors more power-efficient.
Ease of Pipelining: Consistent instruction length and simplicity allow for efficient pipelining.
Scalability: RISC design is easily scalable, making it suitable for a wide range of applications
from embedded systems to high-performance computing.

9. Disadvantages of RISC
Dependency on Compiler: RISC systems rely on sophisticated compilers to manage code
optimisation and handling complex tasks.
Limited Instruction Set: Complex operations may require multiple simple instructions,
resulting in longer programs.
Memory Use: While efficient, the use of multiple instructions for certain operations can
Sometimes increase memory usage.

10. Examples of RISC Processors

Some well-known RISC architectures include ARM, MIPS, and SPARC. These processors are
widely used in mobile devices, gaming consoles, and embedded systems due to their power
efficiency and performance. RISC architecture represents a design philosophy focused on
speed, simplicity, and efficiency, playing a vital role in modern computing across various
applications, especially where high performance and energy efficiency are critical.

Complex Instruction Set Computer (CISC)

CISC (Complex Instruction Set Computer) is a CPU architecture design approach focused on
implementing a broad set of instructions, where each instruction can perform complex
operations. The goal is to minimise the number of instructions per program, even if individual
instructions take more cycles to execute. Here are the key characteristics and principles of
CISC architecture:
1. Extensive Instruction Set
CISC processors feature a large and diverse set of instructions, including complex commands
that can perform multiple tasks in a single instruction. Instructions in CISC may vary in length
and complexity, allowing higher-level operations to be performed in fewer lines of code.

2. Multi-Cycle Instructions
CISC instructions are generally designed to accomplish tasks that would take multiple steps in
RISC architecture. These instructions often take multiple clock cycles to execute, but can
reduce the overall number of instructions needed for a task.

3. Memory-to-Memory Operations
CISC architecture allows instructions to directly access memory without needing to load data
into registers first. This can simplify programming by allowing operations to be performed
directly on memory locations, reducing the need for intermediate instructions.

4. Fewer Registers
Since CISC processors can work directly with memory, they generally require fewer
general-purpose registers than RISC. This design allows for more complex operations at the
cost of increased memory access time, but CISC compensates for this by providing
instructions that handle memory directly.

5. Microcode Control Unit

CISC processors often use microcode to control complex instructions. Microcode is a layer of
instructions that translates high-level CISC instructions into a sequence of simpler steps
executed by the processor. This allows the CPU to handle complex instructions without
significant hardware complexity, improving flexibility.

6. Variable-Length Instructions
CISC instructions often have variable lengths, meaning that they are not all a fixed number of
bits. This allows more flexibility in the types of instructions and operations supported.
While this can make instruction decoding more complex, it allows for a rich set of instructions
that can handle a wide range of tasks.
7. Focus on Reducing Program Size
CISC is designed to reduce the number of instructions per program, which in turn minimises
the amount of memory required for storing the program. Complex instructions mean fewer
instructions are needed, reducing overall program size.

8. Advantages of CISC
Reduced Code Size: Complex instructions allow tasks to be completed with fewer
instructions, making the code more compact.
Easier Compiler Design: Since CISC instructions closely match high-level language
constructs, compilers need to perform fewer optimisations, simplifying their design.
Efficient Use of Memory: With reduced program size, less memory is needed to store
instructions, which can be advantageous in certain systems.

9. Disadvantages of CISC
Slower Instruction Execution: Due to the complexity of instructions, CISC processors may
require multiple clock cycles to execute each instruction, leading to slower execution.
Complexity in Decoding: Variable-length and complex instructions make the instruction
The decoding process is more complicated.
Increased Power Consumption: The complexity of CISC instructions often translates to
increased power usage, making it less suitable for power-sensitive applications.

10. Examples of CISC Processors

Common examples of CISC architecture include the Intel x86 family and IBM System/360
mainframes. x86 processors, widely used in personal computers, are known for their CISC
design, which supports a vast and varied set of instructions.

CISC architecture provides flexibility and reduces program code complexity by implementing
powerful, multi-step instructions. It has traditionally been used in systems where minimising
code size is important, although the trade-offs in power and speed have led to increased
interest in RISC approaches for many applications.
 Vector Processing
Vector processing is a form of parallel processing in which a single instruction operates on a
list (vector) of data elements rather than a single scalar value. It is widely used in scientific
computing, graphics, and modern SIMD/vector extensions (e.g., AVX, NEON) to accelerate
data-parallel workloads.

Basic idea of vector processing

 A vector processor executes a single operation on multiple data elements (a vector) in one
instruction, instead of repeating the same scalar instruction in a loop.
 Programs express data-parallelism explicitly using vector instructions like “add two vectors” or
“multiply vector by scalar”.

Vector processor architecture

 A classic vector processor has a scalar unit for normal (scalar) instructions and a vector unit for
vector operations.
 The vector unit typically includes:
 Vector registers (each holds many elements, e.g., 64 elements per register in VMIPS-like
designs).
 Pipelined vector functional units (add, multiply, logical operations).
 Vector load/store unit for moving vectors between memory and vector registers.

Memory–memory vs register–register
 Memory–memory vector processors: Vector operations read operands directly from memory
and write results back to memory (no vector registers in between).
 Register–register vector processors: Operands are first loaded into vector registers;
arithmetic is done between vector registers; results can then be stored to memory.
Register–register design is generally favoured in modern vector architectures because it
reduces the number of slow memory accesses and allows high reuse of vector data in
registers.

Key vector concepts

 Vector length (VL): Number of elements in the vector operation; hardware often exposes a
maximum vector length and a vector length register.
 Stride: Distance in memory between consecutive vector elements; non-unit stride allows
gathering/scattering non-contiguous data efficiently.
 Vector mask / predication: Bit mask or predicate that enables/disables operation on selected
vector elements, supporting conditional execution within vectors.
 Chaining: Feeding the result stream of one vector operation directly into another vector unit
without writing back to registers/memory, enabling overlapped execution and higher
throughput.

Example vector instruction sequence

 Scalar loop (conceptual):
 For i = 1 to n: C[i] = A[i] + B[i] (n scalar ADDs, with loop overhead).
 Vector form:
 LV V1, A ; load vector A into vector register V1
 LV V2, B ; load vector B into vector register V2
 ADDV V3, V1, V2 ; vector add of V1 and V2 into V3
 SV V3, C ; store result vector V3 into C
This reduces instruction fetch/decode overhead and lets hardware pipelines process many
elements per operation.

Advantages of vector processing

 High throughput for data-parallel workloads: Many arithmetic operations per cycle using
pipelined vector units and multiple lanes.
 Compact code: One vector instruction replaces long scalar loops, improving instruction cache
usage and reducing control overhead.
 Predictable performance: Regular access patterns and long sequences of identical operations
suit deep pipelines and high-memory-bandwidth designs.
 Efficient memory bandwidth usage when data is laid out with unit stride, since vector
loads/stores stream data sequentially.

Limitations and challenges

 Code suitability: Not all algorithms are easily vectorizable (dependencies between iterations
or irregular control flow reduce the benefit).
 Memory layout constraints: Performance depends strongly on data being organized so that
vector loads/stores (with unit or small stride) can access it efficiently.
 Hardware cost and complexity: Wide vector registers, multiple lanes, and high-bandwidth
memory systems increase design complexity and power use.
Relation to SIMD and modern CPUs
 Vector processors and SIMD both exploit data-level parallelism, but classic vector machines use
variable-length vectors with features such as vector length registers and chaining, while many
SIMD ISAs operate on fixed-width registers (e.g., 128/256/512 bits).
 Modern CPUs and GPUs implement vector/SIMD extensions (SSE, AVX, NEON, SVE, etc.) that
bring vector processing concepts to general-purpose and mobile processors.

Parallel computing is computing where the jobs are broken into discrete parts that can be
executed concurrently. Each part is further broken down into a series of instructions.
Instructions from each piece execute simultaneously on different CPUs. Breaking a task into
multiple parts and distributing them across multiple processors can reduce the time to run a
program. Parallel systems use multiple computer resources, including a single computer with
multiple processors, a network of computers forming a parallel processing cluster, or a
combination of both. Parallel systems are more difficult to program than single-processor
computers because their architectures vary, and the processes of multiple CPUs must be
coordinated and synchronised. The difficult problem of parallel processing is portability.
An Instruction Stream is a sequence of instructions that are read from memory. Data Stream is
the set of operations performed on data in the processor.
Flynn’s taxonomy is a classification scheme for computer architectures proposed by Michael
Flynn in 1966. The taxonomy is based on the number of instructions and data streams that a
computer architecture can process simultaneously.
There are four categories in Flynn’s taxonomy:
1. Single Instruction Single Data (SISD): In a SISD architecture, there is a single
processor that executes a single instruction stream and operates on a single data stream. This
is the simplest type of computer architecture and is used in most traditional computers.
2. Single Instruction Multiple Data (SIMD): In a SIMD architecture, there is a single
processor that executes the same instruction on multiple data streams in parallel. This type of
architecture is used in applications such as image and signal processing.
3. Multiple Instruction Single Data (MISD): In a MISD architecture, multiple processors
execute different instructions on the same data stream. This type of architecture is not
commonly used in practice, as it is difficult to find applications that can be decomposed into
independent instruction streams.
4. Multiple Instruction Multiple Data (MIMD): In a MIMD architecture, multiple
processors execute different instructions on different data streams. This type of architecture
is used in distributed computing, parallel processing, and other high-performance
computing applications.
Flynn’s taxonomy is a useful tool for understanding different types of computer architectures
and their strengths and weaknesses. The taxonomy highlights the importance of parallelism in
modern computing and shows how different types of parallelism can be exploited to improve
performance. Systems are classified into four major categories:

Single-Instruction, Single-Data (SISD) Systems

An SISD computing system is a uniprocessor machine that is capable of executing a single
instruction, operating on a single data stream. In SISD, machine instructions are processed in
a sequential manner, and computers adopting this model are popularly called sequential
computers. Most conventional computers have SISD architecture. All the instructions and
data to be processed have to be stored in primary memory.

Single-Instruction, Multiple-Data (SIMD) Systems

An SIMD system is a multiprocessor machine capable of executing the same instruction across
all CPUs while operating on different data streams. Machines based on an SIMD model are
well-suited to scientific computing because they involve many vector and matrix operations.
So that the information can be passed to all the processing elements (PEs), organised data
elements of vectors can be divided into multiple sets(N-sets for N PE systems), and each PE
can process one data set. Dominant representative SIMD systems is Cray’s vector processing
machine.

Multiple-Instruction, Single-Data (MISD) systems

An MISD computing system is a multiprocessor machine capable of executing different
instructions on different PEs but all of them operating on the same dataset.

Example Z = sin(x)+cos(x)+tan(x) The system performs different operations on the same data
set. Machines built using the MISD model are not useful in most of the application, a few
machines are built, but none of them are available commercially.
Multiple-Instruction, Multiple-Data (MIMD) Systems
An MIMD system is a multiprocessor machine that is capable of executing multiple
instructions on multiple data sets. Each PE in the MIMD model has separate instruction and
data streams; therefore, machines built using this model are capable of any kind of
application. Unlike SIMD and MISD machines, PEs in MIMD machines work asynchronously.

MIMD machines are classified into shared-memory and distributed-memory models

depending on how processors connect to memory. In a shared-memory MIMD system (tightly
coupled), all processors use the same global memory, and communication happens through it.
Any change made by one processor is visible to all others. Examples include Silicon Graphics
and Sun/IBM’s SMP systems.

In a distributed-memory MIMD system (loosely coupled), each processor has its own local
memory, and they communicate through an interconnection network (like tree or mesh).
Shared-memory systems are easier to program but harder to scale and more vulnerable to
failures, since a fault can affect the whole system. In contrast, distributed-memory systems are
more scalable and fault-tolerant, since each processor is independent. As a result of practical
outcomes and user requirements, distributed memory MIMD architecture is superior to the
other existing models.
Flynn’s taxonomy itself does not have any inherent advantages or disadvantages. It is simply a
classification scheme for computer architectures based on the number of instruction streams
and data streams that can be processed simultaneously.

However, the different types of computer architectures that fall under Flynn’s taxonomy have
their own advantages and disadvantages. Here are some examples:
 1. SISD architecture: This is the simplest and most common type of computer
architecture. It is easy to program and debug and can handle a wide range of applications.
However, it does not offer significant performance gains over traditional computing systems.
2. SIMD architecture: This type of architecture is highly parallel and can offer significant
performance gains for applications that can be parallelized. However, it requires specialized
hardware and software and is not well-suited for applications that cannot be parallelized.
3. MISD architecture: This type of architecture is not commonly used in practice, as it is
difficult to find applications that can be decomposed into independent instruction streams.
4. MIMD architecture: This type of architecture is highly parallel and can offer significant
performance gains for applications that can be parallelized. It is well-suited for distributed
computing, parallel processing, and other high-performance computing applications.
However, it requires specialized hardware and software and can be challenging to program
and debug.
Overall, the advantages and disadvantages of different types of computer architectures
depend on the specific application and the level of parallelism that can be exploited. Flynn’s
taxonomy is a useful tool for understanding the different types of computer architectures and
their potential uses, but ultimately the choice of architecture depends on the specific needs of
the application.

What is a Hazard?
In a pipelined processor, multiple instructions overlap in execution.
A hazard occurs when this smooth flow is disturbed and the pipeline must stall (insert bubbles) or take
corrective action.

👉 Ideal pipeline CPI = 1

👉 With hazards → CPI > 1 (performance degrades)

🔴 1. Structural Hazards (Hardware Conflict)

🔍 Concept

Occurs when hardware resources are insufficient to support all pipeline stages simultaneously.

💡 Why it happens?

Because pipeline assumes parallel hardware usage, but actual hardware may be limited.
 📌 Example (Classic)

Pipeline stages:

 IF → Instruction Fetch
 MEM → Data Access

If both use same memory:

 Instruction 1 → needs memory (data)

 Instruction 2 → needs memory (instruction fetch)

➡ Conflict occurs → stall needed

⏱ Timeline Example
Cycle Instruction 1 Instruction 2
1 IF
2 ID IF
3 EX ID
4 MEM ❗ IF ❗ (conflict)

✅ Solutions

 Separate memories (Harvard architecture)

 Multi-port memory
 Resource duplication
 Pipeline scheduling

🔵 2. Data Hazards (Dependency Problems)

🔍 Concept

Occurs when instructions are dependent on each other’s data.

📌 Types of Data Hazards (VERY IMPORTANT)

🟡 (1) RAW – Read After Write (True Dependency)

👉 Most common

I1: R1 = R2 + R3
I2: R4 = R1 + R5

Problem:

 I2 needs R1, but I1 hasn’t written it yet.

⏱ Pipeline View
Cycle I1 I2
1 IF
2 ID IF
Cycle I1 I2
3 EX ID (needs R1 ❗)
4 MEM EX (wrong data)

🟡 (2) WAR – Write After Read (Anti-dependency)

I1: R2 = R1 + R3 (reads R1)
I2: R1 = R4 + R5 (writes R1)

Problem:

 I2 writes before I1 reads

👉 Happens in out-of-order execution

🟡 (3) WAW – Write After Write (Output dependency)

I1: R1 = R2 + R3
I2: R1 = R4 + R5

Problem:

 Order of writes must be preserved

✅ Solutions for Data Hazards

1. ⛔ Pipeline Stall (Bubble insertion)

 Delay dependent instruction

2. ⚡ Data Forwarding (Bypassing)

 Directly pass result from one stage to another

👉 Example:

 From EX/MEM → EX stage

3. 🔁 Register Renaming

 Avoid WAR/WAW hazards

 Use different physical registers

4. 📅 Instruction Reordering

 Compiler rearranges instructions

🟢 3. Control Hazards (Branch Hazards)

🔍 Concept

Occurs due to branch instructions where next instruction is unknown.

 📌 Example
BEQ R1, R2, LABEL

👉 Processor doesn’t know:

 Branch taken? or not?

⏱ Pipeline Problem
Cycle Instruction
1 Fetch branch
2 Decode
3 Condition check ❗
4 Target fetch

➡ Meanwhile wrong instructions may be fetched

❌ Problem

 Wrong instructions enter pipeline → must be flushed

✅ Solutions

1. 🔮 Branch Prediction
Static:

 Always taken / not taken

Dynamic:

 Based on history (2-bit predictor etc.)

2. ⏩ Delayed Branch

 Execute next instruction anyway

3. 🚫 Pipeline Flushing

 Remove incorrect instructions

4. 🧠 Speculative Execution

 Execute predicted path

⚡ Performance Impact
CPI Formula:
CPI = Ideal CPI + Stall Cycles per Instruction
Hazards increase:

 Stall cycles
 Execution time

🧠 Key Differences (Exam Table)

Hazard Cause Occurs In Fix
Structural Hardware conflict All pipelines Add resources
Data Dependency Sequential instructions Forwarding
Control Branch Conditional flow Prediction