ACtE0402 Computer arithmetic and memory system¶
Arithmetic and logical operation classes¶
ALU operations commonly include:
- addition, subtraction, increment, decrement;
- AND, OR, XOR, NOT;
- shift left/right;
- compare;
- rotate in some architectures.
Shift cues:
- logical shift inserts zeros;
- arithmetic right shift preserves sign bit in signed 2's complement usage;
- left shift of signed values is representation-dependent/undefined in some language contexts, but hardware instructions define their own result conventions.
Memory hierarchy¶
The hierarchy trades speed for capacity and cost.
| Level | Volatility | Typical role |
|---|---|---|
| Registers | volatile | smallest and fastest CPU-local storage |
| Cache | volatile | fast copies of recently used memory blocks |
| Main memory | volatile | active programs and data |
| SSD / HDD secondary storage | non-volatile | persistent online storage |
| Tape / offline optical archive | non-volatile | tertiary or archival storage with high access latency |
SSD is generally faster than an HDD for random access, but avoid treating broad technology families as one universal speed ordering. An HDD is normally secondary storage, not inherently tertiary backup.
Locality principles justify cache use:
- temporal locality: recently used data/instructions are likely to be reused;
- spatial locality: nearby addresses are likely to be used soon.
Internal and external memory¶
| Class | Typical examples |
|---|---|
| Internal / primary | registers, cache, main memory |
| External / secondary | SSD, HDD, optical, tape |
Internal versus external is about position and access role in the system, not just whether the medium is on the motherboard.
Cache memory principles¶
Cache stores copies of blocks from lower memory levels.
Core terms:
| Term | Meaning |
|---|---|
| Hit | requested block found in cache |
| Miss | requested block not found in cache |
| Hit ratio | fraction of accesses that hit |
| Miss penalty | extra time to fetch from lower level |
Effective access time intuition: higher hit ratio and lower miss penalty improve average performance.
Elements of cache design¶
Cache size¶
- Larger cache can reduce miss rate.
- Larger cache can increase hit time, cost, and power.
- Optimum size is a design tradeoff, not "bigger is always better."
Mapping function¶
| Mapping | Recognition |
|---|---|
| Direct-mapped | one main-memory block maps to exactly one cache line |
| Fully associative | a block may go anywhere |
| Set-associative | a block maps to one set, then any line in that set |
Direct-mapped is simple but more conflict-prone. Fully associative reduces conflict misses but requires more complex lookup. Set-associative is the usual compromise.
Replacement algorithm¶
When a new block must enter a full candidate area:
| Policy | Cue |
|---|---|
| LRU | least recently used |
| FIFO | first in, first out |
| Random | simple hardware, sometimes surprisingly effective |
Replacement matters only where there is a placement choice, so not in direct-mapped caches.
Write policy¶
| Policy | Meaning | Tradeoff |
|---|---|---|
| Write-through | update cache and lower memory on every write | simpler lower-memory visibility, more traffic |
| Write-back | update cache now, lower memory on eviction | lower traffic, needs dirty state |
| Write-allocate | on write miss, bring block into cache first | common with write-back |
| No-write-allocate | on write miss, write around cache | common with write-through |
Write-through does not make a multiprocessor cache coherent by itself. Other cached copies can still become stale, so an invalidate/update coherence protocol or another explicit mechanism is required.
Canonical design choices are write-through versus write-back and write-allocate versus no-write-allocate. A write buffer is an implementation mechanism that can hide lower-memory latency; it is not a mutually exclusive canonical policy in the same taxonomy. “Write within” is not standard cache terminology, and no write policy by itself guarantees multiprocessor coherence.
Number of caches¶
This can mean cache levels or split organization.
- L1, L2, L3 describe hierarchy levels.
- L1 may be split into instruction cache and data cache.
- Unified cache stores both instructions and data.
Memory write ability and storage permanence¶
"Write ability" and "storage permanence" correspond to writability and volatility/non-volatility.
| Memory type | Read/write | Volatility |
|---|---|---|
| SRAM | read/write | volatile |
| DRAM | read/write | volatile |
| ROM | read-only in normal operation | non-volatile |
| Flash | electrically rewritable in blocks | non-volatile |
Trap: non-volatile does not imply unlimited write endurance.
Composing memory¶
Memory composition problems usually ask how to build required capacity/word width from smaller chips.
Rules:
- increase word width by placing chips in parallel;
- increase addressable depth by placing chips in series by address partitioning/select logic;
- total capacity = number of locations times word width.
Example cue:
- to build 8K x 16 from 8K x 8 chips, use two chips in parallel;
- to build 16K x 8 from 8K x 8 chips, use two chips in depth with one extra address bit for selection.
Memory-system revision box¶
- Locality explains cache usefulness.
- Hit ratio high -> average access time low.
- Direct-mapped has one possible line; associative policies have placement choice.
- Write-through updates lower memory immediately; write-back delays until eviction.
- SRAM is fast/no refresh; DRAM is dense/refresh-required.
- Width expansion is parallel; depth expansion is address partitioning.