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 floatingpoint 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 fanin decoder latch
glitch fanout multiplexer flipflop
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 flipflops 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 flipflops, 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 flipflop. (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 flipflop can be made into a T flipflop. The
T flipflop 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 flipflop.
(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