CS 3330: HCL2D part 8: Final homework

This page is for a prior offering of CS 3330. It is not up-to-date.

In the previous HW you pipelined nop, halt, irmovq, rrmovq, OPq and cmovXX. In lab you pipelined rmmovq and mrmovq (if you didn’t finish, we have posted an example solution). To finish your pipelined simulator, you need to combine those two and then add jXX, pushq, popq, call, and ret.

1 Approach

You may approach this however you wish, but I suggest the following flow:

  1. Combine your pipehw1.hcl and pipelab2.hcl and test the combination.
  2. Add jXX with speculative execution and branch misprediction recovery. Predict that all branches are taken. Test.
  3. Add pushq and test.
  4. Add call and test.
  5. Add popq and test.
  6. Add ret with handling for the return hazard, and test.

1.1 Combine and Test

All of the tests that either source file passed ought to still pass the combination.

1.2 jXX

This one is messy because we have branch prediction, speculative execution, and recovery from misprediction through stage bubbling. Let’s look at through a set of questions

What are we predicting?

That all jXX are taken (i.e., that the new PC is valC for all jXX).

How do we store that prediction?

In a predPC register inside the xF register bank (or pP or whatever else you called it).

How do we speculatively execute based on that prediction?

By setting the pc to the predicted PC (pc = F_predPC).

When would our prediction be wrong?

If the condition codes evaluate to false.

When would we learn that our prediction was wrong?

At the end of the jXX’s execute stage (which is when we check the condition codes).

We need to know at the beginning of Fetch…

End of execute = beginning of memory, so we can look in the M_... register bank outputs.

How should we react to misprediction?

We need to fetch the correct address (jXX’s valP) and bubble any stages that we should not have run.

Which stages get bubbled?

Since jXX is in memory, we keep that one (and writeback, which is a pre-jXX instruction); since we are fixing fetch we keep that one too; so we bubble just the decode and execute stages.

How do we fetch the correct address?

By using a mux to pick pc

What is the mux conditions?

mispredicted: oldValP and 1: F_predPC

  1 2 3 4 5 6 7  
jXX F D E (available) M W  
wrong1 F D (needed)  
wrong2 F (needed)  
right1 F D E M W
  1. Add a predicted PC to the xF register bank
  2. Predict all branches as taken: valP for a non-jump, valC for a jump.
  3. Set the pc to

1.3 pushq and popq

Like an rmmovq or mrmovq except you use REG_RSP not rB and ±8 not valC. Also has a writeback component for REG_RSP.

Note that popq updates two registers, so it will need both reg_dstE and reg_dstM.

Note that popq reads from the old %rsp while pushq writes to the new %rsp.

1.3.1 call and ret

call 0x1234 is push valP; jXX 0x1234. Combining the logic of push and unconditional jump should be sufficient.

ret is jump-to-the-read-value-when-popping. It always encounters the ret-hazard:

  1 2 3 4 5 6 7 8  
ret F D E M (available) W  
??? F F F (needed) F D E M W

You’ll have to stall the fetch stage as long as a ret is in decode, execute, or memory and forward the value from W_valM to the pc.

2 Testing your code

2.1 Same Semantics

Your code should have the same semantics as tools/yis: set the same registers and memory

2.2 More cycles

As a general rule, your pipelined processor will need

2.3 Examples

2.3.1 jXX


    irmovq $3, %rax
    irmovq $-1, %rbx
    jmp b
    jge a
    addq %rbx, %rax
    jmp c

takes 25 cycles and leaves

| RAX: ffffffffffffffff   RCX:                0   RDX:                0 |
| RBX: ffffffffffffffff   RSP:                0   RBP:                0 |

A full trace is available as pipe-jxx.txt

2.3.2 pushq


irmovq $3, %rax
irmovq $256, %rsp
pushq %rax

takes 8 cycles and leaves

| RAX:                3   RCX:                0   RDX:                0 |
| RBX:                0   RSP:               f8   RBP:                0 |

| used memory:   _0 _1 _2 _3  _4 _5 _6 _7   _8 _9 _a _b  _c _d _e _f    |
|  0x000000f_:                              03 00 00 00  00 00 00 00    |

A full trace is available as pipe-push.txt

2.3.3 popq


irmovq $4, %rsp
popq %rax

takes 7 cycles and leaves

| RAX:  fb0000000000000   RCX:                0   RDX:                0 |
| RBX:                0   RSP:                c   RBP:                0 |

A full trace is available as pipe-pop.txt

2.3.4 call


    irmovq $256, %rsp
    call a
    addq %rsp, %rsp

takes 7 cycles and leaves

| RBX:                0   RSP:               f8   RBP:                0 |

| used memory:   _0 _1 _2 _3  _4 _5 _6 _7   _8 _9 _a _b  _c _d _e _f    |
|  0x000000f_:                              13 00 00 00  00 00 00 00    |

A full trace is available as pipe-call.txt

2.3.5 ret


    irmovq $256, %rsp
    irmovq a, %rbx
    rmmovq %rbx, (%rsp)
    irmovq $258, %rax

takes 13 cycles and leaves

| RAX:              102   RCX:                0   RDX:                0 |
| RBX:               20   RSP:              108   RBP:                0 |

| used memory:   _0 _1 _2 _3  _4 _5 _6 _7   _8 _9 _a _b  _c _d _e _f    |
|  0x0000010_:   20 00 00 00  00 00 00 00                               |

A full trace is available as pipe-ret.txt.

(It is okay to diagree with this trace about what instruction is fetched and ignored while waiting for the ret, but you should take the same number of cycles and produce the same final results.)

2.4 Other tests

The same tests that should have worked on your single-cycle processor in seqhw should produce the correct results on your pipelined processor.

3 Debugging

As an experiment this semester, one of our TAs prepared a video tutorial on debugging pipelined procesors which is available here.

Our general advice for debugging this assignment:

4 Submit

Submit pipehw2.hcl on the submission page.

Copyright © 2016–2017 by Samira Khan, Luther Tychonievich, and Charles Reiss.
Last updated 2017-04-02 08:51:20