The University of Texas at Austin

Yale N. Patt, Instructor

Kameswar Subramaniam, Onur Mutlu, TAs

Problem Set 5, due: May 2, 2001.

**1. ** (Hennessy and Patterson, p.60, 1.2) Assume that we make an enhancement to a computer that improves
some mode of execution by a factor of 10. Enhanced mode is used 50% of the time, measured as a percentage of the
time *when the enhanced mode is in use*.

a. What is the speedup we have obtained from fast mode?

b. What percentage of the original execution time has been converted to fast mode?

**2. **The state diagram for the Goodman cache consistency scheme makes one assumption about the
size of the cache blocks. What is it? (Hint: Focus on the case in which a block is in the DIRTY state
and a BW signal comes in. Where do we go? Why?) If that assumption is not made, what will be the change
in the state diagram? Draw the new state diagram.

**3. **Draw the state diagrams for the write-through and Illinois cache consistency schemes. (The flow diagrams for
these schemes are given in the cache consistency handout)

**4. **In an Omega network as presented in class, assume that there are n inputs
and n outputs. Let k be the size of each switch. For k taking the values 2, 4, 8, and 64, answer the following
questions. (Assume the cost of each switch is k^2)

a. What is the cost of the network as a function of n?

b. What is the latency of the network?

c. What is a reasonable choice?

**5. **We have got the following expression to compute:

a*x^6 + b*x^5 + c*x^4 + d*x^3 + e*x^2 + f*x + g

a. How many operations and time-steps will the computation take on a single processor system?

b. How many operations and time-steps will the computation take on a multiprocessor system with 4 processors?

c. What are the values for the Utilization, Efficiency, and Redundancy for the multiprocessor system?