Cache pollution

Cache pollution describes situations where an executing computer program loads data into CPU cache unnecessarily, thus causing other useful data to be evicted from the cache into lower levels of the memory hierarchy, degrading performance. For example, in a multi-core processor, one core may replace the blocks fetched by other cores into shared cache, or prefetched blocks may replace demand-fetched blocks from the cache. Consider the following illustration: T[0] = T[0] + 1; for i in 0..sizeof(CACHE) C[i] = C[i] + 1; T[0] = T[0] + C[sizeof(CACHE)-1]; (The assumptions here are that the cache is composed of only one level, it is unlocked, the replacement policy is pseudo-LRU, all data is cacheable, the set associativity of the cache is N (where N > 1), and at most one processor register is available to contain program values). Right before the loop starts, T[0] will be fetched from memory into cache, its value updated. However, as the loop executes, because the number of data elements the loop references requires the whole cache to be filled to its capacity, the cache block containing T[0] has to be evicted. Thus, the next time the program requests T[0] to be updated, the cache misses, and the cache controller has to request the data bus to bring the corresponding cache block from main memory again. In this case the cache is said to be "polluted". Changing the pattern of data accesses by positioning the first update of T[0] between the loop and the second update can eliminate the inefficiency: for i in 0..sizeof(CACHE) C[i] = C[i] + 1; T[0] = T[0] + 1; T[0] = T[0] + C[sizeof(CACHE)-1]; Other than code-restructuring mentioned above, the solution to cache pollution is ensure that only high-reuse data are stored in cache. This can be achieved by using special cache control instructions, operating system support or hardware support. Examples of specialized hardware instructions include "lvxl" provided by PowerPC AltiVec. This instruction loads a 128 bit wide value into a register and marks the corresponding cache block as "least recently used" i.