程序的cache使用效率分析

The Cache Performance Analysis of Algorithms

评价程序的存储效率是提高用户程序性能的重要手段。该文首先提出了程序的装入因子的概念,并据此分析了矩阵乘法;其次,根据时间局部化原则,提出了一种“最小时间差方法”,该方法可以有效地减少cacheline的装入数目;最后,为了评价程序的存储延迟,提出了程序数据相关性的概念,据此给出了计算装入因子的公式,用于分析程序的存储效率。这样就可以用big-O模型来表达程序的时间复杂性,并用装入因子来表达程序的存储访问复杂性。

How to evaluate and improve the program's memo ry access efficiencies is a key question and is discussed widely in the world.In this paper,the concept of loading factor is introduced.Based on this concept ,the matrix multiplication is analyzed,which shows that the loading factor is a suitable parameter to evaluate the program's performance.After that,focusin g on data locality,a method is given,which can reduce the number of cache line s loaded into caches and improve the performances of algorithms.At last,a met hod to calculate the loading factor is introduced.By this way,we can use big-O notation to represent algorithm's time complexity and use the loading fact or to represent algorithm's memory access complexity.