Computer composition and design work06 - based on MIPS

4.9

In this exercise, we examine how data dependences aff ect execution in the
basic 5-stage pipeline described in Section 4.5. Problems in this exercise refer to the
following sequence of instructions:

    or r1,r2,r3
    or r2,r1,r4
    or r1,r1,r2

Also, assume the following cycle times for each of the options related to forwarding:

Without Forwarding	With Full Forwarding	With ALU-ALU Forwarding Only
250ps	300ps	290ps

1

[10] <§4.5> Indicate dependences and their type

Mark the three instructions as ①②③

1. R1 Need to complete in ① The correct value can only be obtained after the write operation ② and ③, So there will be RAW stall
2. R2 stay ② Only after writing can we tell the correct result to ③, There will be RAW stall
3. R2 stay ① It is necessary to load out the data in the ② When loading registers , produce WAR stall
4. R1 stay ② After being loaded out, it should be in ③ When loading registers , produce WAR stall
5. R1 stay ① After loading , stay ③ There are also loads , produce WAW stall

2

[10] <§4.5> Assume there is no forwarding in this pipelined processor. Indicate hazards and add nop instructions to eliminate them.

WAR and WAW dependence No risk . In the absence of forwarding Under the circumstances , Any primitive between one instruction and the next two instructions dependence（ Register writing occurs in the first half , General register reading occurs in the second half of the clock cycle —— That is to say RAW operation ） By inserting NOP Instructions ( Empty operation ) these hazard The code for is as follows

    or r1,r2,r3
    NOP
    NOP
    or r2,r1,r4
    NOP
    NOP
    or r1,r1,r2

3

[10] <§4.5> Assume there is full forwarding. Indicate hazards and add NOP
instructions to eliminate them.

If there is full forwarding, ALU The instruction can pass the value before the next instruction EX The stage does not produce hazard. It should be noted that ：load The relevant value cannot be passed to the next instruction EX Stage . The code is as follows

    or r1,r2,r3
    or r2,r1,r4 #  No, RAW hazrad
    or r1,r1,r2

4

[10] <§4.5> What is the total execution time of this instruction sequence
without forwarding and with full forwarding? What is the speedup achieved by adding full forwarding to a pipeline that had no forwarding?

Total execution time $whenThe\; clockZhouperiodwhenbetween\times ZhouperiodCount$( barring stall Time for )
The three instruction sequence has five cycles （1 An instruction 5 A cycle , Add one instruction for one more cycle ）
No, forwarding Reference resources 4.9.2
Yes forwarding Reference resources 4.9.3

no forward
$$(7+4)\times 250=2750$$
forwarding
$$7\times 300=2100$$

no forwarding	full forwarding
2750ps	2100ps

Speedup ratio
$$2750/2100=1.3095$$

5

[10] <§4.5> Add nop instructions to this code to eliminate hazards if there
is ALU-ALU forwarding only (no forwarding from the MEM to the EX stage).

ALU-ALU-only forwarding, ALU Instructions can be passed to the next instruction before , But it cannot be transmitted to the next instruction ( Otherwise it would not be ALU forwarding 了 , It's just plain forwarding—— from MEM To EX) load Instructions cannot be passed forward ( Because you need to MEM Stage to determine the data of the register , This is for ALU-forwarding It's too late for the operation )

    or r1,r2,r3
    or r2,r1,r4 #  Yes ① Of R1 Conduct  ALU-ALU forwarding
    or r1,r1,r2 #  Yes ② Of R2 Conduct ALU-ALU forwarding

6

[10] <§4.5> What is the total execution time of this instruction sequence
with only ALU-ALU forwarding? What is the speedup over a no-forwarding
pipeline?

$$7\times 290=2030$$
$$2750/2030=1.354$$

4.11

Consider the following loop.

    loop:lw r1,0(r1)
    and r1,r1,r2
    lw r1,0(r1)
    lw r1,0(r1)
    beq r1,r0,loop 

Assume that perfect branch prediction is used (no stalls due to control hazards),
that there are no delay slots, and that the pipeline has full forwarding support. Also
assume that many iterations of this loop are executed before the loop exits.

1

[10] <§4.6> Show a pipeline execution diagram for the third iteration of
this loop, from the cycle in which we fetch the fi rst instruction of that iteration up
to (but not including) the cycle in which we can fetch the fi rst instruction of the
next iteration. Show all instructions that are in the pipeline during these cycles (not
just those from the third iteration).

From the beginning of the first instruction of the loop to the first instruction of the next loop （ This value is not included ） end , Give all the instructions of the pipeline

                        1   2   3   4   5   6   7   8
    lw r1,0(r1)         WB
    lw r1,0(r1)         EX  MEM WB
    beq r1,r0,loop      ID  ... EX  MEM WB  
    
    lw r1,0(r1)         IF  ... ID  EX  MEM WB
    and r1,r1,r2                IF  ID  ... EX  MEM WB
    lw r1,0(r1)                     IF  ... ID  EX  MEM
    lw r1,0(r1)                             IF  ID  ...
    beq r1,r0,loop                              IF  ...

here beq Whether you jump or not , Go to the next one first instruction（ Jump is not performed by default ）, But no instruction 了 , It becomes bubble 了 , So the following and The operation is following bubble After that, I started to talk with lw have to ID Phases operate simultaneously

2

[10] <§4.6> How oft en (as a percentage of all cycles) do we have a cycle in which all fi ve pipeline stages are doing useful work?

In a particular clock cycle , If a stage of the pipeline is suspended or the instructions in that stage do not do any effective work , The assembly line doesn't do any useful work .

In the pipeline execution diagram drawn above ： Because if the name is not displayed for a specific period （ Also is to use … Represented part ）, Pipeline pause , as well as BEQ Of WB and AND Of MEM Have not done effective work . It should be noted that ,BEQ Instruction in MEM Stage is doing useful work , Because it is determining the next instruction at that stage PC The correct value of ,

To sum up, this 8 None of the instructions worked effectively at all stages , All exist bubble

The answer for $0\%$

4.12

4.12 Th is exercise is intended to help you understand the cost/complexity/
performance trade-off s of forwarding in a pipelined processor. Problems in this
exercise refer to pipelined datapaths from Figure 4.45. Th ese problems assume
that, of all the instructions executed in a processor, the following fraction of these
instructions have a particular type of RAW data dependence. Th e type of RAW
data dependence is identifi ed by the stage that produces the result (EX or MEM)
and the instruction that consumes the result (1st instruction that follows the one
that produces the result, 2nd instruction that follows, or both). We assume that the
register write is done in the fi rst half of the clock cycle and that register reads are
done in the second half of the cycle, so “EX to 3rd” and “MEM to 3rd” dependences
are not counted because they cannot result in data hazards. Also, assume that the
CPI of the processor is 1 if there are no data hazards.

EX to 1st Only	MEM to 1st Only	EX to 2nd Only	MEM to 2nd Only	EX to 1st and MEM to 2nd	Other RAW Dependences
5%	20%	5%	10%	10%	10%

Assume the following latencies for individual pipeline stages. For the EX stage,
latencies are given separately for a processor without forwarding and for a processor
with diff erent kinds of forwarding.

IF	ID	EX(no FW)	EX(full FW)	EX (FW from EX/MEM only)	EX (FW from MEM/WB only)	MEM	WB
150 ps	100 ps	120 ps	150 ps	140 ps	130 ps	120 ps	100 ps

1

[10] <§4.7> If we use no forwarding, what fraction of cycles are we stalling
due to data hazards?

Dependency on the next instruction results in 2 Pause cycles , If the dependency exists simultaneously with the first and second instructions in the future , It's also a pause 2 A cycle . Relying only on the next instruction will result in 1 Pause cycles

of 1st Of
$$0.05+0.2+0.1=0.35$$
Just about 2nd Of
$$0.05+0.1=0.15$$
$$CPI=1+0.35\times 2+0.15\times 1=1.85$$
stall cycles =$0.85/1.85=46\%$

2

[5] <§4.7> If we use full forwarding (forward all results that can be
forwarded), what fraction of cycles are we staling due to data hazards?

If it is delivered before use , Only RAW Data dependency ( The next instruction depends on MEM Stage ) Will cause a cycle to pause

MEM The next instruction only accounts for 20%
$$CPI=1+0.2\times 1=1.2$$
stall cycle
$$0.2/1.2=17\%$$

3

4.12.3 [10] <§4.7> Let us assume that we cannot aff ord to have three-input Muxes
that are needed for full forwarding. We have to decide if it is better to forward
only from the EX/MEM pipeline register (next-cycle forwarding) or only from
the MEM/WB pipeline register (two-cycle forwarding). Which of the two options
results in fewer data stall cycles?

Only right EX/MEM If the register is passed before ,EX The pause cycle to the next instruction can be avoided , But other dependencies cannot be avoided , Will cause a pause period （ about MEM TO 1st Even two pause cycles ）.

Only right MEM/WB If the register is passed before , EX In the future, the second instruction dependency will not generate a pause cycle , and MEM A dependency on the next instruction will still produce a stall cycle ,EX It will also cause a pause cycle since the next instruction （ Because we have to wait for the instructions to be completed MEM Only stage operations can be submitted before ）

EX to 1st Only	MEM to 1st Only	EX to 2nd Only	MEM to 2nd Only	EX to 1st and MEM to 2nd	Other RAW Dependences
5%	20%	5%	10%	10%	10%

BTW, Here it is calculated according to the frequency of occurrence （ percentage ）, In order to facilitate the calculation of question 6
And don't think about the last one RAW

EX/MEM
$$0.2+0.05+0.1+0.1=0.45$$

MEM/WB
$$0.05+0.2+0.1=0.35$$

Obviously the latter produces fewer pause cycles

4

4.12.4 [10] <§4.7> For the given hazard probabilities and pipeline stage latencies,
what is the speedup achieved by adding full forwarding to a pipeline that had no
forwarding?

No bypass
$$1.85\times 120=222$$

There's a bypass
$$1.2\times 150=180$$

Speed up
$$222/180=1.23$$

5

4.12.5 [10] <§4.7> What would be the additional speedup (relative to a processor
with forwarding) if we added time-travel forwarding that eliminates all data
hazards? Assume that the yet-to-be-invented time-travel circuitry adds 100 ps to
the latency of the full-forwarding EX stage.

Time travel
$$1\times 250=250$$
Originally EX Stage complete bypass
$$180$$

Speedup ratio
$$180/250=0.72$$

6

4.12.6 [20] <§4.7> Repeat 4.12.3 but this time determine which of the two
options results in shorter time per instruction

EX/MEM
$$1.45\times 140=203$$

MEM/WB
$$1.35\times 130=175.5$$
Obviously the latter

4.13.1-3

4.13 Th is exercise is intended to help you understand the relationship between
forwarding, hazard detection, and ISA design. Problems in this exercise refer to
the following sequence of instructions, and assume that it is executed on a 5-stage
pipelined datapath:

    add r5,r2,r1
    lw r3,4(r5)
    lw r2,0(r2)
    or r3,r5,r3
    sw r3,0(r5)

1

4.13.1 [5] <§4.7> If there is no forwarding or hazard detection, insert nops to
ensure correct execution.

    add r5,r2,r1
    NOP         #RAW To pause for two Cycle
    NOP
    lw r3,4(r5)
    lw r2,0(r2)
    NOP         # We were supposed to pause for two Cycle, But this r3 In the second instruction, so only one is suspended 
    or r3,r5,r3
    NOP
    NOP
    sw r3,0(r5)

2

4.13.2 [10] <§4.7> Repeat 4.13.1 but now use nops only when a hazard cannot be
avoided by changing or rearranging these instructions. You can assume register R7
can be used to hold temporary values in your modifi ed code.

add r5,r2,r1
    lw r2,0(r2)
    NOP
    lw r3,4(r5)
    NOP
    NOP         
    or r3,r5,r3
    NOP
    NOP
    sw r3,0(r5)

Because there is no WAW and WAR rely on , therefore R7 Not used

3

4.13.3 [10] <§4.7> If the processor has forwarding, but we forgot to implement
the hazard detection unit, what happens when this code executes?

No risk detection unit will result in load Operate on Time Travel Adventures , It will let the register pass the old data to the subsequent branches in advance

but 4.13 This code can be executed correctly

4.14.1-2

4.14 Th is exercise is intended to help you understand the relationship between
delay slots, control hazards, and branch execution in a pipelined processor. In
this exercise, we assume that the following MIPS code is executed on a pipelined
processor with a 5-stage pipeline, full forwarding, and a predict-taken branch
predictor:

        lw r2,0(r1)
    label1: beq r2,r0,label2 # not taken once, then taken
        lw r3,0(r2)
        beq r3,r0,label1 # taken
        add r1,r3,r1
    label2: sw r1,0(r2)

1

4.14.1 [10] <§4.8> Draw the pipeline execution diagram for this code, assuming
there are no delay slots and that branches execute in the EX stage.

No delay time slot and move to EX Level execution branch
Each time the time jump is delayed by one cycle, And if it's RAW It will have to be put off until EX end

                    1   2   3   4   5   6   7   8   9   10  11  12  13  14  
lw r2,0(r1)         IF  ID  EX  MEM WB
beq r2,r0,label2        IF  ID  ... EX  MEM WB
lw r3,0(r2)                             IF  ID  EX  MEM WB
beq r3,r0,label1                            IF  ID  ... EX  MEM WB
beq r2,r0,label2                                    IF  ... ID  EX  MEM WB
sw r1,0(r2)                                             IF  ID  EX  MEM WB

2

4.14.2 [10] <§4.8> Repeat 4.14.1, but assume that delay slots are used. In the
given code, the instruction that follows the branch is now the delay slot instruction
for that branch.

Use delay time slots , The instruction that follows the branch is the delay slot instruction

                    1   2   3   4   5   6   7   8   9   10  11  12  13  14  
lw r2,0(r1)         IF  ID  EX  MEM WB
beq r2,r0,label2        IF  ID  ... EX  MEM WB
lw r3,0(r2)                 IF  ... ID  EX  MEM WB
beq r3,r0,label1                        IF  ID  EX  MEM WB
add r1,r3,r1                                IF  ID  EX  MEM WB
    # Let's assume no jump , Execute first add
beq r2,r0,label2                                IF  ID  EX  MEM WB
lw  r3,0(r2)                                        IF  ID  EX  MEM WB      
    # ditto 
sw r1,0(r2)                                             IF  ID  EX  MEM WB

5

4.14.5 [10] <§4.8> For the given code, what is the speedup achieved by moving
branch execution into the ID stage? Explain your answer. In your speedup
calculation, assume that the additional comparison in the ID stage does not aff ect
clock cycle time

Take branch to ID The icon of is as follows

                    1   2   3   4   5   6   7   8   9   10  11  12  13  14  15
lw r2,0(r1)         IF  ID  EX  MEM WB
beq r2,r0,label2        IF  ... ... ID  EX  MEM WB
lw r3,0(r2)                             IF  ID  EX  MEM WB
beq r3,r0,label1                            IF  ... ... ID  EX  MEM WB
beq r2,r0,label2                                        IF  ... ID  EX  MEM WB
sw r1,0(r2)                                                 IF  ID  EX  MEM WB

The speedup is ：
$$14/15=0.93$$

4.15.1-3

Th e importance of having a good branch predictor depends on how oft en
conditional branches are executed. Together with branch predictor accuracy, this
will determine how much time is spent stalling due to mispredicted branches. In
this exercise, assume that the breakdown of dynamic instructions into various
instruction categories is as follows:

R-Type	BEQ	JMP	LW	SW
40%	25%	5%	25%	5%

Also, assume the following branch predictor accuracies:

Always-Taken	Always-Not-Taken	2-Bit
45%	55%	85%

1

[10] <§4.8> Stall cycles due to mispredicted branches increase the
CPI. What is the extra CPI due to mispredicted branches with the always-taken
predictor? Assume that branch outcomes are determined in the EX stage, that there
are no data hazards, and that no delay slots are used.

Incorrect predicted branches can lead to 3 Cycle pauses
According to the data , The corresponding non occurrence prediction is 55%, And there are 25% Branch judgment of

$$3\times 0.55\times 0.25=0.41$$

2

[10] <§4.8> Repeat 4.15.1 for the “always-not-taken” predictor
The reverse is 45%

$$3\times 0.45\times 0.25=0.34$$

3

[10] <§4.8> Repeat 4.15.1 for for the 2-bit predictor.

The corresponding probability of failure to predict success is 1-0.85
$$3\times (1-0.85)\times 0.25=0.7375$$

6

[10] <§4.8> Some branch instructions are much more predictable than
others. If we know that 80% of all executed branch instructions are easy-to-predict
loop-back branches that are always predicted correctly, what is the accuracy of the
2-bit predictor on the remaining 20% of the branch instructions?

1. The prediction accuracy is 0.85
2. Among them is 0.8 It's easy to predict , Subtract to get the rest 20% Among the correct predictions are 5%
3. The formula is $0.05/0.20=25\%$

4.16.1-3

Th is exercise examines the accuracy of various branch predictors for the
following repeating pattern (e.g., in a loop) of branch outcomes: T, NT, T, T, NT

1

4.16.1 [5] <§4.8> What is the accuracy of always-taken and always-not-taken
predictors for this sequence of branch outcomes?

NT Proportion
$$2/5=40\%$$
T Proportion
$$3/5=60\%$$

2

4.16.2 [5] <§4.8> What is the accuracy of the two-bit predictor for the fi rst 4
branches in this pattern, assuming that the predictor starts off in the bottom left
state from Figure 4.63 (predict not taken)?

At first it was 4-63 Lower left corner status
that

1. The forecast did not occur , For the first time T, Turn into 4-63 The lower right state , error
2. The forecast did not occur , The second time is NT, Turn into 4-63 Lower left corner status , correct
3. The forecast did not occur , The third time is T, Turn into 4-63 The lower right state , error
4. The forecast did not occur , The fourth time is T, Turn into 4-63 Top right state , error

accuracy
$$1/4=25\%$$

3

4.16.3 [10] <§4.8> What is the accuracy of the two-bit predictor if this pattern is
repeated forever?

Each cycle

1. The lower left , The lower right , The lower left , The lower right , The upper right
2. The lower right , The upper right , The lower right , The upper right , Top left
3. The upper right , Top left , The upper right , Top left , Top left
4. The upper right , Top left , The upper right , Top left , Top left

From 3 The second cycle begins , The state is fixed on the top right , Top left , The upper right , Top left , The upper left , Accuracy rate is
$$3/5=60\%$$

4.18

In this exercise we compare the performance of 1-issue and 2-issue
processors, taking into account program transformations that can be made to
optimize for 2-issue execution. Problems in this exercise refer to the following loop
(written in C):

for(i=0;i!=j;i+=2)
    b[i]=a[i]–a[i+1];

When writing MIPS code, assume that variables are kept in registers as follows, and
that all registers except those indicated as Free are used to keep various variables,
so they cannot be used for anything else.

i	j	a	b	c	Free
R5	R6	R1	R2	R3	R10, R11, R12

1

4.18.1 [10] <§4.10> Translate this C code into MIPS instructions. Your translation
should be direct, without rearranging instructions to achieve better performance.

        add     r5,r0,r0
loop:   beq     r5,r6,flag
        slli    r12,r5,2    # Here I think of it as int Type array 
                            # If it is a string, put slli Remove it 
        add     r10,r1,r12  #a[i] The address of , The default is string r12 in r5  
        lw      r11,0(r10)
        lw      r10,4(r10)  
        sub     r10,r11,r10 
        add     r11,r12,r2  #b[i] The address of , Ibid 
        sw      r10,0(r11)
        addi    r5,r5,2
flag:

2

4.18.2 [10] <§4.10> If the loop exits aft er executing only two iterations, draw a
pipeline diagram for your MIPS code from 4.18.1 executed on a 2-issue processor
shown in Figure 4.69. Assume the processor has perfect branch prediction and can
fetch any two instructions (not just consecutive instructions) in the same cycle.

Here, for the convenience of drawing, I still default that this is char Array bar ...

3

4.18.3 [10] <§4.10> Rearrange your code from 4.18.1 to achieve better
performance on a 2-issue statically scheduled processor from Figure 4.69.

Default here char Array

        add r5,r0,r0
loop:   add r10,r5,r1
        beq, r5,r6,flag
        lw r11,0(r10)
        add r12,r5,r2
        lw r10,1(r10)
        addi r5,r5,2
        sub r10,r11,r10
        sw r10,0(r12)
        beq r0,r0 loop
flag:

4

4.18.4 [10] <§4.10> Repeat 4.18.2, but this time use your MIPS code from 4.18.3.

5

4.18.5 [10] <§4.10> What is the speedup of going from a 1-issue processor to
a 2-issue processor from Figure 4.69? Use your code from 4.18.1 for both 1-issue
and 2-issue, and assume that 1,000,000 iterations of the loop are executed. As in
4.18.2, assume that the processor has perfect branch predictions, and that a 2-issue
processor can fetch any two instructions in the same cycle.

Single emission processor ：
Every time 9 Instructions take up 10 Cycle , So because of the data risk , There is a between LW and SUB Pipeline pauses the loop

$$10/9=1.11$$

Dual transmit processors
18 Instructions occupy 19 Cycle
Two LW An instruction can be paralleled with another subsequent instruction ,SUB Rely on the second LW Instructions , So it produces a SUB Pause , but SUB above ADDI Unaffected
$$19/19=1.05$$

$$1.11/1.05=1.34$$

6

4.18.6 [10] <§4.10> Repeat 4.18.5, but this time assume that in the 2-issue
processor one of the instructions to be executed in a cycle can be of any kind, and
the other must be a non-memory instruction.

If the other must be a non access instruction
Then I would have 4.18.5 Medium ADDI and BEQ Will be placed in the second iteration in , the second LW Cannot be paralleled with other operations , Eventually lead to every 18 Instructions occupy 15 individual cycle

$$15/19=0.83$$

speedup

$$1.11/0.83=1.34$$