Design and Analysis of Algorithms in the Presence of Caches

这个项目研究缓存如何影响算法的性能。 本文主要研究两个问题：（i）如何分析算法的该高速缓存性能的问题;（ii）如何设计出具有良好缓存性能和良好整体性能的算法的问题。为了分析高速缓存的性能，一个算法被建模的内存访问模式。 将调查和分析近似内存访问模式的模型，以近似缓存未命中的数量。 使用跟踪驱动的高速缓存模拟经验确定的近似的有效性。 随着对算法的该高速缓存性能的更好理解，将设计、实现和评估优化以提高缓存性能的算法。

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.