Cache prefetching

lastmod 2019-11-25created 2019-11-255 edits

The goal of memory optimization is to deliver the minimum amount of memory (values) needed for execution as quickly as possible. Therefore, data structures and memory buffers must be handled carefully to maximize cache hits. When data is not in the cache, the processor's prefetch feature can be used to explicitly bring memory values into the cache.

A prefetch instruction tells the processor that the values at a particular memory location will be used soon, so it should prepare them in the cache in advance. If bus bandwidth is available, the processor loads the data at the specified memory address into the cache. When the memory values are actually used, the data is already in the cache and immediately available. Or at least the first part of the data is immediately available.

There are four types of prefetch instructions depending on which cache the data is (pre)loaded into. Among them, Non-temporal aligned (NTA) should be used only for data that will be read exactly once.¹ If the algorithm updates the data after prefetching (read-modify-write) or accesses it more than once, use T0 instead of NTA.

Types

Below is a table summarizing the four prefetch types.

Assembly Instruction	C++ Compiler Intrinsic Type Used as Second Parameter in _mm_prefetch(char *p, int Hint)	Description
PREFETCHNTA	_MM_HINT_NTA	Loads into the non-temporal buffer for a single read.
PREFETCHT0	_MM_HINT_T0	Loads into all of the processor's caches. Suitable when the data will be read/written right away.
PREFETCHT1	_MM_HINT_T1	Loads the data only into the L2 and L3 caches. L1 is excluded
PREFETCHT2	_MM_HINT_T2	Loads the data only into the L3 cache. L1 and L2 are excluded

More

A prefetch strategy performs best when the data is already in the cache when it is needed. This means the prefetch must be performed sufficiently ahead of when the data is actually needed. How far ahead depends on many factors, but roughly 100 clocks ahead is about right.

Prefetching data used in a loop is a good example of something easy to program that yields good results. Sometimes, to get the best results, you need to prefetch two, four, or as many times as the loop count. Determining the optimal place and data to prefetch takes repeated trial and error (attempts). However, because memory, memory controllers, and bus speeds keep changing (with technological progress), the places to prefetch can vary as well. Prefetch loads in units of cache lines, so up to 64 bytes are loaded from the specified memory.

Prefetching too often actually degrades performance.

Example

The code below is an example that prefetches data to be used 16 loop iterations later.

for ( i = 0; i < 1000; ++i )
{
    x = fn( array[ i ] );
    _mm_prefetch( array[ i + 16 ], MM_HINT_T0 );
}

Favorite site

References

Because after the read, the data is removed from the Non-temporal buffer right away without being stored in the cache (without polluting it). So if a read/write occurs again later for the same data, it has to be brought into the cache. ↩

author Zer0 sitemap