Computer Science 237 Computer Organization Williams College Fall 2006

Agenda

• Announcements
  • CS Colloquium this week: Tim Huang, Middlebury College, Title: "Beyond Deep Blue: Advances in Computer Go"
• Working in a group for the project? Get a Unix group to allow safe sharing of files. Contact Mary Bailey.
• Much more on the WC34000
  • System overview:
    
    • You provide a .mal file containing your microprogram, assemble it into microcode (the hmem file) with the male command
    • You provide a .s file containing a 34000 assembly language program, assemble it into 34000 machine code (the tmem file) with the wc34asm command
    • mice emulator reads hmem into the microcode store, tmem into the 34000 memory, gets any input from the tinput file as it uses the microcode to execute the program, one microinstruction at a time
    • wc34000 emulator reads tmem into the 34000 memory, gets any input from the tinput file as it uses a 34000 simulator to execute the program one assembly instruction at a time
    • Your task: make mice behave the same as wc34000 for any valid 34000 assembly language program
    • The trace command in mice is useful - keep it in mind (see registers.mal example with trace turned on, for example)
    • Also, register command to show values of registers
  • Your microprogram will need to
    1. set up registers with appropriate initial values, initialize needed constants
    2. run a fetch-update-decode-execute loop on the 34000 program in memory
  • Your microprogram will need to fit in 1024 lines
  • There are two (conflicting) goals:
    1. keep the microcode as compact as possible (perhaps a smaller microcode store can be used when you build your 34000)
    2. make the microcode as fast as possible (speed is the number of microinstructions per assembly instruction)
  • Your grade will be automatically computed based on size, speed, and correctness
    • size is what it is - you may choose to focus on this or not, but if you don't, you better have a correct and fast microprogram
    • speed and correctness are determined by running a series of tests (assembly programs) using your microprogram in mice
    • no speed points for failed tests, so correctness is very impoortant
    • speed is the number of microinstructions per assembly instruction over the course of each example run
  • WC34000 assembly examples in /usr/cs-local/share/cs237/ucode
    • some of these will part of the official grading tests
    • some of these will not
    • some of the grading tests are not made public
    • if you write some of your own tests, please share them with your classmates!
  • In the decode/execute phases, you need to interpret the words of memory as 34000 instructions and figure out just what needs to happen, then make it happen
    • the opcode specifies which instruction
    • the operands indicate which registers or memory locations are involved and what addressing modes are to be used
  • Some instructions fit everything they need into the 16 bits of the word pointed to by the pc, others require extension words, subsequent words in memory that contain addition information needed for the execution of the instruction
  • The operand format is detailed on pages 2-3 of the "WC34000 Computer" handout
    • operands are 6-bit values embedded within an instruction
    • 3 of these bits specify the addressing mode (see Appendix B)
    • the other 3 bits specify a register number (or something else)
  • Instruction formats are detailed on pages 4-5 of the "WC34000 Computer" handout
    • Use the band instruction, along with bit-masks to extract appropriate bits
    • For example, the value 63 is 6-bits--the mask for the source operand in most instructions
    • What is 0101000011010100?
  • Register layout
    • You will need to reserve at least 17 registers (d0-d7 and a0-a7 and pc) for user-visible state (no choices here, other than where to put them among your 31)
    • Register 31 encodes R[RP] - use the register specified by the register pointer (R[0])
    • Register 30 is mpc
    • The register pointer (Register 0) need not be used that way (however, no one has successfully written a microcode without use of RP)
    • This leaves 12 registers for other purposes (constants, the instruction or its components) - conserve registers early since you may find that you want or need constants later
  • Source/destination specification
    • Note that some instructions need a source value (e.g. move), while others don't (e.g. clr)
    • Some need a destination value (e.g. neg), while others don't (e.g. move)
    • Some need a source effective address (e.g. clr (a0) or pea x) while others don't (e.g. add)
    • Most need a destination effective address (e.g. move #1,4(a6)), but the cmp d0,#3 statement sometimes does not
  • Unspecified bits or "choice bits"
    • Some instructions have bits that are not examined during decoding
    • You should assume that all unspecified bits are zero (0)
    • The halt instruction, for example, can be assumed to be zero
    • Note that this is a very restrictive assumption - when small data are executed, we would like things to come to a halt. Still, you may assume otherwise for simplicity
    • The other place this is of concern: the two bits (6 and 7) of 1-op instructions
  • Illegal instructions
    • It's nice to recognize illegal instructions, but don't bother
    • your machine may do whatever it wants when illegal operations are preformed
    • you'll only be wasting time since programs as assumed to be correct, at least in that only valid instructions should ever attempt to be executed
  • Multiway branching
    • Notice that you can perform instructions like

          mpc := band(ir,63);
        

    • This allows you to branch to any of the first 64 microcode instructions based on the low six bits of ir
    • This is the equivalent of 64 Tanenbaum-style instructions and saves 5 cycles of execution time (!)
    • Of course, you cannot perform this in more than one place in your code, unless you can make the target instructions consistent
    • See 8waybranch example microprogram
    • If you perform

          srcop := band(ir,63); if z then goto DDir;
          mpc := srcop+mpc;
      ADir: ...           !! Address Reg Direct Mode
      

      it branches to any of the next 63 instructions if the value srcop bits are non-zero, and to the instruction found at DDir if these source bits are zero
    • This relative branch may appear anywhere in your program, as long as it stays in the same relative position with respect to the target instructions
    • If you perform

          mpc:=ir;
      

      the machine decodes the low 10 bits of your instruction in one step (!!!)
    • This could land (almost) anywhere in your microcode
    • "Branching on 10 bits" is a viable option, but it uses all of the microcode store
    • The fastest (and largest) codes use 10-bit branches
    • It is not clear that the low 10 bits are the correct 10 bits to decode in this manner
  • Patterns
    • You should be looking for patterns in the opcodes
    • It may be useful, for example, to distinguish between 1-op and 2-op opcodes
    • The pattern is that the 2-op instructions have either bit 15 or bit 14 set
    • In this interpretation, the LINK instruction looks like a 1-op
    • The 1-op instructions, however, have the prefix 001
    • In this interpretation, the LINK instruction looks like a 2-op
  • Decoding operands before opcodes
    • Notice that every instruction has a source operand
    • This can be decoded even before the opcode is decoded
    • This is useful
  • Microcode subroutines
    • You may be tempted to implement subroutines in your microcode
    • They introduce incredible amounts of pure overhead - just don't do it
  • Notice that the destination operand is almost never immediate (it can be immediate in the cmp instruction)
  • Shifting
    • Division by powers of 2 can be used to perform right shifts, but only if the shifted value is not negative
    • This is not a bad thing, since our ALU can do division just as fast (in one microinstruction) as it can do anything else
    • If the shifted value is negative, it only works if no one (1) bits would be shifted out
    • If a one bit is shifted out, the result is more positive by one than desired for a shift
    • -1 divided by any nontrivial power of 2 is zero, not -1
  • Instruction profiles
    • In making choices between implementations or optimizations, it is sometimes useful to profile your code to see how frequently particular instructions or modes appear
    • If an instruction is used 10% of the time, a 1 microinstruction reduction in your path through the instruction is likely to improve your performance by 0.1 microinstructions/macroinstruction
    • This can help you decide where to focus your optimization efforts
  • Conditional branches
    • You may assume that conditional branches follow either (1) a CMP instruction, or (2) another conditional branch
  • The overflow bit
    • You may ignore any situation that depends on the overflow bit
    • This is not strictly correct, but the assumption may be made
  • PC Indirect
    • PC indirect with displacement is used for PC-relative offsets
    • This happens whenever we refer to a label in assembly code
  • Instruction prefetching
    • It is useful if you develop rules about the state of your machine
    • For example, the pc could always point to the next word of memory to be read from the machine
    • As you read a word of memory, you can increment the program counter (You should think about the implementation of PC-indirect addressing when you make these decisions)
    • Another approach might be to have the pc point to the word currently found in a buffer which is immediately available for use
    • When you use the buffer's value, you increment the pc and read the next value from memory
    • This latter approach prefetches instructions and may be useful when you feel that reading memory is slowing down your machine
    • The instruction

          add 4(a6),5(a6)
      

      for example, requires 3 instruction words, all of whom must be read, along with two more memory reads and one write
    • That's a grand total of 12 cycles of reading or writing
    • If you can prefetch some of this instruction, you may be able to overlap the execution of this instruction with the previous operation
    • It is not clear that prefetching is inherently useful
    • It can take time to maintain the consistency of your buffers and this may introduce speculative or worse, redundant reads which may slow things down considerably
    • Prefetching must be designed in from a fairly early stage (retrofitting your code can be painful)