2 附录A应用：矩阵乘积的快速算法 6:end for 7:end for 例A1在个人电脑(CPU9-10900K,内存128G)上用C语言测试 (test_dgemm.c) ·n=1824,gcc编译加-02选项，KN顺序大概比K顺序快2.5倍.如果加-03选项，则快3.5倍 ·n=2848,cc编译加-02选项，K冈顺序大概比K顺序快6倍.如果加-03选项，则快8倍. 以下分析摘自网络(https:/zhuanlan.zhihu.com/p/1462s0334),仅供参考. 下面分析为什么这两种顺序的计算效果差这么多. 首先从矩阵的存储方式说起.一般而言，矩阵有两种存储方式：一维数组和二维数组.对于矩 阵乘法而言，一维数组显然比二维数组好得多（下文的分析也能看出这一点）.但是如果用矩阵类实 现其他功能的话，可能其他功能用二维数组更方便一些.所以下面对于这两种实现方式都加以分 造成矩阵乘法慢的原因，除了算法本身的复杂度以外，还有内存访问的不连续，这会导致cah 命中率不高.所以为了加速，就要尽可能使内存访问连续，即不要跳来跳去.我们定义一个概念：跳 跃数，来衡量访问的不连续程度。 对于最普通的实现方式四K顺序，它是依次计算C中的每个元素，对应的计算公式是 因此计算c,需要将A的第i行与B的第j列依次相乘相加.按假设，矩阵是按行存储的，所以A 在第i行中不断向右移动时，内存访问是连续的.但B在第j列不断向下移动时，内存访问是不连 续的.计算完时，B已经间断地访问了n次，而A只间断1次（这一次就是算完后跳转到本行的 开头，故总共是n+1次.这样，计算完C中所有n2个元素，跳转了n3+n2次.但刚才没有统计 C的跳转次数，加上以后是n3+n2+n.(注意，在计算完C中每行的最后一个元素时，A是从相应 行末尾转到下一行开头.如果使用一维数组实现的话，这是连续地访问，要诚掉这n次.同时，C也 没有跳转次数了，还要减掉n次.因此对于一维数组，跳转数是n3+n2-n次) 而如果以N顺序实现，则对C一行一行计算，即 G=a41i1+a2b2+…+ambn,i=1,2,,n 其中亡和6分别表示C和B的第i行.当计算C的第i行时，先计算a1高1，即访问a1和B的 第i行（不间断往右移）.然后计算a2d2,此时A往右挪一个元素（不间断），B则跳转到下一行（如 果一维数组则间新一次，一维数组不间断.依次类推，算完C的第行后，恰好按顺序将B遍历一 遍，间断了n次（一维数组是1次），且恰好从左往右遍历了A的第i行，间断了1次（一维数组没有 间断)，加起来是n+1次（一维数组是1次）.故计算C的所有n行后，跳转了n2+n次（一维数组 是n次).刚才没有算C的跳转，算上后跳跃数是2n2+n次（一维数组是n2次）. 由此可见： http://math.ecnu.edu.cn/-jypan · 2 · 附录 A 应用: 矩阵乘积的快速算法 6: end for 7: end for 例 A.1 在个人电脑 (CPU i9­10900K, 内存 128G) 上用 C 语言测试. (test_dgemm.c) • n=1024, gcc 编译加 ‐O2 选项, IKJ 顺序大概比 IJK 顺序快 2.5 倍. 如果加 ‐O3 选项, 则快 3.5 倍. • n=2048, gcc 编译加 ‐O2 选项, IKJ 顺序大概比 IJK 顺序快 6 倍. 如果加 ‐O3 选项, 则快 8 倍. 以下分析摘自网络 (https://zhuanlan.zhihu.com/p/146250334), 仅供参考. 下面分析为什么这两种顺序的计算效果差这么多. 首先从矩阵的存储方式说起. 一般而言, 矩阵有两种存储方式: 一维数组和二维数组. 对于矩 阵乘法而言, 一维数组显然比二维数组好得多 (下文的分析也能看出这一点). 但是如果用矩阵类实 现其他功能的话, 可能其他功能用二维数组更方便一些. 所以下面对于这两种实现方式都加以分 析。 造成矩阵乘法慢的原因, 除了算法本身的复杂度以外, 还有内存访问的不连续, 这会导致 cache 命中率不高. 所以为了加速, 就要尽可能使内存访问连续, 即不要跳来跳去. 我们定义一个概念: 跳 跃数, 来衡量访问的不连续程度. 对于最普通的实现方式 (IJK 顺序), 它是依次计算 C 中的每个元素, 对应的计算公式是 cij = ai1b1j + ai2b2j + · · · + ainbnj . 因此计算 cij , 需要将 A 的第 i 行与 B 的第 j 列依次相乘相加. 按假设, 矩阵是按行存储的, 所以 A 在第 i 行中不断向右移动时, 内存访问是连续的. 但 B 在第 j 列不断向下移动时, 内存访问是不连 续的. 计算完 cij 时, B 已经间断地访问了 n 次, 而 A 只间断 1 次 (这一次就是算完后跳转到本行的 开头), 故总共是 n + 1 次. 这样, 计算完 C 中所有 n 2 个元素, 跳转了 n 3 + n 2 次. 但刚才没有统计 C 的跳转次数, 加上以后是 n 3 + n 2 + n. (注意, 在计算完 C 中每行的最后一个元素时, A 是从相应 行末尾转到下一行开头. 如果使用一维数组实现的话, 这是连续地访问, 要减掉这 n 次. 同时, C 也 没有跳转次数了, 还要减掉 n 次. 因此对于一维数组, 跳转数是 n 3 + n 2 − n 次) 而如果以 IKJ 顺序实现, 则对 C 一行一行计算, 即 c˜i = ai1 ˜b1 + ai2 ˜b2 + · · · + ain˜bn, i = 1, 2, . . . , n, 其中 c˜i 和 ˜bi 分别表示 C 和 B 的第 i 行. 当计算 C 的第 i 行时, 先计算 ai1 ˜b1, 即访问 ai1 和 B 的 第 i 行 (不间断往右移). 然后计算 ai2 ˜b2, 此时 A 往右挪一个元素 (不间断), B 则跳转到下一行 (如 果二维数组则间断一次, 一维数组不间断). 依次类推, 算完 C 的第 i 行后, 恰好按顺序将 B 遍历一 遍, 间断了 n 次 (一维数组是 1 次), 且恰好从左往右遍历了 A 的第 i 行, 间断了 1 次 (一维数组没有 间断), 加起来是 n + 1 次 (一维数组是 1 次). 故计算 C 的所有 n 行后, 跳转了 n 2 + n 次 (一维数组 是 n 次). 刚才没有算 C 的跳转, 算上后跳跃数是 2n 2 + n 次 (一维数组是 n 2 次). 由此可见: http://math.ecnu.edu.cn/~jypan