Thesis (Ph. D.)--University of Rochester. Dept. of Computer Science, 2014.
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 sin-
gle 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.
