Cache Memory Mapping Techniques: Direct, Associative and Set-Associative Mapping

How does the CPU know where a block of main memory should be placed inside cache memory? The answer is cache memory mapping. There are three fundamental cache mapping techniques: Direct Mapping, Associative Mapping and Set-Associative Mapping. Learn how each technique works, how addresses are divided, important formulas, examples, advantages, disadvantages and the complete comparison.

Cache mapping is an important topic in Computer Organization and Architecture. It explains the relationship between main memory blocks and cache lines and is frequently used in CSE, computer architecture and examination questions.

Quick answer: Direct mapping allows each memory block to go to one specific
cache line. Associative mapping allows a memory block to be placed in any cache line.
Set-associative mapping combines the ideas of both techniques by dividing the cache into sets.

What Is Cache Memory?

Cache memory is a small and high-speed memory located close to the CPU. It stores copies of frequently or recently accessed data and instructions so that the processor can access them faster than retrieving them repeatedly from slower main memory.

Modern processors generally contain multiple levels of cache, commonly called L1, L2 and L3 cache.

Basic Cache Organization

CPU
↓
Cache Memory
↓
Main Memory

Because cache is much smaller than main memory, only selected blocks of main memory can be stored in it at any particular time.

This creates an important question:

When a block of main memory is brought into cache, where should it be placed?

The mechanism used to answer this question is called cache mapping.

What Is Cache Memory Mapping?

Cache memory mapping is the technique used to determine the relationship between blocks of main memory and locations, or lines, in cache memory.

Since the cache is smaller than main memory, multiple main memory blocks may need to compete for the same cache location depending on the mapping technique.

The three major mapping techniques are:

Direct Mapping
Associative Mapping
Set-Associative Mapping

Why Is Cache Mapping Needed?

Suppose main memory contains thousands of blocks while cache contains only a limited number of lines. The system needs a method to decide where each main-memory block can be stored.

A mapping technique provides rules for:

Placing memory blocks into cache
Finding whether a required block is already present
Identifying the corresponding cache location
Managing conflicts between memory blocks
Improving cache access efficiency

Types of Cache Mapping

Mapping Technique	Basic Idea
Direct Mapping	Each memory block maps to exactly one cache line.
Associative Mapping	A memory block can be placed in any cache line.
Set-Associative Mapping	A memory block maps to one set but can occupy any line within that set.

1. Direct Mapping

Direct mapping is the simplest cache mapping technique. In direct mapping, each block of main memory is assigned to exactly one specific cache line.

Key idea: One memory block → One possible cache line.

How Direct Mapping Works

The cache is divided into a number of fixed-size cache lines. Main memory is also considered to be divided into blocks of the same size as a cache line.

Each main memory block is mapped to a particular cache line using a mathematical relationship.

Cache Line Number = Main Memory Block Number MOD Number of Cache Lines

For example, suppose a cache contains 8 lines. Then:

Main Memory Block	Cache Line
0	0 MOD 8 = 0
1	1 MOD 8 = 1
2	2 MOD 8 = 2
7	7 MOD 8 = 7
8	8 MOD 8 = 0
9	9 MOD 8 = 1
16	16 MOD 8 = 0

Notice that memory blocks 0, 8 and 16 all map to cache line 0. This can cause conflict misses when those blocks are repeatedly needed.

Address Format in Direct Mapping

A memory address in a direct-mapped cache is commonly divided into three parts:

Tag | Line | Block Offset

Field	Purpose
Tag	Identifies which main-memory block is currently stored in the selected cache line.
Line	Identifies the cache line where the block should be located.
Block Offset	Identifies the specific byte or word within the block.

Direct Mapping Formulas

Number of cache lines = Cache size / Block size

Line number = Block number MOD Number of cache lines

Number of offset bits = log₂(Block size)

Number of line bits = log₂(Number of cache lines)

Direct Mapping Example

Consider:

Main memory = 64 KB
Cache = 1 KB
Block size = 16 bytes

First calculate the number of cache lines:

Cache lines = 1024 / 16 = 64 lines

Therefore, the line field requires:

log₂(64) = 6 bits

The block offset requires:

log₂(16) = 4 bits

The remaining address bits are used for the tag.

2. Associative Mapping

Associative mapping, also called fully associative mapping, provides much greater placement flexibility than direct mapping.

In associative mapping, a main-memory block can be placed in any cache line.

Key idea: One memory block → Any cache line.

How Associative Mapping Works

Unlike direct mapping, there is no fixed cache line for each memory block. When a block is brought into cache, it can be stored in any available cache line.

When the CPU requests a memory block, the cache system compares the requested tag against the tags stored in cache.

Memory Block
↓
Can be placed in
↓
Cache Line 0 | Cache Line 1 | Cache Line 2
| |
Any available cache line

Address Format in Associative Mapping

The address is generally divided into:

Tag | Block Offset

There is no separate line/index field because the block can be located in any cache line.

Associative Mapping Example

Suppose the cache contains 8 lines and the system wants to load memory block 25.

Under direct mapping:

25 MOD 8 = 1

So block 25 must use cache line 1.

Under associative mapping, block 25 can be stored in any available cache line.

This reduces the restrictions caused by fixed cache-line assignments.

3. Set-Associative Mapping

Set-associative mapping combines characteristics of direct mapping and associative mapping.

The cache is divided into multiple sets, and each set contains a fixed number of cache lines.

Key idea: A memory block maps to one set, but can occupy any line within that set.

How Set-Associative Mapping Works

Suppose a cache has 8 lines and uses 2-way set associativity. The cache is divided into:

Number of sets = 8 / 2 = 4 sets

Each set contains two cache lines.

Set	Cache Lines
Set 0	Line 0, Line 1
Set 1	Line 2, Line 3
Set 2	Line 4, Line 5
Set 3	Line 6, Line 7

A memory block is first mapped to a particular set and can then occupy any line within that set.

Address Format in Set-Associative Mapping

Tag | Set Index | Block Offset

Field	Purpose
Tag	Identifies the memory block.
Set Index	Identifies the cache set.
Block Offset	Identifies the location inside the block.

Set-Associative Example

Suppose:

Cache has 8 lines
Cache is 2-way set associative
Therefore, there are 4 sets

For memory block 13:

Set number = 13 MOD 4

Set number = 1

Therefore, block 13 can be stored in either of the two cache lines belonging to set 1.

This provides more flexibility than direct mapping while requiring less searching than fully associative mapping.

Direct vs Associative vs Set-Associative Mapping

Feature	Direct Mapping	Associative Mapping	Set-Associative Mapping
Placement	One specific line	Any cache line	Any line within a specific set
Flexibility	Low	Very high	Moderate to high
Mapping complexity	Low	High	Moderate
Address fields	Tag, line, offset	Tag, offset	Tag, set, offset
Comparison requirement	Limited	Multiple cache tags may need comparison	Multiple tags within the selected set are compared
Hardware complexity	Low	High	Moderate
Cost	Low	High	Moderate
Search method	Directly selects one line	Searches cache tags	Searches selected set
Conflict misses	More likely	Less likely	Reduced compared with direct mapping
Speed	Generally fast	Can require more hardware for searching	Good balance
Implementation	Simple	Complex	Moderately complex
Hardware requirement	Lower	Higher	Between direct and fully associative
Replacement issue	Fixed location	Replacement policy needed across possible lines	Replacement policy needed within a set
Typical concept	One-to-one possible location	Any-to-any possible location	One-to-set, many-to-line within set

Advantages and Disadvantages

Direct Mapping Advantages

Simple to implement.
Low hardware complexity.
Fast line selection.
Lower implementation cost.
Easy to understand and calculate.

Direct Mapping Disadvantages

Limited placement flexibility.
More susceptible to conflict misses.
Different memory blocks may compete for the same cache line.

Associative Mapping Advantages

Very flexible block placement.
Reduces restrictions caused by fixed cache lines.
Can reduce conflict problems.

Associative Mapping Disadvantages

More complex hardware.
Requires tag comparison across possible cache entries.
Higher implementation cost.
Replacement decisions can be more complex.

Set-Associative Mapping Advantages

Balances flexibility and implementation complexity.
Reduces conflict misses compared with direct mapping.
Requires fewer comparisons than fully associative mapping for a given cache.
Provides a practical compromise between the two techniques.

Set-Associative Mapping Disadvantages

More complex than direct mapping.
Requires additional hardware compared with direct mapping.
Replacement decisions are required within sets.

Cache Hit and Cache Miss

Cache Hit

A cache hit occurs when the CPU requests data and the required block is already present in cache.

CPU request → Cache contains required block → Cache Hit

The processor can obtain the required information from cache without fetching the block from main memory.

Cache Miss

A cache miss occurs when the requested block is not present in cache. The system then needs to obtain the required data from a lower level of the memory hierarchy.

CPU request → Required block not found in cache → Cache Miss

Conflict Miss

A conflict miss can occur when multiple memory blocks compete for the same cache location or set even though the cache may have space elsewhere.

Direct mapping is particularly associated with this type of placement restriction.

Why Set-Associative Mapping Is Popular

Direct mapping is simple but can suffer from conflicts because each memory block has only one possible cache line.

Fully associative mapping provides maximum placement flexibility but requires more complex hardware to search possible locations.

Set-associative mapping provides a compromise:

Direct Mapping
Low complexity + Low flexibility

↓

Set-Associative Mapping
Balanced complexity + Flexibility

↓

Fully Associative Mapping
High flexibility + Higher complexity

Important Cache Mapping Formulas

Concept	Formula
Number of cache lines	Cache Size / Block Size
Direct mapping line number	Memory Block Number MOD Number of Cache Lines
Number of sets	Number of Cache Lines / Number of Ways
Set number	Memory Block Number MOD Number of Sets
Offset bits	log₂(Block Size)
Direct mapping line bits	log₂(Number of Cache Lines)
Set index bits	log₂(Number of Sets)

Quick Difference: Direct vs Associative vs Set-Associative

Direct	Associative	Set-Associative
One block → One line	One block → Any line	One block → One set → Any line in that set
Simple	Complex	Moderately complex
Low cost	High cost	Moderate cost
More conflict misses	Fewer placement conflicts	Fewer conflicts than direct mapping

Memory Address Fields at a Glance

Mapping	Address Structure
Direct Mapping	Tag \| Line \| Offset
Associative Mapping	Tag \| Offset
Set-Associative Mapping	Tag \| Set \| Offset

Important Exam Points

Cache mapping determines where main-memory blocks are placed in cache.
There are three major cache mapping techniques.
They are direct, associative and set-associative mapping.
In direct mapping, each memory block maps to exactly one cache line.
Direct mapping uses the modulo operation for line selection.
In associative mapping, a block can be placed in any cache line.
Associative mapping does not require a separate line/index field in the memory address.
Set-associative mapping divides cache into multiple sets.
A block maps to one set in set-associative mapping.
Within the selected set, the block can occupy one of the available lines.
Direct mapping has lower hardware complexity.
Fully associative mapping provides greater placement flexibility.
Set-associative mapping provides a compromise between direct and fully associative mapping.
Cache hit means the requested block is found in cache.
Cache miss means the requested block is not found in cache.
Conflict misses can result from restricted placement.

Short Exam Answer

Cache mapping is the technique used to determine where a block of main memory can be placed in cache memory. The three major techniques are direct mapping, associative mapping and set-associative mapping. Direct mapping assigns a block to one specific cache line, associative mapping allows a block to occupy any cache line, and set-associative mapping allows a block to occupy any line within its assigned set.

Frequently Asked Questions

What is cache memory mapping?

Cache memory mapping is the method used to determine the location where a main-memory block can be stored in cache.

What are the three cache mapping techniques?

The three major techniques are direct mapping, associative mapping and set-associative mapping.

What is direct mapping?

Direct mapping is a cache mapping technique in which each main-memory block can be placed in only one specific cache line.

What is associative mapping?

Associative mapping allows a main-memory block to be placed in any available cache line.

What is set-associative mapping?

Set-associative mapping divides the cache into sets. A memory block maps to one set and can occupy any line within that set.

Which cache mapping technique is simplest?

Direct mapping is generally the simplest cache mapping technique to implement.

Which mapping provides the highest placement flexibility?

Fully associative mapping provides the highest placement flexibility because a block can be stored in any cache line.

Why is set-associative mapping used?

Set-associative mapping provides a compromise between the simplicity of direct mapping and the flexibility of fully associative mapping.

What is the formula for direct mapping?

The cache line is generally determined using: Memory Block Number MOD Number of Cache Lines.

What is a cache hit?

A cache hit occurs when the requested data or instruction is already available in cache.

What is a cache miss?

A cache miss occurs when the requested block is not present in the cache.

Conclusion

Cache memory mapping is an important concept in computer organization and architecture. It determines how blocks of main memory are associated with cache locations.

The three major techniques are direct mapping, associative mapping and set-associative mapping.

Direct mapping is simple and inexpensive but has restricted placement. Associative mapping provides maximum flexibility but requires more complex hardware. Set-associative mapping provides a practical balance between the two.

Understanding these techniques is especially important for questions involving cache organization, memory hierarchy, address mapping, cache hits, cache misses and computer architecture numericals.

Labels

Sunday, 4 October 2026