Department of Electrical and Computer Engineering
The University of Texas at Austin
EE 360N, Spring 2001
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?