改进矩阵乘法程序
实验内容
待优化代码：
// baseline_matmul.cpp
constexpr unsigned MATRIX_SIZE = 16u;
unsigned A[MATRIX_SIZE][MATRIX_SIZE];
unsigned B[MATRIX_SIZE][MATRIX_SIZE];
unsigned C[MATRIX_SIZE][MATRIX_SIZE];
int main(int argc, char **argv) {
// initialization
for (unsigned i = 0; i < MATRIX_SIZE; ++i) {
for (unsigned j = 0; j < MATRIX_SIZE; ++j) {
A[i][j] = i % (j + 1);
B[i][j] = i / (j + 1);
C[i][j] = 0;
}
}
for (int i = 0; i < MATRIX_SIZE; i++)
for (int j = 0; j < MATRIX_SIZE; j++)
for (int k = 0; k < MATRIX_SIZE; k++) C[i][j] += A[i][k] * B[k][j];
unsigned sum = 0;
for (int i = 0; i < MATRIX_SIZE; ++i) {
for (int j = 0; j < MATRIX_SIZE; ++j) {
sum += C[i][j];
}
}
asm volatile(".word 0x0000000b" // exit mark
);
return sum;
}
新建文件 test\sample_cache_matmul.cpp，并在该文件中优化上述代码的逻辑，在给定规格的 cache 上将数据缓存命中率提升至 91% 以上。同时，为了保证优化的正确性，你需要保证程序的运行时间至多增加 20%。
优化过后的矩阵乘法程序既然缓存命中率高了，不应该变得更快吗？
由于本课程实验实现的 Tomasulo 模拟器为单发射 CPU，其最优情况下的 CPI 也仅仅为 1（实际上这都不能算超标量），程序的运行速度显著受到程序运行的指令数的制约。
在进行矩阵分块等优化时，由于需要更改循环结构和遍历顺序，代码的复杂度会显著提高。因此从运行时间的角度来说，实现的优化有很大可能为负优化。
2024 年的实验框架没有检查运行周期数
由于实验框架的下发较早，我们在下发框架时没有注意到可能的绕过检查标准的实现方法（如大量访问同一地址来提高缓存命中率）。需要同学们自行在实验框架中进行如下修改：
48 48 Logger::Warn(
49 - "Before optimization, cache hit rate = %.3lf",
50 - beforeOpt);
49 + "Before optimization, cache hit rate = %.3lf, finished in %u cycles",
50 + beforeOpt, testTime[1]);
51 51 Logger::Warn(
52 - "After optimization, cache hit rate = %.3lf",
53 - afterOpt);
52 + "After optimization, cache hit rate = %.3lf, finished in %u cycles",
53 + afterOpt, testTime[0]);
54 54
55 - return afterOpt > 0.91 - eps;
55 + return afterOpt > 0.91 - eps && testTime[0] < 1.2 * testTime[1];
对 ./cache-exp/matmul.cpp 进行上述的修改，让实验框架输出运行时间并进行检查。
** 如果没有添加上述检查，你会失去本步骤的分数，请务必进行修改 **
如果你希望获取 cache 参数以帮助你更好地进行优化，你可以修改 MeasureMatmulWithCache 的定义，以及程序调用的相关内容。如进行了修改，请在报告中进行说明。同时注意，不要修改正确性检查和命中率检查相关的代码（不包括对上述运行时间检查的修改）。如有修改，你将会失去本步骤的全部分数。
实验要求
- 使用 O2 参数编译
- 不能使用汇编指令直接优化，如内联汇编
- 不能使用并行方法优化，如 openmp，MPI，向量化等等
- 要保证优化后结果正确，会进行正确性检查
方法示例
- 更改运算顺序，使得访存序列更友好
- 矩阵分块
- ……
最后更新:
2024年5月20日
作者：