《深入理解计算机系统(CSAPP)》第5章 优化程序性能 - 学习笔记

写在前面的话：此系列文章为笔者学习CSAPP时的个人笔记，分享出来与大家学习交流，目录大体与《深入理解计算机系统》书本一致。因是初次预习时写的笔记，在复习回看时发现部分内容存在一些小问题，因时间紧张来不及再次整理总结，希望读者理解。

---

《深入理解计算机系统(CSAPP)》第3章 程序的机器级表示 - 学习笔记_友人帐_的博客-CSDN博客

《深入理解计算机系统(CSAPP)》第5章 优化程序性能 - 学习笔记_友人帐_的博客-CSDN博客

《深入理解计算机系统(CSAPP)》第6章 存储器层次结构 - 学习笔记_友人帐_的博客-CSDN博客

《深入理解计算机系统(CSAPP)》第7章 链接- 学习笔记_友人帐_的博客-CSDN博客

《深入理解计算机系统(CSAPP)》第8章 异常控制流 - 学习笔记_友人帐_的博客-CSDN博客

《深入理解计算机系统(CSAPP)》第9章虚拟内存 - 学习笔记_友人帐_的博客-CSDN博客

---

第五章 优化程序性能

1. 编译器优化的能力和局限性

（1）编译器能做的优化

优化选项：-Ox：g-基本优化；1~3 - 更高级优化。

• 寄存器分配
• 代码选择与排序(调度)
• 消除死代码
• 消除轻微的低效率问题

（2）优化的局限性

• 要在基本约束下运行：不能引起程序功能的任何改变；不去优化畸形情况下的程序行为。

• 只在单个文件中进行优化分析，不做文件间的代码优化分析，代价太大。

• 大多数分析都是基于静态信息，难以预测运行时的输入。

• 遇到问题时必须对程序只使用安全的优化，偏保守。

2. 妨碍编译器优化的因素

• 内存别名：两个指针指向同一个内存位置；因此编译器必须假设不同的指针可能会指向内存中同一个位置。

• 函数调用：不能确定函数调用是否有副作用；因此编译器会假设最糟的情况并保持所有的函数调用不变。

解决方法：

• 对于内存别名：

  消除不必要的内存引用：可以增加局部变量，将运算中间值累积在寄存器中，在整个过程结束后写回目标内存。

• 对于函数调用：

  用内联函数替换优化函数调用：将函数调用展开替换为函数体；

  减少过程调用：尽量少地调用函数。

3. 优化方法

（1）不依赖处理器

• 代码移动：如果某段代码总是产生相同的结果，就将其从循环中移出，避免重复计算。

• 复杂运算简化：用更简单的方法替换昂贵的操作，例如使用移位、加代替乘法、除法。

• 共享公用子表达式：找到多个计算的公共部分，重用表达式的一部分。

• 尽量减少循环边界的检查

• 消除不必要的内存引用，用局部变量累积结果

• 使用AVX2编程，使用向量指令计算

（2）实现指令级并行

• 循环展开

通过增加每次迭代计算的元素的数量，减少循环的迭代次数。减少了不直接有助于程序结果的操作的数量，例如循环索引计算和条件分支。它提供了一些方法，可以进一步变化代码，减少整个计算中关键路径上的操作数量。

$k\times 1$展开

limit = length - k + 1;
for (i = 0; i < limit; i += k)
{// 对元素i到i+k-1合并运算
}
for (; i < length; i++)
{// 以每次处理一个元素的方式处理最后0~k-1个元素
}

• 提高并行性

利用更多的功能单元来执行，比单个完全流水线化的功能单元更快，打破延迟界限。

使用多个累积量：对于可结合和可交换的合并运算可以通过将一组合并运算分割成两个或更多的部分，并在最后合并结果来提高性能。

$k\times n$展开：k次循环展开，n路并行

limit = length - k + 1;for (i = 0; i < limit; i += k)
{// 对元素i到i+k-1合并运算// 使用n个累积量
}// 处理最后0~k-1个元素// n个累积量运算结果合并

最好使用$k\times k$展开，且对于延迟为$L$，容量为$C$的操作而言，循环展开因子$k\ge C\cdot L$时达到最大吞吐量。

展开变换时，必须考虑实现的功能是否与原来相同。要考虑运算是否可交换、可结合，溢出情况下是否保证结果与原来相同等。(浮点加法和乘法不可结合，原因在于四舍五入和溢出)

同时k不能过大，否则会出现寄存器溢出的情况：k的个数超过了机器的寄存器个数，会将变量分配在栈上，运行速度反而会降低。(x86-64处理器有16个寄存器，并可以使用16个YMM寄存器来保存浮点数)

• 重组(重新结合变换)

改变运算顺序，以减少计算中关键路径上操作的数量，更好地利用功能单元的流水线能力。下一个循环的部分操作可以早一些开始。

称为$k\times na$展开。

4. 现代CPU设计

（0）基本概念

程序性能度量标准：每元素的周期数 (Cycles Per Element, CPE)

功能单元的性能：

• 延迟(latency)：表示完成运算所需要的总时间；

• 发射时间(issue time)：表示两个连续的同类型的运算之间需要的最小时钟周期数；

• 容量(capacity)：表示能够执行该运算的功能单元的数量。

• 最大吞吐量：发射时间的倒数。一个完全流水线化(发射时间为1)的功能单元有最大的吞吐量，每个时钟周期进行一个运算。具有多个功能单元可以进一步提高吞吐量。对一个容量为C，发射时间为I的操作来说，处理器可能获得的吞吐量为每时钟周期C/I个操作。(每个时钟周期可以完成的操作数)

CPE值的两个基本界限：

• 延迟界限(latency bound)：因为在下一条指令开始之前，这条指令必须结束。给出了任何必须按照严格顺序完成合并运算的函数所需要的最小CPE值。理解：严格按照顺序执行，即使用一个功能单元，执行该合并运算最低能达到的CPE。(即为一个功能单元的极限，但可以通过增加功能单元并行计算以使实际运算速度突破这个界限)
• 吞吐量界限(throughput bound)：刻画了处理器功能单元的原始计算能力。这个界限是程序性能的终极限制。理解：比如执行整数加法的最大吞吐量为2，即每个时钟周期最多可以执行2次整数加法运算，故由于最大吞吐量为2，吞吐量对于整个合并运算的CPE限制为1/2=0.5，即由于最大吞吐量为2，整数加法的CPE最低只能到达0.5。

（1）现代处理器特点

能够实现指令级并行，同时对多条指令求值。

• 超标量(superscalar)：是它可以在每个时钟周期执行多个操作。把计算分解为多个阶段，在阶段间传递部分计算。
  

• 乱序的(out-of-order)：指令执行的顺序不一定与它们在机器级程序中的顺序一致。

（2）主要组成部分

• 指令控制单元(Instruction Control Unit, ICU)：负责从内存中读出指令序列，并根据这些指令序列生成一组针对程序数据的基本操作。

• ICU 从指令高速缓存 (instruction cache) 中读取指令，指令高速缓存是一个特殊的高速存储器，它包含最近访问的指令。通常，ICU会在当前正在执行的指令很早之前取指，这样它才有足够的时间对指令译码，并把操作发送到EU。
• 取指控制的块包括分支预测，以完成确定取哪些指令的任务。
• 指令译码逻辑接收实际的程序指令，并将它们转换成一组微操作。
• 退役单元 (retirement unit) 记录正在进行的处理，控制寄存器文件中所记录的那些寄存器的更新。令译码时，关于指令的信息被放置在一个先进先出的队列中。这个信息会一直保持在队列中，直到发生以下两个结果中的一个。①一旦一条指令的操作完成了，而且所有引起这条指令的分支点也都被确认为预测正确，那么这条指令就可以退役(retired)了，所有对程序寄存器的更新都可以被实际执行了。②如果引起该指令的某个分支点预测错误，这条指令会被清空(flushed)，丢弃所有计算出来的结果。

• **执行单元 (Execution Unit, EU)：**接收来自取指单元的操作并执行。每个时钟周期会接收多个操作 这些操作会被分派到一组功能单元中，分别用来专门处理不同类型的操作。

• 读写内存是由加载和存储单元实现的。
• 加载和存储单元通过数据高速缓存(data cache) 来访问内存。数据高速缓存是一个高速存储器，存放着最近访问的数据值。
• 使用投机执行技术对操作求值，但是最终结果不会存放在程序寄存器或数据内存中，直到处理器能确定应该实际执行这些指令。分支操作被送到EU，确定分支预测是否正确。如果预测错误，EU会丢弃分支点之后计算出来的结果，还会发信号给分支单元，说预测是错误的，并指出正确的分支目的。在这种情况中，分支单元开始在新的位置取指。
• 标记为执行“算术运算”的单元通常是专门用来执行整数和浮点数操作的不同组合。
• 为了加速一条指令到另一条指令的结果的传送，执行单元可以直接将结果发送给彼此。

（3）现代处理器的一些功能

• 分支预测(branch prediction)：处理器会猜测是否会选择分支，同时预测分支的目标地址。

一种方式：投机执行(speculative execution)：处理器会开始取出位于它预测的分支会跳到的地方的指令，并对指令译码，甚至在它确定分支预测是否正确之前就开始执行这些操作。如果过后确定分支预测错误，会将状态重新设置到分支点的状态，并开始取出和执行另一个方向上的指令。

• 寄存器重命名