University of Rochester
Computer Science Department

Xiaoya Xiang
PhD. Defense

December 13, 2013
CSB 601
9:00 AM

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 foorpint measurement, first by using two novel algorithms, one for footprint distribution and the other footprint average, and then by runtime sampling.

• A 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.

Pat Mitchell
University of Rochester
Computer Science Department
RC 270226 CSB Room 734
Rochester, NY 14627
585-275-5671
pmitchell@cs.rochester.edu

_______________________________________________
Seminar mailing list
Seminar@cs.rochester.edu
https://mail.cs.rochester.edu/mailman/listinfo/seminar
———————————————–
To join the mailing list of CS seminar series and to be notified of our
upcoming talks, please send an email to *seminar-join@cs.rochester.edu *