$\require{cancel}$

Parallelism vi Instructions

This is section 4.11
- "Be forewarned: this section is a brief overview of fascinating but advanced topics."
- This was essentially the entire Advanced Architecture course I took.
- It was cool as all get out.
Co-processors
- Floating point is slow and more complex than integer.
- See chapter 3.
- Early on they built a separate floating point co-processor.
- I bet, but don't know, that this lead to the following ideas.
Multiple-issue
- If we have sufficient hardware, could we execute two instructions at the same time?
- This is clearly true for int and floating point with a co-processor.
- Think of finding an average of the array.
- ```
set index to 0
set offset to 0
set sum to 0

beq index maxsize
    lw array[offset]   // integer operation
    add offset to sum  // floating point operation
    increment index
    increment offset
    b top 
```
- Note we could issue
  - line 7 to the fp unit which would probably take 3-5 cycles.
  - At the same time we could issue lines 8 and 9.
- In this case the floating point pipeline would be mostly empty.
- But in others it would be more full.
They have done studies.
- And you can classify integer instructions into two sets
  - For their example they classify ALU and branch instructions together.
  - And LW/SW in a separate case.
- Each instruction, we fetch a double word.
  - Hoping the compiler has packaged 1 instruction from each class in this double word.
  - We can execute these in parallel, assuming we have sufficient hardware.
  - And achieve a CPI of .5.
  - Look at the table on 347.
- They state that modern processors can have as many as 4 instructions per fetch.
- But this tends to make hazards worse
- And truly depends on the compiler.
- This is called static multiple issue.

One technique for filling such pipelines is to unroll loops

i = 0
while i < n
   //A[i] = A[i] + B[i]
      lw A[i]
      Add i 1

      lw B[i]
      nop 

      nop
      add A[i], B[i]

      sw A[i]
      add offset 4

Could become

while i < n
    lw A[i]  // with offset1
    addi i, 2

    lw B[i]
    addi offset2, 8

    lw A[i+1]  // we computed the new offset in previous instruction
    add A[i], B[i]

    lw B[i+1]  // with offset2
    nop

    sw A[i-2] // with offset1 
    add A[i+1], B[i+1]

    sw A[i-1]  // with offset2
    add offset1, 8

I haven't done this in a while and so you might be able to do better.
- Mixing the two load sequences better for example to overcome a load delay slot problem.
this is a pretty tight loop.
- Often you do more work inside a loop
- This would give you more instructions to move.

A better alternative is dynamic scheduling
- This involves multiple functional units.
- See the picture on page 352.
- A reservation station holds an instruction until
  - All required data is present
    - Some might not be ready when it is placed there.
  - It can be run through the functional unit.
- The commit unit
  - Handles any data forwarding needed to the reservation stations
  - Commits the data to the RF in the order needed to assure the same results as in order execution.
Speculation
- Some hardware will issue instructions from both sides of a branch
- And cancel the ones that are not needed.
As expected this creates more hazards and problems.
But ... re-look at the table on 357 again.
By the way, the picture on 358 shows a 8 stage pipeline.
By the way, memory delays become horrid problems here. We should look at that :)