CS 244 A1

Translation

Converts a whole program from one language to another before it runs (e.g. compiling); produces a standalone translated program.

Interpretation

Executes source instructions directly, one at a time, without producing a separate translated program.

Multilevel machine

A computer built as a stack of levels (digital logic, microarchitecture, ISA, OS, assembly, high-level language), each hiding the details of the level below it.

Virtual machine (levels sense)

The idea that each level in a multilevel machine "understands" its own language, as if it were a machine in its own right.

Microcode

Very simple instructions stored in fast control memory that implement a machine's ISA-level instructions in hardware/firmware.

1st computer generation

Vacuum tubes.

2nd computer generation

Transistors.

3rd computer generation

Integrated circuits (ICs).

4th computer generation

VLSI / microprocessors.

5th computer generation

Low-power, multicore, mobile-era design.

Von Neumann architecture

A single memory holds both instructions and data (the "stored program" concept); the CPU fetches, decodes, and executes instructions sequentially over one bus.

Von Neumann bottleneck

The performance limit caused by instructions and data sharing one memory bus, which the CPU must use for both.

PDP-8 significance

Popularised the minicomputer: a simple, orthogonal, affordable architecture.

IBM 360 significance

Introduced one compatible instruction-set architecture spanning a whole family of machines at different price points.

Moore's Law

An observation (not a physical law) that the number of transistors on an affordable chip roughly doubles every ~18-24 months.

Computer spectrum (small to large)

Disposable/embedded -> mobile & games consoles -> servers -> mainframes -> supercomputers.

Ki (kibi)

2^10 = 1024, the binary prefix (vs. decimal kilo = 1000).

Mi (mebi)

2^20 = 1,048,576, the binary prefix (vs. decimal mega = 1,000,000).

Gi (gibi)

2^30 = 1,073,741,824, the binary prefix (vs. decimal giga = 1,000,000,000).

Why disk sizes look smaller than advertised

Manufacturers quote decimal GB (10^9); operating systems report binary GiB (2^30), which is a larger unit, so the same disk shows a smaller number of GiB.

Registers

Small, very fast storage locations built into the CPU.

ALU

Arithmetic Logic Unit - performs arithmetic and logical operations on register values.

Fetch (cycle step)

Read the instruction at the address in the program counter into the instruction register; advance the program counter.

Decode (cycle step)

Determine the instruction's opcode and its operands.

Execute (cycle step)

Perform the operation - an ALU op, a memory access, or a branch.

RISC core idea

Simple, fixed-length instructions, a load/store architecture, a large register set, and instructions designed to execute in about one cycle, enabling pipelining.

Pipelining

Overlapping the fetch/decode/execute stages of successive instructions so several are in flight at once, improving throughput.

Pipeline hazard

A data, control, or structural conflict between overlapping instructions that can stall a pipeline.

Superscalar architecture

Issuing and executing more than one instruction per clock cycle using multiple parallel execution units.

Big-endian

Stores the most-significant byte of a multi-byte value at the lowest memory address.

Little-endian

Stores the least-significant byte of a multi-byte value at the lowest memory address.

Why cache hit rate matters so much

Cache access is much faster than main memory access, so the hit rate dominates the effective (average) memory access time - small hit-rate gains produce large performance gains.

Memory hierarchy (fastest to slowest)

Registers -> Cache -> Main memory (RAM) -> Secondary storage (SSD/HDD).

Track

A concentric ring on a disk platter.

Sector

A fixed-size chunk of a track.

Cylinder

The same track across every platter - accessible without moving the read/write head.

Platter

A physical disk inside a hard drive on which data is stored magnetically.

Seek time

The time for the read/write head to move to the correct track.

Rotational latency

The time waiting for the correct sector to rotate under the head - on average, half a full rotation.

RAID 0

Striping across disks - no redundancy, best performance and capacity.

RAID 1

Mirroring - full duplicate, good safety, halves usable capacity.

RAID 5

Striping plus distributed parity - survives one disk failure.

RAID 6

Like RAID 5 but with double parity - survives two disk failures.

SSD wear levelling

Spreading writes evenly across flash blocks (instead of reusing the same cells) since each cell can only be erased a limited number of times.

Why SSDs can't overwrite in place

Flash memory is organised into pages (the read/write unit) grouped into blocks (the erase unit) - a page can't be overwritten without erasing its whole block first.

DSL (digital subscriber line)

Reuses existing copper telephone lines for digital data, typically asymmetric (faster downstream than upstream).

Fibre-optic advantage

Transmits data as light pulses, giving far higher bandwidth and lower attenuation over distance than copper.

ASCII

A 7-bit code (0-127) for English letters, digits, and control characters - one byte per character.

Unicode

A character set assigning a unique code point to every character across essentially all the world's writing systems.

UTF-8

A variable-width encoding of Unicode code points into 1-4 bytes, backward-compatible with ASCII.

Sign-magnitude negation

Flip the sign bit only; magnitude stays the same.

One's complement negation

Invert every bit.

Two's complement negation

Invert every bit, then add 1.

Why two's complement is preferred

Only one representation of zero, and ordinary binary addition works directly without special-case logic.

IEEE 754 single precision - total bits

32 bits: 1 sign + 8 exponent + 23 mantissa/fraction.

IEEE 754 - sign bit meaning

0 = positive, 1 = negative.

IEEE 754 - exponent bias

127 - the stored exponent equals the true exponent plus 127.

IEEE 754 - mantissa's implicit bit

There's an implicit leading 1 before the stored fraction bits (in the normalised form).

Declaration vs. definition (C)

A declaration introduces a name and type without necessarily allocating storage (e.g. extern int x;); a definition actually allocates storage (e.g. int x;).

auto storage class

Default for local variables - allocated on the stack, lifetime is the enclosing block.

static storage class (local var)

Allocated once for the whole program's lifetime; retains its value between calls to the function.

extern storage class

Refers to a variable definition that lives elsewhere, usually another file.

register storage class

A hint to the compiler to keep the variable in a CPU register - mostly a historical curiosity today.

Struct vs. Java class

A struct groups fields into one aggregate type with no methods, no access control, and no inheritance.

Array bounds checking in C

None - reading or writing outside declared bounds is undefined behaviour, not a caught runtime error.

Array decay

In most expressions, an array's name decays to a pointer to its first element (but sizeof still reports the whole array's size).

Preprocessor's role

Runs before compilation and performs purely textual substitution: #include, #define macros, #ifdef/#ifndef conditional compilation.

Macro pitfall

A function-like macro like #define SQUARE(x) xx isn't parenthesised, so SQUARE(a+b) expands to a+ba+b, not (a+b)*(a+b).

Prefix ++x

Increments x first; the expression evaluates to the new value.

Postfix x++

The expression evaluates to the old value; x is incremented afterwards.

First-class feature

Something a language lets you store in a variable, pass as an argument, return from a function, and create at runtime - pointers are first-class in C.

Reifies / reifiable

Turns an otherwise-invisible concept (like a memory address) into an explicit, manipulable value a program can compute with.

Evaluation strategy: call-by-value

A copy of the argument's value is passed to a function - C's only parameter-passing mode.

Covariance

A subtyping relationship is preserved in the same direction when building a new type from it (if Sub is-a Super, F(Sub) is-a F(Super)).

Invariance

No subtyping relationship is preserved - F(Sub) and F(Super) are unrelated even if Sub is-a Super (roughly describes C pointer types).

Pointer width

Matches the target architecture's address size - 4 bytes on 32-bit, 8 bytes on 64-bit, regardless of the pointed-to type.

malloc

Allocates a given number of bytes on the heap; returns a void* (or NULL on failure).

free

Releases heap memory back to the system; using it afterwards is a use-after-free.

Memory leak

Allocated memory that's never freed and whose only pointer has been lost - can't be reached or reclaimed until the program exits.

Double pointer (T**) use case

Needed when a function must modify the caller's pointer itself, or for dynamically-allocated 2D arrays.

-> operator

Shorthand for accessing a struct member through a pointer - p->field means (*p).field.

Function pointer

A variable holding the address of a function, letting you pass functions as arguments or select between them at runtime.

Hamming code parity bit positions

Positions that are powers of two: 1, 2, 4, 8, … Data bits fill the remaining positions.

Purpose of a Hamming code

To detect and correct a single flipped bit in a transmitted codeword using redundant parity bits.