Skip to main content

优化程序性能 HPC Optimizing program's performance

  1. 优化编译器的能力和局限性
    1. 因为指针引用问题，无法判断函数的功能，所以无法判断是否应当优化，改变函数调用的位置和次数后是否和原来还相同。所以不同的优化等级能达到的效果是不相同的。
  2. 表示程序性能
  3. 优化基本方法
    1. 消除循环的低效率：把不会变化的变量移出循环
    2. 减少过程调用：比如不必要的边界检查
    3. 消除不必要的内存引用：比如用中间变量代替指针赋值，免得翻译成汇编、机器码后，反复把值从指针变量中读到寄存器，计算完后再把寄存器的值存到指针变量里
  4. 现代处理器
    1. 两个下界描述了程序的最大性能，是程序性能的终极限制
      1. 延迟界限（latency bound），指令必须按严格顺序执行
      2. 吞吐量界限（throughput bound），cpu的原始计算能力
    2. 并行功能
    3. 现代处理器采用了一种称为分支预测（branch prediction）的技术，使用投机执行（speculative execution）

优化程序性能​

指令执行速度的度量指标CPE​

  • CPU运行频率：1Ghz。时钟频率，表示程序每秒运行1e9个周期
  • 每元素的周期数 CPE（Cycle Per Element），哦是时钟频率的倒数，通常以纳秒1e-9或者皮秒1e-12为单位。这个度量值表示执行了多少命令，而不是时钟运行得有多快。

p350 5.4

优化程序的基本方法​

  • 代码移动（code motion），减少冗余调用
    • 消除循环的低效率，尤其是渐进低效率（asymptotic inefficiency） ，即CPE为幂指数上升
    • 编译器做这个优化会做得比较小心，因为有可能引入副作用。
  • 减少过程调用
    • 消除循环内反复的函数调用
  • 消除不必要的内存调用
    • 如果用指针的话，汇编中会反复读写到目标地址，可以使用临时变量来承接循环中的计算结果

功能单元的性能衡量指标​

  • 延迟（Latency），表示完成运算所需的时间
  • 发射时间（Issue time），表示两个连续的同类型运算之间需要的最小时钟周期数
    • 发射时间为1的功能单元被称为完全流水线的（fully pipelined）
  • 容量（Capacity），表示同时能发射多少个这样的操作
  • 吞吐量，每时钟周期多少个操作，=容量/发射时间 =C/I

在处理器操作模型中的数据流（data-flow），展示了不同操作之间的数据相关是如何限制它们的执行顺序的。

数据流中的关键路径（critical path），即循环寄存器之间的操作链，限制了处理器性能。

寄存器类型有

  1. 只读
  2. 只写
  3. 局部，在指令内部的操作
  4. 循环，指的是作为源值又作为目的

测试的CPE一般比预测的大，是因为关键路径所提供的只是CPE的下界，其他的因素也会限制性能，比如

  • 可用功能单元的数量
  • 任一步中功能单元传值的数量
  • etc

由于延迟边界是基本的限制，决定了我们的合并运算能执行多快。为了进一步优化执行速度，我们需要调整操作的结构，增强指令的并行性。使得唯一的限制变为吞吐量界限，得到接近1的CPE

高阶优化

5.8+

循环展开​

循环展开是一种程序变换，通过增加每次迭代计算的元素的数量，减少循环的迭代次数

  1. 它减少了不直接有助于程序结果的操作的数量，比如循环索引计算和条件分支判断
  2. 可以进一步变化代码，减少计算中关键路径上的操作数量
res = 0
len = n - 1
for i = 0; i < len; i++:
	res += a[i]
==
res = 0
len = n - 1
limit = n - k + 1
for i = 0; i < limit ; i += k:
	res = a[i] + a[i+1] .. + a[i+k-1]  # i+k-1 < n => i < n-k+1
for ; i < len ; i++:
	res += a[i]

编译器可以很容易地实现循环展开

Reference​

  1. CSAPP: Chapter05 Optimize Program Performance