A Higher Order Theory Of Locality And Its Application In Multicore Cache Management

"As multi-core processors become commonplace and cloud computing is gaining acceptance, applications are increasingly run in parallel over a shared memory hierarchy. While the traditional machine and program metrics such as miss ratio and reuse distance can precisely characterize the memory performance of a single program, they are not composable and therefore cannot model the dynamic interaction between simultaneously running programs. This dissertation presents an alternative metric called program footprint. Given a program execution, its footprint is the amount of data accessed in a given time period. The footprint is composable-- the aggregate footprint of a set of programs is the sum of the footprint of the individual footprints. The dissertation presents the following techniques: Near real-time footprint measurement, first by using two novel algorithms, one for footprint distribution and the other for footprint average, and then by run-time sampling. Higher order theory of cache locality, which shows that traditional metrics can be derived from the footprint and vice versa. (As a result, previous locality metrics can also be obtained in near real time.) Composable model of cache sharing, by footprint composition, which is faster and simpler to use than previous reuse-distance based models. Cache-conscious task regrouping, which reorganizes a parallel workload to minimize the interference in shared cache. Through these techniques, the dissertation establishes the thesis that program interaction in shared cache can be efficiently and accurately modeled and dynamically optimized"--Page vi-vii.