330 Spring 2007 -- Exam 1 Name: __________________
No calculators or other aids.
1. Give the power of 10 associated with these prefixes. (1 pt. each)
kilo ________ giga ________ milli ________ nano ________
mega ________ tera ________ micro ________ 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 Whetstone
server chip CPI geometric mean Dhrystone
supercomputer yield workload speedup SPEC
a. _________________ a computer used inside another device running one
or more predetermined applications
b. _________________ a small square or rectangle of silicon with logic
circuits fabricated onto the surface
c. _________________ a semiconductor device used as a switch
d. _________________ measure of work done per unit time
e. _________________ the ratio of working chips to total chips manufactured
f. _________________ the ratio of the execution times of two computer systems
g. _________________ used to summarize a set of rates
h. _________________ used to summarize a set of unweighted execution times
i. _________________ synthetic systems-based (integer) benchmark
j. _________________ a collection of registers, function units (ALUs), and
interconnects
3. Give typical values for current desktop / laptop computers. (6 pts.)
a. clock frequency ___________
b. main memory size ___________
c. hard disk size ___________
4. Find the execution time for a program that executes 10 billion instructions
on a processor with an avg. CPI of 1.5 and a clock frequency of 2 GHz.
(Show your work, including the CPU time equation you use.) (10 pts.)
5. For the following workload and cycle values, find the average CPI. (4 pts.)
type | freq cycles
-------+-------------- CPI = _____________________________
alu | 0.5 2
branch | 0.2 7
ld/st | 0.3 4
6. If a redesign of the computer in question 5 could achieve twice the clock
frequency and reduced the branch CPI value to 1, what would be the speedup?
(10 pts.)
7. Matching -- logic terms. Write the correct term into each blank. (1 pt. each)
minterm circuit depth decoder latch ALU
sum of products fan-in multiplexer flip-flop shift register
don't care fan-out PLA register binary counter
a. _________________ the number of gates in a circuit that form the longest
path from any input to any output
b. _________________ a form of logical representation that employs a
logical OR of minterms
c. _________________ a circuit in which n select values produce an exclusive
output on one of 2**n output lines
d. _________________ a circuit containing arrays of "and" and "or" gates that
can be programmed to implement sum of product expressions
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 that arranges several flip-flops into a common
read/write structure with a single clocking signal
h. _________________ a circuit that connects several flip-flops into a linear
structure where the output of each flip-flop can be
the input to either of its neighbors
___ _ _
8. Give a truth table to prove DeMorgan's Law A+B = A*B [that is, not(A or B)
is equal to not(A) and not(B)]. (5 pts.)
9. Simplify the following Karnaugh maps. (5 pts. each)
\ BC
A \ 00 01 11 10
+----+----+----+----+
0 | 1 | 0 | 0 | 1 | F = fn(A,B,C) = _________________________
+----+----+----+----+
1 | 1 | 1 | 1 | 1 |
+----+----+----+----+
\ BC
A \ 00 01 11 10
+----+----+----+----+
0 | d | 1 | 0 | d | F = fn(A,B,C) = _________________________
+----+----+----+----+
1 | d | 0 | 1 | d |
+----+----+----+----+
10. What is the logical expression for the output of this circuit? Simplify.
(6 pts.)
[circuit diagram given]
11. 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.)
12. To provide proper rounding for floating-point addition, three extra bits
are included in right shifts of fractions: guard, round, and sticky. The
least-significant of these, the sticky bit, stays one whenever a 1 bit is
shifted through it. In designing the logic for a sticky bit, let the
following truth table define the actions for R (reset) and I (input) on
a D flip-flop.
R I Q(t) | Q(t+1)
----------+--------
0 0 0 | 0
0 0 1 | 1
0 1 0 | 1
0 1 1 | 1
1 d d | 0
a) Five rows are shown (using d = don't care in the last row). If the don't
cares are expanded, how many total rows would there be in the full table?
(2 pts.)
b) Using a Karnaugh map for simplifying the expression, give the input
to the D flip-flop in terms of R, I, and Q(t). (10 pts.)
c) Draw the state diagram for the sticky bit logic from the table above.
Note that the ouput is merely the state value. (10 pts.)
Extra Credit. (up to 5 pts.)
For a shift register, we saw that the per-bit logic that sets each D
flip-flop could be arranged as follows:
selects| external
S0 S1 | meaning input
-------+--------------- .----------. | .-----------.
0 0 | no shift | .-----. | | | |
0 1 | right shift | | v v v v |
1 0 | load register | | .----------. |
1 1 | left shift | | |4-to-1 mux|<--S0 |
| | `----------'<--S1 |
| | v |
| | .-----------. |
| | |D flip-flop| |
| | |for ith bit| |
from --' | `-----------' `-- from
(i+1)st Q | Q | ~Q | (i-1)st Q
`------* v
v
Normally, the edge cases (right shift into most leftmost bit and left
shift into rightmost bit) are handled by shifting in a zero. Consider
shifting for signed two's complement numbers and the effect on the
leftmost (sign) bit in the shift register. Let an input signal A
respresent logical shift (A==0) or arithmetic shift (A==1). Show the
modification necessary in the logic circuit for input to the leftmost
(sign) bit for case for select = 0 1 (right shift) and the A input.
Extra Credit. (up to 20 points)
Consider the design of a serial comparator takes that two inputs A and B.
The comparator has three valid states:
state meaning
00 A==B
01 A**B
11 never reached from stating state of 00
Assume the comparator starts in state 00 and changes state as each pair of
bits, A and B, are examined. (Two unsigned words, a and b, are processed
from the least significant bit to most significant bit. Thus, in the first
step, a0 and b0 are supplied to the A and B inputs. In the second step,
a1 and b1 are supplied. Etc.)
Thus, comparing a=1001 with b=0011 means you will run through the following
steps:
initially: state starts at 00 (a==b)
0: compare A=a0=1 and B=b0=1: state stays at 00 (a==b)
1: compare A=a1=0 and B=b1=1: state changes to 01 (a****b)
thus, for these example four-bit unsigned values a=1001 and b=0011, a>b
Note: transitions from state 11 are don't cares (d's). Also, there is no
need to design a state-reset capability for this problem.
a) give the state diagram
b) give the truth table (there is no need for output columns)
c) design a circuit (output is merely the state values)
**