[Note: used different textbook in Fall 2007]
330 Fall 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. Simplify the following Karnaugh map of function F. (6 pts.)
\ BC
A \ 00 01 11 10
+----+----+----+----+
0 | 1 | 0 | 0 | 1 | F = fn(A,B,C) = _________________________
+----+----+----+----+
1 | 1 | 1 | 1 | 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. (8 pts.)
10. A sequential circuit has one D flip-flop, two inputs X and Y, one output
Z, and is specified by the following logic equations:
Q(t+1) = Q(t) xor Y
Z = Q(t) xor X
(a) Give the circuit implementation. (5 pts.)
(b) Give the truth table. (5 pts.)
(c) Give the state diagram. (5 pts.)
11. 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 JK flip-flop.
Q(t) R I | Q(t+1)
----------+--------
0 0 0 | 0
0 0 1 | 1
1 0 d | 1
d 1 d | 0
(a) Draw the state diagram for the sticky bit logic from the table above.
Note that the ouput is merely the state value. (5 pts.)
(b) Four rows are shown (using d = don't care in the last two rows). If
the don't cares are expanded, give the full table. (5 pts.)
Q(t) R I | J K | Q(t+1) The JK excitation table is
-------------+--------+--------
| | Q(t) Q(t+1) | J K
| | -------------+-----
| | 0 0 | 0 d
| | 0 1 | 1 d
| | 1 0 | d 1
| | 1 1 | d 0
(c) Using two Karnaugh maps for simplifying the expressions, give the
inputs to the JK flip-flop in terms of Q(t), R, and I. (5 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.