Question

Computer Architecture

The format of this document is as follows: First, I give a practice problem for which the solution is also provided. In bold italic font, I slightly modify the problem for your homework.

3) The 4-Stage Pipeline below suffers from the memory access resource conflict as shown below (instruction i and i+2 want to access memory at the same time and i+2 needs to be denied, so it waits for the next cycle; in the next cycle it has a conflict with i+1 so it stalls for another cycle). Is it there any speedup due to pipelining?

[1] FI: Fetch an instruction from memory (500 ps)
[2] DA: Decode the instruction and calculate the effective address of the operand (400 ps)
[3] FO: Fetch the operand (500 ps)
[4] EX: Execute the operation (600 ps)

With one memory, a data and an instruction fetch cannot be initiated in the same clock FI DA FO EX i+1 i+2 stall stal FIDA FO EX The Pipeline is stalled for resource conflict Two-port memory can serve without stalls

HW PROBLEM 3: How would the speed up change if stage 4 completed in 500 ps?

SOLUTION:

If there were no conflicts after filling the pipeline, at every cycle, we would finish one instruction completed, this would be 4 times speedup if the pipeline stages took equal time. Because without multiple instructions in the pipeline, one instruction would complete in 4 clock cycles.

With the given stage latencies, without taking the memory conflict into account, the speedup would be 2000 / 600 » 3.33

Stalls reduce the speedup, to calculate how much, after filling the pipeline, note that we will have 2 stalls every 4 cycles, meaning that every 4 cycles we will have 2 instructions completed (a drawing can help to see the pattern). Thus, for an instruction to complete, in average, we need 2 cycles (two 600 ps cycles).

Speedup = 2000 / (2 x 600) » 1.66

Answer 1

If stage 4 completed in 500 ps Instruction fetch (IF) = 500 ps Decode the instruction = 400 ps Fetch the operand = 500 ps Execute the operation = (500 ps) offer modification Time take in Non pipe line = (500 + 400 + 500 + 500) ps = 1900 Time taken in Pipelined [in each one clock one instruction executed] = 500 Speed up = 1900/500 = 3.8 If there is two stall every 4 cycles then in every 4 cycles 2 instruction completed. One instruction needs = 2 clocks (cycle) Speed up = 1900/(2 times 500) = 1900/100 = 1.9