实验 1 Cache 替换策略设计与分析

实验目的

  • 深入理解各种不同的 Cache 替换策略
  • 理解学习不同替换策略对程序运行性能的影响
  • 动手实现自己的 Cache 替换策略

实验要求

  • 理解学习 LRU 及其它已经提出的 Cache 替换策略
  • 在提供的模拟器上实现自己设计的 Cache 替换策略
  • 通过 benchmark 测试比较不同的 Cache 替换策略
  • 在实验报告中简要说明不同 Cache 替换策略的核心思想和算法
  • 在实验报告中说明自己是怎样对不同的 Cache 替换策略进行测试的
  • 在实验报告中分析不同替换策略下,程序的运行时间、Cache 命中率受到的影响

已有替换策略分析

常见的Cache替换策略有LRU,FIFO, LFU等,本次实验基于MK Qureshi于2007年的Adaptive insertion policies for high performance caching一文提出的LRU Insertion Policy算法进行的实现。

在该文中,作者指出,当程序重用工作集大于可用Cache时或者其存储访问具有低局部相关性时,Cache替换策略中最常用的LRU策略表现出十分低下的命中率。大量新替换入Cache的行对命中率的贡献为零,而原本可能命中的行则由于长期不被访问而替换出Cache。针对这种情况,该文提出了以下一些改进策略:

  • LRU Insertion Policy (LIP) 。该策略将所有替换入Cache的行置于LRU端。相对于传统策略将所有替换入的行置于MRU端,LIP使一部分行得以驻留于Cache中,其驻留时间能比Cache本身容量更长。LIP策略能够很好地应对Thrashing,尤其对于循环访问内存的程序其性能近似于OPT策略。
  • Bimodal Insertion Policy (BIP)。BIP策略是对LIP的加强和改进,新换入的行会小概率地被置于MRU端。BIP可以很好地响应Working Set的切换,并保持一定的命中率。
  • Dynamic Insertion Policy (DIP) 能动态地在LRU和BIP间切换,选择其中命中率较高的策略执行后续指令。DIP对于LRU-friendly的程序块使用LRU策略,对于LRU-averse的程序块使用DIP策略,以求通用效率。对于1MB16路L2 Cache,DIP策略较LRU降低21%的失配率。

LIP和BIP两种策略对于LRU-friendly(高局部性)的程序,性能均不佳。

我实现的替换策略

考虑到实现难度,本次实验我实现了MK Qureshi提出的三个算法中的第一个LIP算法,具体的实现为:

  • 当访存命中时,将命中的Cache块放到对应栈的LRU端,其他块依次移位
  • 当Cache缺失时,替换策略与LRU一致,这时需要将新换入的Cache块放到对应栈的MRU端

在实际的实验过程中发现,LIP算法并没有很明显的改进LRU算法,约有$\frac{1}{3}$的测试样例中LIP算法表现更好,$1/2$的测试样例中LRU算法表现更好,由此,我采用了一个稍大概率值使得其一部分情况下采用LRU算法,一部分情况下采用LIP算法,考虑到LRU算法在大多数情况下表现较好,这里的概率值设置得稍大一些,置为了30%,即对于新换入的Cache块,有30%的概率会被放置在LRU端,有70%的概率会被置于MRU端

具体实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
// 这个函数是根据实现的Cache替换策略函数                                         
INT32 CACHE_REPLACEMENT_STATE::Get_LIP_Victim( UINT32 setIndex ){
// Get pointer to replacement state of current set
LINE_REPLACEMENT_STATE *replSet = repl[ setIndex ];

INT32 lipWay = 0;

// Search for victim whose stack position is assoc-1
// 被替换的块策略与LRU一致,选择栈底被替换出去
for(UINT32 way=0; way<assoc; way++)
{
if( replSet[way].LRUstackposition == (assoc-1) )
{
lipWay = way;
break;
}
}

// return lru way
return lipWay;
}


// This function implements the LIP update routine for the traditional //
// LIP replacement policy. The arguments to the function are the physical //
// way and set index.
void CACHE_REPLACEMENT_STATE::UpdateLIP( UINT32 setIndex, INT32 updateWayID, bool cacheHit )
{
// Determine current LRU stack position
UINT32 currLRUstackposition = repl[ setIndex ][ updateWayID ].LRUstackposition;

// 如果hit
// Update the stack position of all lines before the current line
// Update implies incremeting their stack positions by one
if (cacheHit) {
for(UINT32 way=0; way<assoc; way++)
{
if( repl[setIndex][way].LRUstackposition < currLRUstackposition )
{
repl[setIndex][way].LRUstackposition++;
}
}
// Set the LRU stack position of new line to be zero
repl[ setIndex ][ updateWayID ].LRUstackposition = 0;
}
else {
// Cache缺失时, 把新换入的Cache的行置于LRU端
repl[ setIndex ][ updateWayID ].LRUstackposition = assoc - 1;
}
}

void CACHE_REPLACEMENT_STATE::UpdateBIP( UINT32 setIndex, INT32 updateWayID, bool cacheHit )
{
// Determine current LRU stack position
UINT32 currLRUstackposition = repl[ setIndex ][ updateWayID ].LRUstackposition;

// 如果hit
// Update the stack position of all lines before the current line
// Update implies incremeting their stack positions by one
if (cacheHit || (rand()%100 < probability)) {
for(UINT32 way=0; way<assoc; way++)
{
if( repl[setIndex][way].LRUstackposition < currLRUstackposition )
{
repl[setIndex][way].LRUstackposition++;
}
}
// Set the LRU stack position of new line to be zero
repl[ setIndex ][ updateWayID ].LRUstackposition = 0;
}
else {
// Cache缺失时, 把新换入的Cache的行置于LRU端
repl[ setIndex ][ updateWayID ].LRUstackposition = assoc - 1;
}
}

替换策略测试

测试方法

本次实验中将29个测试程序分别采用LRU,LIP算法进行了测试,测试时的Cache设置为 UL3:1024:64:16

  • 实验在第3级Cache上进行,统一存储指令和数据,
  • Cache 大小为 1024KB
  • Cache 行大小为 64B
  • 16路组相连

在测试时我利用shell脚本自带的time命令输出其运行时间(取real time结果)以此代表程序运行时间,此外,我还采用了CPI,缺失率作为其评价指标

分析不同替换策略下,程序的运行时间、Cache 命中率受到的影响

LRU和LIP算法比较

程序LRU_timeLIP_timeless_timeLRU_CPILIP_CPILess_cpiLRU_missLIP_missless miss
perlbench17.07016.420LIP0.6428230.669326LRU40.795244.9668LRU
bzip2123.840120.870LIP0.5546420.571873LRU61.736955.3261LIP
gcc134.380130.780LIP0.6148640.575939LIP42.752138.5965LIP
bwaves118.230117.520LIP0.2530880.253088=99.663499.6634=
gamess133.080135.110LRU0.300220.312251LRU26.320492.0923LRU
mcf163.610153.580LIP2.553582.04087LIP75.67659.7033LIP
milc148.670144.780LIP1.149391.1807LRU77.016479.3471LRU
zeusmp148.800133.400LIP0.4516330.452046LRU80.8182.492LRU
gromacs143.230153.090LRU0.6077690.664129LRU71.197989.1534LRU
cactusADM133.370130.880LIP0.442490.378492LIP76.116463.7024LIP
leslie3d133.210133.850LRU1.506261.4344LIP84.028479.7774LIP
namd112.000111.370LIP0.2737950.273797LRU66.260366.2661LRU
gobmk127.020127.540LRU0.3838760.388093LRU14.91915.5215LRU
dealII130.630131.960LRU0.4639160.446134LIP45.089247.2678LRU
soplex72.31075.080LRU0.3569090.431378LRU15.201135.9993LRU
povray134.860134.040LIP0.3604310.360387LIP39.925839.7901LIP
calculix130.460127.370LIP0.3213460.359601LRU34.0553.1214LRU
hmmer133.820135.260LRU0.2585130.258513=71.473671.4868LRU
sjeng129.020134.210LRU0.3230060.322841LIP93.541593.3249LIP
GemsFDTD153.820171.260LRU0.3681430.368143=84.152584.1525=
libquantum147.090132.630LIP0.2727490.272749=100.0100.0=
h264ref137.550129.450LIP0.287870.292871LRU70.008672.4714LRU
tonto122.590122.090LIP0.3478560.34803LRU78.869479.2837LRU
lbm175.980175.560LIP1.153791.15439LRU99.972599.7331LIP
omnetpp156.400150.580LIP0.412780.412729LIP59.444359.2859LIP
astar161.890152.050LIP0.2676470.267647=5.847185.84718=
sphinx3148.620145.960LIP0.4456440.445645LRU97.15697.1648LRU
xalancbmk163.490155.190LIP0.4149930.411322LIP66.275963.1589LIP
specrand90.18089.100LIP0.3362110.336348LRU95.937397.6647LRU

LRU和BIP算法比较

程序LRU_timeBIP_timeless_timeLRU_CPIBIP_CPILess_cpiLRU_missBIP_missless miss
perlbench17.07017.490LRU0.6428230.653642LRU40.795242.4235LRU
bzip2123.840144.210LRU0.5546420.570891LRU61.736959.0281BIP
gcc134.380167.270LRU0.6148640.575685BIP42.752137.0908BIP
bwaves118.230152.430LRU0.2530880.253088=99.663499.6634=
gamess133.080159.270LRU0.300220.304011LRU26.320430.4442LRU
mcf163.610182.510LRU2.553582.27179BIP75.67667.9679BIP
milc148.670137.590BIP1.149391.14853BIP77.016476.2688BIP
zeusmp148.800127.220BIP0.4516330.451496BIP80.8181.883LRU
gromacs143.230148.100LRU0.6077690.625808LRU71.197974.1585LRU
cactusADM133.370141.210LRU0.442490.368551BIP76.116462.9769BIP
leslie3d133.210147.700LRU1.506261.44446BIP84.028473.9532BIP
namd112.000122.800LRU0.2737950.273801LRU66.260366.2719LRU
gobmk127.020144.260LRU0.3838760.384353LRU14.91914.2733BIP
dealII130.630143.810LRU0.4639160.42624BIP45.089235.1431BIP
soplex72.31079.220LRU0.3569090.366633LRU15.201117.9177LRU
povray134.860165.980LRU0.3604310.360417BIP39.925839.858BIP
calculix130.460145.710LRU0.3213460.332007LRU34.0539.1968LRU
hmmer133.820157.060LRU0.2585130.258513=71.473671.4868LRU
sjeng129.020166.850LRU0.3230060.322882BIP93.541593.359BIP
GemsFDTD153.820169.420LRU0.3681430.368143=84.152584.1525=
libquantum147.090138.730BIP0.2727490.272749=100.0100.0=
h264ref137.550138.360LRU0.287870.289044LRU70.008670.8777LRU
tonto122.590143.870LRU0.3478560.347883LRU78.869478.898LRU
lbm175.980149.190BIP1.153791.15361BIP99.972599.9688BIP
omnetpp156.400161.910LRU0.412780.412755BIP59.444359.3624BIP
astar161.890156.370BIP0.2676470.267647=5.847185.84718=
sphinx3148.620136.150BIP0.4456440.44566LRU97.15697.2443LRU
xalancbmk163.490142.850BIP0.4149930.421033LRU66.275967.5348LRU
specrand90.18085.870BIP0.3362110.336235LRU95.937396.1932LRU

算法表现统计

LRU与LIP算法

  • CPI值: LRU算法15次更小, LIP算法9次更小

  • 运行时间:LRU算法9次更小, LIP算法20次更小

  • 缺失率: LRU算法15次更小, LIP算法10次更小

LRU与BIP算法

  • CPI值: LRU算法13次更小, BIP算法11次更小

  • 运行时间:LRU算法21次更小, BIP算法8次更小

  • 缺失率: LRU算法13次更小, BIP算法12次更小

结果分析

由统计结果分析,大概一半的测试程序中,LRU的算法的缺失率和CPI指标比LIP算法更优,但是仍然有不少测试样例显示LIP算法表现更好,而这些程序即是前文所说的局部相关性不是特别高的情况,而LIP算法的运行时间明显更优。

新加入的第三种策略(类似于BIP算法)在缺失率上的表现较LIP稍好一些(运行时间偏慢应该是因为在其中做了取随机数和取模的运算操作),其表现与LRU表现不分上下,可以看做是LRU算法和LIP算法的一个综合,可以看出不同的算法对程序局部性的适应度是有区别的,而测试程序的局部性好坏也极大地影响着其缺失率,在实际的操作中综合LIP和LRU算法应该是比较好的。根据测试结果推测,当概率值设置为50%时BIP算法表现可能会优于LRU算法

由此可以分析,通常来说,程序的局部性更强时LRU算法表现会比较好,当程序的局部性表现有较大波动时,LIP一类改进算法会表现更好(即缺失率会降低),实际上,DIP算法的动态调节表现应该是最好的,不过出于实现难度本次实验没有进行实现。

附件:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
## 算法文件
replacement_state.cpp
replacement_state.h

## 实验数据
results/
├── get_time.py // 通过运行数据提取运行结果表格记录
├── time_bip.txt // 算法3的运行时间结果
├── log_all.txt // 分别使用LRU算法和LIP算法运行29个测试程序的输出结果
├── bip_log.txt // 算法3的运行记录
├── name.txt
├── run.sh // 运行脚本,在CRC/项目根目录下运行即可
├── runs // 解压后的测试结果
│   ├── LIP_GemsFDTD.stats
│   ├── LIP_astar.stats
│   ├── LIP_bwaves.stats
│   ├── LIP_bzip2.stats
| ......
|
└── time_log.txt // 每个程序的运行时间记录
----

参考文献

[1] Moinuddin K. Qureshi , Aamer Jaleel , Yale N. Patt , Simon C. Steely , Joel Emer, Adaptive insertion policies for high performance caching, Proceedings of the 34th annual international symposium on Computer architecture(ISCA), June 09-13, 2007, San Diego, California, USA

打赏