CS 311 EXAM 2 (MONEY MAKER!!!!!!!!!!!!!!!)

Tradeoff: Harvard vs Von Neumann

Harvard trades flexibility for optimization; Von Neumann trades some optimization for flexibility (the common choice).

Von Neumann architecture

ONE memory for instructions and data. Flexible (split can change as you go). Used by almost all computers.

Harvard architecture

TWO separate memories (instructions, data). Each can be optimized, but inflexible: sizes fixed up front, can't share spare space.

Design tradeoff (say this on the exam)

A balance among competing goals (cost, speed, power, instruction size, programmer convenience). Improving one hurts another.

Tradeoff: fixed vs variable length

Fixed wastes memory but is faster; variable saves memory but is slower to decode.

Fixed-length instructions

All same size: wastes memory but MUCH faster to fetch/decode (parallel hardware).

Variable-length instructions

Different sizes: saves memory but decoding is iterative and slower.

Iterated in space

Hardware uses parallel copies (one per bit) to work on all bits at once. This is why fixed-length is fast.

Tradeoff: operand counts

More operands = fewer, easier instructions but longer; fewer operands = smaller instructions but more of them. Max is 3.

Tradeoff: CISC vs RISC

CISC: powerful compact programs but complex hardware and slower instructions. RISC: simple fixed-size instructions that finish one per cycle, but more instructions per program.

Tradeoff: SRAM vs DRAM

SRAM fast but power-hungry and big; DRAM slower but low power and dense (so main memory).

Tradeoff: registers vs memory

Registers are very fast but few; memory is large but slow. Keep values you will reuse in registers (eases the Von Neumann bottleneck).

Tradeoff: immediate values

Fast, no register or memory needed, but the value must be known ahead of time and is limited by the bits in the instruction.

Five conceptual units of a processor

Controller, ALU, local data storage (registers), internal interconnection (data path), external interface. Memory and I/O are NOT inside.

Controller

The heart: steps through the program and coordinates all other units.

ALU

Does computation (math, shifts, Boolean). ONE operation at a time, only when the controller directs it. No storage of its own.

External interface

Connects the processor to memory and I/O devices (buses = parallel wires).

Five pipeline stages (in order)

Fetch, Decode, Execute, Memory, Store (F-D-E-M-S).

Pipeline throughput

Once full with no stalls, one instruction finishes every clock cycle (first one in cycle 5).

Stall

A stage must wait, usually because an instruction needs a result an earlier one hasn't produced.

Bubble

The gap a stall sends down the pipeline.

Causes of stalls

Data dependency, branch to a new location, subroutine call, invoking a coprocessor.

Fixes for stalls

Reorder instructions, insert NOP (software); forwarding (hardware).

Forwarding

Hardware passes the ALU result directly to the next instruction's ALU input, avoiding a stall.

NOP

No operation: executes but does nothing; burns a cycle.

ISA (instruction set architecture)

Instruction set + instruction representation. Interface between software and hardware.

ISA part 1: instruction set

The operations the hardware executes, the values they work on, and the results they produce.

ISA part 2: instruction representation

The binary format of instructions: which bits are opcode, which are operands.

IBM System/360

A family of small/medium/large computers sharing ONE ISA, so software ran on all. Same instructions, different implementations.

Fetch-execute cycle

Repeat forever: fetch the next instruction, execute it. The processor never stops; it only fetches and executes.

Instruction (two parts)

Opcode + operand(s).

Opcode

Binary code that uniquely identifies the instruction.

Operand

Value an instruction needs: a register, a memory address, or an immediate value.

Zero-operand (stack)

Operands are implicit, on top of a stack. A = B + C: push B, push C, add, pop A.

One-operand

Implicit accumulator register holds one operand and the result. A = B + C: load B, add C, store A.

Two-operand

Result overwrites the second operand. A = B + C: move B A (copy B into A), then add C A (A gets A + C).

Three-operand

Third operand is an explicit destination. A = B + C: add B C A (one instruction). Fewer instructions, but each is longer.

Operand cost order

Immediate < register < direct memory < indirect < double indirect.

Immediate value

The data itself stored in the instruction. Fast, but value must be known ahead and is size-limited.

Result operand can never be

An immediate value (must be a register or memory address).

Implicit vs explicit operand encoding

Implicit: type in opcode (many opcodes). Explicit: type field in each operand (bigger operands).

Stack

LIFO data structure.

Reverse Polish notation

Operands first, operator last (A B +). How stack machines work.

Register-offset operand

Register plus an offset; great for struct fields.

Direct vs indirect vs double indirect

Direct: operand names the address. Indirect: address is held in a register/memory. Double indirect: pointer to a pointer (slowest).

SRAM

Latch-based: fast, but high power/heat and takes more space.

DRAM

Capacitor-based (charged = 1): lower power, denser, but must be refreshed.

Refresh

Circuit that continuously rewrites every DRAM bit before its charge leaks away.

Volatile

Loses contents when power is off (both SRAM and DRAM).

Word address and offset

W = B div N, O = B mod N. With N a power of 2 it's just bit extraction (low bits = offset).

Byte address 17, 4-byte words: word and offset?

Word 4, offset 1 (17 = 4x4 + 1). In binary 10001: low 2 bits (01) = offset, the rest (100) = word.

Byte address 11, 4-byte words: word and offset?

Word 2, offset 3 (11 = 2x4 + 3).

Address size

k bits = 2^k bytes. 32-bit = 4 GB (gigabytes). 64-bit = 2^64 bytes.

Alignment

N-byte item starts at a multiple of N. Unaligned = exception or slow read-modify-write.

Struct padding tip

Order members largest to smallest to save space.

Memory banks

Identical modules joined into one big memory; helps keep code and data separate.

Interleaving

Consecutive words in different modules; low bits pick the module; helps sequential access.

SDRAM / DDR / QDR

Synchronous clock with the processor / double data rate / quad data rate (power-of-2 multiples).

Fetch-store paradigm

Memory can only fetch (read) and store (write). Store overwrites; nothing is deleted.

Why registers/cache are faster than RAM

They are on the chip: shorter electron travel and smaller.

Pointer

A variable holding a memory address. Memory has no pointer types; the compiler does.

Memory Levels 0 / 1 / 2

Level 0: individual bits. Level 1: array of bytes addressed from 0. Level 2: word-address architecture (bytes grouped into words).

Memory dump row

A hex listing of memory, 16 bytes per row, so adjacent row addresses differ by 16.

FF in hex

255 = 2^8 - 1 (one byte = two hex digits).

Four processor types (least to most flexible)

Fixed, selectable, parameterized, programmable.

Fixed logic

Hardwired for one task.

Selectable logic

Control lines choose among functions (e.g., an ALU).

Parameterized logic

One function whose behavior is set by parameters (e.g., hash with constants p and q).

Programmable logic

Steps come from a program in memory; can change each time.

Coprocessor

Special-purpose processor under another processor's control (e.g., floating point accelerator).

Microcontroller

Programmable processor that controls a physical system (car engine, door); program usually in ROM.

Program counter / instruction pointer

Holds the address of the next instruction.

Clock rate vs instruction rate

NOT the same. Floating point multiply/divide, memory, and I/O take extra cycles.

Bootstrapping

Startup: boot code (boot loader) loads the OS from a device into memory and branches to it.

Pipeline transparency

Results are the same with or without a pipeline; it only affects speed.

CISC

Many complex, variable-size instructions (e.g., Intel x86).

RISC

Small set of simple, fixed-size instructions; one completes per cycle (ARM, MIPS, SPARC).

Why MIPS is RISC

Small instruction set (well under 50) and simple fixed-size instructions.

Von Neumann bottleneck

Every fetch-execute cycle reads RAM at least once, so memory limits speed. Fix: keep data in registers.

Register

Memory on the CPU chip: very fast, fixed size (e.g., 64 bits).

Register allocation

Choosing which values live in registers.

Register spilling

Moving a register value back to memory to free the register.

Register banks / conflict

Operands may need different banks; same bank = conflict, fixed with an extra copy instruction.

Absolute branch (jump)

Loads a specific address into the program counter.

Relative branch

Adds a positive or negative offset to the program counter.

Condition codes

ALU status bits: positive, negative, zero, overflow (overflow = error).

Conditional branch

Tests condition codes to decide whether to branch (e.g., branch if zero).

Return address: stack vs register

Stack (jsr) is slower; register/link register (bl) is faster and avoids stalls.

ARM argument passing

First three arguments in registers, extra on the stack.

MIPS register 0

Always holds zero.

Minimalism / elegance / orthogonality

Fewest instructions / balanced and symmetric / each instruction does a unique task with no overlap.

Clock

Circuit (crystal-driven) that pulses at a regular rate to coordinate the processor's circuits. Hertz = cycles per second.

What causes a branch?

if/else, loops (repetition), and function calls.

Cache invalidation

Marking stored cache data as invalid so it gets overwritten; makes keeping data in fast storage tricky.

CAM / TCAM

Compare the key against all slots in parallel (fast, expensive, hot). TCAM adds a don't-care bit for partial/longest-prefix matches.