suomeksi Kääntöpuolella suomeksi

581365-8 Computer Organization II, Exam 15.10.2013

You may answer in English, Finnish, or Swedish.
Write in each answer sheet your name, signature, id-number, course name, and page nr/total nr of pages.
Write down any assumptions you need to make. One or two page answer is sufficient for each problem.
  1. [7 p] Briefly
    1. What is a Karnaugh map? What problem does it solve?
    2. What is TLB? What problem does it solve?
    3. What type of locality is TLB operation based on?
    4. What is bus multiplexing. What problem does it solve?
    5. What is bus arbitration? What problem does it solve? How can it be implemented?
    6. What is Booth's algorithm? What problem does it solve? Why is it usually better than the basic solution?
    7. What is NUMA? What problem does it solve? Why would you use NUMA?

  2. [8 p] Cache
    1. [4 p] Explain how set-associative cache works. Use as an example an (unrealistically small) cache with 16-bit addresses, cache line length is 16 bytes and total cache size is 512 bytes. The cache is two-way set-associative, i.e., the set size is 2. Right now we are processing a read reference to a 4-byte word in byte address 0x2BC4.
       
      Explain detailed structure of the example cache and draw a diagram, that shows it. Make sure that your answer clearly indicates how the given address is split to parts/fields (on bit-level). Explain carefully how the referenced word is found from the cache. Assume that the referenced word is found from the cache this time.

      2.  
    2. [4 p] In a multicore system each core has its own L1-level data cache. Cache coherence problem is solved with MESI protocol. Threads A, B and C, running respectively on cores 1, 2, and 3, are all reading shared variable Sum. What are the MESI states for the cache lines containing Sum in each L1 data cache? Now process B writes new value to Sum. What happens in these caches and memory now? What are the MESI states now for the cache lines containing Sum in each L1 data cache?

    3.  
  3. [8 p] Give pipeline examples on each of the following hazard types. Make your examples such that it is obvious why performance is slowed down. Explain in what type of architecture and in what situation each hazard can occur. For each hazard type, explain at least one solution method that would not require stopping the pipeline ("bubble").
    1. [2 p] Data dependency (raw)
    2. [2 p] Structural dependency
    3. [2 p] Control dependency
    4. Output dependency (waw)
    5. Antidependency (war)

  4. [7 p] Control
    1. [1 p] What problem is solved with control signals?
    2. [3 p] How is microprogrammed control implemented?
    3. [3 p] Compare microprogram execution to processor machine language execution? What is similar? How do they differ?