Muhammad Bilawal
MSF25006533
Question1:
What is data dependence in pipelined processors? Explain with a simple example.
Example to include in the question:
ADD R1, R2, R3
SUB R4, R1, R5
Answer:
Data Dependence in Pipelined Processors
Data dependence occurs when one instruction depends on the result produced by
a previous instruction. In pipelined processors, multiple instructions are executed
simultaneously, so if the required data is not available on time, it creates a
problem called a data hazard.
For example:
ADD R1, R2, R3 // R1 = R2 + R3
SUB R4, R1, R5 // R4 = R1 - R5
Here, the second instruction (SUB) depends on the result of the first instruction
(ADD) because it needs the updated value of register R1. This is called Read After
Write dependence, which is the most common type of data dependence.
In a pipeline, the SUB instruction may try to read R1 before the ADD instruction
has completed its execution and written the result.
To handle this problem, techniques like:
Stalling (inserting bubbles)
Data forwarding
Question2:
What is name dependence? Explain with a simple example. Example to include in
the question:
ADD R1, R2, R3
MUL R1, R4, R5
Answer:
Name Dependence:
Name dependence occurs when two instructions use the same register name, but
there is no actual data transfer between them. The dependence is only due to the
reuse of the same register, not because one instruction needs the result of the
other.
Example:
ADD R1, R2, R3 // R1 = R2 + R3
MUL R1, R4, R5 // R1 = R4 * R5
Explanation:
Both instructions use the same destination register R1.
The first instruction writes a value to R1, and the second instruction also
writes a new value to R1.
The second instruction does not depend on the result of the first
instruction.
However, using the same register name creates a name dependence.
Types of Name Dependence:
1. WAW (Write After Write):
2. WAR (Write After Read):
Problem in Pipeline:
Instructions may execute out of order.
If not handled properly, the final value in the register may be incorrect.
Solution:
Register Renaming is used to remove name dependence by assigning
different registers.
Question 3:
What is control dependence in instruction execution? Explain with a simple
example. Example to include in the question:
BEQ R1, R2, L1
ADD R3, R4, R5
L1: SUB R6, R7, R8
Answer:
Control Dependence:
Control dependence occurs when the execution of an instruction depends on the
outcome of a previous branch instruction. In pipelined processors, this creates a
control hazard because the next instruction to execute is not known until the branch
condition is evaluated.
Example:
BEQ R1, R2, L1 // if R1 == R2, branch to L1
ADD R3, R4, R5 // next instruction execute or not
L1: SUB R6, R7, R8
Explanation:
The BEQ instruction checks whether R1 == R2.
If the condition is true, control jumps to label L1, and the SUB instruction
executes.
If the condition is false, the next sequential instruction ADD executes.
The execution of ADD and SUB depends on the result of the branch
instruction (BEQ).
This is called control dependence.
Problem in Pipeline:
The processor may fetch the next instruction (ADD) before knowing
whether the branch is taken or not.
This leads to control hazards and possible incorrect instruction execution.
Solutions:
Pipeline Stalling
Branch Prediction
Delayed Branching
Question 4:
What is loop unrolling? Explain with a simple example. Example code in the
question:
for(i = 0; i < 4; i++) {
A[i] = B[i] +C[i]; }
Answer:
Loop Unrolling:
Loop unrolling is an optimization technique in which the loop body is expanded
multiple times to reduce loop overhead and to improve pipeline performance.
Example:
for(i = 0; i < 4; i++) {
A[i] = B[i] + C[i];
}
Unrolled Version:
A[0] = B[0] + C[0];
A[1] = B[1] + C[1];
A[2] = B[2] + C[2];
A[3] = B[3] + C[3];
Explanation:
The loop runs 4 times.
Instead of executing loop control instructions (increment, condition check,
jump) every iteration, we expand the loop manually.
This removes loop overhead and allows better use of pipelining.
Advantages:
Reduces loop control overhead
Increases instruction-level parallelism
Improves pipeline efficiency
Disadvantages:
Increases code size
Not efficient for large loops
Question 5:
What is pipeline scheduling? Explain with a simple example. Rearrange the
instructions to reduce pipeline stalls. Example to include in the question:
LW R1, 0(R2)
ADD R3, R1, R4
SUB R5, R6, R7
Answer:
Pipeline Scheduling:
Pipeline scheduling is a technique used to reorder instructions in such a way that
pipeline stalls (delays) are minimized and processor performance is improved. The
goal is to keep all pipeline stages busy by avoiding hazards.
Example:
LW R1, 0(R2) // Load value into R1
ADD R3, R1, R4 // Uses R1 → data dependence
SUB R5, R6, R7 // Independent instruction
Problem (Without Scheduling):
ADD depends on LW (needs value of R1)
Load instruction takes time to fetch data from memory
So ADD must wait → pipeline stall (RAW hazard)
Rearranged (Scheduled) Instructions:
LW R1, 0(R2)
SUB R5, R6, R7 // Independent, placed in between
ADD R3, R1, R4
Explanation:
SUB does not depend on R1, so it can execute while LW completes
This avoids waiting time for ADD
Hence, pipeline remains busy and efficient