并行与分布式科学计算技术解析

# 并行与分布式科学计算技术解析 ## 1. 矩阵乘法与缓存优化 ### 1.1 矩阵访问与复制策略 在矩阵运算中，矩阵的访问方式会影响性能。若要提前复制矩阵，将其置于最内层循环并复制整个矩阵，这样可按列访问矩阵；否则，将其置于最外层循环，此时复制行面板的成本是低阶项。若两个矩阵具有相同的访问模式，会将矩阵 B 作为最外层矩阵，以便按列访问矩阵 C。 ### 1.2 片上矩阵乘法生成 ATLAS 片上矩阵 - 矩阵乘法代码需根据平台进行调整。输入矩阵以分块形式复制后，仅需考虑一种转置情况，即 \( C \approx A^T B + C \)。选择这种情况是因为在不展开循环时，它能产生最大的 (浮点运算次数)/(缓存缺失次数) 比率。对于硬件允许较小比率的机器，可通过对 M 和 N 循环进行展开来处理（目前 ATLAS 未采用对 K 循环进行置换的技术）。 ### 1.3 缓存重用优化 对于片上矩阵乘法，缓存重用是提升性能的重要因素。当所有的矩阵 A 能放入缓存，且有足够空间存放矩阵 B 的至少两列和矩阵 C 的一个缓存行时，可实现最大的缓存重用（忽略写入成本）。在这种情况下，每次实际仅访问矩阵 B 的一列，有两列的存储空间可确保缓存溢出时旧列成为最近最少使用的数据，从而保证矩阵 A 始终存于缓存中（假设缓存替换策略为最近最少使用）。 ### 1.4 其他影响因素 除缓存重用外，还有其他因素影响片上矩阵乘法性能： - **指令缓存溢出**：指令会被缓存，因此需将片上乘法的指令放入 L1 缓存，这意味着无法完全展开所有三个循环。 - **浮点指令排序**：现代架构的浮点单元多为流水线式，操作结果需等待 s 个周期后才能使用（s 通常为 3 或 5）。对于 \( C \approx A^T B + C \) 形式的矩阵乘法，若架构无融合乘加单元，会导致执行停顿。解决方法是分离乘法和加法操作，并在其间插入无关指令，可通过硬件（乱序执行）或编译器实现，但有时显式实现更高效。 - **减少循环开销**：主要方法是循环展开。若要在不改变指令顺序的情况下减少循环开销，需展开 A 和 B 共同维度的循环（即 K 循环）；沿其他维度（M 和 N 循环）展开会改变指令顺序和内存访问模式。 - **暴露并行性**：许多现代架构有多个浮点单元，但实现浮点计算的完美并行加速存在两个障碍。一是硬件限制，所有浮点单元需访问内存，为实现完美并行加速，内存读取通常也需并行操作；二是编译器需识别并行化机会，可通过展开 M 和/或 N 循环并选择正确的寄存器分配来解决。 - **确定合适的缓存缺失次数**：未在寄存器中的操作数需从内存中获取，若不在 L1 缓存中，可能导致执行延迟。不同架构可同时发出的缓存缺失次数不同，为最小化内存成本，应在每个周期发出最大数量的缓存缺失，直至所有内存数据进入缓存或被使用。实际中，可通过 M 和 N 循环展开来控制缓存命中率。 ## 2. ATLAS 性能结果 ### 2.1 性能测试设置 展示了双精度（64 位浮点运算）在不同平台上的计时结果。与许多 BLAS 计时不同，每次调用前会刷新缓存，且数组的领先维度设置为大于矩阵的行数，因此此处的性能数字通常低于其他论文报告的结果，但更能反映用户在实际应用中看到的性能。 ### 2.2 矩阵乘法和 LU 分解性能 - **矩阵乘法**：图 3.2 展示了 ATLAS 与供应商提供的矩阵乘法（若