COS 116 The Computational UniverseHomework 5Due: April 10, 2008Q1. Consider the following 4-state, 1-input finite state machine:a) Give the truth table for this finite state machine. The table should specify the nextstate for each combination of input and current state.b) Draw a circuit design that implements this finite state machine. Your circuit willconsist of a combinational circuit and some “rising-edge triggered” D flip-flops(like you used in lab). The combinational portion should implement the truth tablefrom part (a). Make your circuit as simple as you can.Q2. A computer manufacturer lists its processor speed as 3.2 GHz. Explain what theymean by this and comment in a line or two in what ways it is a meaningful measure ofspeed and in what ways it is not. Explain in a line or two how circuit designers determinethe maximum speed at which the clock can be run for a circuit in question.Q3. You decide to learn the machine language for a modern CPU. You notice that itassumes that all memory addresses have 32 bits. How large a memory does that imply?Can such a program run on a CPU with 1 Gigabyte memory? Explain in a line or two.Q4. Suppose we have a computer with a main memory that can hold 10 data items, and acache that can hold 3 data items. Initially, the main memory contains the numbers 1through 10, and the cache is empty:Main memory:000101011011100112345678910Cache:Recall that, whenever a program requests a data item, it first checks to see whether it is inthe cache. If it is, the request proceeds normally. If it’s not, the data item is first copiedfrom the main memory to the cache. If the cache is full, some other data item in the cachemust be overwritten.Assume our computer uses the “Least Recently Used” algorithm to decide which dataitem will be overwritten. Now suppose we run a program that requests data items in thefollowing sequence: 2, 4, 7, 2, 1, 3, 4, 2, 4, 10, 4, 9, 2, 5, 2, 2. Show the contents of thecache after each request. Also, say how many times during this sequence the requesteditem was not in the cache.Q5. Consider a computer with three levels of memory: cache, RAM, and hard disk. Thetable below gives the time required to access a data item from each of these memories.Memory TypeAccess TimeCache5 x 10-9sRAM2 x 10-8sHard disk5 x 10-3sSuppose that 98% of data requests are satisfied by the cache, 1.9% by the RAM, and0.1% by the hard disk. Calculate the average time to access a data item in this
View Full Document
Unlocking...