程序的cache使用效率分析  

The Cache Performance Analysis of Algorithms

作　　者：刘方爱[1] 

机构地区：[1]山东师范大学信息管理学院计算机系,济南250014

出　　处：《计算机工程与应用》2004年第5期19-21,共3页Computer Engineering and Applications

基　　金：山东省自然科学基金(编号:Y2002G03)

摘　　要：评价程序的存储效率是提高用户程序性能的重要手段。该文首先提出了程序的装入因子的概念,并据此分析了矩阵乘法;其次,根据时间局部化原则,提出了一种“最小时间差方法”,该方法可以有效地减少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.

关 键 词：CACHE 存储延迟 性能评价 装入因子 存储复杂性 

分 类 号：TP31[自动化与计算机技术—计算机软件与理论]