[Note: used different textbook in Spring 2008] 330 Spring 2008 -- Exam 1 Name: __________________ No calculators or other aids. (110 points total, will be graded out of 100) 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 arithmetic mean Linpack desktop computer transistor CPU time harmonic mean Whetstone server wafer CPI geometric mean Dhrystone supercomputer yield workload speedup SPEC a. _________________ a computer that provides computation, file storage, and/or printing to multiple users across a network b. _________________ the ratio of working chips to total chips manufactured c. _________________ the slice of silicon upon which integrated circuits are built d. _________________ a semiconductor device used as a switch e. _________________ measure of work done per unit time f. _________________ the ratio of the execution times of two computer systems g. _________________ used to summarize a set of unweighted execution times h. _________________ used to summarize a set of rates 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 4 billion instructions on a processor with an avg. CPI of 1.25 and a clock frequency of 2 GHz. (6 pts.) 5. For the following workload and cycle values, find the average CPI. (4 pts.) type | freq cycles -------+-------------- CPI = _____________________________ alu | 0.3 1 ld/st | 0.2 2 branch | 0.5 4 6. If a new compiler for the computer in question 5 could reduce the number of instructions to 1/2 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.6 1 ld/st | 0.2 2 branch | 0.2 4 7. Matching -- logic terms. Write the correct term into each blank. (1 pt. each) minterm race condition half adder ALU register sum of products circuit depth full adder PLA shift register don't care fan-in decoder latch RS latch glitch fan-out multiplexer flip-flop JK flip-flop a. _________________ a form of logical representation that employs a logical OR of minterms b. _________________ the number of gates in a circuit that form the longest path from any input to any output c. _________________ where the output of a circuit depends on small differences in signal timing d. _________________ undesired signal lasting only a short time e. _________________ a circuit with a pair cross-coupled inverting gates (that is, either a pair of nands or pair of nors) f. _________________ a memory element in which the stored state can only change once per clock cycle g. _________________ a circuit in which n select values produce an exclusive output on one of 2**n output lines h. _________________ a circuit containing arrays of "and" and "or" gates that can be programmed to implement sum of products logic expressions 8. Simplify the following Karnaugh maps of function F. (4 pts. each) \ BC A \ 00 01 11 10 +----+----+----+----+ 0 | 1 | 0 | 0 | 1 | F = fn(A,B,C) = _________________________ +----+----+----+----+ 1 | 0 | 0 | 1 | 1 | +----+----+----+----+ \ BC A \ 00 01 11 10 +----+----+----+----+ 0 | 1 | d | 0 | 0 | F = fn(A,B,C) = _________________________ +----+----+----+----+ 1 | d | d | 0 | 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. A bit-serial adder has one D flip-flop, two inputs X and Y, and one output S. The combinational logic consists of a full adder with the carry out being used as the next state. (Ignore the initial clear/set of the carry.) +---------+ X ----->| | sum | full |-----------------------> S Y ----->| | | adder | carry = D_in +---+ Q .---->| |------------->| |---. | +---------+ | D | | | CLK->| | | | +---+ | `--------------------------------------' (a) Give the state transition table with inputs X, Y, current state Q(t), next state Q(t+1), and output S. (8 pts.) (b) Give the state diagram. (8 pts.) 11. Consider a state machine with two input, R and I (reset and in), that, after a reset R, outputs a 1 on each second 1 that it receives on input I. (Reset causes any count of previous and current I=1 inputs 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 0 1 0 0 0 0 0 0 1 1 0 0 input I: 0 1 0 1 1 1 1 0 1 0 1 1 1 1 1 1 0 1 1 1 1 1 output S: 0 0 0 1 0 1 0 0 1 0 0 0 0 1 0 1 0 0 0 0 0 1 (a) Give the state diagram. (8 pts.) (b) Give the state transition table with inputs R, I, current state Q(t), next state Q(t+1), and output S. (8 pts.) (c) Give the simplified logic expressions for Q(t+1) and S. (8 pts.)