绪论

矩阵乘法优化案例

  • 程序运行用时Python > Java > C的原因：
    • C是编译型语言，源代码被直接编译为机器码。
    • Java源代码先被编译为字节码，由JVM进行解释运行，并在运行中由其按需编译为机器码。当代码首次执行时，以解释方式进行，并由运行时系统记录代码块的运行频率，运行频率较高的代码块会被编译成机器码并在后续访问时直接运行。
    • Python是解释型语言，由Python解释器对源代码直接进行解释运行。解释器可以提供更加高级的编程特性，但会带来较多的性能损失。

C语言程序编译过程：
预处理（Preprocessing，输出.i文件）：使用预处理器（cpp），处理源代码中的预处理指令，如宏定义（#define）、头文件包含（#include）等。
编译（Compiling，输出.s文件）：编译器（如gcc）将预处理后的源代码转换成汇编语言。
汇编（Assembling，输出.o文件）：汇编器（as）将汇编语言转换成机器语言指令，生成目标文件。
链接（Linking，输出可执行文件）：链接器（ld）将多个目标文件及所需的库链接在一起，生成最终的可执行文件。

  • 对于Python代码，调整了循环的层次顺序，最大达到了18倍的性能差距。虽然算法的复杂度没有区别，但由于访存方式的改变，程序访存的局部性会有较大差距，可能会导致cache的频繁替换和访存次数的增加，从而影响程序运行时间。（i,k,j的顺序导致了2个矩阵的访存都是按行方式，因此具有最高的Cache命中率和最优的性能）。
  • 编译器优化：
    • O1、O2、O3：在程序编译环节施行不同程度的编译优化策略，使程序拥有更高的性能。
    • Os：优化编译过程以取得更小的程序体积。
    • Og：优化调试过程。
  • 使用并行优化：充分利用多核心特性。
    • cilk_for可以并行进行多次迭代。
    • 外层循环的并行往往比内层更有效；内层多余的并行操作反而有可能带来性能的不升反降。
    • 在可并行化的程序中，并行操作可以带来十分可观的性能提升。
  • 循环分块：将矩阵分为若干个块，对每一块分别进行计算，可以有效提高程序的局部性，增加Cache命中率并提高其性能。分块的大小可以根据多级缓存的具体大小进行设定，以达到最优的Cache利用。
  • 并行分治：利用公式可以将两个$n \times n$矩阵相乘的操作分解为8个$n/2 \times n/2$矩阵的乘法和一次$n \times n$矩阵的加法，从而利用分治的方法，对矩阵乘法进行优化。
    • 可以使用cilk_spawn（创建并行任务）和cilk_sync（等待并行任务全部完成）实现并行优化。
    • 分治的递归边界粒度如果设置过小，会导致较大的函数调用开销，导致分治算法的性能达不到预期。因此需要将该粒度适度扩大，以平衡开销。
  • 向量化
    • 使用编译选项对代码进行向量化编译优化
    • 使用AVX指令集，直接使用硬件层面的向量计算
  • 其他优化方法：
    • 预处理
    • 矩阵转置
    • 数据对齐
    • 内存管理指令
    • 高效利用AVX指令的算法

软件的其他属性

  • 除了性能，软件还有其他属性：
    • 兼容性
    • 功能性
    • 健壮性
    • …
  • 性能的另一层意义：软件各方面属性的“货币”，其他属性可以通过性能“买”来。
  • 近年来，各大软件的bug中有关性能的比例普遍提升，说明了软件对于性能的高要求在持续加深。