Example
Consider the following illustration:
T = T + 1; for i in 0..SIZEOF(CACHE) C = C + 1; T = T + C;(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 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 has to be evicted. Thus, the next time the program requests T 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" because it is obvious that just by changing the pattern of data accesses (e.g. positioning the first update of T between the loop and the second update) the inefficiency can be eliminated.
Read more about this topic: Cache Pollution
Famous quotes containing the word example:
“Our intellect is not the most subtle, the most powerful, the most appropriate, instrument for revealing the truth. It is life that, little by little, example by example, permits us to see that what is most important to our heart, or to our mind, is learned not by reasoning but through other agencies. Then it is that the intellect, observing their superiority, abdicates its control to them upon reasoned grounds and agrees to become their collaborator and lackey.”
—Marcel Proust (1871–1922)