CPSC 330 - Spring and Fall 2012 Study Guide for Exam 1 Coverage: introduction, performance, combinational and sequential logic 1. Be able to define or match these terms. (Definitions can typically be found in chapter 1, but some other locations are noted.) General technical terms bit byte word kilo mega giga tera peta exa milli micro nano pico embedded computer desktop computer server supercomputer instruction set architecture (ISA) memory RAM cache memory primary memory / main memory secondary memory magnetic disk / hard disk transistor wafer die integrated circuit / chip Performance terms throughput execution time (response time) CPU execution time (CPU time) user CPU time system CPU time clock frequency (Hertz) clock cycle clock cycles per instruction (CPI) workload speedup Whetstone Dhrystone Linpack SPEC benchmarks Logic terms combinational logic sequential logic minterm (product term) sum of products form DeMorgan's theorems Karnaugh maps don't care gate glitch race hazard (race condition) number of gate levels (circuit depth) fan-in fan-out propagation delay programmable logic array (PLA) decoder multiplexer (mux) half-adder full-adder ripple-carry adder ALU latch flip-flop master-slave edge-triggered RS latch JK flip-flop D flip-flop register shift register binary counter modulo-(2**n) counter saturating up and down counter ring counter 2. Be able to: A. Give representative values for current machines: i. CPU clock frequency ii. size of main memory iii. size of a hard disk B. Use the standard power-of-two and -ten prefixes in equations. C. Calculate execution time using IC, CPI, and clock cycle time. D. Calculate average CPI. E. Explain why the SPEC benchmarks are better for performance evaluation than Whetstone and Dhrystone. F. Explain how the choice of compiler or choice of compiler optimizations can affect performance. G. Construct a truth table for a given logical function. This could be for a simple gate (and, or, not, nand, nor, ...) or for a given combinational circuit or logic expression. H. Prove that one logic expression is idential to another by use of a truth table. I. Simplify a four-variable (or less) logic function or truth table using a Karnaugh map. J. Give the characteristic table for a given latch or flip-flop (from among RS, JK, D). The test will likely have these parts: matching, problems similar to homeworks 1 and 2, and thought questions. Example questions 1. Give the power of 10 associated with these prefixes. kilo __________ milli __________ mega __________ micro __________ giga __________ nano __________ tera __________ pico __________ 2. Matching. Write the correct term from the list into each blank. embedded computer transistor throughput desktop computer wafer CPU time server chip CPI supercomputer workload a. _________________ a computer with highest performance and cost b. _________________ a computer used inside another device running one or more predetermined applications c. _________________ a semiconductor device used as a switch d. _________________ a device containing dozens to millions of transistors e. _________________ actual time the CPU spends computing for a specific task f. _________________ measure of work done per unit time g. _________________ a set of programs to run on a computer that is either the actual collection of programs run by a user or is constructed from real programs to approximate the actual collection 3. A processor has a 500 MHz clock frequency. What is the clock cycle time? 4. Find the execution time for a program that executes 1 billion instructions on a processor with an avg. CPI of 3.0 and a clock cycle time of 33.3 nsec. 5. For the following instruction set workload and cycle values, find the average CPI. type | freq cycles -------+-------------- alu | 0.5 2 branch | 0.2 6 ld/st | 0.3 6 6. Matching. Write the correct term from the list into each blank. minterm circuit depth multiplexer sum of products fan-in latch asserted signal fan-out flip-flop don't care PLA register gate decoder clock (a) _______________ unused value that can be arbitrarily assigned 0 or 1 (b) _______________ a set of logic variables joined using the AND operator (c) _______________ the maximum number of inputs that a gate can accept (d) _______________ a form of logical representation that employs a logical OR of minterms (e) _______________ the maximum number of inputs for other gates that a given gate output can drive (f) _______________ the number of gates in a circuit that form the longest path from any input to any output (g) _______________ a memory element in which the stored state can only change once per clock cycle (h) _______________ a logic element with a single output for which n control lines select one of 2**n input values 7. Define these two undesirable circuit attributes. (a) glitch (b) race hazard _ 8. Give a truth table to prove that A = AB + AB. That is, A by itself is equal to the expression (A AND B) OR (A AND not-B). [Show three intermediate value columns for not-B, (A AND B) and (A AND not-B).] 9. Consider the following circuit diagram [figure given] (a) Give the logic expression in sum of products form for F. (b) Give the logic expression in sum of products form for G and the truth table for G. (c) Give the maximum circuit depth. 10. Give the truth table (characteristic table) for the JK flip-flop. 11. Can you easily make a JK flip-flop into a D flip-flop? If so, show a circuit diagram in which the the JK flip-flop is represented as a single component (that is, as a box with J, K, and CLK inputs and Q and not-Q outputs). 12. 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. Example sequential logic design questions (harder ones are typically for extra credit) 13. 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, and Q(t), and outputs S and Q(t+1). (b) Give the state diagram. 14. Consider extending the serial adder circuit to a two-bit-serial binary adder (that is, a circuit in which X, Y, and S will each be two-bit signals). 2 +---------+ X --/-->| | sum 2 2 | |---------------------/-> S Y --/-->| adder | | | carry +---+ .---->| |------------->| |---. | +---------+ | | | | +---+ | `--------------------------------------' (a) How many flip-flops will be needed? Explain your answer. (b) How many rows would there be in the state transition table? Explain your answer. 15. Consider a two-bit saturating up-down counter. (a) Draw the state transition diagram. Label the up transitions with '1' and the down transitions with '0'. (b) Give the state transition table. (c) Give a circuit implementation for this counter.