Prev
Home
Next
Suggestion Box
CPSC 418 --- Advanced Computer Architecture --- Spring 1996
Solution 11

Problem 1 (4 Points) Data Hazards

For each of the two pipelines below, specify whether it can have Read-After-Write, Write-After-Read, and Write-After-Write hazards. For each of the hazards that the pipeline can have, give an example code fragment illustrating the hazard. For each hazard that the pipeline can not have, explain why it can not have that hazard.

We will refer to first pipeline as the ``Simple'' pipe and the second pipeline as the ``Complex'' pipe.

RAW WAR WAW
Simple Y n n
Complex Y n Y

Simple: RAW (YES)
DLOAD (R1) R2 ADDx R2 R3 R4 ; RAW hazard on R2 Note: Without the Load/Store stage, this pipeline would not have to worry about RAW hazards, because the bypass path from EX would take care of all RAW data dependencies.
Simple: WAR (no)
All instructions fetch operands before subsequent instructions write results.
Simple: WAW (no)
All instructions write results in WriteBack and all instructions proceed through WB in program order.
Complex: RAW (YES)
DIVx R1 R2 R3 ADDx R3 R4 R5 ; RAW hazard on R3 Note: this pipeline can also have the same RAW hazard as Simple.
Complex: WAR (no)
All instructions fetch operands before subsequent instructions write results.
Complex: WAW (YES)
DIVx R1 R2 R3 ADDx R4 R5 R3 ; WAW hazard on R3

Problem 2 (9 Points) Register-Renaming and Interrupts

Given

MULx R1 R2 R3 ; A * B -> C
DIVx R3 R4 R5 ; C / D -> E
ADDx R2 R3 R4 ; B * C -> F
SUBx R2 R1 R2 ; B - A -> G

Problem 2(a) (5 Points)

Describe the state of the: when the divide-by-zero exception is raised

By analyzing the RAW dependencies in the code, we know that in order for the DIV to have begun execution, the ADD and SUB must have been able to read their operands. Given the number of reservations stations available, it is also almost guaranteed that they will have been able to begin execution as soon as their operands were available.

The DIV and ADD both have RAW dependencies on the result of the MUL. Thus, both DIV and ADD will begin execution at the same time. The SUB does not have any dependencies on the MUL, DIV, or ADD, so it will begin execution in the cycle after it is issue, which is one cycle after the ADD is issued. Thus the SUB will have completed long before the DIV and ADD begin execution.

Divide-by-zero exceptions are detected in the first execute cycle. Thus, when the divide-by-zero is detected, the ADD will be executing and the SUB will have finished.

Assuming the following restore values at time 0:
Arch Reg R1 R2 R3 R4 R5
Restore Value M N O P Q
The MUL, DIV, ADD, and SUB will write to consecutive Physical Registers. So, assuming the MUL mapped R3 to R2':

When the divide-by-zero is detected, R5, R4, and R2 will all be waiting for their results. From the information given in the problem, we can't tell the status of R1 and R3.

The only change in the restore values from the initial state is that the MUL has completed, putting C into R3.

Arch Reg R1 R2 R3 R4 R5
Valid/waiting -- w -- w w
Restore Value M N C P Q
Phys Reg R5' R4' R3'
The physical register for MUL be not-busy and valid, because it has completed. The physical registers for DIV and ADD will be busy and not-valid. The physical register for SUB will be busy and valid and will have the result of the SUB (G) in its value field.

Phys Reg R0' R1' R2' R3' R4' R5'
Busy n Y Y Y
Valid Y n n Y
Value G
PC 100210031004
Arch Reg R5 R4 R2
We don't have enough information about the rest of the program to say anything intelligent about the state of the reservation stations.

Problem 2(b) (4 Points)

Remembering that this machine supports precise exceptions, describe what happens when the divide-by-zero exception is raised.

When the divide-by-zero exception is raised, the CPU will:


Prev
Home
Next
Suggestion Box
Last modified: 01 Apr 96