• 30 Nov 2023: be explicit about assumption that previous register values andphysical registers are available for part 3.
  • 1 Dec 2023: be explicit that when fewer instructions are available to issue, as many as possible are issued; be explicit about the register values read/forwarded in issue being the input ones

Hypothetical OOO processor

For this assignment, we will consider an out-of-order processor which has two execution units for arithmetic instructions, and one execution unit for memory instructions.

This Processor’s Pipeline

Instructions in this processor are executed as follows:

Given these stages, an non-memory instruction will take 7 cycles to go through the pipeline if it does not need to wait for it operands or wait for earlier instructions to commit (fetch, decode, rename, issue/register read, execute, writeback, commit). A memory instruction will take 9 cycles (two extra cycles of `execution’ because of the speed of the data cache).

When operands are not available, an instruction will spend extra cycles waiting in the instruction queue between its rename and issue stage. When an instruction is written back but some prior instructions have not done so, then the instruction will spend extra cycles waiting in the reorder buffer before it is committed.

This processor’s registers

The processor has 15 logical registers %r01 through %r15, but these are implemented using 64 physical registers and register renaming. We call the physical registers %x01 through %x64.

We will show instructions in a three-argument form like (regardless of whether register renaming has taken place):

add %r01, %r02 -> %r03

this indicates to add %r01 and %r02 and put the result into %r03.

Answer the questions on this answer sheet.

Part 1: register renaming

Assume initially that %r01 is assigned to %x01, %r02 to %x02, and so on. Registers %x16 through %x63 are available for register renaming.

Rewrite the following instructions using the %x01 taking into account how register renaming might occur that would allow all of these instructions to be placed in the instruction queue at once:

add %r01, %r01 -> %r01
add %r02, %r01 -> %r01
add %r03, %r01 -> %r01
add %r04, %r01 -> %r01
movq 0x1234(%r05) -> %r02
imul %r02, %r03 -> %r03
movq 0x1234(%r06) -> %r03
imul %r02, %r04 -> %r04

Record your answer at the answer sheet linked above.

Part 2: instruction dispatch

Suppose the instruction queue for this processor contains the following instructions after renaming:

A. add %x05, %x06 -> %x16
B. sub %x16, %x07 -> %x17
C. movq 0x100(%x05) -> %x18
D. imul %x17, %x09 -> %x19
E. add %x05, %x07 -> %x20
F. sub %x18, %x07 -> %x21
G. add %x20, %x19 -> %x22
H. movq 0x200(%x22) -> %x23
I. imul %x08, %x16 -> %x24

Initially the value of registers %x01 through %x15 is available.

Complete the timeline to show how all the instructions can be issued and executed:

                cycle 1    2    3   4    5    6   7
execution unit:       
arithmetic 1          A
arithmetic 2          E
memory stage 1        C
memory stage 2             C
memory stage 3                  C

Record your answer at the answer sheet linked above.

Part 3: pipeline diagram

Complete a pipeline diagram for the processor running the following instructions (shown in the form from before register renaming):

1. add %r01, %r01 -> %r01
2. add %r02, %r03 -> %r03
3. add %r04, %r05 -> %r05
4. add %r05, %r01 -> %r01
5. add %r01, %r01 -> %r01
6. add %r04, %r05 -> %r05
7. add %r02, %r04 -> %r04

Identify the stages as:

Leave the specified stage blank when an instruction is not being processed in any of the above ways (such as when the instruction is in the instruction queue waiting to be issued or any cycles between when an instruction is written back and when it is committed).

The first three rows are:

1 F D R I E W C
2 F D R I E W C
3   F D R I E W C

complete the remaining rows of the table at the answer sheet linked above.

You may assume that register values computed by previous instructions are available and that physical registers are free such that stages will not be delayed for missing previous register values or lack of available physical registers.