(10 points) In the programming assignment #1, even though the processor is an in-order processor,
it can cause WAW dependencies. Discuss when WAW dependencies can occur, and how can we solve this problem?
There are at least more than one solution.
Because of valid bits in the register file is only one bit, it can causes WAW Dependences.
Here is one example.
Assuming the following sequence of instructions:
ADD R1, R2, R3 // I1
SUB R1, R3, R4 // I2
MUL R3, R1, R5 // I3
| Cycle | valid bit register[1] | FE_stage_latch | ID_stage_latch | EX_stage_latch | MEM_stage_latch |
| 1 | 1 | ADD | xxx | xxx | xxx |
| 2 | 0 | SUB | ADD | xxx | xxx |
| 3 | 0 | MUL | SUB | ADD | xxx |
| 4 | 0 | MUL | xxx | SUB | ADD |
| 5 | 1 | | MUL | xxx | SUB |
At cycle 5, R1 register valid bit it set true by the ADD instruction. However, the MUL instruction should use the outcome of the SUB instruction.
This is a WAW dependency.
Possible solutions.
Solution 1: Check WAW dependence. If there is WAW dependence, it stalls the pipeline.
Solution 2: Before an instruction sets a valid bit in the WB stage, the processor checks the destination register ids of instructions in the MEM/EX stage instructions.
If destination register ids are the same, the processor does not set the valid bit to true.
Solution 3: A reference counter. Whenever there is a write to a register, it increments the counter and when the processor writes a result into the register file it decrements the counter. It sets the valid bit as true only if the reference counter value is 0.
[4-5]
A graduate student, Mary, likes drinking coffee. She drinks coffee every day. She wrote a simple program to decide which coffee shop to go every day.
Here is the code. (to simplify the problem, we assume that Mary drinks coffee only Th,F, Sa and Sunday)
class date_c{
public:
void get_coffee();
};
class weekday_c: public date_c{
public:
void get_coffee();
}
class saturday_c:public date{
public:
void get_coffee();
}
class sunday_c:public date{
public:
void get_coffee();
}
void TutoTh_c::get_coffe(){
// beginning of the function body starts at 0x800
If (time >= 7 am && time < 8 am) printf("go to Seattle's Best\n"); // br: pc 0x801
else if (time >= 8 am && time < 1pm ) printf ("go to CCB \n"); // br: pc 0x807
else if (time < 6 pm ) printf ("go to IIB \n"); // br: pc 0x80a
else if (time <=10 pm) printf("go to StarBucks\n"); // br: pc 0x815
else printf("sorry. No more coffee\n");
}
void MF_c::get_coffe(){
// beginning of the function body starts at 0x820
If (time >= 7 am && time < 8 am) printf("go to Seattle's Best\n"); // br: pc 0x821
else if (time >= 8 am && time < 1pm ) printf ("go to CCB \n"); // br: pc 0x827
else if (time < 5 pm ) printf ("go to IIB \n"); // br: pc0x82a
else if (time <=10 pm) printf("go to StarBucks\n"); // br: pc 0x825
else printf("sorry. No more coffee\n");
}
void Sa_c::get_coffee() {
// beginning of the function body starts at 0x900
if (time >= 7 am && time < 10 pm) printf(\"go to Starbucks \n"); // br: pc 0x902
else printf("sorry, No more coffee\n");
}
void Su_c::get_coffee(){
// beginning of the function body starts at 0xa00
if (time> =10 am && time < 6 pm) printf("go to Starbucks \n"); // br: pc 0xa03
else printf("sorry, No more coffee\n");
}
main()
{
// initial code. // week array is initialized
for (today= Thursday ; today <= Sunday; today++) { // br: pc 0x100 : NT: Loop exit
date_c *data = week[today];
for (time = 7 am ; time < 5 pm; time = time + 6) { // br: pc 0x102, NT Loop exit
date->get_coffee(); // indirect branch at PC 0x110
}
}
Assumptions:
- To simplify the problem, we assume that multiple condition branches are handled by only one branch. i.e,
if (time > 7 am && time < 10 pm) correspond to only one branch.
- today is incremented from Th, F, Sa to Su.
each day data->get_coffee calls a different function.
Th : TutoTh_c::get_coffee
F: MF_c::get_coffee
Sa: Sa_c::get_coffee
Su: Su_c::get_coffee