编写高校程序需要几类活动：第一，我们必须选择一组合适的算法和数据结构。第二，我们必须编写出编译器能够有效优化以转换成高效可执行代码的源代码。第三、针对处理运算量特别大的计算，将一个任务分成多个部分，这些部分可以在多核和多处理器的某种组合上并行地计算。
程序优化步骤：
- 消除不必要的内容，让代码尽可能有效地执行它期望的工作。这包括消除不必要的函数调用、条件测试和存储器引用。这些优化不依赖于目标机器的任何具体属性
- 利用处理器提供的指令级并行（instruction-level parallelism）能力，同时执行多条指令。
优化编译器的能力和局限性
- 两个指针可能指向同一个存储器位置的情况称为存储器别名使用（memory aliasing）
- 函数调用
表示程序性能
度量标准每元素的周期数（Cycles Per Element, CPE）作为一种表示程序性能并指导我们改进代码的方法。
处理器活动的顺序是由时钟控制的，时钟提供了某个频率的规律信号，通常用千兆赫兹（GHz）,即十亿周期每秒来表示。
什么是最小乘方拟合？
对于一个数据点$$（x_1,y_1）…(x_n,y_n)$$的集合，我们常常试图画一条线，它能最接近于这些数据代表的X-Y趋势。使得最小二乘方拟合，寻找一条形如y=mx+b的线，使得下面的这个误差度量最小：
$$E(m, b) = \Sigma(mx_i+b-y_i)^{2}$$
将E(m,b)分别对m和b求导，把两个导数函数设置为0，进行推导就能得出计算m和b的算法。
程序示例
消除循环的低效率
- 代码移动（code motion）这类优化包括识别要执行多次但是计算结果不会改变的计算。因此可以将计算移动到代码前面不会被多次求值的部分。
隐藏的渐近低效率（asymptotic inefficiency）
例子循环使用strlen判断字符串长度的问题。
减少过程调用
消除不必要的存储器引用
理解 x86-64的浮点代码：x86-64指令集扩展了IA32的32位寄存器，例如，用’r’替换’e’，将%eax、%edi和%esp 扩展到64位版本%rax、%rdi和%rsp。还增加了8个寄存器，命名为%r8~%r15，极大地增强了在寄存器中保存临时值的能力。后缀’q’用于整数指令（例如 addq、cmpq）表明是64位操作。
浮点数据保存在一组XMM寄存器中，命名为%xmm0~%xmm15。每个寄存器都是128位长，能够存放4个单精度（float）或着2个双精度（double）浮点数。在初始描述中，我们只使用对保存在SSE寄存器中的单精度值进行运算的指令。movss指令复制一个单精度数。像各种IA32 MOV 指令一样，源操作数和目的操作数可以是存储器位置，也可以是寄存器，但是它使用XMM寄存器，而不是通用寄存器。mulss指令进行单精度数乘法，乘积存放在第二个操作数的位置。同样地，源和目的操作数载存储器位置中，或着在XMM寄存器中。
理解现代处理器
指令级并行
现代微处理器取得的了不起的功绩之一是：它们采用复杂而奇异的微处理器结构，其中，多指令可以并行地执行，同时又呈现一种简单地顺序执行指令的表象。
- 延迟界限（latency bound）
- 吞度量界限（throughput bound）
乱序（out-of-order），意思就是指令执行的顺序不一定要与它们在机器级程序中的顺序一致。整个设计有两个主要部分：
- 指令控制单元（Instruction Control Unit, ICU）
- 执行单元（Execution Unit, EU）
前者负责从存储器中读出指令序列，并根据这些指令序列生成一组针对程序数据的基本操作；而后者执行这些操作。
ICU从指令高速缓存（instruction cache）中读取指令。指令高速缓存时一个特殊的高速缓存存储器，它包含最近访问的指令。
EU接收来自取指单元的操作。通常，每个时钟周期接收若干个操作。
循环展开
循环展开是一种程序变换，通过增加每次迭代计算的元素的数量，减少循环的迭代次数。
循环展开能够从两个方面改程序的性能。
- 首先，它减少了不直接有助于程序结果的操作的数量，例如循环索引计算和条件分之。
- 其次，它提供了一些方法，可以进一步变化代码，减少整个计算中关键路径上的操作数量。
提高并行性
- 多个累积变换
- 重新结合变换
优化合并代码的结果小结
一些限制因素
- 寄存器溢出
- 分支预测和预测错误处罚
如果我们的并行度p超过了可用的寄存器数量，那么编译器会诉诸益处（spiling），将某些临时值存放到栈中。
不要过分关心可预测的分支
书写适合用条件传送实现的代码
理解存储器性能
- 加载的性能
- 存储的性能
应用：性能提高技术
优化程序性能的基本策略：
- 高级设计。为遇到的问题选择适当的算法和数据结构。
- 基本编码原则。消除连续的函数调用，在可能时，将计算移到循环外。考虑有选择地妥协程序的模块性以获得更大的效率。消除不必要的存储器引用。引用临时变量来保存中间的结果。只有在最后的值计算出来时，才将结果存放到数组或全局变量中。
- 低级优化。展开循环，降低开销，并且使得进一步的优化成为可能。通过使用例如多个累积变量和重新结合等技术，找到方法提高指令级并行。 用功能的风格重写条件操作，使得编译采用条件数据传送。
确认和消除性能瓶颈
- 程序剖析
- 使用剖析程序来指导优化
- Amdahl定律
References:
Computer Systems: A Programmer’s Perspective 2E
