Homework #5Due November 19th20 pointsPurpose: The purpose of this homework is to learn about pipelining, and all the particulars thatinvolves.Task: Your task, in a nutshell, is to take Homework #4 and pipeline it. Your pipeline will be aconventional 5-stage MIPS pipeline. When in doubt, the ultimate resource for your questions isthe R2000 processor [except for changes listed in this handout and HW4].Particulars:Use SMOK.Pipeline:The pipeline is:Fetch -> Register Read -> Execute -> Memory Access -> Register WritebackI refer you to Figure 6.40 in your book for a detailed explanation of the pipeline stages.Branch delay slots:Note, HW4 has post-incremented addressing for branches. That is the target of a branch is PC +4 + Immediate. We will continue to have this, but change the MIPS conventions slightly. Theinstruction slot after a branch is called a "delay slot". The delay slot comes about because thatinstruction will be fetched and in the pipeline before you are able to even know that you havejust fetched a branch. We are going to follow the conventions of always executing theinstruction in that delay slot. Different processors handle this differently. Some will execute it ifthe branch is taken, but then "squash" the instruction if the branch is not taken (squashing meansto remove it from the pipeline). However, as I said, to make this a little easier we will alwaysexecute it.So, your machine, when it encounters an control instruction (jump, jal, branching, etc) it willalways execute 1 additional instruction past the control instruction. However, it will onlyexecute just one. Since the branch will not be resolved until later in your pipeline your pipelinewill have "bubbles" in it when a branch is encountered. These bubbles come about because youshould stop fetching once you've fetched this 1 additional instruction past a branch and wait forthe branch target to be resolved and start fetching from there.Load Delays:Accessing memory will be an issue. Your processor should support interlocks that detectinstruction sequences like:LW $1, 0($2)ADD $3, $1, $4It should STALL the processor on the ADD for 1 cycle. The result of a LOAD is not valid untilthe following instruction. I.e.:LW $1, 0($2)ADD $0, $0, $0 <---- No-operations (NOP)ADD $3, $1, $4Other Hazards:You should put in other appropriate logic such that no other hazards in the machine are aproblem. I.e., consider this sequence of instructions:ADD $1, $2, $3ADD $2, $1, $4You will need a forwarding network to handle this. See Figure 6.40 from your book.Memory layoutUse the same memory layout as HW4.Instructions:Support the following instructions:Arithmetic:ADDU, ADDIUSUBUSLTIU, SLTUORI, ORSRL, SLL <--------- these are new for HW5Load/Store:LW, SWBranch:JAL, JRBEQ, BNEStartup code:Modify the startup code from HW4 to take into account the delay slots. Either stick a NOP inthere or do something clever (like move an instruction down there that is useful).Normal code:Write a new procedure in MIPS assembly and hand compile it down to the instructions youimplemented for HW4/5. This procedure is called countbits(int x). What this procedure does isit counts the number of 1 bits in a word. In C this procedure looks like:intcountbits(int x){int v;v=0;while( x != 0 ){if ( (x & 1) != 0 )v=v+1;x=x>>1;}return ( v );}Try and be "optimal" about this and not use the result of a load until 2 cycles later; try and fill thedelay slot of control-flow instructions with meaningful instructions, not just no-ops.EXTRA CREDIT:YOU CAN ONLY GET CREDIT FOR THESE IF YOUR BASIC PIPELINE ABOVE WORKS.YOU CAN ASK THE TA'S QUESTIONS ABOUT THESE ONCE YOUR BASIC HW5WORKS.(2 points) Add a branch predictor. This will be a simple predictor that simply predicts the lastaddress of the branch. This is nominally called a "branch target buffer" (BTB). What you do istake the address of the control instruction in the 2nd pipeline stage and feed the low bits of theaddress to a table (use a memory of 16 entries). From this table start fetching in the next cyclefrom the outcome of this table. When you resolve the actual branch target write this target intothe table location of the branch address. If you predicted the branch target correctly, then youcan keep fetching and executing. HOWEVER, if you predicted incorrectly you will need tosquash the instructions that where incorrectly fetched (but not the delay slot instruction!).(2 points) Make a wide-issue LIW (long instruction word) machine. This machine has adifferent instruction set than MIPS. Here it is:Each instruction is 64 bits. This instruction has two instruction bundles in it:[ instruction 0 ][ instruction 1 ]Each bundle looks like a conventional MIPS instruction EXCEPT instruction 0 mustdraw its SOURCE operands from registers 0 - 15 and its destination operand MUST be a registerbetween register 16 - 31. On the other hand instruction 1 must draw its source from registers 16-31 and its destination must be in 0 - 15.MAKE REGISTER 0 AND 16 HARDWIRED TO ZEROLOAD/STORE instructions must go in bundle 0. (Hence loads will address fromregisters 0-15, but write to a register in 16-31, and STORE's will draw their operands fromregisters 0 - 15).CONTROL-FLOW instructions must go in bundle 1To do this extra credit, split the register file apart into 2 register files of 16 registers each. Thestrange destination/source restrictions outlined above are to get around SMOK issues, butpartitioned register files are a reality in computer architecture so its not that
View Full Document
Unlocking...