Harnessing Hardware Prefetching in Dynamic Programming

by
Jeremy Cho

Abstract:

In recent years, significant progress has been made in developing cache-efficient algorithms for several classic problems in computer science. While such algorithms have provably good bounds on the number of cache misses incurred, they can be difficult to implement in practice, due to their complexity. Hardware prefetching is a relatively new technology which analyzes memory access patterns and attempts to cache data before it is needed. Using this technology, we develop a series of refinements to a particular class of dynamic programming algorithms which exhibit a property known as monotonicity. These refinements are straightforward to implement and are experimentally shown to exhibit good cache performance due to the impact of the prefetcher.

Advised by Richard Ladner

CSE 203
Wednesday
April 30, 2008
3:30 - 4:20 pm