330 Spring 2009 -- Exam 1 Name: __________________ No calculators or other aids. 1. Give the power of 10 associated with these prefixes. (1 pt. each) exa ________ giga ________ tera ________ peta ________ micro ________ milli ________ nano ________ pico ________ 2. Matching -- technology/performance terms. Write the correct term from the list into each blank. (1 pt. each) embedded computer datapath throughput speedup desktop computer transistor CPU time Whetstone server wafer CPI Dhrystone supercomputer die workload SPEC a. _________________ a computer that provides computation, file storage, and/or printing to multiple users across a network b. _________________ a computer used inside another device running one or more predetermined applications c. _________________ a semiconductor device used as a switch d. _________________ a round slice of silicon upon which integrated circuits are built during the manufacturing process e. _________________ a rectangular piece of silicon containing manufactured integrated circuits (up to millions of transistors) f. _________________ the ratio of the execution times of two computer systems g. _________________ measure of work done per unit time h. _________________ a synthetic benchmark for integer and system operations i. _________________ a synthetic floating-point benchmark, which today has more historical than practical value j. _________________ a set of benchmark suites that are used to compare the performance of various desktops and small servers 3. Give the CPU time equation and define the terms you use. (10 pts.) 4. Find the execution time for a program that executes 5 billion instructions on a processor with an avg. CPI of 1.5 and a clock frequency of 3 GHz. (6 pts.) 5. For the following workload and cycle values, find the average CPI. (4 pts.) type | freq cycles -------+-------------- CPI = _____________________________ alu | 0.4 1 ld/st | 0.4 2 branch | 0.2 2 6. If a new compiler for the computer in question 5 could reduce the number of instructions to 80% 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.5 1 ld/st | 0.3 2 branch | 0.2 2 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. _________________ the number of signals in a circuit that can be supplied as valid inputs from the output of a single gate b. _________________ where the output of a circuit depends on small differences in signal timing c. _________________ a circuit in which n select values route one of 2**n input values to the single output d. _________________ a circuit in which two 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 circuit containing arrays of "and" and "or" gates that can be programmed to implement sum of products logic expressions g. _________________ a circuit that arranges several flip-flops into a common read/write structure with a single clocking signal h. _________________ a memory element in which the stored state can only change once per clock cycle 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 | 0 | 1 | +----+----+----+----+ \ BC A \ 00 01 11 10 +----+----+----+----+ 0 | 1 | 0 | 1 | 1 | F = fn(A,B,C) = _________________________ +----+----+----+----+ 1 | x | x | x | 1 | +----+----+----+----+ 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.) 10. Given the following truth table, give the state diagram and a circuit implementation using two D flip-flops, A and B. (12 pts.) A(t) B(t) I | A(t+1) B(t+1) Out -------------+------------------- 0 0 0 | 0 0 0 0 0 1 | 0 1 0 0 1 0 | 0 0 0 0 1 1 | 1 1 0 1 0 0 | 0 0 1 1 0 1 | 1 1 1 1 1 0 | 1 0 1 1 1 1 | 1 1 1 11. Consider a state machine with a single input I and a single output S. S is 1 whenever there are two consecutive 1s in input I. That is, the state machine behaves like this input I: 0 1 0 1 1 1 0 1 0 1 1 0 output S: 0 0 0 0 1 1 0 0 0 0 1 0 (a) Give the state diagram. (6 pts.) (b) Give the state transition table with input I, current state Q(t), next state Q(t+1), and output S. (6 pts.) (c) Give the simplified logic expressions for Q(t+1) and S. (6 pts.) Extra credit. Give the expanded characteristic table and the excitation table for the JK flip-flop. (up to 4 pts.) J K Q(t) | Q(t+1) Q(t) Q(t+1) | J K ----------+------- ------------+---------- | | 0 0 0 | 0 0 | | | 0 0 1 | 0 1 | | | 0 1 0 | 1 0 | | | 0 1 1 | 1 1 | | | 1 0 0 | | 1 0 1 | | 1 1 0 | | 1 1 1 | | Extra credit. Show how a JK flip-flop can be made into a T flip-flop. The T flip-flop characteristic table is shown below. (up to 3 pts.) T | Q(t+1) ----+------- 0 | Q(t) 1 | ~Q(t) // toggle or invert Extra credit. Show how a clear (or reset) can be added to T flip-flop. (up to 3 pts.) C T | Q(t+1) ------+------- 0 0 | Q(t) 0 1 | ~Q(t) // toggle or invert 1 0 | 0 1 1 | 0