330 Fall 2010 -- 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 arithmetic mean Linpack desktop computer transistor CPU time harmonic mean TPC-C 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 normalized performance ratios h. _________________ used for determining a computer's rank on the TOP 500 supercomputer list i. _________________ a synthetic integer benchmark, which was the basis of calculating relative MIPS values 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. (3 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. (6 pts.) (b) Give the state diagram. (6 pts.) 11. Consider a state machine that acts as a signal edge detector. There is one input (I) and two outputs, positive (P) and negative (N). P=1 whenever I transitions from 0 to 1, and N=1 whenever I transitions from 1 to 0. That is, the state machine behaves like this input I: 0 0 1 0 1 1 0 0 1 1 1 0 0 0 1 1 0 1 0 0 output P: 0 0 1 0 1 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 output N: 0 0 0 1 0 0 1 0 0 0 0 1 0 0 0 0 1 0 1 0 (For this trace, the state machine starts in a state which records a prior input of 0.) (a) Give the state diagram. (5 pts.) (b) Give the state transition table with input I, current state Q(t), next state Q(t+1), and outputs P and N. (5 pts.) (c) Give the simplified logic expressions for Q(t+1), P, and N. (6 pts.) (d) Draw the circuit using a single D flip-flop. (4 pts.)