Previous Reviews: Refer to the reviews for Exam 1 and Exam 2 for material covered up to the second exam: (see Review for Exam 1 and Review for Exam 2).

Previous Exams: Previous exams are available through the individual web pages. (See here, with links on the "calendar" page, and earlier at the end of each main page.) This final may be significantly different from previous ones.

Review topics: Here are the new topics since the second exam. Note that the final will be comprehensive, but will emphasize material since the last exam, especially Chapter 6, since that is the most important topic since the second exam. The final also covers the new topics of the Hamming code, caches, and the recitation on exceptions.

• Coding and information theory in computer storage and communications (see Coding theory, Hamming code, Recitation 12: Hamming Code).
  • The three types of coding:
    • Source coding, using data compression.
    • Channel coding, using error detection/correction. This is the area we went into in more detail, including a discussion of the Hamming code to do single-error correction and double-error detection:
      • The idea of a parity check (even parity) using an extra check bit.
      • Assume the final message with the Hamming code added is in bit positions 1, 2, 3, 4, 5, ....
        • The Hamming code uses bits in positions 1, 2, 4, 8, 16, 32, ... for (even) parity checks of selected bits (not all of them). The remaining bits in positions 3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 17, ... hold the bits of the message.
        • The parity bit in position 1 checks odd-numbered bits (those for which the position number written in binary has a 1 as least significant bit).
        • The parity bit in position 2 checks bits 2, 3, 6, 7, 10, 11, 14, 15, ... (those for which the position number written in binary has a 1 as next-to-least significant bit).
        • The parity bit in position 4 checks bits 4, 5, 6, 7, 12, 13, 14, 15, ... (those for which the position number written in binary has a 1 as second-from-least significant bit).
        • The parity bit in position 8 checks bits 8, 9, 10, 11, 12, 13, 14, 15, 24, ... (those for which the position number written in binary has a 1 as third-from-least significant bit).
        • The parity bit in position 16 checks bits 16, 17, 18, 19, 20, 21, ... (those for which the position number written in binary has a 1 as third-from-least significant bit).
      • We went over an example showing how it works. (See tables at the end for this example.)
      • Add a parity bit in position 0 to check all bits. This gives double error detection as well as single error correction.
    • Secrecy coding, using cryptography.

• Exceptions and the trap handler in MIPS (see Recitation 13: Exceptions, Quiz 7: Exceptions ).
  • The specifics of how the trap handler works.
  • Take-home quiz on exceptions.

• Pipelined Implementation (Chapter 6, 6.1-6.8).
  • Overview (Section 6.1, includes especially discussion of hazards).
  • Pipelined datapath (Section 6.2, ignores hazards). Note the several ways of graphically representing pipelines on pages 397-398, especially the series of diagrams in Figures 6.19-6.21.
  • Pipelined control (Section 6.3, ignores hazards). The control signals from the Control unit are the same as for the single-cycle implementation, but the pipelined implementation makes use of extra latched register storage between pipeline stages to pass along control information. (See Figures 6.26 and 6.27.)
    (See also Recitation 10: (first part) Pipelined Control)
  • Data hazards and forwarding (Section 6.4). You should understand how forwarding works, with the Forwarding Unit and extra control and data lines. This applies to dependencies between the register result of one instruction and the use of that new register value in subsequent instructions. (See especially the material on the CD.) There are 6 inputs to the forwarding unit and 2 outputs.
    (See also Recitation 10: (second part) Data Hazards and the Forwarding Unit)
  • Data hazards and stalls (Section 6.5). In case of a dependency involving a lw instruction, the machine must stall for one instruction. This uses the Hazard Detection Unit. Note how the stall is inserted by de-asserting write lines to the PC and the IF/ID registers, and by inserting all zeros on control lines. (These zeros propagate along from cycle to cycle, as the "bubble" of a stalled instruction moves along the pipeline.) See diagrams in Figures 6.47-6.49. Note that the final forwarding is done by the Forwarding Unit as before.
    (See also Recitation 11: Stalls and lw)
  • Branch hazard (Section 6.6). In case of a branch, if the branch is taken (in one simple implementation), the computer must stall and wipe out the start of the next instruction. (Also need to move branch handling into step 2 of pipeline.) See Figures 6.38 and 6.54. Skip material at the end of 6.6 from pape 421 on. The stall is inserted by zeroing the instruction in the IF/ID pipeline register (making it a nop instruction), so that as it moves through the pipeline, nothing happens.
  • Exceptions (Section 6.8). Example of arithmetic overflow. IF.Flush, ID.Flush, EX.Flush lines to put nop in first stage and to set control lines to zeros in second and third stages.

• Caches (Chapter 7, 7.1 and 7.2, with a little bit of 7.3).
  • The general idea of caching, used not just for memory, but with disk storage and elsewhere.
  • SRAM versus DRAM (B.9, pages B-57 to B-66).
  • 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.
  • A very simple example, with 3-bit cache addresses, and 5-bit memory addresses. Use the low-order 3 bits of the memory address for the cache address. See Figures 7.5 and 7.6.
  • A simple approach to a cache, involving a cache table such as the one shown in Figure 7.7, with 1024 cache entries (using a 10-bit cache address), 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 (which means that if an item is referenced, items whose addresses are close by will tend to be referenced soon): As illustrated in Figure 7.9, each cache entry could be a block of 16 words, so that a cache miss will fetch 16 adjacent words, leading to likely hits afterwards.
  • Associative caches, as illustrated in Figure 7.17, where 4 completely distinct words are held for each cache index (4-way associative).

• doubles: Representation and MIPS assembly language (parts of Section 3.6).
  • Conversions between scientific notation and internal bit representation of a double, using the IEEE standard.
  • MIPS assembler language for handling doubles.
  • See Recitation 14: Floating Point.

• 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), or access to memory (use of lw or sw), or saving and restoring a register on the stack.
• Possibly one question about the correspondence between machine code and assembler code (as in Recitation 7: Hand Assembly of MIPS Code.
• At least one, perhaps 2, questions on either the single-cycle or multi-cycle implementation.
  Don't forget the recitation asking how to implement the addi instruction in both the single-cycle and the multi-cycle models, without additional control lines (Recitation 9: addi in single/multi).
• Extra emphasis on the pipelining chapter.
  • I might ask about the pipelined datapath (lots of figures in section 6.2).
  • I might ask about the pipelined control (more figures in section 6.3 and on the CD).
  • I may 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). There are 6 inputs to the forwarding unit, and you should understand how each of them is needed and is used. Similarly you should understand the two outputs.
  • I might ask about the hazard detection unit and the stall used to handle the lw instruction (section 6.5). How does the computer know it is a lw instruction? How does the computer insert the stall?
  • 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).
  • I might ask about handling arithmetic overflow exception by flushing the pipeline and restarting the instruction at address 40000040 (section 6.8).
• Probably one question about exception handlers.
• Probably one question about caches.
• Probably one question about the internal representation of doubles.
• Possibly one question about MIPS assembler instructions involving doubles.

Good Luck!!!