330 Spring 2010 -- Exam 1 Name: ____ No calculators or other aids. 1. Give the power of 10 associated with these prefixes. (1 pt. each) giga ________ kilo ________ mega ________ micro _______ milli ________ nano ________ peta ________ pico ________ giga +9 kilo +3 mega +6 micro -6 milli -3 nano -9 peta +15 pico -12 2. Matching -- technology/performance terms. Write the correct term from the list into each blank. (1 pt. each) embedded computer transistor throughput Hertz server wafer response time workload supercomputer die CPU time speedup a. _______________ a computer with highest cost and performance b. _______________ the program(s) currently being run and associated inputs c. _______________ measure of work done per unit time d. _______________ the ratio of the execution times of two computer systems e. _______________ unit of measure for clock frequency f. _______________ a rectangular piece of silicon containing manufactured integrated circuits (up to millions of transistors) g. _______________ a computer used inside another device running one or more predetermined applications h. _______________ measure of time from user depressing return or clicking mouse until first output appears a. supercomputer b. workload c. throughput d. speedup e. Hertz f. die g. embedded computer h. response time 3. Give the CPU time equation and define the terms you use. (10 pts.) CPU time = IC * CPI * CCT = ( IC * CPI ) / CR IC = instruction count CPI = clock cycles per instruction CCT = clock cycle time ( = 1/CR where CR = clock rate ) 4. Find the execution time for a program that executes 40 million instructions on a processor with an avg. CPI of 2.5 and a clock frequency of 2 GHz. (5 pts.) CPU time = 40*10^6 insts * 2.5 cycles per inst / 2*10^9 cycles per sec = ( 100 * 10^6 / 2 * 10^9 ) seconds = 50 milliseconds 5. For the following workload and cycle values, find the average CPI. (5 pts.) type | freq cycles -------+-------------- CPI = _____________________________ alu | 0.5 1 ld/st | 0.25 2 branch | 0.25 4 CPI = 0.5*1 + 0.25*2 + 0.25*4 = 0.5 + 0.5 + 1 = 2 6. If a new compiler for the computer in question 5 could reduce the number of instructions to 60% of the original total and alter the instruction frequencies in the following manner, what would be the total speedup? (10 pts.) type | freq cycles -------+-------------- alu | 0.2 1 ld/st | 0.45 2 branch | 0.35 4 new CPI = 0.2*1 + 0.45*2 + 0.35*4 = 0.2 + 0.9 + 1.4 = 2.5 new IC = 0.6 * old IC old CPU time IC * 2 * CCT 2 _ speedup = ------------ = ------------------ = --- = 1.3 new CPU time 0.6*IC * 2.5 * CCT 1.5 7. Matching -- logic terms. Write the correct term into each blank. (1 pt. each) minterm race condition half adder register sum of products circuit depth full adder PLA don't care fan-in decoder latch glitch fan-out multiplexer flip-flop a. _________________ a short but undesired signal b. _________________ the number of signals in a circuit that can be supplied as valid inputs from the output of a single gate c. _________________ where the output of a circuit depends on small differences in signal timing d. _________________ a circuit in which three input values produce a sum and carry output e. _________________ a circuit in which n select values produce an exclusive output on one of 2**n output lines f. _________________ a memory element in which the stored state can only change once per clock cycle a. glitch b. fan-out c. race condition d. full adder e. decoder f. flip-flop 8. Simplify the following Karnaugh maps of function F. (4 pts. each) \ BC A \ 00 01 11 10 +----+----+----+----+ 0 | 1 | 0 | 1 | 1 | F = fn(A,B,C) = _________________________ +----+----+----+----+ 1 | 0 | 0 | 1 | 0 | +----+----+----+----+ \ CD AB \ 00 01 11 10 +----+----+----+----+ 00 | 1 | 0 | 0 | 0 | F = fn(A,B,C,D) = _______________________ +----+----+----+----+ 01 | 1 | 1 | d | 1 | d = don't care +----+----+----+----+ 11 | 1 | d | d | 0 | +----+----+----+----+ 10 | 1 | 0 | d | 0 | +----+----+----+----+ \ BC A \ 00 01 11 10 +----+ +----+ +---+ 0 1 | 0 | 1 | | 1 F = fn(A,B,C) = ~A*~C + B*C +----+ + + +---+ 1 0 0 | 1 | 0 +----+ \ CD AB \ 00 01 11 10 +----+ 00 | 1 | 0 0 0 F = fn(A,B,C,D) = ~A*B + ~C*~D +----+----+----+----+ 01 | 1 | 1 | d | 1 | +----+----+----+----+ 11 | 1 | d d 0 +----+ 10 | 1 | 0 d 0 +----+ 9. Draw a block diagram of the generic model of a sequential circuit (that is, a finite state machine). Be sure to identify the following component parts or signals: combinational circuit, memory element, input, output, current state, and next state. (6 pts.) .---------------. | | input --->| combinational |-----------------> output | logic | .-->| |--> next state --. | | | | | `---------------' | | | | .---------. | `-- current state <--| memory |<-----' | element | `---------' 10. Consider the following truth table. (a) Give the state diagram. Note that there are no inputs or outputs to place on the transition arcs. (5 pts.) (b) Give the simplified logic expressions for A(t+1), B(t+1), and C(t+1). Use K-maps if needed. (3 pts.) (c) Show the implementation using three D flip-flops. (4 pts.) (d) Give the name of the resulting circuit. (3 pts. extra credit) A(t) B(t) C(t) | A(t+1) B(t+1) C(t+1) ---------------+--------------------- 0 0 0 | 0 0 0 0 0 1 | 0 0 0 0 1 0 | 0 0 1 0 1 1 | 0 0 1 1 0 0 | 0 1 0 1 0 1 | 0 1 0 1 1 0 | 0 1 1 1 1 1 | 0 1 1 (a) .---. |100| `---'\ .---. >--->|010| .---./ `---'\ .--. |101| \ v \ `---' \ .---. .---. | >--->|001|--->|000| | .---. / `---' `---' | |110| / \ / `---'\ .---./ `--' >--->|011| .---./ `---' |111| `---' (b) A(t+1) = 0 B(t+1) = A(t) C(t+1) = B(t) (c) +-----+ +-----+ +-----+ 0-->| Q|-->| Q|-->| Q|--> | A _| | B _| | C _| | Q|- | Q|- | Q|- +-----+ +-----+ +-----+ (d) shift register 11. To provide proper rounding for floating-point addition, three extra bits are included in right shifts of fractions: guard, round, and sticky. The least-significant of these, the sticky bit, stays one whenever a 1 bit is shifted through it. In designing the logic for a sticky bit, let the following truth table define the actions for R (reset) and I (input) on a D flip-flop. R I Q(t) | Q(t+1) ----------+-------- 0 0 0 | 0 0 0 1 | 1 0 1 0 | 1 0 1 1 | 1 1 d d | 0 (a) Five rows are shown (using d = don't care in the last row). If the don't cares are expanded, how many total rows would there be in the full table? (2 pts.) (b) Using a Karnaugh map for simplifying the expression, give the input to the D flip-flop in terms of R, I, and Q(t). (10 pts.) (c) Draw the state diagram for the sticky bit logic from the table above. There is no separate output signal. (10 pts.) (a) eight (b) \ I Q(t) R \ 00 01 11 10 +----+----+----+----+ 0 | 0 | 1 | 1 | 1 | Q(t+1) = ~R*I + ~R*Q(t) +----+----+----+----+ 1 | 0 | 0 | 0 | 0 | +----+----+----+----+ (c) 01 .---. .----. .---. / v.---./ v.---./ \ 00,1d | | 0 | | 1 | | 00,01 \ /`---'^ /`---'^ / `---' `----' `---' 1d