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.