A processor can execute instructions much faster than the main memory can supply data. If every memory request had to wait for a comparatively slower RAM access, the CPU would frequently remain idle. Cache memory is one of the important hardware techniques used to reduce this delay.
Cache is a small and fast memory located close to the processor. It keeps copies of data and instructions that are likely to be needed again. Instead of repeatedly obtaining the same information from main memory, the processor can often obtain it from cache with a shorter access time.
The effectiveness of cache memory is closely related to a property of programs called locality of reference. Programs tend to access some data repeatedly and often access nearby memory locations. Cache takes advantage of this behavior to improve the average memory access time.
In this chapter, we will study the working of cache memory, cache hits and misses, locality of reference, cache levels, mapping techniques, replacement policies, and important numerical concepts used in Computer Organization and Architecture.
Cache memory is a high-speed memory used to store selected blocks of data and instructions from main memory. It is much smaller than RAM but provides faster access to the processor.
When the processor requests information, the memory system checks whether the required block is already available in cache. If it is present, the processor can use the cached copy. If it is absent, the required block must be obtained from a lower level of the memory hierarchy.
The purpose of cache is therefore not to replace main memory. Its purpose is to reduce the average time required to access information.
CPU
|
v
Cache
|
|-- Data found --> Cache Hit
|
|-- Data not found --> Main Memory
|
v
Required block
|
v
Cache
The diagram represents the basic idea. The CPU checks the faster cache before going to a slower memory level.
A processor performs a large number of operations during program execution. Many of these operations require repeated access to instructions or data. If every request were sent directly to main memory, the processor would spend more time waiting for memory responses.
Cache reduces this waiting time by keeping selected information close to the CPU. The benefit becomes especially significant when a program repeatedly uses the same information or accesses addresses that are close to one another.
Suppose a loop repeatedly uses a variable named count. After the required data has been brought into a suitable cache location, subsequent accesses may be served by cache rather than requiring the processor to obtain the same block again from main memory.
This does not mean every access will be a cache hit. Cache space is limited, and other memory blocks may replace existing blocks. The performance benefit depends on the access pattern and the cache design.
Cache memory works effectively because programs usually do not access memory locations completely at random. Their memory access patterns commonly show locality of reference.
Temporal locality means that if a particular instruction or data item has been accessed recently, there is a reasonable possibility that it will be accessed again soon.
For example, a loop counter may be read and updated repeatedly while a loop is executing. Keeping the corresponding information in a fast memory level can reduce repeated access to slower memory.
Spatial locality means that when one memory location is accessed, nearby memory locations are likely to be accessed soon.
Sequential execution of instructions is a common example. After fetching one instruction, the processor will often need instructions stored at nearby addresses.
Sequential locality can be viewed as a common access pattern in which memory locations are accessed in an ordered sequence. Array traversal and sequential instruction execution are typical examples.
These locality patterns help explain why a relatively small cache can provide useful performance improvements despite being much smaller than main memory.
A cache hit occurs when the processor requests a block that is already available in the cache at the required location and with a matching tag.
A cache miss occurs when the requested block cannot be supplied from that cache level. The memory system then has to obtain the block from another level, such as a lower cache level or main memory.
| Condition | Meaning | Result |
|---|---|---|
| Cache Hit | Requested block is available in cache | Data can be supplied from cache |
| Cache Miss | Requested block is not available in the checked cache | Another memory level must be accessed |
Suppose a processor requests block X. First request: X is not in cache Result = Cache Miss Block X is fetched from a lower memory level. Later request: X is already present in cache Result = Cache Hit
The effectiveness of a cache can be described using the hit ratio and miss ratio.
Hit Ratio = Number of Cache Hits / Total Memory Accesses
Miss Ratio = Number of Cache Misses / Total Memory Accesses
For a simple hit/miss model:
Miss Ratio = 1 - Hit Ratio
Assume a processor performs 1,000 memory accesses. Out of these, 920 accesses are satisfied by cache.
Total accesses = 1000
Cache hits = 920
Cache misses = 1000 - 920
= 80
Hit Ratio = 920 / 1000
= 0.92
= 92%
Miss Ratio = 80 / 1000
= 0.08
= 8%
The example shows that 92 percent of the requests were satisfied at the cache level being considered, while the remaining 8 percent required access to another memory level.
Modern processors commonly use multiple cache levels. The exact organization varies between processor designs, but the general principle is that smaller caches are usually placed closer to the execution cores, while larger caches can be farther away and may be shared.
| Level | General Characteristic | Typical Purpose |
|---|---|---|
| L1 | Very small and very fast | Provide extremely fast access to frequently required data and instructions |
| L2 | Larger than L1 with somewhat higher access latency | Provide additional fast storage when data is not found in L1 |
| L3 | Larger and generally slower than L1/L2 | Provide a larger shared cache layer in many processor designs |
The exact size, latency, and sharing arrangement of these levels depends on the processor architecture. Therefore, L1, L2, and L3 should be understood as levels in a hierarchy rather than as fixed specifications that are identical for every CPU.
CPU Request
|
v
L1
|
| Miss
v
L2
|
| Miss
v
L3
|
| Miss
v
Main Memory
A processor may use additional cache or memory levels depending on its architecture. The important idea is that the memory hierarchy attempts to provide a useful balance between speed, capacity, and cost.
Cache does not normally store an arbitrary single byte as an independent cache entry. Data is transferred between memory levels in groups of bytes commonly called cache blocks or cache lines.
For example, suppose a cache line contains 64 bytes. If the processor requests one byte from a memory region and that block is brought into cache, the cache may receive the complete 64-byte line containing that byte.
This organization makes use of spatial locality. If the processor soon accesses nearby bytes, they may already be present in the same cache line.
A memory address is divided into fields so that the cache can determine where to look and whether the requested block is present.
The exact division depends on the mapping technique, but a typical cache address contains:
+----------------+----------------+----------------+ | Tag | Index | Offset | +----------------+----------------+----------------+
The number of bits assigned to each field depends on the main memory size, cache size, number of cache lines or sets, and cache block size.
Direct mapping is the simplest cache placement technique. Every memory block has exactly one cache line where it can be stored.
The cache line is commonly determined using:
Cache Line = Memory Block Number MOD Number of Cache Lines
Suppose a cache contains 8 lines and memory block number 21 needs to be loaded.
Cache Line = 21 MOD 8
= 5
Therefore, block 21 can be placed in cache line 5.
Now consider block 29:
Cache Line = 29 MOD 8
= 5
Both blocks 21 and 29 map to line 5. If both are actively required, they can repeatedly replace one another. This situation is called a conflict miss.
In fully associative mapping, a memory block is not restricted to one particular cache line. It may be stored in any available cache line.
When the processor searches for a block, the cache compares the requested tag against the tags stored in the cache entries.
Cache contains four lines: Line 0 Line 1 Line 2 Line 3 Memory block 25 can be placed in any available line.
This flexibility reduces the type of conflict caused by fixed direct mapping. However, the hardware required to compare the requested tag against many cache entries is more complex.
Set-associative mapping combines ideas from direct and fully associative mapping. The cache is divided into sets, and each set contains a fixed number of cache lines.
A memory block first maps to one particular set. Within that set, however, the block can occupy any available line.
Suppose a cache contains 8 lines arranged as 4 sets with 2 lines per set. This is a 2-way set-associative cache.
Number of sets = 4
Memory block = 13
Set number = 13 MOD 4
= 1
Therefore, block 13 must go into set 1. Because the set has two lines, the block can use either line in that set if an appropriate position is available.
Set-associative mapping therefore provides more placement flexibility than direct mapping while avoiding the need to search the entire cache for every request.
| Feature | Direct Mapping | Fully Associative | Set-Associative |
|---|---|---|---|
| Placement | One fixed line | Any cache line | Any line within one set |
| Hardware Complexity | Low | High | Moderate |
| Conflict Possibility | Higher | Lower due to flexible placement | Lower than direct mapping |
| Lookup | Simple | More complex | Limited to selected set |
A replacement policy is required when a new block needs to enter a cache or set that has no free space. The policy determines which existing entry should be removed.
LRU removes the entry that has not been accessed for the longest period of time. It is based on temporal locality: recently used information may be useful again.
Cache entries: A B C Recent access order: A → B → C → A → B C is now the least recently used entry. If D must be loaded: C is replaced by D.
Depending on the processor design, replacement can also be based on simpler or implementation-specific strategies. The important point is that replacement decisions are mainly relevant when multiple possible locations are available, such as in set-associative and fully associative caches.
Cache misses are commonly categorized into three major types. Understanding these categories helps explain why a cache access can fail even when the cache is reasonably well designed.
A compulsory miss occurs when a block is accessed for the first time and has not previously been loaded into the cache.
A capacity miss occurs when the cache cannot hold all the blocks required by the program. Previously loaded information may have been removed because the cache is too small for the active working set.
A conflict miss occurs when multiple memory blocks compete for the same cache location. Direct mapping is particularly susceptible to this type of conflict because each block has only one permitted cache line.
Cache performance can also be studied using Average Memory Access Time (AMAT). A simplified model is:
AMAT = Hit Time + (Miss Rate × Miss Penalty)
Here:
Assume:
Cache hit time = 2 ns
Miss rate = 5% = 0.05
Miss penalty = 40 ns
AMAT = Hit Time + (Miss Rate × Miss Penalty)
= 2 + (0.05 × 40)
= 2 + 2
= 4 ns
The example illustrates why both hit time and miss rate matter. A cache that has a low hit time but a very high miss rate may still produce poor overall memory performance.
| Concept | Formula |
|---|---|
| Hit Ratio | Hits / Total Accesses |
| Miss Ratio | Misses / Total Accesses |
| Miss Ratio | 1 − Hit Ratio |
| Direct Mapping Line | Block Number MOD Number of Cache Lines |
| Set Mapping | Block Number MOD Number of Sets |
| AMAT | Hit Time + (Miss Rate × Miss Penalty) |
Consider a simplified cache with the following characteristics:
Main memory = 1024 bytes Cache = 128 bytes Block size = 16 bytes Direct mapping
First calculate the number of cache lines:
Number of cache lines = Cache Size / Block Size = 128 / 16 = 8 lines
Each block contains 16 bytes, so the offset requires:
Offset bits = log2(16)
= 4 bits
There are 8 cache lines, so the index requires:
Index bits = log2(8)
= 3 bits
Main memory contains 1024 bytes:
Address bits = log2(1024)
= 10 bits
Therefore, the remaining address bits are used for the tag:
Tag bits = 10 - 3 - 4
= 3 bits
Thus, for this simplified direct-mapped cache:
+-----------+---------+----------+ | Tag (3) | Index(3)| Offset(4)| +-----------+---------+----------+
This type of calculation is useful for understanding how a processor divides a memory address into fields during cache lookup.
| Feature | Cache Memory | Main Memory |
|---|---|---|
| Speed | Higher | Lower than cache |
| Capacity | Much smaller | Much larger |
| Location | Very close to or integrated with processor | Separate main memory subsystem |
| Purpose | Reduce average memory access time | Hold programs and data currently in use |
| Cost per byte | Higher | Lower |
The mapping technique determines how the memory hierarchy organizes the relationship between main-memory blocks and cache locations. This affects both hardware complexity and the probability that two useful blocks will compete for the same location.
Direct mapping is straightforward and inexpensive but can suffer from repeated conflicts. Fully associative mapping provides maximum placement freedom but requires more complex hardware. Set-associative mapping provides a compromise by restricting a block to a set while allowing several possible locations inside that set.
The choice of mapping strategy is therefore not simply a question of which technique is "best." Cache architecture must balance access time, hardware complexity, cache capacity, power consumption, and expected workload behavior.
Cache memory is a small, high-speed memory used to keep selected blocks of data and instructions close to the processor so that frequently required information can be accessed more quickly.
A cache hit occurs when the requested memory block is found in the cache being searched.
A cache miss occurs when the requested block is not available in the cache level being checked and must be obtained from another memory level.
Direct mapping assigns each main-memory block to one predetermined cache line, commonly using the modulo operation.
Fully associative mapping allows a memory block to be placed in any cache line.
Set-associative mapping divides cache into sets. A memory block maps to one set but can occupy any suitable line within that set.
Locality of reference describes the tendency of programs to access recently used data again or to access memory locations close to recently accessed locations.
Average Memory Access Time is a performance measure that combines cache hit time with the additional cost caused by cache misses.
Cache memory is an important part of the computer memory hierarchy because it reduces the average time required by the processor to obtain data and instructions. Its effectiveness comes largely from locality of reference: programs frequently reuse recently accessed information and often access nearby memory locations.
The organization of cache determines how efficiently this principle can be used. Direct mapping provides simple fixed placement, fully associative mapping provides flexible placement, and set-associative mapping provides a balance between the two. Replacement policies determine what happens when available cache space is exhausted, while hit ratio, miss ratio, and AMAT provide useful ways to evaluate cache behavior.
Understanding these concepts is particularly important for Computer Organization and Architecture because cache questions often combine conceptual knowledge with numerical calculations involving cache lines, address fields, mapping, hit ratio, and memory access time.