CS Memory Systems Lab

An Interactive Exploration of Computer Architecture & Memory Hierarchy

Fundamental Concepts

Understanding computer memory and system architecture begins with grasping the basics of how data is stored, accessed, and processed.

Data Representation

Data is represented in computers using binary digits (bits). Key concepts include:

Binary System

Computers use base-2 (binary) numbering, where each digit is either 0 or 1.

Binary Example

10102 = 1×2³ + 0×2² + 1×2¹ + 0×2⁰ = 1010

Hexadecimal System

Often used as a shorthand for binary, hexadecimal (base-16) simplifies representation of large binary numbers.

Hex Example

Binary: 1101 1010 → Hex: DA

ASCII/Unicode

Standards for encoding characters (e.g., letters, symbols) into binary for storage and processing.

Character Encoding

'A' → ASCII: 65 → Binary: 01000001

Memory Units

Unit Size Typical Use
Bit 1 bit Basic unit of information (0 or 1)
Byte 8 bits Characters, small integers
Word 32/64 bits Native CPU operations
Cache Line 64/128 bytes Memory transfer unit
Kilobyte (KB) 1024 bytes Small files, program instructions
Megabyte (MB) 1024 KB Medium-sized files, images
Gigabyte (GB) 1024 MB Large files, software applications
Terabyte (TB) 1024 GB Storage for large datasets, backups

Bit-Level Operations

Bit manipulation is fundamental to low-level programming and memory management. These operations are performed directly on the binary representations of data. 
// Binary Operations Examples
byte = 0b10101010  // 170 in decimal

// Common Operations:
AND:  10101010 & 11110000 = 10100000
OR:   10101010 | 00001111 = 10101111
XOR:  10101010 ^ 11110000 = 01011010
NOT:  ~10101010           = 01010101
LEFT SHIFT:  10101010 << 2 = 10101000
RIGHT SHIFT: 10101010 >> 2 = 00101010

Bitwise Operation Applications

Operation Symbol Use Case Example
AND & Masking bits, testing bit values value & mask
OR | Setting bits, combining flags flags | new_flag
XOR ^ Toggling bits, simple encryption data ^ key
NOT ~ Inverting bits, creating masks ~mask
Left Shift << Multiply by powers of 2 x << 2 (x * 4)
Right Shift >> Divide by powers of 2 x >> 1 (x / 2)

Bit Manipulation Techniques

These techniques are commonly used in system programming and optimization: 
// Check if a number is a power of 2
function isPowerOfTwo(x) {
  return (x & (x - 1)) === 0;
}

// Count set bits (Hamming weight)
function countSetBits(x) {
  let count = 0;
  while (x > 0) {
    count += x & 1;
    x >>= 1;
  }
  return count;
}

// Swap two variables without temp
a ^= b;
b ^= a;
a ^= b;

Memory Hierarchy

Memory hierarchy organizes storage systems based on speed, cost, and capacity. This pyramid structure optimizes performance by keeping frequently accessed data in faster memory.
CPU Registers ~1KB, <1ns access
L1 Cache 32-64KB, ~1ns access
L2 Cache 256KB-1MB, ~4ns access
L3 Cache Several MB, ~10ns access
Main Memory (RAM) GB range, ~100ns access
Storage (SSD/HDD) TB range, µs-ms access

Cache Organization

Caches are organized into blocks (cache lines) with specific mapping techniques:

Direct Mapped

Each memory block maps to exactly one cache line.

Direct Mapped Cache

Simple but can cause collisions

Address: [Tag | Index | Offset]

Fully Associative

Any block can go in any cache line.

Fully Associative Cache

No collisions but slower search

Address: [Tag | Offset]

Set Associative

Each block maps to a set of cache lines.

Set Associative Cache

Balance between direct and fully associative

Address: [Tag | Index | Offset]

Cache Performance Metrics

Metric Definition Calculation
Hit Rate Fraction of accesses found in cache Hits / (Hits + Misses)
Miss Rate Fraction of accesses not in cache 1 - Hit Rate
AMAT Average Memory Access Time Hit Time + (Miss Rate × Miss Penalty)

Virtual Memory

Virtual memory provides an abstraction layer between programs and physical memory, enabling efficient memory management, protection, and the illusion of a large contiguous address space.

Address Translation Process

Virtual Address Space
|--------------------|
|     Page Table     |
|--------------------|
|    Translation     | →→→ TLB Cache →→→ Physical Memory
|--------------------|
|   Page Mapping    |
|--------------------|

Page Table Structure

Page tables map virtual addresses to physical addresses with various structures:

Hierarchical

Multi-level page tables to save space

Example: 2-level Page Table

Virtual Address: [PD Index | PT Index | Offset]

Hashed

Hash function maps virtual to physical

Hashed Page Table

Good for large sparse address spaces

Inverted

One entry per physical page

Inverted Page Table

Space efficient but slower lookups

Page Replacement Algorithms

Algorithm Description Advantage Disadvantage
LRU Least Recently Used Optimal for temporal locality Expensive to implement
Clock Second-chance algorithm Efficient approximation of LRU Not truly LRU
Working Set Track active pages Prevents thrashing Complex implementation
FIFO First In First Out Simple to implement Poor performance (Belady's anomaly)

Memory Management

Memory management involves allocation strategies and garbage collection techniques to optimize resource usage in both operating systems and applications.

Memory Allocation Strategies

Strategy Advantages Disadvantages Use Case
First Fit Simple, fast allocation Can lead to fragmentation General purpose allocators
Best Fit Minimizes wasted space Slower allocation time Memory-constrained systems
Buddy System Fast, minimal fragmentation Some internal fragmentation Kernel memory allocators
Slab Allocation Fast for fixed-size objects Not flexible for variable sizes Object caches

Garbage Collection Methods

Automatic memory management techniques used in high-level languages:

Mark-and-Sweep

Traverses and marks reachable objects, then sweeps unreachable ones

Characteristics

• Handles cyclic references

• Can cause pauses

• Used in JavaScript, Java

Reference Counting

Counts references to each object, frees when count reaches zero

Characteristics

• Immediate reclamation

• Can't handle cycles

• Used in Python, PHP

Generational

Divides heap into generations, collects younger generations more often

Characteristics

• Based on weak generational hypothesis

• Reduces pause times

• Used in modern JVMs

Memory Management Unit (MMU)

Hardware component that handles virtual-to-physical address translation and memory protection: 
MMU Functions:
1. Address Translation (via page tables)
2. Memory Protection (page permissions)
3. Cache Control (cacheability attributes)
4. TLB Management (translation lookaside buffer)