Computer Science 237 Computer Organization Williams College Fall 2006

Agenda

• Announcements
  • CS Colloquium this week: Charles Sutton, University of Massachusetts at Amherst , Title: Natural Language Processing and the Scientific Literature, 2:35 PM Friday TCL 206.
• Exams In
• Optional Lab 9 - due next week
• Instruction Set Architecture
  • Today, macroarchitectures or macroinstruction sets are called instruction set architectures or ISA's. There are several very successful ISA's competing for world markets today: POWER, IA32, IA64, M68K, MIPS, Alpha, various VLIW (very long instruction word), etc.
  • We have been using one of these all semester: M68K, but we have not thought about how our assembly instructions are encoded in memory
  • We consider the instruction set in Fig. 4-14 of Tanenbaum 1990
    • All instructions are 16 bits wide
    • "Binary" column specifies how 16-bit values should be interpreted as instructions, "Meaning" shows what should happen when one of these is executed
    • Memory is only 4K 16 bit words, thus 12 bits of address space (Aside: address space grows by 1.5 bits per year)
    • No registers, just an accumulator (AC). A stack pointer, but no frame pointer
    • Most instructions also carry data--either a 12-bit address (e.g. LODD) or a 12-bit constant (e.g. LOCO)
    • There are more than 16 instructions, so 4 bits is not sufficient. We break out instruction 15 (opcode 1111) into 8 instructions.
    • LODL, STOL, ADDL, SUBL provide an alternative way to access local variables in the absence of a frame pointer
    • There is room to add more instructions - for example any of PSHI through SWAP with bits set in low 9 bits, or INSP/DESP with bit 8 set
    • Instructions are grouped by function
    • Instructions with more bits will be harder to decode; they should be used less frequently (an information theory argument can be used here)
    • This simplistic approach is totally insufficient for modern architectures with 32- or 64-bit addresses and values - more on this later
  • Example assembly program in this ISA: a translation from a Pascal (!) program
    • Program in Fig. 4-11(a) in Tanenbaum 1990 performs the inner product of two 20-element vectors (Notice that arrays are indexed beginning at 1, here; look for this during indexing)
    • The program uses a function to achieve multiplication because the assembly langauage doesn't provide a multiply instruction
    • Variables k, x, and y are global, but thought of as local to the main procedure (at the bottom, lines 14-19)
    • Memory is still 4,096 16-bit words
      • no distinction in this machine among bytes/words/longwords - everything is a 16-bit word
      • The compiler places the globals in high memory, below stack (K is at 4020, X is 20 below K, Y is 20 below X)
      • These fixed values make the code nonrelocatable: it would be impossible to have two of these programs running on the same machine, or a version running in a different location, since the values are hard-wired into the code
    • Other assignments are setting up the call frame offsets for the routines pmul and inner
    • Notice the direct line-by-line translation puts main at the bottom, but the first instruction jumps to the main procedure (This is how a compiler might perform the translation)
    • main: SP starts at 0, DESP 41 allocates a frame for main's locals (41 words worth)
    • Notice calling convention pushes arguments on in order - Pascal does not have C-like arbitrary parameter semantics (except system I/O routines, handled in a different manner, but not our concern)
    • pmul: has 2 locals. SOTL supports frame-relative stores, but relative to the SP. Check out call frame offsets.
    • Important things to notice: this is a valid assembly language that we would like to implement on top of the MIC1 using microcode to implement each instruction and the processing of those instructions.
• Tanenbaum's MIC1 Microarchitecture
  • Tanenbaum's horizontally microcoded MIC-1 - implementing the MAC-1 ISA on Tanenbaum's microarchitecture
  • Another layer of abstraction - we want to present an ISA, given a microarchitecture
  • We can specify microcode instructions using Pascal-like statements
  • Tanenbaum 1990 Fig. 4-15 shows the kinds of statements we can use to specify microcode instructions
    • Mostly straightforward, numbers indicate values presented on various control lines.
    • ADDR is specified as 2 hex digits
    • Note that the first statement tells us that the PC is in scratchpad 0.
    • other statements tell us that IR is scratchpad 3, scratchpad 6 contains a 1, etc.
    • some of these statements could be combined to happen at the same time - such as the first (mar:=pc; rd) and fourth (pc:=pc+1)
  • A microinstruction sets values for all control lines - If a control line is not determined by the current operation group, other operations may be specified. For example:

    mar := pc; pc := 1 + pc; mbr := 1 + pc; rd;
    

    This is a single instruction; it takes one line of store (32 bits) and one (major) cycle to execute. Removing parts of the instruction only reduces the work accomplished.
    Here, we need to
    1. put 1 onto A
    2. put the PC onto B
    3. tell the ALU to add
    4. tell the shifter to do nothing
    5. copy the PC (which is on B) into the MAR
    6. store the result of the ALU/shifter operation in the MBR
    7. enable the C bus
    8. put the value on C into the PC
    9. read from memory
    So our microinstruction:

    0 00 00 00 1 1 1 0 1 000 000 111 00000000
    

  • The operations rd and wr take two cycles to execute (because memory is slow). These cycles must be consecutive. From memory's point-of-view, when the rd line is held high, it must control the bus, etc. Interruptions in this protocol will cause problems.
  • ALU-based operations appear in the microcode source as binary operations (e.g. pc+1), or functions (e.g. band(ir,mask)).
  • Shifter operations appear as functions lshift and rshift and are composed with ALU operations.
  • The setting of the N and Z bits (for condition testing) happens during the ALU computation; the shifter has no effect on N or Z.
  • An optional if or unconditional goto sets the COND and ADDR bits. In Tanenbaum, the values of ADDR are simply the address of the target instruction. Branching occurs at no cost.