🧮 Formula & Numerical Reference — CPU, Cache, Memory, Bus, RAID

CSS Computer Science Optional · Paper-II · Section A · I. Computer Organization & Architecture

Purpose: A single formula and numerical reference covering the full architecture chapter, not just cache. Organised in syllabus order. Each entry includes when to use it, assumptions and an exam-style numerical. Read the topic pages for detailed theory.

Syllabus basis: FPSC CE-2016-and-onwards Computer Science Paper-II, Section A (architecture, processor metrics, machine instructions, internal/external representation, cache, memory, I/O, buses, arithmetic, ILP and multiprocessors). Relevant numerical patterns also drawn from the past-paper questions retained in the topic subpages. Formulas not explicitly asked previously are marked additional practice, not falsely attributed to an FPSC year.

Exam convention: Unless a question says otherwise, 1 KiB = 2¹⁰ bytes, 1 MiB = 2²⁰ bytes; 1 KB = 10³ bytes when a rate explicitly uses decimal KB. Always state byte-addressed versus word-addressed assumptions.

🗺️ Quick index — question → formula

1. Processor performance, CPI and MIPS ⭐

Symbols: IC = dynamic instruction count, CPI = average cycles per instruction, f = clock cycles per second (Hz), t = cycle time.

$$\begin{aligned} t &= 1/f\\ \text{CPU cycles} &= IC\times CPI\\ T_{CPU} &= IC\times CPI\times t = \frac{IC\times CPI}{f}\\ CPI_{avg} &= \frac{\sum_i IC_i\,CPI_i}{\sum_i IC_i}\\ \text{MIPS} &= \frac{IC}{T\times 10^6}=\frac{f}{CPI\times 10^6}\\ \text{CPU speedup} &= T_{old}/T_{new} \end{aligned}$$

When: 2017 CPU-speed limitation; 2024 CPU time and CPI; 2025 instruction-mix numerical in Performance Metrics.

Worked example (2025-style instruction mix): 40 MHz CPU; 100,000 instructions: 45,000 at 1 cycle, 32,000 at 2 cycles, 15,000 at 2 cycles and 8,000 at 2 cycles.

1. Total cycles = 45,000(1) + 32,000(2) + 15,000(2) + 8,000(2) = 155,000 cycles.
2. Average CPI = 155,000/100,000 = 1.55.
3. Execution time = 155,000/(40×10⁶) = 0.003875 s = 3.875 ms.
4. MIPS = 40/1.55 = 25.806 MIPS.

Important wording trap (2024-style): “1 billion instructions per second” implies T for 1 million instructions = 10⁶/10⁹ = 1 ms, whatever CPI was used to obtain that rate. “1 billion clock cycles per second, CPI 4” instead gives T = 10⁶×4/10⁹ = 4 ms. Do not silently confuse instructions/s and cycles/s.

Other performance formulas:

$$\begin{aligned} \text{Throughput} &= \text{completed jobs}/\text{time}\\ \text{IPC} &= \text{retired instructions}/\text{cycles}\\ CPI &= 1/IPC\quad\text{(for the same workload)} \end{aligned}$$

Dynamic-power estimate: P_dynamic ≈ α C V² f, where α is switching activity. Doubling f doubles dynamic power if voltage, capacitance and activity stay fixed. Increasing V can amplify the power cost.

2. Instruction cycle, pipelining and throughput ⭐

For n independent instructions, k pipeline stages each taking t time, with balanced stages and no stalls:

$$\begin{aligned} T_{nonpipe} &= nkt\\ T_{pipe} &= (k+n-1)t\\ \text{Speedup} &= \frac{nk}{k+n-1}\\ \text{Ideal throughput after fill} &= 1/t \end{aligned}$$

Example: n = 100, k = 5, t = 2 ns: non-pipeline = 100×5×2 = 1000 ns; pipeline = (5+100−1)×2 = 208 ns; speedup ≈ 4.81×. First result latency = k×t = 10 ns, not 2 ns.

Unequal stages: Minimum synchronous clock period ≥ longest stage delay + register overhead. With delays 30, 9, 20, 35, 10 ns and no register overhead, the clock must be ≥35 ns; five-stage pipeline latency for one instruction = 5×35 = 175 ns. Non-overlapped asynchronous stage-time sum = 30+9+20+35+10 = 104 ns (2025-style problem). Do not treat throughput and single-instruction latency as identical.

Stall-aware practice: T ≈ (k+n−1 + total stall cycles)×clock period, if stalls are counted for the execution schedule. For steady-state CPI: CPI_effective ≈ CPI_ideal + average stall cycles per instruction.

3. Parallel processing and Amdahl's law ⭐

$$\begin{aligned} S(N) &= \frac{1}{(1-P)+P/N}\\ S_{max} &= \frac{1}{1-P}\quad(N\to\infty)\\ E &= S(N)/N\quad\text{(parallel efficiency)} \end{aligned}$$

P = parallelizable fraction of original runtime; N = processors (under ideal parallel division). General form when a portion P is accelerated by factor s: S = 1/[(1−P)+P/s].

Example (multiprocessor question): P = 0.90 and N = 8: S = 1/(0.10+0.90/8) = 1/0.2125 = 4.71×; efficiency = 4.71/8 ≈ 58.8%. Upper limit = 1/0.10 = 10×.

Additional practice — Gustafson scaling: S_scaled(N) = N − α(N−1), where α is the serial fraction of the scaled workload. State the scaled-workload assumption.

4. Number representation and arithmetic ⭐

Unsigned n-bit: minimum 0, maximum 2ⁿ−1.

Signed n-bit two's complement: −2ⁿ⁻¹ through 2ⁿ⁻¹−1.

Negative X in n bits: write +X in exactly n bits → invert → add 1.

Example: +5 in 8 bits = 00000101; invert = 11111010; add 1 = 11111011 (−5).

Subtraction: A−B = A + two's complement of B, dropping carry outside the n-bit word. Example 4-bit 7−3: 0111 + 1101 = 1 0100 → 0100 = 4.

Overflow rules: Unsigned addition overflows if carry-out = 1; signed two's-complement addition overflows when operands have the same sign but the n-bit result has the opposite sign (equivalently carry into sign bit XOR carry out of sign bit). Carry-out alone is NOT the signed-overflow test.

Shifts: For a non-overflowing unsigned value, left shift by k multiplies by 2ᵏ; right shift by k divides by 2ᵏ with remainder discarded. Signed negative shifts depend on language/hardware rules; state assumptions.

Base conversion: Positional value = Σ digit_i × base^i. Binary-group shortcuts: 1 hex digit = 4 bits; 1 octal digit = 3 bits.

Floating point (additional practice): IEEE-754 normal binary32 value = (−1)^sign × (1.fraction)_2 × 2^(exponent−127). Normal binary64 bias = 1023. Subnormal numbers and special exponent patterns need separate rules.

5. Instruction encoding and addressing modes

Instruction field sizing: An opcode identifying K distinct operations needs at least ⌈log₂K⌉ bits. A register field identifying R registers needs ⌈log₂R⌉ bits. If an instruction has length W and fixed opcode/register fields, remaining bits = W−sum of those field widths.

Example: 64 opcodes → 6 opcode bits; 16 registers → 4 bits per register. A 16-bit instruction with one opcode and two register fields leaves 16−6−4−4 = 2 bits for other fields.

Effective address (EA) quick reference:

2021-style worked example: A = 500, R1 = 400, Memory[500] = 800, Memory[800] = 300. Direct → EA 500, operand 800; memory-indirect → EA 800, operand 300; register-indirect → EA 400, operand Memory[400]. A register identifier is not automatically register number 500; interpret the field according to its instruction format.

6. Cache performance, hit ratios and AMAT ⭐⭐⭐

$$\begin{aligned} H &= \frac{\text{hits}}{\text{accesses}}\\ M &= 1-H = \frac{\text{misses}}{\text{accesses}}\\ AMAT &= T_{hit}+M\times P_{miss} \end{aligned}$$

Definitions matter: P_miss here is extra time beyond the hit lookup. If a question instead provides complete miss access time T_miss, use weighted average:

$$AMAT = H\,T_{hit} + (1-H)\,T_{miss}$$

Example: Hit = 2 ns, miss rate = 5%, extra penalty = 80 ns → AMAT = 2+0.05(80) = 6 ns.

Block-transfer miss penalty: Number of transfer words = block bytes / bytes per word. If first word costs F and each additional word costs D:

$$T_{fetch} = F+(W-1)D$$

2025-style complete numerical: Cache lookup 2.5 ns, 64-byte line, 4-byte words, first word 50 ns, additional word 5 ns, H = 0.95; miss requires initial lookup, line fetch and a second lookup.

1. W = 64/4 = 16 words.
2. Fetch = 50 + 15×5 = 125 ns.
3. Total miss time = 2.5+125+2.5 = 130 ns.
4. AMAT = 0.95(2.5)+0.05(130) = 8.875 ns.
5. For 128-byte line and H = 0.97: W = 32; fetch = 50+31×5 = 205 ns; full miss = 210 ns; AMAT = 0.97(2.5)+0.03(210) = 8.725 ns.
6. Savings = 8.875−8.725 = 0.150 ns ≈1.69%.

Two-level sequential cache:

$$AMAT = T_{L1}+M_{L1}\big(T_{L2}+M_{L2(local)}P_{memory}\big)$$

Example: L1 = 1 ns, L1 miss = 0.10, L2 = 10 ns, L2 local miss = 0.20, memory extra penalty = 100 ns → AMAT = 1 + 0.10(10+0.20×100) = 4 ns.

Three levels (additional practice): AMAT = T1 + M1[T2 + M2(T3 + M3×Pmem)] (local miss rates, nested sequential lookups).

Global miss rate at L2: M_L1 × M_L2(local), e.g., 0.10 × 0.20 = 2% of CPU accesses reach memory beyond L2.

Cache effect on CPI:

$$CPI_{effective}=CPI_{base}+(\text{misses per instruction})\times\text{miss penalty in cycles}$$

When instruction and data misses are separately specified: CPI = CPI_base + I-misses/instruction × I-penalty + data accesses/instruction × D-miss-rate × D-penalty. Do not double-count stall cycles already inside CPI_base.

7. Cache mapping, tag/index/offset and capacity ⭐⭐⭐

Symbols: A = address bits; B = block size in addressable units; C = cache data capacity in same units; L = lines = C/B; N = associativity (ways); S = sets = L/N; O = offset bits.

$$\begin{aligned} O &= \log_2 B\\ L &= C/B\\ S &= L/N\\ I_{direct} &= \log_2L\\ I_{set} &= \log_2S\\ T &= A-I-O \end{aligned}$$

Placement equations:

$$\begin{aligned} \text{Block number} &= \lfloor \text{address}/B \rfloor\\ \text{Within-block offset} &= \text{address}\bmod B\\ \text{Direct line} &= \text{block}\bmod L\\ \text{Set} &= \text{block}\bmod S\\ \text{Set tag} &= \lfloor\text{block}/S\rfloor \end{aligned}$$

2022 CSS-style 6-mark calculation: Cache 64 lines, 4 lines/set, RAM = 4K blocks ×128 words/block. Word-addressed main memory = 2¹²×2⁷ = 2¹⁹ words → A = 19. Offset = log₂128 = 7. Sets = 64/4 = 16 → set bits 4. Tag = 19−4−7 = 8. Address: | Tag 8 | Set 4 | Word 7 | (total 19). Do not add byte offset without a specified word size.

Cache directory overhead (additional practice): Data bits = L×B_bytes×8; metadata bits ≈ L×(tag bits + valid bit + dirty bit if used) + replacement-policy metadata. Total physical cache storage ≈ data bits + metadata bits. Example: 128 lines, 16-byte blocks, 7 tag bits, 1 valid bit, 1 dirty bit → data = 16,384 bits; line metadata = 128×9=1152 bits; total = 17,536 bits, excluding replacement-state and control overhead.

Replacement-trace instructions: Draw one row for every block reference; show line/set contents, hit/miss, and victim. FIFO removes oldest loaded; LRU removes least recently used; OPT removes block with farthest next use. FIFO can exhibit Bélády's anomaly; LRU and OPT are stack algorithms.

8. Memory chips, SRAM/DRAM and refresh ⭐⭐

Chip organization: Capacity = number of locations × bits/location. For memory needing W-bit words and chips providing w bits per output word, chips in parallel (per bank) = W/w. For required addressable depth D and chip depth d, number of banks = ⌈D/d⌉. Total chips = chips/bank × banks, provided compatible word organization.

Example: Assemble 16K×8 using 4K×4 chips: width ratio 8/4 = 2 chips per bank; depth ratio 16K/4K = 4 banks → 8 chips.

Address lines: n address bits select 2ⁿ locations (if powers of two). Example 64K locations require 16 lines.

DRAM refresh overhead:

$$\text{Refresh fraction} = \frac{\text{refresh operations per period}\times\text{time consumed per refresh}}{\text{period}}$$

2023-style: 64 refreshes/ms, 150 ns each → busy time 64×150 = 9600 ns per 1,000,000 ns → 0.96%. If a question states each refresh occupies a full 250-ns memory cycle rather than just 150 ns, overhead would instead be 64×250/10⁶×100 = 1.6%. Explain which interpretation the question uses.

SRAM vs DRAM: SRAM stores bits in bistable cells and does not need periodic refresh while powered; DRAM stores charge in capacitors and does need refresh. These are conceptual, not numerical, contrasts.

9. Virtual memory, paging and TLB ⭐⭐

Basic paging: Page size = 2^p bytes if offset field has p bits. Virtual pages = virtual address space/page size; physical frames = physical memory/page size.

$$\begin{aligned} \text{VA} &= VPN\times P + offset\\ \text{PA} &= PFN\times P + offset\\ VPN &= \lfloor VA/P\rfloor,\quad offset = VA\bmod P \end{aligned}$$

Example: 32-bit virtual addresses with 12-bit page offset → page size = 2¹² = 4096 bytes = 4 KiB; VPN bits = 32−12 = 20; maximum virtual address space = 2³² = 4 GiB.

Single-level page-table size: entries = virtual pages; table bytes = entries × PTE bytes. Example: 2²⁰ PTEs at 4 bytes each = 2²² bytes = 4 MiB (ignoring multi-level sparsity).

TLB effective access time, simplified serial lookup:

$$EAT = h(t_{TLB}+t_M)+(1-h)(t_{TLB}+2t_M)$$

Assumes TLB hit = one data-memory access, miss = one page-table memory access plus one data access, no page fault, one-level page table. Example h=.98, tTLB=2 ns, tM=100 ns → EAT = .98(102)+.02(202) = 104 ns. For multi-level page tables or overlapping TLB/memory operations, modify the assumptions.

10. External memory: disk and storage ⭐

$$\begin{aligned} T_{disk} &= T_{seek}+T_{rotational}+T_{transfer}+T_{controller}\quad\text{(if specified)}\\ T_{avg\ rotation} &= \frac{60}{2\times RPM}\text{ seconds}\\ T_{full\ rotation} &= 60/RPM\\ \text{Transfer time} &= \text{data size}/\text{transfer rate} \end{aligned}$$

Example: 7200 RPM, 8-ms seek, 1-ms transfer (controller time ignored): average rotation = (60/7200)/2 = 0.004167 s = 4.167 ms; total ≈ 13.17 ms.

Disk capacity, textbook geometry: capacity = usable surfaces × tracks/surface × sectors/track × bytes/sector. Modern disks use zone bit recording and logical block addresses; uniform sectors/track is a simplifying exam assumption.

11. RAID capacity and efficiency ⭐

Assume n drives of equal usable capacity d, and no hot spares or filesystem overhead.

Efficiency: η = usable capacity/raw capacity ×100%.

Example: Six 2-TB disks: RAID 5 → (6−1)×2 = 10 TB, 83.3% efficiency; RAID 6 → (6−2)×2 = 8 TB, 66.7%; RAID 10 → 6/2×2 = 6 TB, 50%.

Mixed sizes: For a simple conservative exam model, substitute the smallest drive's capacity for d. Actual controller behavior varies. RAID is not a backup.

12. Address/data/control buses and bandwidth ⭐⭐

Address bus: A bits can distinguish 2^A addressable units. For byte-addressed memory, capacity = 2^A bytes; for word-addressed memory with W bytes/word, capacity = 2^A × W bytes.

Data bus: A D-bit bus moves D/8 bytes in one full-width transfer.

$$\text{Peak bandwidth (B/s)} = \frac{D}{8}\times f\times q$$

q = transfers per clock (e.g. 1 for single-data-rate; 2 for ideal double-data-rate); exclude protocol overhead, arbitration delays and idle cycles for this theoretical peak.

Example: 64-bit data bus, 100 MHz, one transfer/clock → 8×100×10⁶ = 800 MB/s theoretical peak.

Cycles needed: approximately ceiling(total bytes / bytes per transfer) for an ideal zero-overhead bus; total transfer time depends on clock/transfer rate and protocol setup.

Common distinction: Address width governs maximum addressable locations, not transfer speed; data width governs bits per transfer, not necessarily processor word size.

13. Input/output, DMA and channels ⭐⭐

CPU polling overhead (model): busy-wait cycles = polls × cycles/poll. Polling frequency and service delays determine real CPU cost.

DMA transfer time, idealised: T ≈ data bytes / sustainable DMA transfer bandwidth + setup/interrupt overhead. DMA frees the CPU from copying every transfer word, but uses memory/bus bandwidth.

DMA CPU saving:

$$\text{CPU utilisation saving}\approx\frac{T_{CPU,programmed}-T_{CPU,DMA\ overhead}}{T_{CPU,programmed}}\times 100\%$$

This measures CPU work, not necessarily elapsed transfer-time savings.

Selector vs multiplexor channel — 2023 12-mark numerical: A selector channel usually serves one attached high-speed device at a time, so peak instantaneous channel rate is bounded by the fastest active device; a multiplexor channel interleaves data from multiple low-speed devices, so sum service rates where the stated channel can sustain them.

Given two selector channels each with two 800-KB/s disks and two 200-KB/s tapes; one multiplexor with two printers at 6.6 KB/s, two readers at 1.2 KB/s, ten terminals at 1 KB/s:

1. One selector channel = max(800,800,200,200) = 800 KB/s.
2. Two independent selector channels = 2×800 = 1600 KB/s.
3. Multiplexor = 2(6.6)+2(1.2)+10(1) = 13.2+2.4+10 = 25.6 KB/s.
4. Total = 1600+25.6 = 1625.6 KB/s (≈1.6256 MB/s using decimal MB), assuming all channels operate concurrently and do not share a narrower bottleneck.

Interrupt prioritisation: Sequential handling masks/defers other interrupts while a handler runs; nested priority permits urgent interrupts to preempt. These are primarily conceptual questions, so a flow diagram and comparison score better than an invented calculation.

14. Conversions, symbols and common mistakes

Most important traps:

• Distinguish instructions/s from clock cycles/s.
• Use average CPI, weighted by instruction counts, not simple unweighted averaging.
• For a cache, distinguish total miss access time from extra miss penalty.
• In an N-way cache, N is lines per set; number of sets = total lines/N.
• For cache blocks of words, do not invent byte-offset bits.
• For pipelining, distinguish latency, throughput and speedup.
• For bus capacity, specify byte- vs word-addressing.
• For RAID, never confuse physical capacity with usable capacity.
• For DRAM refresh, distinguish actual refresh-duration from occupied memory-cycle time.
• Do not assume DMA runs with zero overhead or guarantees higher total I/O bandwidth.

15. How to answer CSS numericals according to marks

3–5 marks: Given values → one correct formula → numerical substitution → boxed answer with units.

6–8 marks: Given / Required → numbered working (including conversions) → labeled address diagram or comparison table where useful → result and brief interpretation.

10–12 marks: State assumptions → show all component-wise calculations → intermediate results in units → combine → verify and identify likely traps.

Fast final checklist: Are units consistent? Is the formula model appropriate? Are powers of two explicit? Have you used the correct denominator? Does the result make physical sense? Did you answer all subparts?

Chapter links: Performance Metrics · Cache Memory · Memory Organization · Input/Output System · BUS · RAID.