CPU cache

From Wikipedia, the free encyclopedia

Jump to: navigation, search

"Cache memory" redirects here. For the general use in computing, see Cache (computing).

A CPU cache is a cache used by the central processing unit of a computer to reduce the average time to access memory. The cache is a smaller, faster memory which stores copies of the data from the most frequently used main memory locations. As long as most memory accesses are cached memory locations, the average latency of memory accesses will be closer to the cache latency than to the latency of main memory.

Contents 1 Overview 1.1 Cache Entries 1.2 Cache Performance 1.2.1 Replacement Policies 1.2.2 Write Policies 1.2.3 CPU stalls 2 Cache entry structure 2.1 Flag bits 3 Associativity 3.1 Direct-mapped cache 3.2 2-way set associative cache 3.3 Speculative execution 3.4 2-way skewed associative cache 3.5 Pseudo-associative cache 4 Cache miss 5 Address translation 5.1 Homonym and synonym problems 5.2 Virtual tags and vhints 5.3 Page coloring 6 Cache hierarchy in a modern processor 6.1 Specialized caches 6.1.1 Victim cache 6.1.2 Trace cache 6.2 Multi-level caches 6.2.1 Multi-core chips 6.2.2 Exclusive versus inclusive 6.3 Example: the K8 6.4 More hierarchies 7 Implementation 7.1 History 7.1.1 First TLB implementations 7.1.2 First data cache 7.1.3 In x86 microprocessors 7.1.4 Current research 7.2 Multi-ported cache 8 See also 9 Notes 10 References 11 External links

Overview

When the processor needs to read from or write to a location in main memory, it first checks whether a copy of that data is in the cache. If so, the processor immediately reads from or writes to the cache, which is much faster than reading from or writing to main memory.
Most modern desktop and server CPUs have at least three independent caches: an instruction cache to speed up executable instruction fetch, a data cache to speed up data fetch and store, and a translation lookaside buffer (TLB) used to speed up virtual-to-physical address translation for both executable instructions and data. The data cache is usually organized as a hierarchy of more cache levels (L1, L2, etc.; see Multi-level caches).

Cache Entries

Data is transferred between memory and cache in blocks of fixed size, called cache lines. When a cache line is copied from memory into the cache, a cache entry is created. The cache entry will include the copied data as well as the requested memory location (now called a tag).
When the processor needs to read or write a location in main memory, it first checks for a corresponding entry in the cache. The cache checks for the contents of the requested memory location in any cache lines that might contain that address. If the processor finds that the memory location is in the cache, a cache hit has occurred (otherwise, a cache miss). In the case of:

• a cache hit, the processor immediately reads or writes the data in the cache line.
• a cache miss, the cache allocates a new entry, and copies in data from main memory. Then, the request is fulfilled from the contents of the cache.

Cache Performance

The proportion of accesses that result in a cache hit is known as the hit rate, and can be a measure of the effectiveness of the cache for a given program or algorithm.
Read misses delay execution because they require data to be transferred from memory much slower than the cache itself. Write misses may occur without such penalty, since the processor can continue execution while data is copied to main memory in the background.
Instruction caches are similar to data caches, but the CPU only performs read accesses (instruction fetches) to the instruction cache. (With Harvard architecture and modified Harvard architecture CPUs, instruction and data caches can be separated for higher performance, but they can also be combined to reduce the hardware overhead.)

Replacement Policies

Main article: cache algorithms

In order to make room for the new entry on a cache miss, the cache may have to evict one of the existing entries. The heuristic that it uses to choose the entry to evict is called the replacement policy. The fundamental problem with any replacement policy is that it must predict which existing cache entry is least likely to be used in the future. Predicting the future is difficult, so there is no perfect way to choose among the variety of replacement policies available.
One popular replacement policy, least-recently used (LRU), replaces the least recently accessed entry.
Marking some memory ranges as non-cacheable can improve performance, by avoiding caching of memory regions that are rarely re-accessed. This avoids the overhead of loading something into the cache, without having any reuse.

• Cache entries may also be disabled or locked depending on the context.

Write Policies

If data is written to the cache, at some point it must also be written to main memory. The timing of this write is known as the write policy.

• In a write-through cache, every write to the cache causes a write to main memory.
• Alternatively, in a write-back or copy-back cache, writes are not immediately mirrored to the main memory. Instead, the cache tracks which locations have been written over (these locations are marked dirty). The data in these locations are written back to the main memory only when that data is evicted from the cache. For this reason, a miss in a write-back cache may sometimes require two memory accesses to service: one to first write the dirty location to memory and then another to read the new location from memory.

There are intermediate policies as well. The cache may be write-through, but the writes may be held in a store data queue temporarily, usually so that multiple stores can be processed together (which can reduce bus turnarounds and improve bus utilization).
The data in main memory being cached may be changed by other entities (e.g. peripherals using direct memory access or multi-core processor), in which case the copy in the cache may become out-of-date or stale. Alternatively, when the CPU in a multi-core processor updates the data in the cache, copies of data in caches associated with other cores will become stale. Communication protocols between the cache managers which keep the data consistent are known as cache coherence protocols.

CPU stalls

The time taken to fetch one cache line from memory (read latency) matters because the CPU will run out of things to do while waiting for the cache line. When a CPU reaches this state, it is called a stall.
As CPUs become faster, stalls due to cache misses displace more potential computation; modern CPUs can execute hundreds of instructions in the time taken to fetch a single cache line from main memory. Various techniques have been employed to keep the CPU busy during this time.

• Out-of-order CPUs (Pentium Pro and later Intel designs, for example) attempt to execute independent instructions after the instruction that is waiting for the cache miss data.
• Another technology, used by many processors, is simultaneous multithreading (SMT), or — in Intel's terminology — hyper-threading (HT), which allows an alternate thread to use the CPU core while a first thread waits for data to come from main memory.