Computer Science 237 Computer Organization Williams College Fall 2006

Agenda

• Announcements
• Microcode
  • Sign up for microcode meetings today or tomorrow - I want to meet with all groups
  • Form groups by today
  • See the link on the class page if you still want to set up a Subversion repository (and I believe you do want this).
• Leftover item from last week - assembly examples from various systems
• Pipelines
  • Many instructions, especially in a RISC system, have a sequence of operations such as:
    1. IF: instruction fetch
    2. ID: instruction decode
    3. OD: operand decode
    4. X: execution
    5. WB: write back
  • Some instructions may skip some steps, but will do some subset of these
  • Different stages of this sequence are likely to use different parts of the computer
  • Consider how we might overlap the execution of a sequence of instructions: add, sub, move, cmp, beq
    • At step 1, we can fetch the add instruction
    • At step 2, we can decode the add and fetch the sub instruction
    • At step 3, we can decode the add operand, and decode the sub instruction, and fetch the move instruction
    • At step 4, we can execute add, decode the operand to sub, decode the move, and fetch the cmp
    • At step 5, we can write back the result of add, execute sub, decode the move operand, decode the cmp, and fetch the beq
    • At this point, we are executing 5 instructions simultaneously!
    • At step 6, we'll be completely done with the add, and some 6th instruction can start its way through this pipeline
    • As long as our substages take about the same amount of time, we can potentially execute 5 instructions for each time unit that would normally be required for a single instruction
  • All modern processors do this kind of pipelining, but there are certainly complications
    • What about things after a branch?
      • We don't know it's a branch until after ID is done, and by then we have already fetched the next instruction
      • If we notice a branch, we need to go back into our pipeline and cancel any instructions that we've started into the pipeline that are no longer going to happen because there was a branch
      • This will introduce "bubbles" into the pipeline: we can't start doing more useful work in that slot in the pipeline, because we'd already have had to fetch the instruction and we don't know what instruction that will be
      • Big danger: cancelled instruction could destroy some context before we realize it's not supposed to happen - in this simple pipeline, we're probably safe, since nothing is written back to a register or memory until the last step, but longer pipelines may require more care
    • Also will need to be careful about things like

              add     d0, d1
              sub     #5, d1
      

      Here, we need to make sure we don't fetch the operand d1 of sub before the previous instruction writes it
  • Typical pipelines:
    • RISC system: a 5-stage pipeline like this
    • CISC system: a 12-18 stage pipeline
    • Goal: 100-200 stage pipelines to get very significant speedups
    • Many architectures now have multiple pipelines as well
    • The original Pentium had two pipelines, and a smart compiler could keep both pipelines busy, effectively doubling the number of instructions completed in the same number of cycles
    • If 2 is good, why not 4 or more? Too much duplication of hardware
  • Another option: just have multiple functional units, not all stages of the pipeline
    
    • especially useful if the execute stage takes longer anyway
    • this is a superscalar processor
• Branch Prediction
  • Consider the execution of this code in a pipelined system:

            jmp     l
            add
    

  • The jump/branch is in the pipeline, but by the time we know it's a branch, the add is already in the pipeline
  • Similarly:

            bsr     something
            add
    

    or

            rts
            add
    

  • A compiler can do this on purpose - we know the add is going to happen even though we're taking a branch before we get there
  • Most modern architectures have a delayed branch of 1 or 2 instruction cycles to allow this optimization
  • If we don't have something to do in those delay slots, the compiler may have to fill them with nops
  • This helps eliminate some bubbles in the pipeline, but when we do have nops, that's still a bubble
  • Compilers (or programmers) can also unroll loops to help eliminate branches and keep pipelines full
  • This is generally a good thing anyway because branches aren't doing useful work - just wasted time
  • But what about conditional branches?

            bne     loop
            add
    

  • If we take the branch, then the add instruction should never have happened and we have to kill the instruction
  • Branch prediction is very useful - try to determine which instruction is most likely to be executed after a branch in an attempt to keep the pipeline going
  • Consider

       if (C)
          S1
       else
          S2
    

  • Which is more likely? Programmers probably make the "then" part the more likely case
  • So a compiler might want to set things up to start pipelining S1 after the condition is checked
  • How about a while loop or a for loop?

        while (C)
          S1
    

  • Here, C will be false only once for the life of the while loop, so the best assumption is to predict a successful branch (another time around the loop)
  • The UltraSparc III actually has special branch instructions that a compiler can use when it knows a certain branch is likely to be taken the vast majority of the time
  • Some rules of thumb:
    1. If a branch leads deeper into code, assume the branch will fail
    2. Otherwise, assume the branch will be taken
    This gives about an 80% success rate for human-written code.
  • Today's branch prediction techniques in optimizing compilers are more intelligent and clever and can get more like 98%
  • No matter how good our branch prediction is, it will sometimes fail and we need to be able to make sure instructions can be cancelled
  • One possibility: allow instructions to do everything but store their result until we're absolutely sure
  • Another headache: multiple conditional branches in the pipeline
• Register Windows
  • A RISC system may have hundreds of registers in its register file
  • One way to organize these registers is to treat the register file as circular and give each routine a "view" of a limited subset of these registers at any given time
  • Sparc has many, many registers but only 32 visible at any given time
  • One subset of registers is designated as "globals" and are visible to all routines
  • Each routine has three additional subsets of registers
    • "ins" - the actual parameters
    • "locals" - local variables, temporaries
    • "outs" - parameters to any subroutines called by this routine
  • The "outs" of a routine become the "ins" of a subroutine that it calls
  • Much of what we do with the stack on the 68000 can be replaced with this
  • We eliminate some of the problems of registers getting clobbered by subroutines and we speed function calls by reducing memory accesses needed to pass parameters on the stack
  • But what if we have a deep call stack and we run out of registers? We can't just clobber things, so we'd need to keep a stack also for those cases
  • The actual implementation involves "pretending" to write things to the stack, but it only actually does this ("spill" to the stack, and "fill" from the stack to restore) if necessary given the current state of the register file
  • Another problem: what about functions with more parameters than can be passed in the register window?
  • Observation: a compiler for a system using register windows would do well to eliminate recursion when possible
• Some Stats
  • 20-25% of bits fetched are not used
  • Branches occur approximately 1 in 6 instructions
  • Approximately 50 instructions per (PASCAL) routine; 6-8 branches
  • 25% of all branches are subroutine calls or returns
  • There are 1.5-3 times as many loads as stores
  • On RISC machines, about 30% of all ALU usage is support of multiply and divide
  • 40% of all comparisons are beq/bne
  • 84% of all immediate move instruction involve constants -1 (10%), 0 (50%), 1 (20%), through 7