Computer Science 237 Computer Organization Williams College Fall 2005

Announcements

• Computer Science Colloquium today, 2:35 p.m., TCL 206. The speaker is Hilary Hutchinson '97 from the University of Maryland. Title: "Children's Interface Design for Searching and Browsing".
• Please tear down your memory circuits when you get a chance. Please put the wires back in the boxes neatly. Remove labels from chips. You can refile chips or put them onto an antistatic foam block for later refiling. Be assured that the circuits have been preserved for posterity.
• Microcode phase 1 due Monday. It really shouldn't take long, so try to get it done quickly so you can get started on phase 2.
• Everyone in class should e-mail me by this weekend about their groups (or that they are going to be working alone).
• We're done with formal lab meetings, but I will be holding a session during normal lab times next week to help people get their group permissions and source code control set up. You are encouraged to attend one of these sessions.

  It's best to contact Mary today to get your Unix group set up, so you'll be ready to set up a repository on Monday or Tuesday.

  Remember, sharing passwords is not an acceptable way to share files.

  Even if you are not planning to work in a group, keeping your microcode under source code control is a very good idea.

Agenda

• More on running male and mice
• Running an assembly program
• The WC34000 Computer
• WC34000 assembly programming
• WC34000 assembly examples in /usr/cs-local/share/cs237/ucode
• Microcode questions/answers/hints/suggestions
  • trace command in mice is useful
  • Register layout. You will need to reserve at least 17 registers (D0-D7 and A0-A7 and PC) for user-visible state. There is no compromise here. Register 31 encodes R[RP] and register 30 is MPC. Register 0 is frequently called RP, though it need not be used that way (no one has successfully written a microcode without use of RP). This leaves you 12 registers for your own use. Some will be constants, others will store the instruction or its components. Use registers sparingly and buy constants for use later.
  • State. Notice 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.
  • Choice bits. You may assume that all unspecified bits are zero (0). The HALT instruction, for example, can be assumed to be zero. This is a very restrictive assumption, however. When small data are executed, we would like things to come to a halt. Still, you may assume otherwise. Other places this is of concern: the two bits (6 and 7) of 1-op instructions.
  • Illegal instructions. It's grand to recognize illegal instructions, but you may have your machine do whatever it wants when illegal operations are preformed.
  • Shifting. Division by powers of 2 can be used to perform right shifts, but only if the shifted value is not negative. 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.
  • Masking. 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.
  • 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.

    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. 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.
  • Microcode subroutines. Don't implement subroutines in your microcode. They introduce incredible amounts of pure overhead in your microcode. Don't.
  • Surprising symmetry. Notice that the destination operand is almost never immediate. It can be immediate in the CMP instruction.
  • 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.
  • 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. These can slow you down considerably, if your microcode is running fast.

    Prefetching must be designed in from a fairly early stage. Retrofitting your code can be painful.