Unit 4: Stack and memory organization
Computer System Architecture notes · PTU syllabus (BSIT301/BSBC204)
On this page
Unit summary
Memory organisation balances speed, size and cost. This unit covers memory and register stacks, the memory hierarchy, RAM and ROM chips, logical and physical addresses, associative memory, cache memory — initialisation, writing, locality of reference and hit ratio — replacement algorithms (LRU, FIFO), direct, associative and set-associative mapping, Harvard architecture, and mobile device architectures.
After this unit you can
- Explain register and memory stacks
- Explain the memory hierarchy, RAM and ROM chips and associative memory
- Explain cache memory, mapping and replacement
- Explain Harvard and mobile device architectures
PTU syllabus topics
- Memory and register stack
- memory hierarchy
- RAM/ROM chips
- logical/physical addresses
- associative memory
- cache memory initialization/writing/locality of reference/hit ratio
- replacement algorithms (LRU, FIFO)
- direct/associative/set-associative mapping
- Harvard architecture
- mobile device architectures
Topic 1
Stack organisation
- Stack: last-in, first-out storage with a stack pointer (SP).
- Register stack: a set of registers (e.g., 64 words) with SP, FULL and EMPTY flags; memory stack: part of main memory used as a stack (grows towards lower addresses).
PUSH
SP ← SP − 1; M[SP] ← DR
POP
DR ← M[SP]; SP ← SP + 1
- Uses: subroutine calls and returns, evaluating postfix expressions (zero-address instructions), interrupts.
Example
Zero-address evaluation: to compute (3 + 4) × 5 with a stack: PUSH 3, PUSH 4, ADD (stack now 7), PUSH 5, MUL (stack now 35). The result is on top of the stack.
Exam tip
Learn the RTL for push (SP ← SP + 1; M[SP] ← DR) and pop (DR ← M[SP]; SP ← SP − 1), and the full/empty flags.
Topic 2
Memory hierarchy
The memory hierarchy balances speed, cost and capacity: memory near the top is fast and costly, memory near the bottom is slow, cheap and large. It works because programs show locality of reference.
- Registers
Fastest, smallest
- Cache memory
SRAM
- Main memory
DRAM
- Secondary storage
SSD, magnetic disk
- Tertiary storage
Tape, optical, cloud archives
- Moving down: larger capacity, lower cost per bit, slower access.
Example
Locality in practice: a loop runs the same instructions many times (temporal locality) and reads array elements one after another (spatial locality). Keeping these in cache means most accesses are fast even though RAM is slower.
Exam tip
Explain both kinds of locality — they justify cache memory.
Topic 3
RAM and ROM chips
- RAM chip: read-write; inputs — address lines, chip select (CS), read and write controls; data lines bidirectional. SRAM (flip-flops, fast, cache) vs DRAM (capacitors, needs refresh, main memory).
- ROM chip: read-only; types — mask ROM, PROM, EPROM (UV erasable), EEPROM and flash (electrically erasable) — used for firmware (BIOS/UEFI).
- Memory address map: assigns address ranges to each RAM and ROM chip.
Example
Building a memory: to make 512 bytes of RAM from 128 × 8 RAM chips, four chips are needed. Address lines A0–A6 go to all chips, and A7–A8 go to a 2-to-4 decoder whose outputs drive each chip's chip select.
Exam tip
Number of chips = total memory ÷ chip size; use a decoder for chip select.
Topic 4
Logical and physical addresses
- Logical (virtual) address: generated by the CPU for a program. Physical address: actual location in main memory.
- Memory management unit (MMU): maps logical to physical addresses (paging, segmentation), enabling virtual memory and protection.
Example
Translating an address: with 1 KB pages, logical address 2,100 is page 2 (2,100 ÷ 1,024), offset 52. If the page table maps page 2 to frame 7, the physical address is 7 × 1,024 + 52 = 7,220.
Exam tip
Physical address = frame number × page size + offset.
Topic 5
Associative memory
- Associative (content-addressable) memory: accessed by content rather than address — all words compared in parallel with an argument register under a key (mask) register.
- Use: fast table look-ups such as translation lookaside buffers (TLB) and cache tags; expensive.
Example
A TLB: the translation look-aside buffer is an associative memory holding recent page-to-frame mappings. The CPU searches all entries at once for the page number; a hit gives the frame immediately, avoiding a slower page-table lookup in memory.
Exam tip
Associative memory is fast but expensive because every word needs its own comparison logic.
Topic 6
Cache memory
- Locality of reference: programs reuse recent data (temporal) and nearby data (spatial).
Hit ratio
Hits ÷ (hits + misses)
Average access time
h × Tc + (1 − h) × (Tc + Tm); or h Tc + (1 − h) Tm when cache and memory are searched in parallel
Example
Hit ratio 0.9, cache 10 ns, memory 100 ns: average access ≈ 0.9 × 10 + 0.1 × 110 = 20 ns.
- Writing: write-through (update memory every write — simple, consistent) vs write-back (update memory only when the block is replaced — faster, uses a dirty bit).
- Initialisation: valid bits cleared at power-on so that all lines are treated as empty.
Topic 7
Cache mapping techniques
Direct mapping
Block j goes to line j mod (number of lines)
Simple and cheap; conflict misses
Associative mapping
Block can go in any line; tags searched in parallel
Flexible; expensive comparison hardware
Set-associative mapping
Block maps to one set, any line within the set (k-way)
Balance of cost and hit ratio
Example
Direct mapping: with a cache of 8 lines, main memory block 13 goes to line 13 mod 8 = 5. Blocks 5, 13 and 21 all compete for line 5, which can cause frequent replacements; set-associative mapping reduces such conflicts.
Exam tip
Line = block number mod number of lines (direct mapping).
Topic 8
Replacement algorithms
- FIFO: replace the block that has been in the cache longest.
- LRU (least recently used): replace the block not used for the longest time — usually better hit ratio.
- Others: random, LFU (least frequently used), optimal (theoretical).
Example
LRU in a 3-line cache: for references 1, 2, 3, 1, 4 — after 1, 2, 3 the cache is full; referencing 1 makes it recently used; when 4 arrives, block 2 (least recently used) is replaced, giving the cache {1, 3, 4}.
Exam tip
FIFO is simple; LRU usually performs better because it uses recent usage.
Topic 9
Harvard and mobile device architectures
- Harvard architecture: separate memories and buses for instructions and data — simultaneous fetch; used in DSPs and microcontrollers; modern CPUs use a modified Harvard design with split L1 caches.
- Mobile device architecture: system-on-chip (SoC) integrating ARM CPU cores (often big.LITTLE for power efficiency), GPU, neural processing unit, modem, image signal processor and memory controller; focus on low power and heat; examples — Qualcomm Snapdragon, Apple A-series, MediaTek Dimensity.
Example
Harvard in practice: many microcontrollers and digital signal processors use Harvard architecture, so they can fetch the next instruction while reading data. Mobile phones use ARM processors — RISC designs with low power use — in a system-on-chip with CPU, GPU and modem on one chip.
Exam tip
Compare Harvard and Von Neumann in a table: memories, buses, speed and cost.
Key terms
- Stack pointer
- Register holding the address of the top of the stack
- Locality of reference
- Tendency to reuse recent and nearby data
- Hit ratio
- Fraction of accesses found in the cache
- Set-associative mapping
- Block placed in any line of one set
- System-on-chip
- Integrated chip with CPU, GPU and other units
Quick revision
- Register and memory stacks; PUSH and POP.
- Hierarchy: registers → cache → main → secondary → tertiary.
- RAM (SRAM, DRAM), ROM types; address map; logical vs physical; MMU.
- Associative memory; cache locality, hit ratio, write policies.
- Direct, associative, set-associative mapping; FIFO, LRU; Harvard and mobile SoC.
Important exam questions
Practice questions written to the PTU exam pattern for this unit's syllabus: short answers (Section A style) and long answers (Sections B and C style).
Short-answer questions
- Q1.State the PUSH operation in RTL.
- Q2.Distinguish SRAM and DRAM.
- Q3.What is associative memory?
- Q4.Define hit ratio.
- Q5.Distinguish write-through and write-back.
- Q6.What is a system-on-chip?
Long-answer questions
- Q1.Explain register and memory stack organisation.
- Q2.Explain the memory hierarchy and RAM and ROM chips.
- Q3.Explain cache memory, its performance and mapping techniques.
- Q4.Explain replacement algorithms and Harvard and mobile device architectures.
Stuck on this unit?
Message SBS on WhatsApp for help with Computer System Architecture, or to ask about studying B.Sc IT at Synetic.
