大概5年前, 我在Stack overflow上看到一个问题: Why is processing a sorted array faster than processing an unsorted array?
问题已经是11年前的了,这里面最高赞的那个答案, 用CPU的分支预测解释了这个问题. 这里简单描述下: CPU每次会加载一段而非一条语句,如果分支判断错误,则需要回退重新加载新的语句执行. 这产生了消耗, 如果CPU在分支判断中的命中率越高, 则程序执行的效率越快. 因此CPU会作分支预测优化, 以提高每次分支预测的命中率.
分支预测也不用想的高大上, 可能就是根据之前的数据找到潜在的规律或者模式来预测, 举个例子: 如果发现前面90%是True, 10%的False, 那么只需要每次都预测为True, 就有90%的正确率了不是吗?
根据分支预测策略, 可以再程序上做出优化: 比如将True和False的判断更规律一些. 比如一个循环判断1-100的数是否为偶数的例子:如果按照1,2,3,4的规律循环,那么结果是FTFTFTFT,但是如果先按照1,3,5,7…99顺序,2,4,6,8…100,结果是FFFFFFFTTTTTTT. 后者对于CPU的分支预测来更为容易,因此会有更高的预测正确率.
那么今天想了解的关键的问题是:
CPU如何做分支预测?
分支预测的算法和策略依赖于历史数据, 越好的策略依赖的历史数据就越多,所以使用越少的历史数据,减少额外空间使用量的同时, 提高分支预测的正确率,是策略的发展方向.
静态分支预测
静态分析预测约等于没有分析, 因为不使用任何的额外空间存储历史数据, 只能假定一直为True或者False. 因此对于之前举的1-100判断奇偶数的例子, 有50%的正确预测率.
动态分支预测
动态分支预测则会使用额外空间存储历史数据.比如使用1个bit的1-bit prediction和2个bit的2-bit prediction.
1-bit prediction
1个bit可以记录两种状态(T或者F), 因此1-bit prediction可以根据前一次的记录来调整对下一次分支的预测. 还是举个例子,如果策略是:将分支预测调整为前一次的判断结果.那么对于1-100的奇偶数的例子,这种策略将是灾难性的..因为一次都没有正确. 但是如果事先已经按奇偶数排好顺序了,那么就能达到98%的正确率.
2-bit prediction
2bit可以记录四种状态(TT,TF,FT,FF), 因此策略可以更细致. 假设现在的策略是:只有碰到TT或者FF且与当前分支结果不一致时才更换预测结果,否则维持原本的分支判断. 那么以1-100的奇偶数判断例子来看,假设一开始预测为T,那么因为结果是TFTFTFT,因此会保持一致是T的预测,这样会有50%的正确率. 如果是事先将数字按奇偶数排好序,那么会有98%的正确率. 从数学期望来看, 2-bit下相比1-bit下的分支预测又优化了
除了这两种, 还有许多动态分支预测的策略, 例如两级自适应预测器, 局部分支预测, 全局分支预测等等, 这里就不做详细介绍了.因为策略核心的本质已经在开头说明.
CPU的分支预测策略发展到什么阶段了?
我其实想知道的是, 在神经网络算法,机器学习和AI发展的当下, CPU分支预测能否使用这些算法, 让开发者们不用在代码层面思考CPU级别的优化..
在互联网上,我查找了一些论文和资料
例如知乎上:
google 搜索deep learning in branch prediction的靠前的一些论文:
A Survey of Deep Learning Techniques for Dynamic Branch Prediction
Branch Prediction with Multi-Layer Neural Networks: The Value of Specialization
总的来说,深度学习在CPU分支预测方面已经有一些理论和研究, 但是似乎还并没有在实际生产中使用. 并且, 使用深度学习来做分支预测的一个弊端正如前文提到的: 更多的数据需求会导致CPU额外存储空间的消耗, 这对本就资源珍贵的CPU核心来说是一个考验.
最后
虽然说能在写代码的时候考虑到这点是极好的, 但要求每一个写代码的人去注意这些几乎是不可能的, 更好的还是期待CPU继续更好的发展. 就像SQL一样, 让SQL自己进化优化选择最佳执行路径. 减少开发者的负担才是未来.
