|
ALS 2000 Abstract
The Elements of Cache Programming Style
Chris B. Sears, Google, Inc.
Abstract
Cache memories work on the carrot and stick principle. The carrot is the Principle of Locality and the stick is Amdahl's
Law. The Principle of Locality says that programs tend to cluster their memory references. A memory location
referenced once is likely to be referenced again: temporal locality. A memory location nearby a referenced location is
likely to be referenced soon: spatial locality. And Amdahl's Law says that the performance improvement to be gained
from using some faster component is limited by the fraction of time the faster component is used. In this case, CPU and
cache are fast components and memory is slow.
If your program adheres to the Principle of Locality, it benefits from fast cache memory and runs at processor speed. If
it doesn't, it is held accountable to Amdahl's Law and runs at memory speed. Hit rates have to be very high, say 98%,
before incremental increases in processor speed are even noticeable.
Amdahl's Law has a special circumstances penalty for multiprocessors [Schimmel94]. Thrashing on a multiprocessor
can slow down all of the processors. They each wait for each other waiting for memory and the leverage a
multiprocessor offers works in reverse. Adherence to the Principle of Locality for multiprocessors, but not to the point
of False Sharing, isn't just a nicety, it is a necessity.
The object of cache programming style is to increase this locality. It is important to understand the structure and
behavior of caches, but it is more important to know the basic properties to take advantage of and the worst cases to
avoid. This article goes into details and the summary provides guidelines.
|
Need help? Use our Contacts page.
