Question 1: Data Dependence
ANSWER:
Data dependence, also known as
RAW (Read-After-Write) dependence, occurs when an instruction relies on the result of a
previous instruction to execute. In a pipelined processor, this is a challenge because the
second instruction might try to read a register before the first instruction has finished writing
the new value to it.
Example
1. ADD R1, R2, R3 (Calculates $R2 + R3$ and stores it in *R1*)
2. SUB R4, R1, R5 (Needs the value of *R1* to calculate $R1 - R5$)
In this case, the SUB instruction is data-dependent on the ADD instruction because it requires
the specific value produced by the first operation. If the pipeline doesn't use "forwarding," the
SUB instruction must wait (stall) until the ADD instruction reaches the Write-Back stage.
Question 2: Name Dependence
ANSWER:
Name dependence occurs when two instructions use the same register name, but there is no
actual flow of data between them. Unlike true data dependence, these instructions could
technically run in any order or simultaneously if we just renamed the registers. There are two
types:
Antidependence (WAR): Instruction B writes to a register that Instruction A reads.
Output dependence (WAW):Both instructions write to the same register.
Example (Output Dependence)
1. ADD R1, R2, R3 (Writes result to *R1*)
2. MUL R1, R4, R5 (Also writes result to *R1*)
There is no data flowing from the ADD to the MUL. The "dependence" exists only because
both instructions are using the "name" *R1. If the MUL finished before the ADD, the final
value in **R1* would be wrong.
Question 3: Control Dependence
ANSWER:
Control dependence (also called branch dependence) occurs when the execution of an
instruction is determined by the outcome of a previous conditional branch instruction. The
processor doesn't know whether to fetch the next instruction until the branch condition is
evaluated.
Example
1. BEQ R1, R2, L1 (If $R1 == R2$, jump to label *L1*)
2. ADD R3, R4, R5 (Only executes if the branch is *not* taken)
3. L1: SUB R6, R7, R8 (Executes regardless, but is the target of the jump)
The ADD instruction is control-dependent on the BEQ. The processor cannot safely execute
the ADD until it knows for sure that $R1$ does not equal $R2$.
Question 4: Loop Unrolling
ANSWER:
Loop unrolling* is an optimization technique where the loop body is replicated multiple
times to reduce the "overhead" of the loop (like incrementing the counter and checking the
branch condition). This also provides more opportunities for the processor to schedule
instructions efficiently.
Example Code
*Original:*
for (i = 0; i < 4; i++)
{
A[i] = B[i] + C[i];
}
Unrolled:
A[0] = B[0] + C[0];
A[1] = B[1] + C[1];
A[2] = B[2] + C[2];
A[3] = B[3] + C[3];
By unrolling, we eliminate the four branch checks and four increments of i, executing the
same logic in a straight line of code.
Question 5: Pipeline Scheduling
ANSWER:
*Pipeline scheduling* is the process of rearranging instructions to increase the distance
between dependent operations. This minimizes "bubbles" or stalls in the pipeline.
The Problem
1. LW R1, 0(R2) (Load value from memory into *R1*)
2. ADD R3, R1, R4 (*Stall!* Cannot use R1 until the load completes)
3. SUB R5, R6, R7 (Independent instruction)
In the original order, the ADD must wait for the LW to finish its memory access, causing a
stall.
The Rearranged Solution
By moving the independent SUB instruction between the LW and the ADD, we "fill" the stall
slot with useful work:
1. LW R1, 0(R2)
2. *SUB R5, R6, R7* (Executes while the hardware is still fetching R1)
3. ADD R3, R1, R4 (Now R1 is ready; no stall needed)