CSAPP / CSE 351 学习笔记（处理器体系结构 & 优化程序性能)

处理器体系结构这一章涉及硬件的知识比较多，我只是翻了一翻，了解一下概念。（尝试去读，但发现还是读不懂）
优化程序性能这一章还是很好读的，学到了一些优化的思想和经验法则。

处理器体系结构

一个处理器支持的指令和指令的字节级编码称为它的指令集体系结构（Instruction-Set Architecture，ISA）。不同的处理器「家族」，例如 Intel IA32 和 x86-64、IBM/Freescale Power 和 ARM 处理器家族，都有不同的 ISA。ISA 在编译器编写者和处理器设计人员之间提供了一个概念抽象层：

• 编译器编写者需要知道允许哪些命令，以及它们是如何编码的。
• 处理器设计者必须建造出执行这些指令的处理器。

现代处理器的实际工作方式可能跟 ISA 隐含的计算模型大相径庭。ISA 模型看上去应该是顺序指令执行。然而，通过同时处理多条指令的不同部分，处理器可以获得更高的性能。

（以下内容作者们使用 Y86-64 来表示简单版的 x86-64）

Y86-64 程序中的每条指令都会读取或修改处理器状态的某些部分，这称为程序员可见状态。

状态码指明程序是否正常运行。

CISC 和 RISC 指令集

参考：p249

读音：CISC（sisk）、RISC（risk）。

CISC	早期的 RISC
指令数量数量很多。Intel 描述全套指令的文档有 1200 多页。	指令数量通常少于 100 条。
有些指令的延迟很长。	没有较长延迟的指令。
编码是可变长度的。	编码是固定长度的。
指定操作数的方式很多。	简单寻址方式。通常只有基址和偏移量寻址。
可以对内存和寄存器操作数进行算术和逻辑运算。	只能对寄存器操作数进行算术和逻辑运算。
对机器级程序来说实现细节是不可见的。ISA 提供了清晰的抽象。	对机器级程序来说实现细节是可见的。
有条件码。	没有条件码。
栈密集的过程链接。栈被用来存取过程参数和返回地址。	寄存器密集的过程链接。寄存器被用来存取过程参数和返回地址。

先出现 CISC（Intel），再出现 RISC（Sun Microsystems、IBM、PowerPC）。20 世纪 90年代早期，争论逐渐平息，因为事实已经非常清楚了，无论是单纯的 RISC 还是单纯的 CISC 都不如结合两者精华的思想和设计。RISC 机器发展进化的过程中，引入了更多的指令，而许多这样的指令都需要执行多个周期。今天的 RISC 机器的指令表中有几百条指令，几乎与其名不相符。

存储器和时钟

组合电路从本质上讲，不存储任何信息。相反，它们只是简单地响应输入信号，产生等于输入的某个函数的输出。除了产生时序电路（sequential circuit），也就是有状态并且在这个状态上进行计算的系统，我们必须引入按位存储信息的设备。存储设备都是由同一个时钟控制的，时钟是一个周期性信号，决定什么时候要把新值加载到设备中。

• 时钟寄存器（寄存器）：存储单个位或字。时钟信号控制寄存器加载输入值。
• 随机访问存储器（内存）：存储多个字，用地址来选择该读或写哪个字。

流水线

流水线化一个重要特性就是提高了系统的吞吐量（throughput），也就是单位时间内服务的顾客总数，不过它也会轻微地增加延迟（latency），也就是服务一个用户所需要的时间。（这里的顾客就是指令）

优化程序性能

编写高效程序需要做到：

1. 我们必须选择一组适当的算法和数据结构。
2. 我们必须编写出编译器能够有效优化以转换成高效可执行代码的源代码，所以需要理解优化编译器的能力和局限性是很重要的。

优化编译器能力和局限性

大多数编译器，包括 GCC，向用户提供了一些对它们所使用的优化的控制。最简单的控制就是制定优化级别。例如，以命令行选项-Og调用是让 GCC 使用一组基本的优化。以选项-O1、-O2或-O3调用将得到更多的优化。

编译器必须很小心地对程序只使用安全的优化，也就是说对于程序可能遇到的所有可能的情况，在 C 语言标准提供的保证之下，优化后得到的程序和未优化的版本有一样的行为。

void twiddle1(long *xp, long *yp) {
  *xp += *yp;
  *xp += *yp;
}

void twiddle2(long *xp, long *yp) {
  *xp += 2 * *yp;
}

这两个过程似乎有相同的行为，将存储在由指针 yp 指示的位置的值两次加到指针 xp 指示位置的值。另一方面，twiddle2 的执行效率更高一些，它只要求三次内存引用（读 *xp、读 *yp、写 *xp），而 twiddle1 需要六次内存引用（两次读 *xp、两次读 *yp、两次写 *xp）。

不过，考虑 xp 等于 yp 的情况。此时，函数 twiddle1 会执行下面的计算：

*xp += *xp;
*xp += *xp;

结果是 xp 指向的值增加到 4 倍。另一方面，twiddle2 会执行下面的计算：

*xp += 2 * *xp; /* Triple value at xp */

结果是 xp 指向的值仅增加到 3 倍。编译器不知道 twiddle1 会如何被调用，因此它必须假设参数 xp 和 yp 可能会相等。因此，我们不能使用 twiddle2 版本对 twiddle1 进行优化。

这种两个指针可能指向同一个内存位置的情况称为内存别名使用（memory aliasing）。在只执行安全的优化中，编译器必须假设不同的指针可能会指向内存中同一个位置。

用内联函数替换优化函数调用

包含函数调用的代码可以用一个称为内联函数替换（inline substitution），或者简称内敛（inline）的过程进行优化，此时，将函数调用替换为函数体。

这样的转换减少了函数调用的开销，也允许对展开的代码做进一步的优化。

参考：p345

在各种编译器中，就优化能力来说，GCC 被认为是胜任的，但是并不是特别突出。它完成基本的优化，但是它不会对程序进行更加「有进取心」的编译器所做的那种激进变换。因为，使用 GCC 的程序员必须花费更多的精力，以一种简化编译器生成高效代码的任务的方式来编写程序。

p350 结论：

未经优化的代码是从 C 语言代码到机器代码的直接翻译，通常效率明显较低。简单地使用命令行选项-O1，就会进行一些基本的优化。程序员不需要做什么，就会显著地提高程序性能——超过两个数量级。通常，养成至少使用这个级别优化的习惯是很好的。

表示程序性能

处理器活动的顺序是由时钟控制的，时钟提供了某个频率的规律信号，通常用千赫兹（GHz），即十亿周期每秒来表示。例如，当表明一个系统有4GHz处理器时，这表示处理器时钟运行频率为每秒 $4\times 10^9$ 个周期。每个时钟周期的时间是时钟频率的倒数，通常是纳秒、皮秒。

从程序员的角度来看，用时钟周期来表示度量标准要比用纳秒或皮秒来表示有帮助得多。用时钟周期来表示，度量值表示的是执行了多少条指令，而不是时钟运行得有多快。

消除循环的低效率

*dest = IDENT;
for (long i = 0; i < vec_length(v); ++i) {
  data_t val;
  get_vec_element(v, i, &val);
  *dest = *dest OP val;
}

这个程序在每次循环迭代时都必须对测试条件求值。另一方面，向量的长度并不会随着循环的进行而改变。因此，只需计算一次向量的长度，然后在我们的测试条件中都使用这个值。

long length = vec_length(v); // calculate first
*dest = IDENT;
for (long i = 0; i < length; ++i) {  // remove vec_length(v)
  data_t val;
  get_vec_element(v, i, &val);
  *dest = *dest OP val;
}

这个优化是一类常见的优化，称为代码移动（code motion）。这类优化包括识别要执行多次（例如在循环里）但是计算结果不会改变的计算。因而可以将计算移动到代码前面不会被多次求值的部分。

优化编译器会试着进行代码移动。不幸的是，对于会改变在哪里调用函数或调用多少次的变换，编译器通常会非常小心（它们不知道啊）。为了改进代码，程序员必须经常帮助编译器显式地完成代码的移动。

还有个strlen()的例子：

for (long i = 0; i < strlen(s); ++i)
  // foo-1

long len = strlen(s);
for (long i = 0; i < len; ++i)
  // foo-2

在理想的世界里，编译器会认为循环测试中对 strlen 的每次调用都会返回相同的结果，因此应该能够把这个调用移出循环。但是，这需要非常成熟完善的分析，编译器需要检查字符串的元素以判断。程序员还是自己做这种转换吧。

这个示例说明了编程时的一个常见的问题，一个看上去无足轻重的代码片段有隐藏的渐近低效率（asymptotic inefficiency）。这段无危险的代码变成了一个主要的性能瓶颈。一个有经验的程序员工作的一部分就是避免引入这样的渐近低效率。

减少过程调用

尽量减少在循环中进行函数调用，但也要考虑这种变换严重损害了程序的模块性。

*dest = IDENT;
for (long i = 0; i < length; ++i) {
  data_t val;
  get_vec_element(v, i, &val);
  *dets = *dest OP val;
}

// better
*dest = IDENT:
data_t *data = get_vec_start(v);
for (long i = 0; i < length; ++i) {
  *dest = *dest OP data[i];  // val -> data[i]
}

消除不必要的内存引用（临时变量做累积值）

上述的代码将合并运算计算的值累积在指针 dest 指定的位置。通过检查编译出来的为内循环产生的汇编代码可以看出这个属性：

.L17:
  vmovsd  (%rbx), %xmm0          # Read product from dest
  vmulsd  (%rdx), %xmm0, %xmm()  # Multiply product by data[i]
  vmovsd  %xmm0, (%rbx)          # Store product at dest
  addq  $8, %rdx                 # Increment data+i

为了消除这种不必要的内存读写，我们可以引入一个临时变量 acc，它在循环中用来累积计算出来的值，只有在循环完成之后结果才存放在 dest 中。此时，编译器现在可以用寄存器 %xmm0 来保存累积值。

data_t acc = IDENT;  // local variable
for (long i = 0; i < length; ++i) {
  acc = acc OP data[i];
}

.L25:
  vmulsd  (%rdx), %xmm0, %xmm0   # Multiply acc by data[i]
  addq  $8, %rdx                 # Increment data+i

理解现代处理器

乱序处理最早是在 1964 年 Control Data Corporation 的 6600 处理器中实现的。

处理器可以在每个时钟周期执行多个操作，而且是乱序的（out-of-order）。这些处理器在工业界被称为超标量（superscalar）。整个设计有两个主要部分：

• 指令控制单元（Instruction Control Unit，ICU）：负责从内存中读出指令序列，并根据这些指令序列生成一组针对程序数据的基本操作。
• 执行单元（Execution Unit，EU）：执行以上操作。

ICU 从指令告诉缓存（instruction cache）中读取指令，指令高速缓存是一个特殊的告诉存储器，它包含最近访问的指令。通常，ICU 会在当前正在执行的指令很早之前取指，这样它才有足够的时间对指令译码，并把操作发送到 EU。

当遇到分支时，现代处理器采用了一种称为分支预测（branch prediction）的技术，猜测是否会选择分支，同时还预测分支的目标地址。使用投机执行（speculative execution）的技术，处理器会开始取出位于它预测的分支会跳到的地方的指令，并执行译码。这种逻辑是通过取指控制来完成的。

一条指令可以被译码成多个操作，关于指令如何被译码操作序列的细节，不同的机器都会不同，这个信息可谓是高度机密。

在 ICU 中，退役单元（retirement unit）记录正在进行的处理，并确保它遵守机器级程序的顺序语义。

循环展开

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

for (long i = 0; i < limit; ++i) {
  acc = acc OP data[i];
}
/* Combine 2 elements at a time */
for (long i = 0; i < limit; i+=2) {
  acc = (acc OP data[i]) OP data[i + 1];
}
/* Finish any remaining elements */
for (; i < length; ++i) {
  acc = acc OP data[i];
}

编译器可以很容易地执行循环展开。只要优化级别设置得足够高，许多编译器都能例行公事地做到这一点。用优化级别 3 或更高等级调用 GCC，它就会执行循环展开。

提高并行性

• 多个累积变量（multiple accumulators）

  for (long i = 0; i < limit; i+=2) {
    acc0 = acc0 OP data[i];
    acc1 = acc1 OP data[i + 1];
  }

  注意：浮点乘法和加法是不可结合的。不同的结合方式可能产生不同的结果。

• 重新结合变换（reassociation transformation）

  // 1
  acc = (acc OP data[i]) OP data[i + 1];
  // 2
  acc = acc OP (data[i] OP data[i + 1]);

  因为括号改变了向量元素与累积值 acc 的合并顺序，产生了我们成为2 x 1a的循环展开形式。这种方法可以增加并行执行的操作数量。

  具体原理参考：p374

  注意：对于浮点数情况，必须再次评估这种重新结合是否有可能严重影响结果。

  大多数编译器不会尝试对浮点运算做重新结合，因为这些运算不保证是可结合的。当前的 GCC 版本会对整数运算执行重新结合，但不是总有好的效果。通常，并行地累积变量是更好地方法。

总结

1. 高级设计

• 适当的算法和数据结构

2. 基本编码原则

• 消除连续的函数调用（将计算移到循环外）
• 消除不必要的的内存引用（引入临时变量保存中间结果）

3. 低级优化
   • 展开循环
   • 多个累积变量和重新结合（提高指令级并行）