Memory Hierarchy

In modern computer systems, memory is organized in a hierarchy of different types, each with unique characteristics. This layered structure exists because no single type of memory can simultaneously offer the best speed, capacity, and cost. Understanding this hierarchy is essential for grasping how computers manage data efficiently.

Imagine you are working on a project and need to access various documents. You might keep your most frequently used papers right on your desk for quick access (fast but limited space), store less-used files in a nearby cabinet (slower but larger space), and archive old files in a distant storage room (slowest but very large capacity). Similarly, computers use different memory types to balance speed, size, and cost.

Why Multiple Types of Memory?

Speed: Faster memory allows the CPU to access data quickly, improving performance.
Cost: Faster memory is more expensive per unit of storage.
Capacity: Larger memory can hold more data but is usually slower and cheaper.

By combining different memory types in a hierarchy, computers achieve a balance: small amounts of very fast memory close to the CPU, and large amounts of slower, cheaper memory further away.

Memory Hierarchy Levels

The memory hierarchy is typically visualized as a pyramid, with the fastest and smallest memory at the top, and the slowest and largest memory at the bottom. Let's explore each level:

Registers: These are tiny storage locations inside the CPU itself. Registers hold data that the CPU is currently processing. They are the fastest memory but extremely limited in size (usually a few bytes to a few hundred bytes).
Cache Memory: Cache is a small, fast memory located close to the CPU. It stores copies of frequently accessed data from main memory to speed up access. Cache is larger than registers but smaller than main memory. It is often divided into levels: L1 (smallest and fastest), L2, and L3 (largest and slowest among caches).
Main Memory (RAM): This is the primary memory where programs and data reside while running. It is larger and slower than cache but faster than secondary storage. RAM is volatile, meaning data is lost when power is off.
Secondary Storage: This includes hard drives, solid-state drives (SSD), and other long-term storage devices. It has the largest capacity but is the slowest and cheapest memory type. Data here is persistent, remaining stored even when the computer is off.

This pyramid shape reflects the trade-offs between speed, size, and cost:

Principle of Locality: The design of memory hierarchy relies on the principle of locality, which states that programs tend to access a relatively small portion of their address space at any given time. This means:

Temporal locality: Recently accessed data is likely to be accessed again soon.
Spatial locality: Data near recently accessed data is likely to be accessed soon.

Cache memory exploits this principle by keeping recently or frequently used data close to the CPU, reducing the need to access slower memory levels.

Cache Memory and Performance Metrics

Cache memory plays a crucial role in speeding up data access. When the CPU needs data, it first checks the cache:

Cache Hit: The data is found in the cache, allowing very fast access.
Cache Miss: The data is not in the cache, so the system must fetch it from the slower main memory, causing a delay.

To evaluate cache performance, we use several key metrics:

Hit Ratio: The fraction of memory accesses found in the cache.
Miss Ratio: The fraction of memory accesses not found in the cache (Miss Ratio = 1 - Hit Ratio).
Miss Penalty: The additional time required to fetch data from main memory when a cache miss occurs.
Average Memory Access Time (AMAT): The expected time to access memory, considering both hits and misses.

Below is a comparison of typical memory types showing their access times, cost per bit, and capacity:

Memory Type	Access Time (ns)	Cost per Bit (INR)	Typical Capacity
Registers	~0.5 - 1	Very High	Few Bytes
Cache (L1)	1 - 3	High	32 - 64 KB
Cache (L2)	3 - 10	Moderate	256 KB - 1 MB
Main Memory (RAM)	50 - 100	Low	4 GB - 64 GB
Secondary Storage (SSD)	10,000 - 100,000 (10 µs - 100 µs)	Very Low	256 GB - Several TB

Calculating Average Memory Access Time (AMAT)

The average time to access memory depends on how often data is found in the cache (hit) versus how often it must be fetched from slower memory (miss). The formula for AMAT is:

Average Memory Access Time (AMAT)

\[AMAT = (Hit\ Ratio \times Cache\ Access\ Time) + (Miss\ Ratio \times Miss\ Penalty)\]

Calculates average time to access memory considering cache hits and misses

Hit Ratio = Fraction of accesses found in cache

Cache Access Time = Time to access cache

Miss Ratio = Fraction of accesses not found in cache (1 - Hit Ratio)

Miss Penalty = Time to access main memory on cache miss

This formula helps system designers and programmers understand the impact of cache performance on overall system speed.

Worked Examples

Example 1: Calculating Average Memory Access Time Medium

Given a cache hit ratio of 0.9, cache access time of 1 ns, and main memory access time of 50 ns, calculate the average memory access time.

Step 1: Identify the given values:

Hit Ratio (HR) = 0.9
Cache Access Time (CAT) = 1 ns
Main Memory Access Time (MMAT) = 50 ns

Step 2: Calculate Miss Ratio (MR):

MR = 1 - HR = 1 - 0.9 = 0.1

Step 3: Apply the AMAT formula:

\[ AMAT = (HR \times CAT) + (MR \times MMAT) \]

\[ AMAT = (0.9 \times 1) + (0.1 \times 50) = 0.9 + 5 = 5.9 \text{ ns} \]

Answer: The average memory access time is 5.9 nanoseconds.

Example 2: Cache Hit and Miss Scenario Medium

Consider a cache that can store 4 blocks. The CPU accesses the following sequence of memory blocks: 2, 3, 2, 1, 5, 2, 4, 5. Determine the number of cache hits and misses assuming an empty cache initially and a Least Recently Used (LRU) replacement policy.

Step 1: Start with an empty cache (capacity 4 blocks).

Step 2: Process each access:

Access 2: Miss (cache empty), cache = [2]
Access 3: Miss, cache = [2, 3]
Access 2: Hit (2 is in cache), cache = [3, 2] (2 becomes most recently used)
Access 1: Miss, cache = [3, 2, 1]
Access 5: Miss, cache = [3, 2, 1, 5]
Access 2: Hit, cache = [3, 1, 5, 2]
Access 4: Miss, cache full, evict least recently used (3), cache = [1, 5, 2, 4]
Access 5: Hit, cache = [1, 2, 4, 5]

Step 3: Count hits and misses:

Hits: 3 (accesses 2, 2, 5)
Misses: 5

Answer: Number of cache hits = 3, cache misses = 5.

Example 3: Memory Cost Comparison Easy

Given the cost per bit of cache memory is Rs.0.10 and main memory is Rs.0.01, calculate the cost difference to store 1 GB of data in each.

Step 1: Convert 1 GB to bits:

1 GB = 1 x 1024 MB = 1024 x 1024 KB = 1024 x 1024 x 1024 bytes = 1,073,741,824 bytes

Each byte = 8 bits, so total bits = 1,073,741,824 x 8 = 8,589,934,592 bits

Step 2: Calculate cost for cache memory:

Cost = 8,589,934,592 bits x Rs.0.10 = Rs.858,993,459.20

Step 3: Calculate cost for main memory:

Cost = 8,589,934,592 bits x Rs.0.01 = Rs.85,899,345.92

Step 4: Find cost difference:

Difference = Rs.858,993,459.20 - Rs.85,899,345.92 = Rs.773,094,113.28

Answer: Storing 1 GB in cache memory costs approximately Rs.773 million more than in main memory.

Example 4: Impact of Cache Size on Hit Ratio Hard

A system has a cache size of 256 KB with a hit ratio of 0.85. Increasing the cache size to 512 KB improves the hit ratio to 0.92. If cache access time is 2 ns and main memory access time is 60 ns, calculate the reduction in average memory access time.

Step 1: Calculate AMAT for 256 KB cache:

Hit Ratio = 0.85, Miss Ratio = 0.15

\[ AMAT_{256} = (0.85 \times 2) + (0.15 \times 60) = 1.7 + 9 = 10.7 \text{ ns} \]

Step 2: Calculate AMAT for 512 KB cache:

Hit Ratio = 0.92, Miss Ratio = 0.08

\[ AMAT_{512} = (0.92 \times 2) + (0.08 \times 60) = 1.84 + 4.8 = 6.64 \text{ ns} \]

Step 3: Calculate reduction in AMAT:

\[ 10.7 - 6.64 = 4.06 \text{ ns} \]

Answer: Increasing cache size reduces average memory access time by 4.06 nanoseconds.

Example 5: Memory Access Time with Multi-level Cache Hard

A computer has two levels of cache: L1 with access time 1 ns and hit ratio 0.95, and L2 with access time 5 ns and hit ratio 0.9. Main memory access time is 50 ns. Calculate the average memory access time.

Step 1: Understand the hierarchy:

First, CPU checks L1 cache.
If miss in L1, check L2 cache.
If miss in L2, access main memory.

Step 2: Calculate miss ratios:

L1 Miss Ratio = 1 - 0.95 = 0.05

L2 Miss Ratio = 1 - 0.9 = 0.1

Step 3: Use the formula for multi-level cache AMAT:

\[ AMAT = L1\_Access\_Time + L1\_Miss\_Ratio \times (L2\_Access\_Time + L2\_Miss\_Ratio \times Main\_Memory\_Access\_Time) \]

Step 4: Substitute values:

\[ AMAT = 1 + 0.05 \times (5 + 0.1 \times 50) \]

\[ = 1 + 0.05 \times (5 + 5) = 1 + 0.05 \times 10 = 1 + 0.5 = 1.5 \text{ ns} \]

Answer: The average memory access time with two-level cache is 1.5 nanoseconds.

Formula Bank

Average Memory Access Time (AMAT)

\[ AMAT = (Hit\ Ratio \times Cache\ Access\ Time) + (Miss\ Ratio \times Miss\ Penalty) \]

where: Hit Ratio = fraction of accesses found in cache; Cache Access Time = time to access cache; Miss Ratio = 1 - Hit Ratio; Miss Penalty = time to access main memory on cache miss

Miss Ratio

\[ Miss\ Ratio = 1 - Hit\ Ratio \]

where: Hit Ratio = fraction of accesses found in cache

Tips & Tricks

Tip: Remember the pyramid shape of memory hierarchy to recall speed and size order

When to use: When trying to quickly identify which memory type is faster or larger

Tip: Use the formula AMAT = (Hit Ratio x Cache Time) + (Miss Ratio x Miss Penalty) for all average access time problems

When to use: Whenever calculating average memory access time in cache-related questions

Tip: Convert all times to the same unit (usually nanoseconds) before calculations

When to use: During numerical problems involving access times to avoid unit mismatch

Tip: Associate higher cost per bit with faster memory types to remember cost-speed trade-offs

When to use: When comparing memory types in cost or speed questions

Tip: Practice identifying cache hits and misses by simulating memory access sequences

When to use: To improve speed and accuracy in cache-related questions

Common Mistakes to Avoid

❌ Confusing hit ratio with miss ratio

✓ Remember miss ratio = 1 - hit ratio

Why: Students often forget that hit and miss ratios are complementary probabilities

❌ Mixing units of time (e.g., milliseconds with nanoseconds)

✓ Always convert all time units to the same scale before calculations

Why: Unit inconsistency leads to incorrect average access time results

❌ Assuming cache size does not affect hit ratio

✓ Understand that larger cache sizes generally improve hit ratio

Why: Students overlook the impact of cache size on performance metrics

❌ Ignoring miss penalty in average memory access time calculations

✓ Include miss penalty as it significantly affects AMAT

Why: Neglecting miss penalty underestimates actual memory access time

❌ Confusing different levels of cache (L1, L2, L3)

✓ Learn the hierarchy and typical access times of each cache level

Why: Misunderstanding cache levels leads to errors in multi-level cache problems

Key Concept

Memory Hierarchy Summary

Each memory type balances speed, cost, and capacity. Registers are fastest but smallest and most expensive; secondary storage is slowest but largest and cheapest.

The Joy of Learning

Login

The Joy of Learning

Sign-up

The Joy of Learning

Forgot Password

Memory Hierarchy

Memory Hierarchy

Why Multiple Types of Memory?

Memory Hierarchy Levels

Cache Memory and Performance Metrics

Calculating Average Memory Access Time (AMAT)

Average Memory Access Time (AMAT)

Worked Examples

Formula Bank

Tips & Tricks

Common Mistakes to Avoid

Memory Hierarchy Summary

Try Practice next.

Rank

eBook

Online Test Series + eBook

Book is added to your cart!