In this exercise, we will look at how variations on Tomasulo’s algorithm perform when running the loop from Exercise 3.14. The functional units (FUs) are described in the following table.

Assume the following:
■ Functional units are not pipelined.
■ There is no forwarding between functional units; results are communicated by the common data bus (CDB).
■ The execution stage (EX) does both the effective address calculation and the memory access for loads and stores. Thus, the pipeline is IF/ID/IS/EX/WB.
■ Loads require one clock cycle.
■ The issue (IS) and write-back (WB) result stages each require one clock cycle.
■ There are five load buffer slots and five store buffer slots.
■ Assume that the Branch on Not Equal to Zero (BNEZ) instruction requires one clock cycle.

a. For this problem use the single-issue Tomasulo MIPS pipeline of Figure 3.10 with the pipeline latencies from the preceding table. Show the number of stall cycles for each instruction and what clock cycle each instruction begins execution (i.e., enters its first EX cycle) for three iterations of the loop.
How many cycles does each loop iteration take? Report your answer in the form of a table with the following column headers:
■ Iteration (loop iteration number)
■ Instruction

■ Issues (cycle when instruction issues)
■ Executes (cycle when instruction executes)
■ Memory access (cycle when memory is accessed)
■ Write CDB (cycle when result is written to the CDB)
■ Comment (description of any event on which the instruction is waiting)
Show three iterations of the loop in your table. You may ignore the first instruction.

b. [20] Repeat part (a) but this time assume a two-issue Tomasulo algorithm and a fully pipelined floating-point unit (FPU).

Transcribed Image Text:

Cycles in EX FU type Integer FP adder 1 10 FP multiplier 15 Number of FUS 1 1 1 Number of reservation stations 5 3 2