EE 360N
Fall, 1999
Y. N. Patt, Instructor
Francis Tseng, Seema Prasad, TAs
Problem Set 3
Due: October 22, 1999
1. 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?2. In class, we discussed the state transitions of the bus controller for the Unibus. For this problem, state which signals generated by the controller are associated with the state and which signals are associated with the transition. Draw the finite state machine.
b. What is the latency of the network?
c. What is a reasonable choice?
3. A cache is being designed for a computer with 2^32 bytes of memory. The cache will have a total of 256 slots and use a 32-byte block. Compute for both a 2-way set associative cache and a direct-mapped cache how many bytes the cache will occupy. Specify the size of the RAM needed to house the tag store in both cases. Assume a write-back cache and LRU replacement policy.
4. (Hennessey and Patterson, p. 631, qn. 7.25) Can you make a fully associative cache containing exactly 3K words of data? How about a set-associative cache or a direct-mapped cache containing exactly 3K words of data? For each of these, describe how or why not.
5. (Hamacher et al., p. 255, qn. 5.18) Assume that a computer has a primary and secondary cache. The cache block consists of 8 words. Assume that the hit rate is the same for both the caches and that it is equal to 0.95 for instructions and 0.90 for data. Assume also that the times needed to access an 8-word block in these caches are C1 = 1 cycle and C2 = 10 cycles.
a. What is the average access time experienced by the CPU if the main memory uses interleaving? Assume that the memory is built with DRAM chips that allow the first word to be accesses in 8 cycles, but subsequent words of the block are in 4 clock cycles per word.Also, one clock cycle is required to send one word to the cache.6. Prof. Patt's graduate students have decided to build a computer system using the LC-2. The system will have one LC-2 processor connected to physical memory and several disk units via a shared bus. The disk units have the ability to transfer data directly to/from the memory via the Direct Memory Access controller.
b. What is the average access time if the main memory is not interleaved?
c. What is the improvement obtained with interleaving?
Every time a disk unit finishes a transfer, the LC-2 is interrupted, and the disk unit is given another transfer operation. The unit of transfer between the disk and the memory is a 2^12 byte page and the disk units are capable of maintaining a transfer rate of 2^18 bytes/sec. The bus itself is the latest technology and has infinite bandwidth.
After a few experiments, Prof. Patt's students found that the average disk transfer consisted of 2 pages of data. The disk interrupt handler on the LC-2 was known to take 5 msec of processing time per interrupt. The goal of their experimentation was to figure out how many disk units could be connected to the system and fully utilized. Help them out.
7. Express the relationship between speedup( Sp[A] ), efficiency( Ep[A] ), and redundancy( Rp[A] ) as presented in class.