330 Fall 2011  Exam 1 Name: ____
No calculators or other aids.
1. Give the power of 10 associated with these prefixes. (1 pt. each)
mega ________ tera ________ micro ________ nano ________
6, 12, 6, 9
2. Matching  technology/performance terms. Write the correct term from
the list into each blank. (2 pts. each)
embedded computer chip clock cycle arithmetic mean Linpack
desktop computer die CPU time harmonic mean Whetstone
server wafer speedup geometric mean Dhrystone
supercomputer CPI workload response time SPEC
transistor Hertz memory throughput TPCC
a. _________________ a computer used inside another device running one
or more predetermined applications
b. _________________ a computer that provides computation, file storage,
and/or printing to multiple users across a network
c. _________________ a semiconductor device used as a switch
d. _________________ unit of measure for clock frequency
e. _________________ used to summarize a set of normalized performance
values
f. _________________ used to summarize a set of rates
g. _________________ a transactionprocessing benchmark
h. _________________ a synthetic benchmark that was once a popular basis
of measuring floatingpoint performance
a. embedded computer
b. server
c. transistor
d. Hertz
e. geometric mean
f. harmonic mean
g. TPCC
h. Whetstone
3. Give typical values for current desktop / laptop computers. (6 pts.)
a. clock frequency ___________
b. main memory size ___________
c. hard disk size ___________
a. 2 GHz
b. 4 GB
c. 1 TB
4. Find the execution time for a program that executes 3 billion instructions
on a processor with an avg. CPI of 1.5 and a clock frequency of 3 GHz.
(Show your work, including the CPU time equation you use.) (8 pts.)
CPU time = ( IC * CPI )/CR
= ( 3x10^9 insts * 1.5 cycles/inst ) / 3x10^9 cycles/sec
= 1.5 secs
5. For the following instruction set workload and cycle values, find the
average CPI. (3 pts.)
type  freq cycles
+
alu  0.5 0.5
branch  0.2 1
ld/st  0.3 2
avg CPI = 0.5*0.5 + 0.2*1 + 0.3*2
= 0.25 + 0.2 + 0.6
= 1.05
6. A redesign of the computer in question 5 is proposed that can achieve
twice the clock frequency but requires that the load/store CPI value
double. Would the redesign be faster, and if so, what would be the
speedup? (8 pts.)
new CPI
type  freq cycles
+
alu  0.5 0.5 avg CPI = 0.5*0.5 + 0.2*1 + 0.3*4
branch  0.2 1 = 1.65
ld/st  0.3 >>4<<
speedup
( IC * 1.05 ) / CR 2.1
speedup =  =  = 1.27
( IC * 1.65 ) / 2*CR 1.65
7. Consider a computer that has an enhanced mode of execution that can
speedup up execution by a factor of ten. For what fraction of the
normal execution time must the 10x enhancement be used to achieve an
overall speedup of 2? Show the result as a fraction. (8 pts.)
1
2 = 
(1f) + f/10
multiply both sides by ((1f)+(f/10))/2
1f + f/10 = 1/2
multiply both sides by 10
10  10*f + f = 5
subtract 10 from both sides
9f = 5
divide both sides by 9
f = 5/9
8. Matching  logic terms. Write the correct term from the list into each
blank. (2 pts. each)
minterm don't care gate half adder flipflop
sum of products glitch PLA full adder register
race condition fanin ALU decoder shift register
circuit depth fanout latch multiplexer ring counter
a. _________________ undesired signal lasting only a short time
b. _________________ unused value that can be arbitrarily assigned 0 or 1
c. _________________ where the output of a circuit depends on small
differences in signal timing
d. _________________ the number of gates in a circuit that form the
longest path from any input to any output
e. _________________ a circuit with n D flipflops connected together in
a circular shift pattern and designed to provide
an exclusive output of 1 on only one of the n
output lines each clock cycle in successive order
f. _________________ a circuit in which n select values route one of
2**n input values to the single output
a. glitch
b. don't care
c. race condition
d. circuit depth
e. ring counter
f. multiplexer
9. Consider the following circuit. The * represents a connection, the o
represents an inversion (or NOT), the DFF represents a D flipflop,
and both gates are AND gates. The clock input is assumed and not
depicted.
___
X * \
 ___ .. and  Z
` \  Q___/
and  DFF _
Y o___/  Q
`'
(a) Give the input to the DFF as a logic expression in terms of X
and Y, and give the function Z as a logic expression in terms of
X and Q(t).
(b) Give the truth table for the circuit in terms of inputs X and Y,
current state Q(t), next state Q(t+1), and output Z.
(c) Give the state diagram for the circuit.
(a) DFF input = Q(t+1) = X*(~Y)
Z = X*Q(t)
(b) X Y Q(t)  Q(t+1) Z
+
0 0 0  0 0
0 0 1  0 0
0 1 0  0 0
0 1 1  0 0
+
1 0 0  1 0
1 0 1  1 1
1 1 0  0 0
1 1 1  0 1
(c) 10/0
.. .. ..
00/0, / v../ v../ \
01/0,   0   1   10/1
11/0 \ /`'^ /`'^ /
`' `' `'
00/0,
01/0,
11/1
10. Consider a state machine with two inputs, R and I (reset and in),
that, after a reset R, outputs a 1 whenever the input I is one in two
consecutive cycles. Reset causes any memory of an I=1 input 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 1 0 0 0 0 0 1 1 0 0
input I: 0 1 0 1 1 1 0 1 0 1 1 1 1 1 0 1 1 1 1 1
output S: 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 1
(a) Give the state diagram. (There should be only two states.)
(b) Give the state transition table with inputs R, I, current state
Q(t), next state Q(t+1), and output S.
(c) Give the simplified logic expressions for Q(t+1) and S.
(d) Extend the state transition table with J and K columns and, using
the JK excitation table, fill in the appropriate values for causing
the required state transitions.
Q(t) Q(t+1)  J K
+
0 0  0 d
0 1  1 d
1 0  d 1
1 1  d 0
(e) Give the simplified logic expressions for J and K.
(a) 01/0
.. .. ..
00/0, / v../ v../ \
10/0,   0   1   01/1
11/0 \ /`'^ /`'^ /
`' `' `'
00/0,
10/0,
11/0
(b) R I Q(t)  Q(t+1) S
+
0 0 0  0 0
0 0 1  0 0
0 1 0  1 0
0 1 1  1 1
+
1 0 0  0 0
1 0 1  0 0
1 1 0  0 0
1 1 1  0 0
(c) Q(t+1) = (~R)*I
S = (~R)*I*Q(t)
(d) R I Q(t)  Q(t+1) S  J K
++
0 0 0  0 0  0 d
0 0 1  0 0  d 1
0 1 0  1 0  1 d
0 1 1  1 1  d 0
++
1 0 0  0 0  0 d
1 0 1  0 0  d 1
1 1 0  0 0  0 d
1 1 1  0 0  d 1
(e) \ I Q(t)
R \ 00 01 11 10
+++====+====+
0  0  d  d  1  J = (~R)*I
+++====+====+
1  0  d  d  0 
+++++
\ I Q(t)
R \ 00 01 11 10
+====+====+++
0  d  1  0  d  K = (~I) + R
+==+==+====+====+
1  d  1  1  d  note: (~I) + R = ~(I*(~R)) = ~J
+====+====+====+====+
XC. Show the implementation of a 3bit register using D flipflops with a
twobit control value, where the control values and actions are given
in the table.
i2 i1 i0 (inputs) control  action
   +
++ 2 0 0  hold value
clock > / control 0 1  external load
++ 1 x  clear to zero
  
o2 o1 o0 (outputs)
each bit position has this design
in
 0 0
..   
 ++
 0 1 2 3
   control_1 (high bit of mux select)
  4to1 control_0 (low bit of mux select)
  mux 
 ++
 
 ++
  D 
  
  DFF 
clock > 
  Q 
 ++
 
`*

out
i2 i1 i0
  
 .** cntl_1
 .** cntl_0
..  0 0  ..  0 0  ..  0 0 
 ++   ++   ++ 
  4to1'   4to1'   4to1'
  mux '   mux '   mux '
 ++  ++  ++
     
 ++  ++  ++
 .> DFF   .> DFF   .> DFF 
 ++  ++  ++
        
clk **' 
     
`* `* `*
  
o2 o1 o0
other solutions might use one of these base designs
in

.. 
 ++
 0 1
 mux control_0 (low bit of mux select)
 ++
 
  0
  
 ++
 0 1
 mux control_1 (high bit of mux select)
 ++
 
 ++
  D 
  
  DFF 
clock > 
  Q 
 ++
 
`*

out
in

++
 D  c_1 c_0  action
  +
  0 0  hold value
__  DFF  0 1  external load
control_0  \   1 x  clear to zero
 \  
clock AND> clk 
 /  
.o__/   clear (and preset) are
   asynchronous inputs that
control_1 *clear  will affect the state of
  the flipflop even when
 Q  the clock is not high
++

out