Doctor of Philosophy - Comprehensive Exam (2008-2009)
Computer Architecture
Highlights of the Readings
Parts of Appendix: Exercises A.1 thru A.22, A.32 thru A.40
A.31 is interesting to think about.
See how to convert boolean functions to circuit diagrams
A.1, A.2, A.3, A.4, A.5
key vocabulary: combinational logic, digital, analog, truth table,
logic gate, Boolean logic functions, AND, OR, COMPLEMENT, NOT, NOR,
NAND, XOR, XNOR, inverter, (not worried about transistors although
stuff about threshold is useful background), communitive property,
principle of duality, distributive property, identity property,
DeMorgan's Theorem, Sum of Products Form, circuit diagram
sample problems:
1) What is the truth table for the circuit in Figure A.15?
2) What is the sum-of-products circuit for the truth table
in Figure A.24?
Standard components
A.9
key vocabulary: components, multiplexer, demultiplexer, decoder,
encoder, priority encoder, programmable logic array (PLA),
ripple carry adder, half adder, full adder
sample problems:
1) Explain how Figure A.29 works.
2) Use notation of Figure A.33 to ipmlement truth table of
Figure A.24.
3) Show how to use multiplexers to implement a 2-bit ripple
carry adder.
Circuit performance
A.11
key vocabulary: propagation delay, latency, rise time, fall time,
power consumption, circuit depth, fan-in.
sample problems:
1) What is the circuit depth of Figure A.22?
2) Redo Figure A.22 so that no component has a fan-in larger than
2? What is the new depth of this Figure? Is it minimal?
Representing finite state machines in circuitry
A.12, A.14, A.15
key vocabulary: sequential logic, finite state machine, inputs,
outputs, state bits, flip-flop, SR flipflop, clocked SR flipflop,
glitch, hazard, clock, cycle time, clock rate, milli, micro, nano,
kilo, mega, giga, hertz, D flip-flop, level-triggered flipflop,
edge-triggered flipflop, negative edge-triggered d flipflop,
state table, Mealy machines, Moore machines.
sample problems:
1) what is the logic diagram for the NOR implementation of
an SR flipflop? (everyone should know this, the simplest,
flipflop)
2) Given the diagram in Figure A.62, if CLK is 0 and D is 1,
what are the values on R, S, and Q? Possible answers are
0, 1, or ?. Use ? in the case where the input conditions of
the question are not sufficient to determine the value on
the wire.
3) Given the situation described in question 2, if the value of
CLK changes from 0 to 1, what is the impact on the values
of R, S, and Q? (same set of 3 possible values)
4) Draw a finite state machine that reads a binary sequence
and outputs 0 if the number of 1's seen so far is even and
1 if the number of 1's seen so far is odd. Convert this
state machine into a circuit diagram for a Moore machine
using only D-flipflops and the basic logic gates (AND, OR,
and NOT).
Registers and counters
A.16, A.17
key vocabulary: tri-state buffer, enable, disable, register, write line,
enable line, clock line
sample problems:
1) if you did not have tri-state buffer as an available feature,
how would you implement a 2-bit register with the same control
inputs using only D flipflops and the basic logic gates (AND, OR,
and NOT).
Chapter 2
key vocabulary: SRC (our standard example for the exam), register
transfer notation (RTN), opcode, operands, result, next instruction,
syntax, semantics, mneumonics, instruction format, program counter,
instruction register, direct addressing, indirect addressing,
displacement, relative addressing, relocatable instructions,
3-register instructions, circular shift, logical shift, arithmetic
shift, link register, processor state registers, main memory,
main memory state, register formats, displacement address,
right arrow notation, register number versus register contents,
relative address, fetch-execute cycle, instruction interpretation,
Table 2.7 notation, metalanguage, bus, tri-state bus, abstract RTN,
concrete RTN, control signals, data path
sample problems:
Exercise 2.4, 2.12 thru 2.26
Chapter 3.1, 3.2
key vocabulary: upward compatibility, workload, benchmark,
program execution time, wall clock time, MIPS, FLOPS, MFLOPS,
RISC, CISC, memory latency, prefetching, pipelining, superscalar
operation, RISC design philosophy, delay slot, speculative
execution
sample problems:
we are pretty much just establishing vocabulary here. such
vocabulary could arise in questions like:
1) explain the RISC design philosophy
or
2) to what degree does the SRC machine follows the RISC
design philosophy.
Chapter 4
key vocabulary: our design process, data path, control signals,
control unit, abstract RTN, concrete RTN, microarchitecture,
1-Bus design, rule of buses, MA, MD, IR, PC, latch, register file,
memory address register, memory data register, ALU, control
sequences, bus skew, estimating minimum clock period (calculating
maximum clock frequency), hardwired controller, control step
generator, 2-bus, 3-bus, calculating percentage speedup,
relation of execution time, instruction count, clocks per instruction,
and clock time, exceptions, interrupting device, exception handler,
memory page, illegal instruction, privileged instruction, page fault,
microstate.
sample problems:
Exercises 4.1 thru 4.7, 4.15, 4.16
4.17 is interesting to think about.
Chapter 6.1, 6.2, 6.3
key vocabulary: digital number representation, radix conversion,
radix point, fixed-point number, overflow, sign-magnitude,
2's complement, 1's complement, floor operator, ceiling operator,
arithmetic shifts, fixed point addition, fixed point subtraction,
ripple carry adders, carry lookahead adder, Figure 6.8 on
multiplication (don't worry about Booth recoding), Figure 6.9 on
division, Figure 6.12 on shifting.
sample problems:
Exercise 6.1 thru 6.12, 6.21, 6.23, 6.24
Chapter 7
key vocabulary: MAR, MDR, memory words, word size, REQUEST, R/W-bar,
RAM, ROM, read, write, memory latency, memory bandwidth, memory
hierarchy, access time, cycle time, block transfer, SRAM, DRAM,
refresh, miss ratio, hit ratio, virtual memory, cache miss,
main memory miss, cache lines, associative-mapped caches,
tag bit, valid bit, associative memory, direct-mapped caches,
block-set associative caches, write thru, write back, dirty bit,
LRU, random replacement, cache access time, memory management unit,
page fault, logical address, virtual address, physical address,
demand paging, page table, access control bit, presence bit, DMA
sample problems:
mostly establishing vocabulary so that you can follow diagrams like
Figures 7.8 and 7.20. stuff on cache and memory hierarchy significantly
impacts the speed of execution of programs, so being able to trace
through the cache and virtual memory algorithms is also important.
Exercise 7.7, 7.19, 7.20, 7.23, 7.25
Chapter 8
key vocabulary: i/o latency, i/o bandwidth, peak bandwidth, i/o interface,
programmed i/o, interrupt-driven i/o, DMA, memory-mapped i/o, command
registers, status registers, device driver, device handler, polling,
interrupt handler, interrupt request line, interrupt acknowledge line,
nested interrupts, critical section, interrupt mask, bus master,
bus request, bus grant, cycle stealing, parity checking, parity bits,
even and odd parity,
sample problems:
Exercise 8.1, 8.4 thru 8.6, 8.11, 8.15, 8.18
Chapter 9
key vocabulary: hard disk drive, platter, read/write head, rpm, disk
surface, disk controller, tracks, sectors, cylinder, typical hard
disk sector organization, disk formatting, disk seek, maximum areal
density, maximum linear bit density, average bit density, unformatted
capacity, formatted capacity, seek time, track-to-track time,
rotational latency, access time, read recalibration, disk zones,
magnetic tape, CD ROM, video monitor, spatial resolution, display
memory, keyboard, mouse, analog to digital converter, digital to
analog converter, quantization error.
sample problems:
mostly we are establishing vocabularly, but in addition to definitional/
explain type questions, we are also setting up calculation questions
like Exercises 9.1 thru 9.4.
Also from this web page:
