CompOrg Spring 2004 Final Exam Information
 


The final exam will be given on Tuesday, May 4th from 8:00-11:00AM in Sage 3510. The final will be closed book, no notes or computers are allowed.

An IA32 Instruction reference will be distributed with the test, as will a description of the Y86 instruction set.

Roughly 1/3 of the test will be on material covered in class since test #2 (Optimization and Memory - caching and virtual memory). Below are a list of topics from these last sections.

The comprehensive part of the test will include material described here and from test#1 and test#2. You should expect lots of short questions for this part of the test.

Topics covered since Test #2

Topic What to know What to expect on the test
Code Optimization
  • Loop inefficiencies.
  • C function calls (and why compilers don't attempt to reduce the number of function calls).
  • Avoiding memory references
    		•
  • Be able to predict the relative performance of two code segments (C or assembly language).
  • Given some C/IA32 code, be able to make some improvments and discuss the impact on performance.
  • Given a simple loop, be able to do some (simple) loop un-rolling
  • Given some code, be able to discuss what optimizations are possible, and which if these could be handled by a compiler.
    		•
    Measuring Execution Time
  • user, system and elapsed time.
  • Timer Interrupts
  • Interval Counting
  • Cycle Counting
  • Caching, system load and measuring time
  • K-best measurement scheme
    		•
  • Be able to define user, system and elapsed time.
  • Be able to compare using interval counting vs. cycle counting to measure execution time.
  • Understand how the system load and/or caching can effect execution time measurements. Be able to discuss how to predict execution time even in environments where cache and load effects are not under your control.
  • Be able to describe/simulate the k-best measurement scheme for making execution time measurements.
    		•
    Memory Hierarchy and Caching
  • Basic concepts related to the access time of DRAM, SDRAM and hard disks.
  • General issues related to memory hierarchies
  • Principles of Temporal and Spatial Locality
  • Cache Architecture
    • Blocks and Slots
    • Direct Mapping
    • Set-Associative
    • Tag and Valid bits
    • Replacement Policy
    • Write Policy
  • Cache Friendly Code
    • Memory access patterns
    • The "Memory Mountain" (sect 6.6.1)
    		•
  • Be able to describe the timings involved in accessing SDRAM, DRAM and hard disk.
  • Be able to describe the principles of locality, and why these matter to cache designers
  • Be able to determine the size of a cache (total number of bits of storage required) given a cache design.
  • Be able to compare two versions of some code in terms of memory access patterns and which would be better if a cache is used.
  • Be able to discuss the tradeoffs of implementing various cache designs (direct-mapped vs set assoc., replacement and write policies).
  • Be able to make some predictions about the performance of code given specific cache designs (code like the code used to produce the "memory mountain".
    		•
    Virtual Memory
    • Physical vs. Virtual Addresses
    • Motivation:
      • Caching of pages
      • Memory Management (linking,loading,sharing)
      • Protection
    • Address Translation (Page Tables)
    • Translation Lookaside Buffer
    • Multi-level Page Tables

    • Be able to determine page table sizes, address sizes, etc. Look at practice problems 10.1 and 10.2

    • Understand what a page fault is, and how it is resolved.

    • Be able to discuss how temporal and spatial locality are exploted by Virtual Memory

    • Be able to discuss why linking and loading of programs is simplified by Virtual Memory

    • Understand how and why Virtual Memory provides memory protection (so one process can't read the memory used by another).

    • Be able to describe a page table, including where it is physically located, what the indicies are and what is held in the page table.

    • Be able to describe the need for TLB, and talk about the perfomance implications of having a TLB or not.

    • Be able to discuss the advantages/disadvantages of caching virtual addresses vs. caching physical addresses.

    Practice Problems