改进矩阵乘法程序

实验内容

待优化代码：

// 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（实际上这都不能算超标量），程序的运行速度显著受到程序运行的指令数的制约。

在进行矩阵分块等优化时，由于需要更改循环结构和遍历顺序，代码的复杂度会显著提高。因此从运行时间的角度来说，实现的优化有很大可能为负优化。

如果你希望获取 cache 参数以帮助你更好地进行优化，你可以修改 MeasureMatmulWithCache 的定义，以及程序调用的相关内容。如进行了修改，请在报告中进行说明。同时注意，不要修改正确性检查和命中率检查相关的代码（不包括对上述运行时间检查的修改）。如有修改，你将会失去本步骤的全部分数。

实验要求

• 使用 O2 参数编译
• 不能使用汇编指令直接优化，如内联汇编
• 不能使用并行方法优化，如 openmp，MPI，向量化等等
• 要保证优化后结果正确，会进行正确性检查

方法示例

• 更改运算顺序，使得访存序列更友好
• 矩阵分块
• ……

---

最后更新: 2025年3月11日

作者：cuibst