This project studies how caches affect the performance of algorithms. There are two component problems to study: (i) the problem of how to analyze the cache performance of algorithms, and (ii) the problem of how to design algorithms with good cache performance and good overall performance. In order to analyze cache performance, an algorithm is modeled by its pattern of memory accesses. Models that approximate patterns of memory accesses will be investigated and analyzed to approximate the number of cache misses. The validity of the approximation is determined empirically using trace-driven cache simulation. With a better understanding of the cache performance of algorithms, algorithms that are optimized to improve cache performance, will be designed, implemented and evaluated.
