一种异构内存环境下的缓存替换方法

摘要

本发明公开了一种异构内存环境下的缓存替换方法，其特征在于，包括：在缓存行硬件结构中增加一位来源标志位，用于标记该缓存行数据是来源于DRAM还是PCM；在CPU中新增采样存储单元，用于记录程序访存行为，记录数据重用距离信息；还包括采样方法、等效位置计算方法和替换方法三个子方法，采样子方法用于对访问缓存的行为进行采样统计，等效位置计算子方法用于计算等效位置，替换子方法用于确定需要被替换出去的缓存行。本发明针对异构内存环境下程序的访存特性，对传统缓存替换策略进行了优化，实施本发明能减少因为缓存不命中而需要访问PCM内存的高昂时延代价，从而提升系统整体的访存性能。

主权项

一种异构内存环境下的缓存替换方法，其特征在于，包括如下步骤：(1)设置步骤，包括下述子步骤：(1.1)在缓存行硬件结构中增加一位来源标志位I，用于标记该缓存行数据是来源于DRAM还是PCM：该位为1表示数据来自PCM，为0表示数据来自DRAM；(1.2)在CPU内部新增采样存储单元，其包含DRAM采样区、PCM采样区，其中PCM采样区存储标志位为1的缓存行的标记位组，DRAM采样区存储标志位为0的缓存行的标记位组；其中标记位组指的是64位地址中代表缓存行标记Tag的二进制位组；(1.3)在CPU内部新增采样存储单元，分别建立一张DRAM重用距离统计表DT和一张PCM重用距离统计表PT，大小均为LLC相联度加上1，均包含位置字段及相应的命中次数字段，分别用于记录标记位组在DRAM采样区、PCM采样区的位置和命中对应位置上标记位组的次数；(2)采样并填写重用距离统计表，包括如下子步骤：(2.1)将统计表DT和统计表PT的命中次数字段清零；每0.5至5秒采样一次，每次采样持续时间为T,T等于5‑15毫秒；(2.2)每次采样，读入每次LLC访存信息，计算访问地址中的缓存组号N，对缓存组号N以采样组间隔数L为模，进行取模运算，判别运算结果是否为0，是则表明该访存行为需要采样，转(2.3)；否则转子步骤(2.4)；其中采样组间隔数L指的是需要采样的相邻缓存组之间的组号差，取值为128，对组号为0、128、256…的缓存组进行采样；(2.3)判别该次访问LLC是否命中，是则转(2.5)；否则转(2.7)；(2.4)判别采样时间是否大于T，是则转步骤(3)；否则转(2.2)等待下一次LLC访存；(2.5)将N/L的商作为需要访问的DRAM采样区或PCM采样区的组号，进行子步骤(2.6)；(2.6)判别标志位I是否为0，是则按LRU算法将该命中的缓存行标记位组插入DRAM采样区，更新统计表DT；否则按LRU算法将命中的缓存行标记位组插入PCM采样区，更新统计表PT；更新时，若命中某标记位组，则将对应的次数字段加1，若不命中，则将相联度+1下标对应的次数字段加1；更新完成后，判别采样时间是否大于T，是则当次采样结束，转步骤(3)；否则转步骤(2.2)；(2.7)判定收到的数据块是否来自DRAM，是则将标志位I赋值为0，否则将标志位I赋值为1，转步骤(2.6)；(3)计算等效位置，其子步骤如下：(3.1)分别计算P_d(X)、P_p(X)、λ_d和λ_p；其中，P_d(X)、P_p(X)分别为DRAM重用距离概率分布和PCM重用距离概率分布，分别通过统计表DT和统计表PT每一个位置对应的命中次数字段除以命中次数字段总和求得；重用距离统计表的位置字段即代表重用距离；λ_d和λ_p分别为访问DRAM缓存行次数占采样总次数的百分比和访问PCM缓存行次数占采样总次数的百分比；(3.2)记LLC的相联度为assoc，缓存组中缓存行的位置下标为n，n＝1代表MRU位置，n＝assoc代表LRU位置，当n分别取{1,2,3，…,assoc‑1}中的值时，根据P_d(X)、P_p(X)、λ_d、λ_p以及选定的n计算平均访存时间AMAT：AMAT＝λ_d×(T_h+T_d×(1‑H_d))+λ_p×(T_h+T_p×(1‑H_p))，式中，T_h、T_d、T_p分别为缓存的命中时延，DRAM的访问时延和PCM的访问时延，三个参数可查询硬件的技术手册获得；H_d和H_p分别为DRAM缓存行和PCM缓存行的命中率：$H_d=\underset{i=1}{\overset{\mathrm{assoc}}{\Sigma }}(\underset{j=i}{\overset{\mathrm{assoc}}{\Sigma }}{\alpha }_{j,i}\times P_a(X=i)),$$H_p=\underset{i=1}{\overset{\mathrm{assoc}}{\Sigma }}(\underset{j=i}{\overset{\mathrm{assoc}}{\Sigma }}{\beta }_{j,i}\times P_p(X=i)),$式中，α_j,i为缓存组第j个位置上恰好为该组中第i个DRAM缓存行的概率，β_j,i为缓存组第j个位置上恰好为该组中第i个PCM缓存行的概率；若i＝j＝1，则α_j,i＝λ_d，β_j,i＝λ_p；若j<i或i<1,则α_j,i＝0，β_j,i＝0；若j≤n+1,则${\alpha }_{j,i}=\frac{{\alpha }_{j-1,i}\times {\lambda }_p\times {\Sigma }_{k-j-i}^{\mathrm{assoc}+1}{P}_p(X=k)+{\alpha }_{j-1,i-1}\times {\lambda }_d\times {\Sigma }_{k=i}^{\mathrm{assoc}+1}{P}_d(X=k)}{1-{\lambda }_d\times {\Sigma }_{k=1}^{i-1}{P}_d(X=k)-{\lambda }_p\times {\Sigma }_{k=1}^{j-i}{P}_p(X=k)},$${\beta }_{j,i}=\frac{{\beta }_{j-1,i}\times {\lambda }_d\times {\Sigma }_{k-j-i}^{\mathrm{assoc}+1}{P}_d(X=k)+{\beta }_{j-1,i-1}\times {\lambda }_p\times {\Sigma }_{k=i}^{\mathrm{assoc}+1}{P}_p(X=k)}{1-{\lambda }_p\times {\Sigma }_{k=1}^{i-1}{P}_p(X=k)-{\lambda }_d\times {\Sigma }_{k=1}^{j-i}{P}_d(X=k)},$若j>n+1,则α_j,i＝0，β_j,i＝β_{n+1,i‑j+n+1}；(3.3)找出assoc‑1个平均访存时间中的最小值，其对应的缓存行下标n所指的位置就是所求等效位置；(4)缓存替换，包括以下子步骤：(4.1)在缓存中查找所要访问的数据，若命中，则转子步骤(4.2)；若未命中，转子步骤(4.3)；(4.2)将命中缓存行在缓存组中由当前位置移至MRU位置，转子步骤(4.7)；(4.3)判别等效位置是否已初始化，是则转子步骤(4.4)；否则清除LRU缓存行，转子步骤(4.6)；(4.4)判别缓存组LRU缓存行的来源标志位是否为0，是则清除该缓存行，转子步骤(4.6)；否则转子步骤(4.5)；(4.5)由次LRU位置向MRU位置方向依次检查每一个缓存行，判别是否在抵达等效位置之前发现来源标志位为0的缓存行，是则清除该缓存行并停止检查，转子步骤(4.6)；否则清除LRU缓存行，转子步骤(4.6)；(4.6)新数据插入MRU位置，转子步骤(4.7)；(4.7)结束。