[Note: used different textbook in Spring 2008]
330 Spring 2008 -- Exam 1 Name: __________________
No calculators or other aids. (110 points total, will be graded out of 100)
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 arithmetic mean Linpack
desktop computer transistor CPU time harmonic mean Whetstone
server wafer CPI geometric mean Dhrystone
supercomputer yield workload speedup SPEC
a. _________________ a computer that provides computation, file storage,
and/or printing to multiple users across a network
b. _________________ the ratio of working chips to total chips manufactured
c. _________________ the slice of silicon upon which integrated circuits
are built
d. _________________ a semiconductor device used as a switch
e. _________________ measure of work done per unit time
f. _________________ the ratio of the execution times of two computer systems
g. _________________ used to summarize a set of unweighted execution times
h. _________________ used to summarize a set of rates
i. _________________ a synthetic floating-point 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 4 billion instructions
on a processor with an avg. CPI of 1.25 and a clock frequency of 2 GHz.
(6 pts.)
5. For the following workload and cycle values, find the average CPI. (4 pts.)
type | freq cycles
-------+-------------- CPI = _____________________________
alu | 0.3 1
ld/st | 0.2 2
branch | 0.5 4
6. If a new compiler for the computer in question 5 could reduce the number
of instructions to 1/2 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.6 1
ld/st | 0.2 2
branch | 0.2 4
7. Matching -- logic terms. Write the correct term into each blank. (1 pt. each)
minterm race condition half adder ALU register
sum of products circuit depth full adder PLA shift register
don't care fan-in decoder latch RS latch
glitch fan-out multiplexer flip-flop JK flip-flop
a. _________________ a form of logical representation that employs a
logical OR of minterms
b. _________________ the number of gates in a circuit that form the longest
path from any input to any output
c. _________________ where the output of a circuit depends on small
differences in signal timing
d. _________________ undesired signal lasting only a short time
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 in which n select values produce an exclusive
output on one of 2**n output lines
h. _________________ a circuit containing arrays of "and" and "or" gates
that can be programmed to implement sum of products
logic expressions
8. Simplify the following Karnaugh maps of function F. (4 pts. each)
\ BC
A \ 00 01 11 10
+----+----+----+----+
0 | 1 | 0 | 0 | 1 | F = fn(A,B,C) = _________________________
+----+----+----+----+
1 | 0 | 0 | 1 | 1 |
+----+----+----+----+
\ BC
A \ 00 01 11 10
+----+----+----+----+
0 | 1 | d | 0 | 0 | F = fn(A,B,C) = _________________________
+----+----+----+----+
1 | d | d | 0 | 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. 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, current state
Q(t), next state Q(t+1), and output S. (8 pts.)
(b) Give the state diagram. (8 pts.)
11. Consider a state machine with two input, R and I (reset and in), that,
after a reset R, outputs a 1 on each second 1 that it receives on input
I. (Reset causes any count of previous and current I=1 inputs 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 0 1 0 0 0 0 0 0 1 1 0 0
input I: 0 1 0 1 1 1 1 0 1 0 1 1 1 1 1 1 0 1 1 1 1 1
output S: 0 0 0 1 0 1 0 0 1 0 0 0 0 1 0 1 0 0 0 0 0 1
(a) Give the state diagram. (8 pts.)
(b) Give the state transition table with inputs R, I, current state
Q(t), next state Q(t+1), and output S. (8 pts.)
(c) Give the simplified logic expressions for Q(t+1) and S. (8 pts.)