581365 Computer Organization II,

Separate Exam 3.6.2008


1. BOOTH'S ALGORITHM FOR INTEGER MULTIPLICATION [15 p]

  1. What is the basic idea in Booth's algorithm? (5 p)
  2. Give as an example how Booth's algorithm works with multiplication 14*14. (6 p)
  3. When is Booth's algorithm faster than the conventional approach? Give an example.(2 p)
  4. When is Booth's algorithm slower than the conventional approach? Give an example.(2 p)

2. CACHE AND TLB [15p]

  1. Why are caches needed and why do they work? (2 p)
  2. Why is a TLB used and why does it work? (2 p)
  3. What are the similarities and differences of a cache and a TLB? How do the cache and the TLB relate to each other? (4 p)
  4. Assume that a system using (unrealistically) small cache memory refers to a 4-byte word using the byte address 0xA0B4 (i.e. the address is 16 bits long). Assume that the cache line size is 16 bytes and the cache size is 256 bytes. Draw a picture and explain how the solution finds the above mentioned byte from the cache, when the implementation is based on 2-way set associative mapping. Show clearly how the byte address is divided into separate fields used by the implementation. You may assume that the referenced data is found in the cache.( 7 p)
3. SUPERSCALAR [14p]
  1. How does superscalar implementation differ from superpipelining? How do superscalar implementations
    improve the performance? (4 p)
  2. What are the main problems that restrict the maximum throughput of a pipeline in a superscalar processor?
    Give small code examples. Explain what could be done to handle these situations. (10 p)

4. IA-64 AND ITANIUM [16p]
Explain the following concepts. Give a (machine language level) example to each one.

  1. Predicated execution (4 p)
  2. Speculative loading or control speculation (4 p)
  3. Data speculation (4 p)
  4. Software pipelining (4 p)





Suomeksi toisella puolella!