330 Spring 2010 -- Exam 1 Name: ____
No calculators or other aids.
1. Give the power of 10 associated with these prefixes. (1 pt. each)
giga ________ kilo ________ mega ________ micro _______
milli ________ nano ________ peta ________ pico ________
giga +9 kilo +3 mega +6 micro -6
milli -3 nano -9 peta +15 pico -12
2. Matching -- technology/performance terms. Write the correct term from
the list into each blank. (1 pt. each)
embedded computer transistor throughput Hertz
server wafer response time workload
supercomputer die CPU time speedup
a. _______________ a computer with highest cost and performance
b. _______________ the program(s) currently being run and associated inputs
c. _______________ measure of work done per unit time
d. _______________ the ratio of the execution times of two computer systems
e. _______________ unit of measure for clock frequency
f. _______________ a rectangular piece of silicon containing manufactured
integrated circuits (up to millions of transistors)
g. _______________ a computer used inside another device running one or
more predetermined applications
h. _______________ measure of time from user depressing return or clicking
mouse until first output appears
a. supercomputer
b. workload
c. throughput
d. speedup
e. Hertz
f. die
g. embedded computer
h. response time
3. Give the CPU time equation and define the terms you use. (10 pts.)
CPU time = IC * CPI * CCT = ( IC * CPI ) / CR
IC = instruction count
CPI = clock cycles per instruction
CCT = clock cycle time ( = 1/CR where CR = clock rate )
4. Find the execution time for a program that executes 40 million instructions
on a processor with an avg. CPI of 2.5 and a clock frequency of 2 GHz.
(5 pts.)
CPU time = 40*10^6 insts * 2.5 cycles per inst / 2*10^9 cycles per sec
= ( 100 * 10^6 / 2 * 10^9 ) seconds
= 50 milliseconds
5. For the following workload and cycle values, find the average CPI. (5 pts.)
type | freq cycles
-------+-------------- CPI = _____________________________
alu | 0.5 1
ld/st | 0.25 2
branch | 0.25 4
CPI = 0.5*1 + 0.25*2 + 0.25*4 = 0.5 + 0.5 + 1 = 2
6. If a new compiler for the computer in question 5 could reduce the number
of instructions to 60% 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.2 1
ld/st | 0.45 2
branch | 0.35 4
new CPI = 0.2*1 + 0.45*2 + 0.35*4 = 0.2 + 0.9 + 1.4 = 2.5
new IC = 0.6 * old IC
old CPU time IC * 2 * CCT 2 _
speedup = ------------ = ------------------ = --- = 1.3
new CPU time 0.6*IC * 2.5 * CCT 1.5
7. Matching -- logic terms. Write the correct term into each blank. (1 pt. each)
minterm race condition half adder register
sum of products circuit depth full adder PLA
don't care fan-in decoder latch
glitch fan-out multiplexer flip-flop
a. _________________ a short but undesired signal
b. _________________ the number of signals in a circuit that can be supplied
as valid inputs from the output of a single gate
c. _________________ where the output of a circuit depends on small
differences in signal timing
d. _________________ a circuit in which three input values produce a sum
and carry output
e. _________________ a circuit in which n select values produce an exclusive
output on one of 2**n output lines
f. _________________ a memory element in which the stored state can only
change once per clock cycle
a. glitch
b. fan-out
c. race condition
d. full adder
e. decoder
f. flip-flop
8. Simplify the following Karnaugh maps of function F. (4 pts. each)
\ BC
A \ 00 01 11 10
+----+----+----+----+
0 | 1 | 0 | 1 | 1 | F = fn(A,B,C) = _________________________
+----+----+----+----+
1 | 0 | 0 | 1 | 0 |
+----+----+----+----+
\ CD
AB \ 00 01 11 10
+----+----+----+----+
00 | 1 | 0 | 0 | 0 | F = fn(A,B,C,D) = _______________________
+----+----+----+----+
01 | 1 | 1 | d | 1 | d = don't care
+----+----+----+----+
11 | 1 | d | d | 0 |
+----+----+----+----+
10 | 1 | 0 | d | 0 |
+----+----+----+----+
\ BC
A \ 00 01 11 10
+----+ +----+ +---+
0 1 | 0 | 1 | | 1 F = fn(A,B,C) = ~A*~C + B*C
+----+ + + +---+
1 0 0 | 1 | 0
+----+
\ CD
AB \ 00 01 11 10
+----+
00 | 1 | 0 0 0 F = fn(A,B,C,D) = ~A*B + ~C*~D
+----+----+----+----+
01 | 1 | 1 | d | 1 |
+----+----+----+----+
11 | 1 | d d 0
+----+
10 | 1 | 0 d 0
+----+
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.)
.---------------.
| |
input --->| combinational |-----------------> output
| logic |
.-->| |--> next state --.
| | | |
| `---------------' |
| |
| .---------. |
`-- current state <--| memory |<-----'
| element |
`---------'
10. Consider the following truth table.
(a) Give the state diagram. Note that there are no inputs or outputs
to place on the transition arcs. (5 pts.)
(b) Give the simplified logic expressions for A(t+1), B(t+1), and C(t+1).
Use K-maps if needed. (3 pts.)
(c) Show the implementation using three D flip-flops. (4 pts.)
(d) Give the name of the resulting circuit. (3 pts. extra credit)
A(t) B(t) C(t) | A(t+1) B(t+1) C(t+1)
---------------+---------------------
0 0 0 | 0 0 0
0 0 1 | 0 0 0
0 1 0 | 0 0 1
0 1 1 | 0 0 1
1 0 0 | 0 1 0
1 0 1 | 0 1 0
1 1 0 | 0 1 1
1 1 1 | 0 1 1
(a) .---.
|100|
`---'\ .---.
>--->|010|
.---./ `---'\ .--.
|101| \ v \
`---' \ .---. .---. |
>--->|001|--->|000| |
.---. / `---' `---' |
|110| / \ /
`---'\ .---./ `--'
>--->|011|
.---./ `---'
|111|
`---'
(b) A(t+1) = 0
B(t+1) = A(t)
C(t+1) = B(t)
(c) +-----+ +-----+ +-----+
0-->| Q|-->| Q|-->| Q|-->
| A _| | B _| | C _|
| Q|- | Q|- | Q|-
+-----+ +-----+ +-----+
(d) shift register
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 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.
There is no separate output signal. (10 pts.)
(a) eight
(b) \ I Q(t)
R \ 00 01 11 10
+----+----+----+----+
0 | 0 | 1 | 1 | 1 | Q(t+1) = ~R*I + ~R*Q(t)
+----+----+----+----+
1 | 0 | 0 | 0 | 0 |
+----+----+----+----+
(c) 01
.---. .----. .---.
/ v.---./ v.---./ \
00,1d | | 0 | | 1 | | 00,01
\ /`---'^ /`---'^ /
`---' `----' `---'
1d