CPSC 330 - Fall 2009
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
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.