330 Fall 2011 -- Exam 1 Name: ____ No calculators or other aids. 1. Give the power of 10 associated with these prefixes. (1 pt. each) mega ________ tera ________ micro ________ nano ________ 6, 12, -6, -9 2. Matching -- technology/performance terms. Write the correct term from the list into each blank. (2 pts. each) embedded computer chip clock cycle arithmetic mean Linpack desktop computer die CPU time harmonic mean Whetstone server wafer speedup geometric mean Dhrystone supercomputer CPI workload response time SPEC transistor Hertz memory throughput TPC-C a. _________________ a computer used inside another device running one or more predetermined applications b. _________________ a computer that provides computation, file storage, and/or printing to multiple users across a network c. _________________ a semiconductor device used as a switch d. _________________ unit of measure for clock frequency e. _________________ used to summarize a set of normalized performance values f. _________________ used to summarize a set of rates g. _________________ a transaction-processing benchmark h. _________________ a synthetic benchmark that was once a popular basis of measuring floating-point performance a. embedded computer b. server c. transistor d. Hertz e. geometric mean f. harmonic mean g. TPC-C h. Whetstone 3. Give typical values for current desktop / laptop computers. (6 pts.) a. clock frequency ___________ b. main memory size ___________ c. hard disk size ___________ a. 2 GHz b. 4 GB c. 1 TB 4. Find the execution time for a program that executes 3 billion instructions on a processor with an avg. CPI of 1.5 and a clock frequency of 3 GHz. (Show your work, including the CPU time equation you use.) (8 pts.) CPU time = ( IC * CPI )/CR = ( 3x10^9 insts * 1.5 cycles/inst ) / 3x10^9 cycles/sec = 1.5 secs 5. For the following instruction set workload and cycle values, find the average CPI. (3 pts.) type | freq cycles -------+-------------- alu | 0.5 0.5 branch | 0.2 1 ld/st | 0.3 2 avg CPI = 0.5*0.5 + 0.2*1 + 0.3*2 = 0.25 + 0.2 + 0.6 = 1.05 6. A redesign of the computer in question 5 is proposed that can achieve twice the clock frequency but requires that the load/store CPI value double. Would the redesign be faster, and if so, what would be the speedup? (8 pts.) new CPI type | freq cycles -------+-------------- alu | 0.5 0.5 avg CPI = 0.5*0.5 + 0.2*1 + 0.3*4 branch | 0.2 1 = 1.65 ld/st | 0.3 >>4<< speedup ( IC * 1.05 ) / CR 2.1 speedup = -------------------- = ---- = 1.27 ( IC * 1.65 ) / 2*CR 1.65 7. Consider a computer that has an enhanced mode of execution that can speedup up execution by a factor of ten. For what fraction of the normal execution time must the 10x enhancement be used to achieve an overall speedup of 2? Show the result as a fraction. (8 pts.) 1 2 = ------------ (1-f) + f/10 multiply both sides by ((1-f)+(f/10))/2 1-f + f/10 = 1/2 multiply both sides by 10 10 - 10*f + f = 5 subtract 10 from both sides -9f = -5 divide both sides by -9 f = 5/9 8. Matching -- logic terms. Write the correct term from the list into each blank. (2 pts. each) minterm don't care gate half adder flip-flop sum of products glitch PLA full adder register race condition fan-in ALU decoder shift register circuit depth fan-out latch multiplexer ring counter a. _________________ undesired signal lasting only a short time b. _________________ unused value that can be arbitrarily assigned 0 or 1 c. _________________ where the output of a circuit depends on small differences in signal timing d. _________________ the number of gates in a circuit that form the longest path from any input to any output e. _________________ a circuit with n D flip-flops connected together in a circular shift pattern and designed to provide an exclusive output of 1 on only one of the n output lines each clock cycle in successive order f. _________________ a circuit in which n select values route one of 2**n input values to the single output a. glitch b. don't care c. race condition d. circuit depth e. ring counter f. multiplexer 9. Consider the following circuit. The * represents a connection, the o represents an inversion (or NOT), the D-FF represents a D flip-flop, and both gates are AND gates. The clock input is assumed and not depicted. ___ X ---*---------------------------| \ | ___ .-------. |and |---- Z `----| \ | Q|----|___/ |and |----| D-FF _| Y -------o|___/ | Q|-- `-------' (a) Give the input to the D-FF as a logic expression in terms of X and Y, and give the function Z as a logic expression in terms of X and Q(t). (b) Give the truth table for the circuit in terms of inputs X and Y, current state Q(t), next state Q(t+1), and output Z. (c) Give the state diagram for the circuit. (a) D-FF input = Q(t+1) = X*(~Y) Z = X*Q(t) (b) X Y Q(t) | Q(t+1) Z ---------+--------- 0 0 0 | 0 0 0 0 1 | 0 0 0 1 0 | 0 0 0 1 1 | 0 0 ---------+--------- 1 0 0 | 1 0 1 0 1 | 1 1 1 1 0 | 0 0 1 1 1 | 0 1 (c) 10/0 .---. .----. .---. 00/0, / v.---./ v.---./ \ 01/0, | | 0 | | 1 | | 10/1 11/0 \ /`---'^ /`---'^ / `---' `----' `---' 00/0, 01/0, 11/1 10. Consider a state machine with two inputs, R and I (reset and in), that, after a reset R, outputs a 1 whenever the input I is one in two consecutive cycles. Reset causes any memory of an I=1 input to be lost, and the counting of I=1 inputs starts in the subsequent clock cycle after the reset signal goes back to 0. That is, the state machine behaves like this input R: 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 input I: 0 1 0 1 1 1 0 1 0 1 1 1 1 1 0 1 1 1 1 1 output S: 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 1 (a) Give the state diagram. (There should be only two states.) (b) Give the state transition table with inputs R, I, current state Q(t), next state Q(t+1), and output S. (c) Give the simplified logic expressions for Q(t+1) and S. (d) Extend the state transition table with J and K columns and, using the JK excitation table, fill in the appropriate values for causing the required state transitions. Q(t) Q(t+1) | J K -------------+----- 0 0 | 0 d 0 1 | 1 d 1 0 | d 1 1 1 | d 0 (e) Give the simplified logic expressions for J and K. (a) 01/0 .---. .----. .---. 00/0, / v.---./ v.---./ \ 10/0, | | 0 | | 1 | | 01/1 11/0 \ /`---'^ /`---'^ / `---' `----' `---' 00/0, 10/0, 11/0 (b) R I Q(t) | Q(t+1) S ---------+--------- 0 0 0 | 0 0 0 0 1 | 0 0 0 1 0 | 1 0 0 1 1 | 1 1 ---------+--------- 1 0 0 | 0 0 1 0 1 | 0 0 1 1 0 | 0 0 1 1 1 | 0 0 (c) Q(t+1) = (~R)*I S = (~R)*I*Q(t) (d) R I Q(t) | Q(t+1) S | J K ---------+----------+---- 0 0 0 | 0 0 | 0 d 0 0 1 | 0 0 | d 1 0 1 0 | 1 0 | 1 d 0 1 1 | 1 1 | d 0 ---------+----------+---- 1 0 0 | 0 0 | 0 d 1 0 1 | 0 0 | d 1 1 1 0 | 0 0 | 0 d 1 1 1 | 0 0 | d 1 (e) \ I Q(t) R \ 00 01 11 10 +----+----+====+====+ 0 | 0 | d || d | 1 || J = (~R)*I +----+----+====+====+ 1 | 0 | d | d | 0 | +----+----+----+----+ \ I Q(t) R \ 00 01 11 10 +====+====+----+----+ 0 || d | 1 || 0 | d | K = (~I) + R +=-=-+=-=-+====+====+ 1 || d | 1 || 1 | d || note: (~I) + R = ~(I*(~R)) = ~J +====+====+====+====+ XC. Show the implementation of a 3-bit register using D flip-flops with a two-bit control value, where the control values and actions are given in the table. i2 i1 i0 (inputs) control | action | | | ---------+-------------- +-----------+ 2 0 0 | hold value clock --|> |--/-- control 0 1 | external load +-----------+ 1 x | clear to zero | | | o2 o1 o0 (outputs) each bit position has this design in | 0 0 .---. | | | | +-------+ | |0 1 2 3| | | |--- control_1 (high bit of mux select) | | 4-to-1|--- control_0 (low bit of mux select) | | mux | | +-------+ | | | +-------+ | | D | | | | | | D-FF | clock -|--|> | | | Q | | +-------+ | | `--------* | out i2 i1 i0 | | | | .----------|-------*------------------*-- cntl_1 | |.---------|-------|*---------|-------|*- cntl_0 .---. | 0 0 || .---. | 0 0 || .---. | 0 0 || | +-------+ || | +-------+ || | +-------+ || | | 4-to-1|--'| | | 4-to-1|--'| | | 4-to-1|--'| | | mux |---' | | mux |---' | | mux |---' | +-------+ | +-------+ | +-------+ | | | | | | | +-------+ | +-------+ | +-------+ | .|> D-FF | | .|> D-FF | | .|> D-FF | | |+-------+ | |+-------+ | |+-------+ | | | | | | | | | clk -|-*------|---------|-*------|---------|-' | | | | | | | `--------* `--------* `--------* | | | o2 o1 o0 other solutions might use one of these base designs in | .----. | | +---+ | |0 1| | |mux|--- control_0 (low bit of mux select) | +---+ | | | | 0 | | | | +---+ | |0 1| | |mux|--- control_1 (high bit of mux select) | +---+ | | | +-------+ | | D | | | | | | D-FF | clock -|--|> | | | Q | | +-------+ | | `--------* | out in | +-----------+ | D | c_1 c_0 | action | | --------+-------------- | | 0 0 | hold value __ | D-FF | 0 1 | external load control_0 -------| \ | | 1 x | clear to zero | \ | | clock -----------|AND|---|> clk | | / | | .---o|__/ | | clear (and preset) are | | | asynchronous inputs that control_1 --*------------|clear | will affect the state of | | the flip-flop even when | Q | the clock is not high +-----------+ | out