摘要
循环Cache命中率的分析是编译优化中的关键技术之一。CME(CacheMissEquation)作为描述一个精确描述程序循环中数组引用的Cache冲突情况的数学模型及其相关的理论为较精确地分析循环的Cache命中率奠定了理论基础。该文以CME理论为基础,从数理统计的角度对CME抽样分析作了理论上的说明,采用序贯抽样方法来进行CME的抽样分析,并对抽样检验过程中判断线性约束条件下丢番图方程是否存在整数解这一NP问题,结合一些整数计算的理论,给出了格测试的快速算法。
Loop cache hit rate analysis is one of the key technology of compile optimization.CME(Cache Miss Equation),as a math framework precisely describing the cache conflict of array reference data access in a loop,together with its theory,has made a foundation for us to precisely analyze the cache hit rate of loop.Based on the CME theory,This paper uses the theory of mathematic statistic to explain the rationality of CME sampling analysis,brings forward sequential sampling method to do the CME sampling analysis.Facing the NP problem of testing whether a diophantine equation in linear limited conditions in the process of sampling test,this paper gives a quick algorithm:Lattice Test.
出处
《计算机工程与应用》
CSCD
北大核心
2002年第1期78-81,84,共5页
Computer Engineering and Applications
基金
国家自然科学基金(编号:100720077)
关键词
Cache命中率分析
CME
序贯抽样
格测试
Cache hit rate analysis,Cache Miss Equation(CME),sequential sampling,Lattice Test
