代码优化之条件分支预测

《代码优化之条件分支预测》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、代码优化之优化条件分支预测关键词:代码优化，条件分支，饱和，MMX，CMOV，掩码条件分支是编程中经常使用的基本操作，然而在某些时候它确可能带来严重的性能问题。当前的CPU都能对条件分支做预测(动用了庞大的晶体管资源)，如果分支预测正确，那么条件指令一般只需要花费一个CPU周期，而如果预测错误，那么将可能花费几十个CPU周期。本文将讨论条件分支的一些有效优化方法。文章为收集加经验编辑而成的文章，对优化条件分支做了较全面的阐述。文章假定的CPU为x86，示例代码为CC++。A．什么是分支?处理器中分支预测器设

2、计的本质是在对分支指令行为认识的基础上，提出分支指令的预测机制，从而减少分支惩罚，也就是分支预测失败时导致的流水线清空。一组分支指令组合起来就成为程序的分支行为。分支是编程语言中的常见结构。分支可以分为条件分支和非条件分支。条件分支举例:条件判断:if(a>255)a=255;elseif(a<0)a=0;循环:for(i=0;i<1000;++i){...;}while(!bOk){bOk=...;}...对应汇编指令的jnz,jg等等非条件分支举例:函数调用(call)、函数返回(returnret)、

3、软件中断(int3)、直接跳转(jmp)...非条件分支又可以进一步分为立即分支指令、间接分支指令和返回分支指令。立即分支指令就是分支的地址就在分支指令中，一般都是直接跳转，比如跳转（jump）这类指令；间接分支就是分支的目标地址不在分支指令中，而是从其他寄存器中取得；返回型分支的分支目标地址是从链接寄存器（Linkregister）或者堆栈中得到，一般是程序返回使用。统计分析程序结果表明，分支指令中72%是条件分支，17％是无条件立即跳转指令，10％是返回指令，1％是间接分支指令。其中立即分支跳转可以采用B

4、TB（BranchTargetBuffer，分支预测缓冲区）这种方式精确预测，返回型跳转可以采用返回地址栈(RAS1)精确预测，间接分支跳转的预测一直没什么好的办法。所以分支预测大量的工作是进行条件分支预测。B．CPU分支预测错误的惩罚由来流水线是指在程序执行时多条指令重叠进行操作的一种技术。指令流水执行是将指令执行分成几个子过程，每个子过程对应一个工位，称为流水级或流水节拍，这个工位在计算机里就是可以重叠工作的功能部件，称为流水部件。这些不同的功能部件同时处理不同指令的不同子过程。流水级一个连着一个形成一个

5、流水线，一条指令流过所有的流水级，就完成了他的任务。他通过提高各流水部件的利用率提高指令的平均执行速度。我们先对流水线的级数与其周期的关系给出一个公式，一个k级流水线，处理n个任务总共需要花费“k+(n-1)”个周期，这是因为先是处理第一个任务就需要k个时钟周期，k个周期后流水线被装满，剩余n－1个任务只需n-1个周期就能完成。如果同样数量的n个任务不采用流水线处理，那么就需要n＊k个周期，我们把两者做比，得到另一个概念，叫做流水线加速比C，所以C＝n*k/[k+(n-1)]，当n远远大于k时，C的值趋进于k

6、，也就是说，理论上k级流水线几乎可以提高k倍速度，但这仅限于理论。为了加快CPU的处理频率，现代CPU都设计了多级流水线，有的甚至有20级以上；当CPU遇到分支跳转指令的时候，会做一个预测，把预测的分支代码载入流水线，当发现预测错误的时候，需要清空流水线，重新载入正确的分支到流水线。那么预测错误的代价周期数至少应该和流水线长度相当。然而考虑到各级的缓存失效、指令解码等等，实际损失的周期数有可能是流水线长度的几倍！对于非条件分支，一般来说CPU都能得到相当高的预测准确率，我们主要来讨论一下条件分支的预测。有人可

7、能会说，当CPU遇到条件分支时不做预测不就没有预测错误的惩罚了吗?这种流水线空着的惩罚实质和每次都预测错误然后清空流水线的代价相当，退一步说就算每次随机选择一个分支来执行也有50%的收益。C．需要优化的条件分支当前的CPU对各种简单的条件分支模式都能做出很的预测，比如奇偶模式：for(inti=0;i<1000;++i){if(a%2==0)do0();elsedo1();}而对于随机的分支模式，再好的预测器也不可能做出好的预测；我们要优化条件分支，这些分支代码应该满足：该分支处于时间热点上，并且分支预测错误

8、率较高；这样我们才能得到优化的收益(intel的VTune工具可以采样分支预测错误率)。1．把条件分支移动到热点外比如前面的那个奇偶循环模式，假设CPU不能正确预测，那么可以尝试改写为两个for循环，一个处理偶数，一个处理奇数。一些图像处理算法里(比如模板运算卷积运算形态学运算等)，经常需要判断边界像素点，进行特殊处理，可以考略的优化方案是把边界区域和内部区域分开处理，或者条件允许的话，可以扩大