CS 3330: HW 6: Pipelined Jumps

This page does not represent the most current semester of this course; it is present merely as an archive.

We'll add just one more instruction: jXX.

We won't need call or ret for this homework (though having them won't hurt, so if you got the lab working you may use that); a correct implementation of irmovl, rrmovl, and OPl is available as hw6_base.hcl.

At one time, hw6_base.hcl contained a typo on line 72, which should have been need_regs = d_icode in {RRMOVL, IRMOVL, OPL}; not need_regs = d_icode in {RRMOVL, IRMOVL};. Check if your version has that problem and if so, correct it.

To test your code, use jumps.ys (also available as jumps.yo). There are comments in the code explaining its operation. The end result (for any of the part of this assignment) should be

| EAX:        0   ECX:      ace   EDX:      ace   EBX: ffffffff |
| ESP:      ace   EBP:      ace   ESI:        0   EDI:        0 |

with pc of 0x2b, and at no point should any register be given the value 0xbad.

Prediction and mis-prediction

We'll try out a few different branch prediction strategies. All of them will have the following pipeline diagrams on a misprediction:

that is,

• Every jXX has two locations it could jump to: valC and valP. We'll predict (and thus fetch from) one, and send the other through the pipeline so that we have it to use in correcting mispredictions.
• We detect misprediction by checking the conditions codes when jXX is in execute (e.g., m_cnd)
• On a misprediction, we bubble the pipline registers after fetch (which is the D register bank) and decode (which is the E register bank).
• The cycle after a misprediction we fetch based on a value we sent through the pipeline for recovering from mispredictions (which will be in the pipeline register between execute and memory, which is the M register bank).

Taken

Write a file hw6_take.hcl that has at least irmovl, rrmovl, OPl, and jXX working and predicts all jumps as taken.

All jXX should predict that the new PC is valC. However, the pc should not be the predicted pc if there was a misprediction. Mispredictions are detected for the purposed of setting pc based on M_cnd and M_icode. They are fixed by fetching the not-predicted PC (in this case, valP) which we need to also get to the M register bank. As with call in the lab, you can either get that valP to M by using valA or by adding valP to a few pipeline register banks.

As a bookkeeping item, the m_stat checks for legal ifun for OPl and cmovXX; it should also check for jXX.

We'll also need to have some branch-misprediction logic. Down where you had retHazard in Lab 6, add a 1-bit wire for misprediction hazards (name it whatever you want). We can tell there was a misprediction as soon as m_cnd is set by a jXX instruction; for always-taken predictions, we have a misprediction if m_cnd is false. Given a misprediction, bubble D and E.

Running hw6_take on jumps.yo should access the following 23 program counters, in the following order:

pc = 0x0; i6bytes = 0x00000003f030 (irmovl $0x3, %eax)
pc = 0x6; i6bytes = 0xfffffffff330 (irmovl $0xFFFFFFFF, %ebx)
pc = 0xc; i6bytes = 0x000050753060 (addl %ebx, %eax)
pc = 0xe; i6bytes = 0x300000005075 (jge 0x50)
pc = 0x50; i6bytes = 0x00000acef430 (irmovl $0xACE, %esp)
pc = 0x56; i6bytes = 0x000013713060 (addl %ebx, %eax)
pc = 0x58; i6bytes = 0x760000001371 (jle 0x13)
pc = 0x13; i6bytes = 0x00000badf730 (irmovl $0xBAD, %edi)
pc = 0x19; i6bytes = 0x00000badf630 (irmovl $0xBAD, %esi)
pc = 0x5d; i6bytes = 0x300000002c76 (jg 0x2C)
pc = 0x2c; i6bytes = 0x00000acef530 (irmovl $0xACE, %ebp)
pc = 0x32; i6bytes = 0x000074763060 (addl %ebx, %eax)
pc = 0x34; i6bytes = 0x700000007476 (jg 0x74)
pc = 0x74; i6bytes = 0x00000badf730 (irmovl $0xBAD, %edi)
pc = 0x7a; i6bytes = 0x00000badf630 (irmovl $0xBAD, %esi)
pc = 0x39; i6bytes = 0x300000008670 (jmp 0x86)
pc = 0x86; i6bytes = 0x00000acef230 (irmovl $0xACE, %edx)
pc = 0x8c; i6bytes = 0x000000002570 (jmp 0x25)
pc = 0x25; i6bytes = 0x00000acef130 (irmovl $0xACE, %ecx)
pc = 0x2b; i6bytes = 0x000acef53000 (halt)
pc = 0x2b; i6bytes = 0x000acef53000 (halt)
pc = 0x2b; i6bytes = 0x000acef53000 (halt)
pc = 0x2b; i6bytes = 0x000acef53000 (halt)

(you can get just the pcs to display by running ./hw6_take.exe | grep 'pc =')

If you see the wrong jump addresses as e.g. the fourth pc line being pc = 0xe; i6bytes = 0x300000005075 (jge 0x80) instead of pc = 0xe; i6bytes = 0x300000005075 (jge 0x50) then you are running an old version of hcl2d that had incorrect debug output; you can re-download and re-make hcl2d or simply ignore the problem since it impacts the debug output only).

As with all parts of this assignment, the registers should end up as

| EAX:        0   ECX:      ace   EDX:      ace   EBX: ffffffff |
| ESP:      ace   EBP:      ace   ESI:        0   EDI:        0 |

Not Taken

Write a file hw6_nt.hcl that has at least irmovl, rrmovl, OPl, and jXX working and predicts only jmp as taken, but all other jumps (jg, jge, etc.) as not taken.

The structure of the logic will be like it was for Taken, but the details will differ based on the new predictions (and the new address you'll need to jump to on a misprediction).

Most solutions to this problem add something to the pipeline registers so you can tell the difference between jmp and other jumps in the phase where you detect mispredicted branches.

Running hw6_nt on jumps.yo should access the following 23 program counters, in the following order:

pc = 0x0; i6bytes = 0x00000003f030 (irmovl $0x3, %eax)
pc = 0x6; i6bytes = 0xfffffffff330 (irmovl $0xFFFFFFFF, %ebx)
pc = 0xc; i6bytes = 0x000050753060 (addl %ebx, %eax)
pc = 0xe; i6bytes = 0x300000005075 (jge 0x50)
pc = 0x13; i6bytes = 0x00000badf730 (irmovl $0xBAD, %edi)
pc = 0x19; i6bytes = 0x00000badf630 (irmovl $0xBAD, %esi)
pc = 0x50; i6bytes = 0x00000acef430 (irmovl $0xACE, %esp)
pc = 0x56; i6bytes = 0x000013713060 (addl %ebx, %eax)
pc = 0x58; i6bytes = 0x760000001371 (jle 0x13)
pc = 0x5d; i6bytes = 0x300000002c76 (jg 0x2C)
pc = 0x62; i6bytes = 0x00000badf730 (irmovl $0xBAD, %edi)
pc = 0x68; i6bytes = 0x00000badf630 (irmovl $0xBAD, %esi)
pc = 0x2c; i6bytes = 0x00000acef530 (irmovl $0xACE, %ebp)
pc = 0x32; i6bytes = 0x000074763060 (addl %ebx, %eax)
pc = 0x34; i6bytes = 0x700000007476 (jg 0x74)
pc = 0x39; i6bytes = 0x300000008670 (jmp 0x86)
pc = 0x86; i6bytes = 0x00000acef230 (irmovl $0xACE, %edx)
pc = 0x8c; i6bytes = 0x000000002570 (jmp 0x25)
pc = 0x25; i6bytes = 0x00000acef130 (irmovl $0xACE, %ecx)
pc = 0x2b; i6bytes = 0x000acef53000 (halt)
pc = 0x2b; i6bytes = 0x000acef53000 (halt)
pc = 0x2b; i6bytes = 0x000acef53000 (halt)
pc = 0x2b; i6bytes = 0x000acef53000 (halt)

As with all parts of this assignment, the registers should end up as

| EAX:        0   ECX:      ace   EDX:      ace   EBX: ffffffff |
| ESP:      ace   EBP:      ace   ESI:        0   EDI:        0 |

Extra credit: backwards-taken forwards-not-taken

For extra credit, you may write a file hw6_btfnt.hcl that has at least irmovl, rrmovl, OPl, and jXX working and predicts that

1. all jmp are taken, and
2. all other jumps (jg, jge, etc.) are taken only if valC < valP.

The structure of the logic will be like it was for the previous two, but detecting mispredictions will be more complicated because of the more complicated predictions.

Running hw6_btfnt on jumps.yo should access the following 23 program counters, in the following order:

pc = 0x0; i6bytes = 0x00000003f030 (irmovl $0x3, %eax)
pc = 0x6; i6bytes = 0xfffffffff330 (irmovl $0xFFFFFFFF, %ebx)
pc = 0xc; i6bytes = 0x000050753060 (addl %ebx, %eax)
pc = 0xe; i6bytes = 0x300000005075 (jge 0x50)
pc = 0x13; i6bytes = 0x00000badf730 (irmovl $0xBAD, %edi)
pc = 0x19; i6bytes = 0x00000badf630 (irmovl $0xBAD, %esi)
pc = 0x50; i6bytes = 0x00000acef430 (irmovl $0xACE, %esp)
pc = 0x56; i6bytes = 0x000013713060 (addl %ebx, %eax)
pc = 0x58; i6bytes = 0x760000001371 (jle 0x13)
pc = 0x13; i6bytes = 0x00000badf730 (irmovl $0xBAD, %edi)
pc = 0x19; i6bytes = 0x00000badf630 (irmovl $0xBAD, %esi)
pc = 0x5d; i6bytes = 0x300000002c76 (jg 0x2C)
pc = 0x2c; i6bytes = 0x00000acef530 (irmovl $0xACE, %ebp)
pc = 0x32; i6bytes = 0x000074763060 (addl %ebx, %eax)
pc = 0x34; i6bytes = 0x700000007476 (jg 0x74)
pc = 0x39; i6bytes = 0x300000008670 (jmp 0x86)
pc = 0x86; i6bytes = 0x00000acef230 (irmovl $0xACE, %edx)
pc = 0x8c; i6bytes = 0x000000002570 (jmp 0x25)
pc = 0x25; i6bytes = 0x00000acef130 (irmovl $0xACE, %ecx)
pc = 0x2b; i6bytes = 0x000acef53000 (halt)
pc = 0x2b; i6bytes = 0x000acef53000 (halt)
pc = 0x2b; i6bytes = 0x000acef53000 (halt)
pc = 0x2b; i6bytes = 0x000acef53000 (halt)

As with all parts of this assignment, the registers should end up as

| EAX:        0   ECX:      ace   EDX:      ace   EBX: ffffffff |
| ESP:      ace   EBP:      ace   ESI:        0   EDI:        0 |

TAs have been instructed not to help on the extra credit part of this assignment.

Submit

Submit two (or three) files, one named hw6_take.hcl and one named hw6_nt.hcl (and optionally one named hw6_btfnt.hcl) on the submission page. You will need to submit them one at a time.