CS 2734 Computer Organization II

The second exam came relatively late, so there has not been much material since then. Here are the new topics:

• Pipelined Implementation (Chapter 6)
  • Data hazards and stalls (Section 6.5). In case of a dependency involving a lw instruction, the machine must stall for one instruction. Use of the Hazard Detection Unit.
  • Branch hazard (Section 6.6). In case of a branch, if the branch is taken (in one simple implementation), must stall and wipe out the start of the next instruction. (Also need to move branch handling into step 2 of pipeline.)
  • Exceptions (Section 6.7).
• Floating point numbers: Especially the bit representation for a double, as described on pages 275-280, and worked on in lab 13. (Given the bit representation, what is the number?)
• Caches
  • The general idea of caching, used not just for memory, but with disk storage and elsewhere.
  • SRAM versus DRAM (B.5, pages B-26 to B-33).
  • The idea of hashing, with a hash function and with some method for resolving collisions:
    • Open addressing, that is, using the next available sequential location after the hash address.
    • Bucketting, that is, using a linked list attached to to each hash address.
    • Overflow area. Using an additional area for data that collided.
  • Simple approach to a cache, involving a cache table such as the one shown in Figure 7.7, with 1024 entries, indexes in the range from 0 to 1023, a valid bit, a 20-bit tag field, and a 32-bit data field.

    For lookup:

    • The CPU generates an address.
    • Extract a 10-bit index from bits 11-2 of the address.
    • For the address of a word, bits 1-0 will be 0.
    • Compare the 20-bit quantity from bits 32-12 of the address with the tag field. If equal, you have a hit, and return the data field. If not equal, you have a miss; go out to main memory.
    • In case of a miss, stall the CPU, fetch the word from memory, load it into the cache, and restart the instruction so that this time there will be a cache hit.
  • Using spatial locality: As illustrated in Figure 7.10, each cache entry could be a block of 4 words, so that a cache miss will fetch 4 adjacent words, leading to likely hits afterwards.
  • Associative caches, as illustrated in Figure 7.19, where 4 completely distinct words are held for each cache index (4-way associative).

Likely final exam questions:

• No questions about the use of CMOS transistors to create gates.
• Probably several questions about MIPS assembly and machine language. I might ask for the code for a simple loop (use of beq or bne), or for a simple call to a function (jal) and the code for the function (jr $ra to return). I might ask you to unravel machine code.
• At least one question on either the single-cycle or multi-cycle implementation. This might even ask you to do something creative, such a implementing a new instruction.
• Some emphasis on the pipelining chapter, the first seven sections.
  • I might ask about the pipelined datapath or pipelined control (lots of figures in sections 6.2, 6.3).
  • I plan to give you a diagram with a forwarding unit, for you to explain how the forwarding unit works in simple cases not involving a stall (section 6.4, figures 6.41, 6.42).
  • I might ask about the hazard detection unit and stall used to handle the lw instruction (section 6.5, figures 6.47, 6.48, 6.49).
  • I might ask about handling the beq instruction by moving everything into step 2, and by putting in a 1-cycle stall bubble (for successful branch) (section 6.6, figures 6.51, 6.52).
  • I might ask about handling arithmetic overflow exception by flushing the pipeline and restarting the instruction at address 40000040 (section 6.7, figures 6.55, 6.56).
• At least one question about the format of floating point numbers.
• At least one question about hashing and cache memory (perhaps two).