一种改进的多核共享cache替换方法

摘要

本发明涉及一种改进的多核共享cache替换方法，主要分成三个阶段：初始化，替换策略，回溯。初始化是指平均划分cache列，保证每个核拥有属于自己的cache列；替换策略又细分为选择逐出单元，插入访问单元，提升优先级。其中选择逐出单元表示根据一定的原则，尽可能选择效益最小的单元替换出去；插入访问单元是将从内存取出的cache单元放置到cache组的合适位置；优先级提升，则是当cache单元命中时，提高cache单元的优先级，以利于下次利用局部性原理访问。本发明在cache划分的基础上，尽可能将部分当前使用的工作集保留在cache内，从而提高cache的命中率。

主权项

一种改进的多核共享cache替换方法，其特征在于包含以下步骤：1)、初始化：1.1)初始化cache列划分信息表和路窃取信息表，以核为单位将cache列平均划分，保证每个核拥有自己的cache列，列划分信息表为矩阵I_A×B，A表示核的个数，B表示能访问的所有cache列的个数，其中I_ij为矩阵I_A×B中第i行第j列的元素，I_ij表示cache的第j列是否属于第i个核core_i；路窃取信息表为矩阵L_A×A，A表示核的个数,L_ij为矩阵L_A×A中第i行第j列的元素,L_ij包含两类信息，其一为核core_i是否窃取了核core_j对应的cache的存储单元，其二为被窃取的核core_j的存储单元对应的组号集合；1.2)当处理器核core_i发出一个L2Cache的访问请求时，根据所要访问的地址确定地址所映射的Cache组q，根据cache组q和core_i的列划分信息表确定属于core_i的cache存储单元集合，并在存储单元集合中判断是否命中，1.2.1)如果命中，存取cache存储单元，命中单元即为请求所要访问的单元，继续执行步骤3；1.2.2)如果未命中，判断核core_i是否窃取了其他核的cache列；1.2.2.1)如果核core_i窃取了核core_m的列，根据路窃取信息表确定被窃取的核core_m的存储单元对应的组号集合Q；并判断q是否属于Q；1.2.2.1.1)如果q属于Q，则搜索组q中核core_m对应的存储单元；判断是否命中；1.2.2.1.1.1)如果命中，存取cache存储单元，继续执行步骤4；1.2.2.1.1.2)如果未命中，顺序执行步骤2；1.2.2.1.2)如果q不属于Q，顺序执行步骤2；1.2.2.2)如果核core_i并未窃取其他核的列，顺序执行步骤2；2)、cache替换算法:(2.1)根据Cache组q对应的候选路信息M_q，核core_i的列划分信息，以及核core_i对应的cache路窃取信息选择逐出单元，所述的候选路M_q表示Cache组q中按访问频率升序排列中的前M个存储单元对应的Cache列号，选择逐出单元的步骤如下：2.1.1)如果候选路信息M_q对应的存储单元存在属于core_i的存储单元C_i，则C_i为逐出单元,继续执行步骤(2.2)；否则顺序执行步骤2.1.2)；2.1.2)根据路窃取信息表，判断core_k是否窃取了核core_i的存储单元；2.1.2.1)如果存在core_k窃取了核core_i的存储单元,判断窃取的是否是组q中的cache存储单元；2.1.2.1.1)如果是，将组q中所对应的存储单元选为逐出单元,更新路窃取信息表，继续执行步骤(2.2)，2.1.2.1.2)如果不是，顺序执行步骤2.1.3)2.1.2.2)如果core_k没有窃取核core_i的存储单元，顺序执行步骤2.1.3)；2.1.3)选择候选路信息M_q中访问频率最低的存储单元作为逐出单元，更新路窃取信息表，顺序执行步骤(2.2)；(2.2)将要存取的数据块插入到cache组q中优先级为M的存储单元f中，更新存储单元f的访问频率信息，继续执行步骤4，其中用访问频率信息排列优先级；3)、提升优先级：当cache存储单元命中时，更新命中的cache存储单元的优先级，更新步骤如下：如果命中的存储单元属于候选路M_q，则将命中的存储单元的优先级提升为最近访问的列的优先级，继续下一步；如果命中的存储单元不属于候选路M_q，则将命中的cache存储单元的优先级提升一级继续下一步；4)、回溯阶段，程序运行时间t后，如果程序结束继续执行步骤5，否则，清除所有cache存储单元访问频率信息和路窃取信息表,并返回步骤1.2)；5)、输出运行结果，分析缺失率，功耗，以及整体IPC。