计算机系统-从应用程序到底层实现 课件 第28讲-性能优化-2

《计算机系统》优化程序性能下

篇《计算机系统》课程教学组2025年春季学期待优化代码combine1函数实现功能：对于已知数组v，循环遍历其所有元素，进行累加或累乘，最终结果赋值给*dest代码移动：combine2函数只计算一次vec_length(v)，并保存在一个变量中，在后续的循环中使用此变量代码移动：识别要执行多次但值不会改变的代码，将其移动到代码前部分，避免重复求值改进循环效率：将vec_length移除循环外

因为向量的长度不会随着循环的进行而改变减少函数调用：combine3函数措施：消除循环中的函数调用使用局部变量：combine4函数采用局部变量存储：若CPU工作寄存器数量较多，当局部变量不多，可直接放在寄存器内，而不是放到内存里，这样也提高了执行速度可以存放在SP（Stackpointer）寄存器，当然也可存在CPU的通用寄存器中优化需要软硬兼施DavidPatterson-ANewGoldenAgeforComputerArchitecture:History,ChallengesandOpportunities冯•诺伊曼结构combine2，3，4的优化均不依赖于机器的特性若更进一步优化，需要先了解一下计算机体系结构与处理器的知识JohnvonNeumann冯•诺伊曼结构五大部件控制器（分析和执行机器指令并控制各部件的协同工作）运算器（根据控制信号对数据进行算术运算和逻辑运算）存储器（内存存储中间结果，外存存储需要长期保存的信息）输入设备（接收外界信息）输出设备（向外界输送信息）冯•诺伊曼结构设计特点：

处理单元包含算术逻辑单元和处理器寄存器

控制单元包含一个指令寄存器和程序计数器

内存存储数据与指令

外部大容量存储

输入与输出机制存储程序计算机：Astored-programcomputerisacomputerthatstoresprograminstructionsinelectronicmemory15236798以存数指令为例4完成一条指令的过程CU控制单元主存储器数据寄存器地址寄存器存储体CPU程序计数器控制器指令寄存器…运算器乘商寄存器累加器算术逻辑运算单元操作数寄存器I/O设备指令流水线

经典五段

取指令(IF)：根据PC的值从存储器取出指令指令译码(ID)：产生指令执行所需的控制信号取操作数(OF)：读取存储器操作数或寄存器操作数执行(EX)：对操作数完成指定操作写回(WB)：将操作结果写入存储器或寄存器想一想，如果每条语句完全顺序执行？指令流水线基础

经典五段流水线

取指令(IF)：根据PC的值从存储器取出指令指令译码(ID)：产生指令执行所需的控制信号取操作数(OF)：读取存储器操作数或寄存器操作数执行(EX)：对操作数完成指定操作写回(WB)：将操作结果写入存储器或寄存器

如果各指令之间不存在相关性，那么它们在流水线中是可以同时执行的，这种指令间潜在的重叠就是指令级并行（Instruction-LevelParallelism,ILP）结构相关（也称为名相关）指不同指令同时访问相同硬件资源，但这些指令间不存在数据流。

在冯·诺依曼存储结构中，数据和程序放在同一存储器，若此时一条指令要读或写数据，而刚好取指单元要取指令，就出现结构相关（访存冲突）结构相关指令间相关性数据相关数据相关

指某条指令的操作数依赖前一条或前几条指令的运行结果写后读相关（RAW，ReadAfterWrite）A=B+CD=A-C//在数据A上写后读指令间相关性数据相关数据相关

指某条指令的操作数依赖前一条或前几条指令的运行结果写后读相关（RAW，ReadAfterWrite）A=B+CD=A-C//在数据A上写后读指令间相关性数据相关数据相关

指某条指令的操作数依赖前一条或前几条指令的运行结果写后读相关（RAW，ReadAfterWrite）A=B+CD=3*A//在数据A上写后读读后写相关（WAR，WriteAfterRead）A=B+CB=D*2//在数据B上读后写指令间相关性数据相关数据相关

指某条指令的操作数依赖前一条或前几条指令的运行结果写后读相关（RAW，ReadAfterWrite）A=B+CD=3*A//在数据A上写后读读后写相关（WAR，WriteAfterRead）A=B+CB=D*2//在数据B上读后写写后写相关（WAW，WriteAfterWrite）A=B+CA=D*2//在数据A上写后写指令间相关性数据相关数据相关

指某条指令的操作数依赖前一条或前几条指令的运行结果写后读相关（RAW，ReadAfterWrite）A=B+CD=3*A//在数据A上写后读读后写相关（WAR，WriteAfterRead）A=B+CB=D*2//在数据B上读后写写后写相关（WAW，WriteAfterWrite）A=B+CA=D*2//在数据A上写后写指令间相关性控制相关控制相关

是对PC寄存器的RAW相关问题取指阶段需要读PC的内容但分支语句会在执行阶段计算出新的转移地址写入PC寄存器，

那么当分支条件满足的时候，就出现：下一条指令读PC寄存器（取指阶段）早于分支语句写该寄存器（执行阶段）的情况。

指令间相关性控制相关控制相关

是对PC寄存器的RAW相关问题取指阶段需要读PC的内容但分支语句会在执行阶段计算出新的转移地址写入PC寄存器，

那么当分支条件满足的时候，就出现：下一条指令读PC寄存器（取指阶段）早于分支语句写该寄存器（执行阶段）的情况。

执行时间：！提升预测准确性10.36800msvs.3.0000ms！提升预测准确性流水技术小结流水线可以增加吞吐量相关性又会导致性能下降数据与指令分开避免访问（存）冲突（结构相关）数据前递、顺序重排等降低数据依赖（数据相关）分支预测降低猜错概率，减少控制相关带来的流水停顿完全避免流水线的阻塞几乎不可能的理解现代处理器：分析combine4现代处理器结构很复杂：实际的处理器操作是同时对多条指令求值（多条指令可并行执行），而程序员所编写的程序也是按顺序编写的，看到的机器程序指令是顺序执行的当前代码性能瓶颈在循环内部分理解现代处理器：分析combine4以float的乘法为例的汇编代码理解现代处理器：分析combine4将4条指令扩展为5个步骤（如下图所示）：mulss指令的两个操作：load指令加载rax的值（data数组）与rdx的值（i）并将计算的结果直接传入到mul指令中与xmm0(存储acc值)进行乘法运算并将结果写回到xmm0(存储acc值)中理解现代处理器：分析combine4

图(a)：重画前页数据流图，使得结果看起来更清晰一些图(b)：删除了白色区域（无相关项）和没有修改寄存器的部分，只留下了循环执行过程中对寄存器xmm0和rdx迭代进行的一系列操作1）load指令加载rax的值（data数组）与rdx的值（i）并将计算的结果直接传入到mul指令中；2）与xmm0(存储acc值)进行乘法运算并将结果写回到xmm0(存储acc值)中。

理解现代处理器：分析combine4左边的mul链条会成为关键路径若要再一步进行优化，那就只有对关键路径进行优化了，关键路径分析：两个相关链条分别是：1）mul对acc的操作；2）add对i的操作循环展开：真正意义上的进化（combine5）变化1：将for循环展开2次，每次循环处理2个元素；将limit定义为length-1，以防止越界（因为数组的长度不一定是2的倍数）变化2：加入一个新的for循环，对limit外的元素进行处理我们假设有集合a={1,2,4,5,7,9,10,12,16}，使用combine5函数进行求和运算：模拟计算机的执行顺序，一步步在草图上分析combine5代码实现的功能循环展开：真正意义上的进化（combine5）对于浮点数：CPE无变化

虽然展开了两次循环，但是依然有n个乘法操作，迭代次数减半，（关键路径无变化）对于整数：有性能优化循环展开：真正意义上的进化（combine5）延迟界限：任何严格顺序完成合并运算的函数所需最小CPE在下一条指令执行之前，当前指令必须结束当代码中的数据相关性限制了处理器利用指令集并行的能力时，延迟界限会限制程序的性能吞吐量界限：CPE的最小界限刻画了处理器功能单元全力运行时的原始计算能力如：处理器具有两个能同时做乘法的单元，对于只有1次乘/元素的循环而言，此时的吞吐量界限就是0.5吞吐量界限是程序性能的终极界限

提高并行性：K路并行（combine6）变化：循环（12行处）的代码中，加入两个累积变量：acc0和acc1两次循环展开两路并行

提高并行性：K路并行（combine6）变化：循环体内，

使用了两个累积变量：acc0和acc1两次循环展开两路并行

提高并行性：K路并行（combine6）combine5:

acc=(accOPdata[i])OPdata[i+1]转变为

combine6:acc0=acc0OPdata[i]以及acc1=acc1OPdata[i+1];

提高并行性：K路并行（combine6）引入新变量acc0和acc1，(多个累积变量)分配到不同寄存器xmm0和xmm1在每次迭代中实现并行处理提高并行性：K路并行（combine6）K次循环展开+K路并行强强联合

提高并行性：重新结合变换（combine7）还有没有其他方法能打破顺序相关而提高效率？

提高并行性：重新结合变换（combine7）还有没有其他方法能打破顺序相关而提高效率？相比combin5,combine7实现了重新结合变换combine5中的acc=(accOPdata[i])OPdata[i+1]变成了combine7中的acc=accOP（data[i]OPdata[i+1]）提高并行性：重新结合变换（combine7）combine5：

loadmul顺序执行，必须等到第一个loadmul执行完成以后才能进行第二次load和mul操作在combine7：第一个mul通过两个load指令将i和i+1的乘积计算出来，然后交给第二个mul将乘积累积到xmm1（acc）中combine5vs.combine7提高并行性：重新结合变换（combine7）“重新结合变换”后的combine7的数据流只有一条关键路径，而且包含n/2个操作每次迭代的第一个乘法不需要等待前一次迭代的累积值就可以执行关键路径提高并行性：重新结合变换（combine7）乘法运算在combine7中得到显著提高；编译器可以自动对“加法”进行“重新结合变换”，gcc觉得可以做（并不总是做）优化，就会做这种优化；对于浮点数，编译器不会尝试对浮点运算做重新结合，因为这种结合不会保证结果是成功的重新结合变换有时候能够减少计算中关键路径上操作的数量，但并不是总是有效的方法，K次循环展开，K路并行是更可靠的方法优化小结使用C代码和标准编译器，性能提高10倍以上关键路径明确了执行所需时间的基本下限功能单元的吞吐界限也是执行时间的下限

理解存储器性能：读写相关至此，已完成了从combine1到combine7的进化，带来了至少10倍以上的效率提高；循环展开、并行累积值在多个变量中，是可靠的提高程序性能的方法还有那些限制因素影响程序的性能？当待处理的数据小于1000个元素的向量，数据量不会超过8000个字节，这些内容都会存放在高速缓存(Cache)存储器中，可方便快速访问高速缓存中的加载和存储操作对性能影响明显，充分利用高速缓存来编写高效率的代码加载(load):

从存储器读到CPU寄存器存储(store)：从寄存器写入存储器

理解存储器性能：读写相关加载对性能的影响：加载操作的延迟函数list_len计算链表的长度理解存储器性能：读写相关在第3行中，使用movq指令，加载值到rdi寄存器中，而加载操作又依赖于rdi来计算加载的位置即，必须要等到前一次加载完成才能进行下一次循环ls=ls->next的对应汇编代码理解存储器性能：读写相关对于CPU来说，它是控制中心与运算中心存储操作（

寄存器向存储器写数据）：理论上不影响寄存器的值加载操作（

寄存器从存储区读数