循环Cache命中率分析方法的研究与实现

摘要

循环Cache命中率的分析是编译优化中的关键技术之一.CME(Cache Miss Equation)作为描述一个精确描述程序循环中数组引用的Cache冲突情况的数学模型及其相关的理论为较精确地分析循环的Cache命中率奠定了理论基础.该文以CME理论为基础,从数理统计的角度对CME抽样分析作了理论上的说明,采用序贯抽样方法来进行CME的抽样分析,并对抽样检验过程中判断线性约束条件下丢番图方程是否存在整数解这一NP问题,结合一些整数计算的理论,给出了格测试的快速算法.