何哲 2019011313 计95
查看 Cache 参数
实验环境为Intel(R) Core(TM) i7-8565U CPU @ 1.80GHz 2.00 GHz，基于wsl2。从以上图片可以看到参数为：CPU0，1共用L1和L2 cache，其中L1D cache 大小为32KB，8路组相联；L2 cache 大小为256KB，4路组相联。
测量 Cache Size
测试结果
测试代码
for (register int j = 0; j < total_test_size * step_size / num; j++) {
for (register int k = 0; k < num; k += step_size) {
a[k] = 1;
}
}访存序列
8KB 到 131072KB 大小的数组，步长为16 * int（64B）。
测试思路
num为数组的大小，step_size取了16（访问步长）。通过不断顺序以一定步长遍历数组来测试cache大小，保证总体访问次数固定。当num比L1D和L2大的时候，分别会有一个时间上的激增。
结果分析
- 由结果来看，在test_size取32KB和256KB的时候时间分别有明显增大，说明此时出现了cache缺失，需要从下一级cache或内存中获取数据，从而时间显著增加。
- 于是可以知道，L1D为32KB，而L2 cache为256KB。和机器参数一致。
一个有趣的现象
当我在访问的数组下标中增加一些计算时，整体时间会发生很大变化，使得测试结果不明显。例如使用随机下标，代码如下：
for (register int j = 0; j < total_test_size * step_size / num; j++) {
for (register int k = 0; k < num; k += step_size) {
register int r = rand() % num;
a[r] = 1;
}
}对应测试结果为：
甚至只是增加了一些很简单的运算，都会带来结果上的变化，例如：
for (register int j = 0; j < total_test_size * step_size / num; j++) {
for (register int k = 0; k < num; k += step_size) {
a[k % num] = 1;
}
}这里由于k总是小于num，所以 % num 的操作无意义，只是增加了一些计算量。（我查看了对应的汇编代码，可以确认只增加了几句取模的操作）
结果却变得不再显著（在数组大小较小的时候时间增加了很多，在数组大小较大的时候时间变化不大，在32KB和256KB的时候不再有时间上的增加）：
对此，我的猜想为：当增加了取模或者取随机数这样的操作之后，整体耗时最多的部分从访存（store）变成了取模 / 取随机数，这就给cpu优化带来了空间，可能会导致计算与访存重叠，从而无法体现出单纯的访存时间的变化。而当数组过大时，需要写入到内存中而不是缓存中，访存时间显著增加，所以又能体现出访存时间的变化。
测量 L1D Cache Line Size
测试结果
测试代码
for (register int i = 0; i < total_size * test_size / num; i++) {
for (register int j = 0; j < num; j += test_size) {
a[j] = 0;
}
}访存序列
大小为1M的数组，步长为 4B 到 64B （即1 * int到16 * int）
结果分析
- 可以看到在block size增大到64B的时候，时间产生了一个激增。这意味着之前的步长可以访问到一个cache line里面的内容，从而减少了访问时间；而当block size到64B之后，每次访问都是从一个新的cache line开始，所以命中率显著降低，测试时间显著增加。
- 于是可以知道，这台测试机器的L1D Cache Line Size为64B。
测量 L1D Cache 的相联度
测试结果
测试代码
register int each_group_size = num / num_of_groups;
for (register int times = 0; times < 100000; times++) {
register int gap_size = 2 * each_group_size;
for (register int i = 0; i < num; i += gap_size) {
for (register int j = 0; j < each_group_size; j += 16) {
a[i + j] = 0;
}
}
}访存序列
大小为64KB（两倍于L1D cache）的数组。将数组分为块，顺序访问其中的奇数块；步长为64B，即cache line的大小。重复100000次。
算法分析与证明
设largest_index = cache_size / ways，即为每路的大小，假设它的单位为int，即4B。那么数组中，下标mod largest_index余数相同的那些项均会对应到不同路的同一个index。
将大小为2 * cache_size的数组分成份时，奇数块首元素之间的间隔为gap_size = 2 * cache_size / * 2 = cache_size / 。
当ways大于时，ways被整除，于是所有奇数块首元素的下标mod largest_index余数相同，所以它们对应到不同路的同一个index。此时的一块奇数块的大小会大于largest_index，所以整体数组恰能充满整个cache，不会发生冲突替换。
当ways恰等于的时候，每一个奇数块的对应相同位置的元素会被放在cache里不同路的同一个index，也就会产生冲突，一共有个奇数块，所以会发生次冲突替换。
而当n更大，也就是ways小于的时候，块分得更细，在总体长度小于largest_index的块的合集里面，不会产生冲突。所以会产生冲突的只有上一步（ways恰等于）说的那个奇数块之间。而这些奇数块在这之后被细分，这些奇数块内部的访问次数不变，只是访问位置发生变化。所以总体还是只发生了次冲突替换。
于是只有当ways恰等于的时候会看到访问时间突然变慢。
结果分析
可以看到在test number of groups为32的时候时间突然变大，说明本机器L1D Cache的相联度为8，与参数相符。
矩阵乘优化
测试结果
加速比维持在2.7以上。
优化代码
for (i = 0; i < MATRIX_SIZE; i ++)
for (j = 0; j < MATRIX_SIZE; j ++) {
int t = a[i][j];
for (k = 0; k < MATRIX_SIZE; k ++)
d[i][k] += t * b[j][k];
}优化思路
转换矩阵相乘的顺序，取消竖直访问的过程，改成固定一个元素和另一行相乘。
选做部分
测出 L1D Cache 的替换策略
测试结果
测试代码
register int num = 96 << 8; // 96 KB = ( 96 << 8 ) * int = 3 * cache size
// first
for (register int times = 0; times < 100000; times++) {
for (register int t = 0; t < 64; t++) {
for (register int i = 0; i < 8; i++) {
for (register int j = 8 - i; j > 0; j--) {
a[i * block_size + t] = 0;
}
}
a[9 * block_size + t] = 0;
}
}
// clean cache
for (int i = num / 3 * 2; i < num; i++) {
a[i] = 0;
}
// second
for (register int times = 0; times < 100000; times++) {
for (register int t = 0; t < 64; t++) {
for (register int i = 7; i >= 0; i--) {
for (register int j = 8 - i; j > 0; j--) {
a[i * block_size + t] = 0;
}
}
a[9 * block_size + t] = 0;
}
}实现思路
做两组对比实验。由于之前测出本机器的组相联路数为8，所以实验顺序访问9个block，命名为block 1-9。（以下用[block i] * j表示block i 被连续访问了j次）
两遍实验的访问顺序分别为：
- 第一遍：[block 1] * 8，[block 2] * 7，...，[block 8] * 1，[block 9] * 1
- 第二遍：[block 8] * 1，[block 7] * 1，...，[block 1] * 7，[block 9] * 1，[block 7] * 1，[block 6] * 1，...，[block 1] * 1
两遍实验各自循环1000000次。
在第一遍中，如果机器采用LRU替换策略，则当block 9进入的时候会将block 1替换出去。之后再访问block 1的时候会将block 2替换出去，依次类推，每次访问L1D都会缺失；如果机器采用LFU替换策略，则block 9进入的时候只会替换block 8，之后访问均命中直到block 8进入，会替换block 9。最终每轮访问共访问了38个block，平均只有2个未命中L1D。
在第二遍中，无论是LRU还是LFU替换策略，每轮访问都共访问了38个block，平均只有2个未命中L1D。
所以如果两遍实验时间基本一致，则说明使用的是LFU替换策略，若第二遍比第一遍时间显著减少则为LRU替换策略。
结果分析
第一遍平均耗时为3.642s，第二遍平均耗时为2.84s，显著减少，故为LRU（或者类似LRU的）替换策略。
测出 L1D Cache 是否使用写直达策略
测试结果
测试代码
// write 2 * cache size
for (register int times = 0; times < 100000; times++) {
for (register int i = 0; i < num; i += 16) {
a[i] = 0;
}
}
// write cache size
for (register int times = 0; times < 100000 * 2; times++) {
for (register int i = 0; i < cache_size; i += 16) {
a[i] = 0;
}
}实现思路
构造一个2 * cache_size大小的数组。第一遍写入的时候顺序遍历整个数组，也就是2 * cache_size大小的数组；第二遍则只顺序遍历一半数组，也就是cache_size大小。于是第一遍每次写入都无法命中cache，而第二遍则只有第一次写入的时候未命中，之后全部都命中。
顺序访问的过程中，步长为64B，即为之前测得的cache line的大小。
如果第一遍访问时间显著长于第二遍，则可知写命中时访问延迟明显小于写不命中，故为写回策略；否则访问延迟相似，为写直达策略。
结果分析
第一遍平均耗时0.100s，第二遍平均耗时0.065s，显著小于第一遍，故可知本机器为写回策略。
对实验的建议
可以多给一些在测试效果不显著时候的建议，例如减少访存过程中的复杂计算，以及设置步长为cache line的大小，减少连续命中的情况等等。这些感觉不算实验重点考察的内容，但却会对结果产生很大影响。
Loading Comments...