330 Fall 2010 -- 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 arithmetic mean Linpack
desktop computer transistor CPU time harmonic mean TPC-C
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 normalized performance ratios
h. _________________ used for determining a computer's rank on the TOP 500
supercomputer list
i. _________________ a synthetic integer benchmark, which was the basis of
calculating relative MIPS values
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. (3 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. (6 pts.)
(b) Give the state diagram. (6 pts.)
11. Consider a state machine that acts as a signal edge detector. There
is one input (I) and two outputs, positive (P) and negative (N). P=1
whenever I transitions from 0 to 1, and N=1 whenever I transitions from
1 to 0. That is, the state machine behaves like this
input I: 0 0 1 0 1 1 0 0 1 1 1 0 0 0 1 1 0 1 0 0
output P: 0 0 1 0 1 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0
output N: 0 0 0 1 0 0 1 0 0 0 0 1 0 0 0 0 1 0 1 0
(For this trace, the state machine starts in a state which records
a prior input of 0.)
(a) Give the state diagram. (5 pts.)
(b) Give the state transition table with input I, current state Q(t),
next state Q(t+1), and outputs P and N. (5 pts.)
(c) Give the simplified logic expressions for Q(t+1), P, and N. (6 pts.)
(d) Draw the circuit using a single D flip-flop. (4 pts.)