一种面向低功耗的多核共享Cache混合划分方法

摘要

本发明涉及一种面向低功耗的多核共享Cache混合划分方法，属于计算机体系结构领域。随着片上集成的核心数目的增加，低功耗设计成为必然趋势，然而目前的Cache划分方法大都是面向吞吐量或者公平性的，忽视了功耗问题。本发明提供了一种新的面向低功耗的划分方法。划分方法利用程序的局部性原理，将在二级Cache中访问差异度较大的线程合并为一个划分单位来实现Cache列划分，从而在运行同一个应用时，使用较少的Cache列，关闭剩余的Cache列，在满足性能的基础上达到降低功耗的目的。

主权项

1.一种面向低功耗的多核共享Cache混合划分方法，其特征在于包含以下步骤：(1)初始化：1.1)将每个线程作为一个单独的划分单位，给每个划分单位划分一列二级Cache；1.2)一个时间片t后，判断程序是否运行结束，结束则跳转到步骤(4)，否则继续执行步骤1.3)；时间片t是指将应用程序的运行时间均匀分块，每块时间称为一个时间片t；1.3)根据公式①计算系统性能IPC_[par]，IPC是每个时钟执行的指令数(Instruction Per Cycle)；${\mathrm{IPC}}_{\left[\mathrm{par}\right]}=\underset{i=1}{\overset{n}{\Sigma }}{\mathrm{IPC}}_{\left[{\mathrm{app}}_i\right]}=\underset{i=1}{\overset{n}{\Sigma }}\frac{1}{\alpha +\beta \times {\theta }_i\left(x\right)}$①其中，n表示应用程序所包含的线程总数，表示线程i(1≤i≤n)的每个时钟执行的指令数，用来表征线程i的性能，根据下式②计算得到：${\mathrm{IPC}}_{\left[{\mathrm{app}}_i\right]}=\frac{1}{\alpha +\beta \times {\theta }_i\left(x\right)}$②②式中的α和β计算公式如下式③，θ_i(x)是根据栈距离特性获取的线程i的失效率，表示当为线程i分配x大小的二级Cache时，线程i在时间片t内的缺失次数；α＝CPI_[base]+E₁+M₁×E₂，β＝E₃            ③③式中的CPI_[base]为平均每条指令的执行周期数，E₁为访问一级Cache的命中开销，M₁为一级Cache的缺失次数，E₂为一级Cache缺失时访问二级Cache的命中开销，E₃为二级Cache缺失时访问主存的命中开销；M₁、E₁、E₂、E₃和CPI_[base]的值由所使用的计算机体系结构决定；1.4)若此时系统性能IPC_[par]≥(1-PLT)IPC_[initial]，则关闭剩余的Cache列，执行步骤(3)；否则执行步骤(2)；其中，回溯阈值IPC_[initial]表示Cache进行单纯列划分时的系统性能，PLT表示性能损失阈值；(2)划分阶段：令所有未合并的线程T组成线程集TS，TS＝{T_i|1≤i≤n}2.1)若|TS|≥2，执行步骤2.2)，否则跳转到步骤2.5)；2.2)根据公式④计算TS中任意两个线程访问Cache列的差异度R_diff；R_diff＝|P_i-P_j|，(1≤i≤n，1≤j≤n且i≠j)        ④其中P是线程访问偏度，由式⑤计算得到，$P=\frac{U_{\mathrm{up}}-U_{\mathrm{down}}}{U_{\mathrm{used}}}$⑤将Cache的每一列均分为上下两部分，U_up表示在线程所分得的一列Cache中，上半部分访问过的Cache块数，U_down表示在线程所分得的一列Cache中，下半部分访问过的Cache块数，U_used表示这一列中访问过的Cache块总数；2.3)对于所有差异度R_diff满足R_diff≥R_share的线程对，将R_diff取得最大值的两个线程<T_i，T_j>合并为一个划分单位，TS＝TS-{T_i，T_j}；其中，R_share表示差异度阈值；2.4)若|TS|≥2，则执行步骤2.3)，否则执行步骤2.5)；2.5)判断是否有未划分的Cache列，是则执行2.6)，否则执行步骤(3)；2.6)计算所有划分单位的IPC增加量Plus_IPC_k(x)值，Plus_IPC_k(x)是指当划分单位k(1≤k≤n)分配的Cache列从x(x∈[0，C_L2))列增加到x+1列时，划分单位k的IPC增加量，其中C_L2为二级Cache的总列数；Plus_IPC_k(x)的计算公式如下式⑥：⑥其中，函数的计算公式如上式②；2.7)划分一列Cache给取的最大Plus_IPC_k(x)的划分单位；2.8)根据式①计算系统划分性能IPC_[par]；2.9)如果此时IPC_[par]≥(1-PLT)IPC_[initial]，则划分阶段结束，关闭剩余的Cache列，转到步骤(3)；否则执行2.5)；(3)回溯阶段：程序运行一个时间片t后，3.1)程序是否运行结束，是则转到步骤(4)，否则执行步骤3.2)；3.2)根据式①计算系统划分性能IPC_[par]；3.3)如果此时IPC_[par]≥(1-PLT)IPC_[initial]，转到步骤(3)，否则，恢复初始划分，执行(2)；(4)输出运行结果，用功耗评估工具评估系统所节省的功耗。