Skip to content
Tutorials Center
My learning

Topics

Lesson 67 of 67 ยท Practice and Interview

Computer Organization Cheat Sheet

A quick reference for computer organization: number ranges, IEEE 754 formats, performance equations, pipeline, cache, paging and I/O formulas, with runnable calculators.

This page collects the numbers, tables and formulas you reach for again and again while studying or working with computer organization. It is a reference, not a lesson: every entry links to the lesson that explains it. Bookmark it, and use the two calculators at the end to check your arithmetic.

A useful habit when using any formula here is to check the units. Cycles times seconds-per-cycle gives seconds; bytes divided by bytes-per-block gives blocks. Most wrong answers on exams fail a units check.

Number systems and ranges

Base Digits One digit equals
Binary (2) 0, 1 1 bit
Octal (8) 0 to 7 3 bits
Decimal (10) 0 to 9 about 3.32 bits
Hexadecimal (16) 0 to 9, A to F 4 bits (a nibble)
Power Value Name
2^10 1,024 1 KiB
2^20 1,048,576 1 MiB
2^30 1,073,741,824 1 GiB
2^40 about 1.1 x 10^12 1 TiB

Integer ranges for n bits (see Signed Integers and Two's Complement):

  • Unsigned: 0 to 2^n - 1.
  • Two's complement: -2^(n-1) to 2^(n-1) - 1. Negate by flipping the bits and adding 1.
  • Sign extension copies the sign bit into the new upper bits; zero extension fills with zeros.
  • Carry flag: unsigned result did not fit. Overflow flag: operands with equal signs gave a result of the other sign.

The calculator below prints the ranges and the properties of the three IEEE 754 formats, so you do not have to remember them.

Python Ranges and float formats

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

IEEE 754 at a glance

A value is (-1)^sign x 1.fraction x 2^(exponent - bias) for normal numbers. See Floating-Point Numbers and IEEE 754.

Exponent field Fraction Meaning
All zeros Zero Zero (+0 or -0)
All zeros Non-zero Subnormal: 0.fraction x 2^(1 - bias)
1 to max - 1 Anything Normal number
All ones Zero Infinity
All ones Non-zero NaN (not a number)
  • Machine epsilon (spacing just above 1.0) is 2^-fraction bits: about 1.19e-7 for single and 2.22e-16 for double.
  • Single precision has about 7 decimal digits of precision; double has about 15 to 16.
  • NaN is not equal to anything, including itself. Compare floats with a tolerance.

Boolean algebra

Law AND form OR form
Identity A . 1 = A A + 0 = A
Null A . 0 = 0 A + 1 = 1
Idempotent A . A = A A + A = A
Complement A . A' = 0 A + A' = 1
Absorption A . (A + B) = A A + A . B = A
De Morgan (A . B)' = A' + B' (A + B)' = A' . B'

XOR: A xor B = A . B' + A' . B. NAND and NOR are universal. Half adder: sum = A xor B, carry = A . B. Full adder: sum = A xor B xor Cin, carry-out = A . B + Cin . (A xor B). An n-to-1 multiplexer needs log2(n) select lines; an n-input decoder has 2^n outputs. See Logic Gates and Boolean Algebra and Combinational Circuits.

Performance equations

Text
CPU time        = instruction count x CPI x clock period
                = instruction count x CPI / clock rate
MIPS            = instruction count / (execution time x 10^6)
Speedup         = time before / time after
Amdahl          = 1 / ((1 - p) + p / s)
Gustafson       = (1 - p) + p x N   (p is the parallel fraction of the scaled run)
Average CPI     = sum over classes of (fraction x CPI)

See Measuring Performance and Parallel Processing and Flynn's Taxonomy.

Flynn class Meaning Example
SISD One instruction stream, one data stream A simple single-core CPU
SIMD One instruction, many data items Vector units, GPUs
MISD Many instructions, one data stream Rare (fault-tolerant designs)
MIMD Many instruction streams, many data streams Multicore CPUs, clusters

Instruction set quick facts

  • Common addressing modes: immediate, register, direct, register indirect, indexed, base plus offset, PC-relative. See Addressing Modes.
  • A 32-bit RISC-V R-type instruction has the fields funct7 (7 bits), rs2 (5), rs1 (5), funct3 (3), rd (5) and opcode (7). See Instruction Formats and Encoding.
  • RISC: fixed length, load/store, many registers, easy to pipeline. CISC: variable length, memory operands, complex instructions.
  • Control unit: hardwired (fast, hard to change) or microprogrammed (flexible, slower). See The Control Unit.

Pipelining

The classic stages are IF (fetch), ID (decode and register read), EX (execute), MEM (memory access) and WB (write back). See Instruction Pipelining.

  • Cycles for n instructions on a k-stage pipeline with no stalls: k + n - 1.
  • Ideal speedup over a non-pipelined machine approaches k; stalls and unbalanced stages lower it.
  • Pipeline CPI = 1 + stall cycles per instruction.
  • Load-use hazard: one bubble even with forwarding. Without forwarding, a dependent instruction right behind its producer waits two bubbles in the classic design with split-cycle register file access.
  • Branch penalty adds branch frequency x misprediction rate x flush cycles to the CPI.
  • A 2-bit saturating counter has four states and predicts taken in the upper two. See Branch Prediction.

Cache

flowchart LR
  A["Address (m bits)"] --> T["Tag<br/>m - index - offset"]
  A --> I["Index<br/>log2(sets)"]
  A --> O["Offset<br/>log2(block size)"]

The three fields of a cache address, from most to least significant: tag, index, offset.

Text
blocks in cache   = cache size / block size
sets              = blocks / ways           (direct-mapped: ways = 1; fully associative: sets = 1)
offset bits       = log2(block size)
index bits        = log2(sets)
tag bits          = address bits - index bits - offset bits
AMAT              = hit time + miss rate x miss penalty
AMAT (2 levels)   = T(L1) + m(L1) x [T(L2) + m(L2 local) x T(memory)]
global miss rate  = product of the local miss rates of the levels above and including it
memory stall CPI  = memory references per instruction x miss rate x miss penalty
Mapping Where a block may go Conflict misses
Direct-mapped One line (block number mod lines) Most
n-way set-associative Any of n lines in one set Fewer
Fully associative Any line None (only capacity and compulsory)
  • Misses: compulsory (first touch), capacity (cache too small), conflict (set too crowded).
  • Write-through: update memory every store, usually with a write buffer. Write-back: set the dirty bit, write on eviction. Write-allocate fetches the block on a write miss; no-write-allocate does not.
  • Replacement: LRU, FIFO, random. See Replacement and Write Policies.
  • Coherence (MESI): Modified, Exclusive, Shared, Invalid. See Cache Coherence and Memory Consistency.

Virtual memory

Text
offset bits         = log2(page size)
virtual page number = virtual address bits - offset bits
page table size     = 2^(VPN bits) x entry size       (single level)
physical address    = frame number x page size + offset
EAT with TLB        = h x (t_tlb + t_mem) + (1 - h) x (t_tlb + 2 x t_mem)    (one-level table)
  • A page fault occurs when the page is not in memory; the OS loads it from disk.
  • Page replacement: FIFO (can show Belady's anomaly), LRU, Optimal (best possible, needs the future).

Memory, storage and I/O

Technology Stores a bit as Refresh Typical use
SRAM Cross-coupled transistors (about 6 per bit) No Caches, registers
DRAM Charge in a capacitor Yes Main memory
Flash Charge in a floating gate No SSDs, USB sticks
ROM Fixed or programmed connections No Firmware
Text
disk access time  = seek time + rotational latency + transfer time + controller overhead
rotational latency (average) = 0.5 x 60 / RPM seconds
memory bandwidth  = transfers per second x bus width in bytes
dynamic power     = activity factor x capacitance x voltage^2 x frequency
RAID level Usable capacity (N equal disks) Survives
0 (striping) N No disk failure
1 (mirroring, 2 disks) N / 2 One disk
5 (distributed parity) N - 1 One disk
6 (double parity) N - 2 Two disks
10 (stripe of mirrors) N / 2 One per mirrored pair
  • Polling: CPU checks the device. Interrupt: the device signals. DMA: a controller moves a block and interrupts once at the end. See I/O Organization.
  • Power grows with the square of voltage, so lowering voltage together with frequency saves far more energy than lowering frequency alone.

The second calculator packs the main formulas into functions. Change the inputs to match your own problem.

Python A calculator for the main formulas

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

If a result looks off by a factor of about 1.05 or 1.07, check whether you mixed decimal prefixes (1 KB = 1,000 bytes) with binary ones (1 KiB = 1,024 bytes). Hardware sizes are almost always powers of two.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. How many tag bits does a 32-bit address have for a 32 KB, 8-way cache with 64-byte blocks?

    The offset is 6 bits. The cache has 32 KB / 64 B = 512 blocks, so 512 / 8 = 64 sets and 6 index bits. The tag is 32 - 6 - 6 = 20 bits.
  2. 2. Which float format field layout is single precision?

    Single precision uses 1 + 8 + 23 = 32 bits with bias 127. Half uses 5 and 10, double uses 11 and 52.
  3. 3. Which RAID level survives any two disk failures?

    RAID 6 stores two independent parity blocks per stripe, so any two disks can fail. RAID 5 survives one, RAID 1 with two disks survives one, and RAID 0 survives none.
  4. 4. Lowering the supply voltage from 1.0 V to 0.8 V at the same frequency changes dynamic power by what factor?

    Dynamic power is proportional to voltage squared: 0.8 x 0.8 = 0.64, a 36 percent saving.

Summary

  • Know the ranges: unsigned 0 to 2^n - 1, signed -2^(n-1) to 2^(n-1) - 1.
  • IEEE 754: sign, biased exponent, fraction; special exponents encode zero, subnormals, infinity and NaN.
  • Execution time = instructions x CPI / clock rate; Amdahl and Gustafson bound parallel gains.
  • Cache bits: offset = log2(block), index = log2(sets), tag = the rest; AMAT nests across levels.
  • Paging replaces the virtual page number with a frame number; the TLB speeds that up.
  • Power scales with voltage squared times frequency.

This is the end of the track. Go back to the track overview to revisit any chapter, or build something with the projects.