我目前正在分析二分查找的实现。使用一些特殊指令来测量，我发现代码的错误预测率约为20%。我想知道是否有办法检查由于这个问题可能会损失多少个周期。这是基于MIPS架构的。
4个回答
4
每次迭代您会损失 0.2 * N 个周期，其中 N 是在错误预测分支后清空流水线所需的周期数。假设 N = 10，则表示您每次迭代会损失 2 个时钟周期。除非您有一个非常小的内部循环，否则这可能不会对性能造成重大影响。
- Paul R
3
2嗯...如果每次迭代中有很多20%的错误预测分支，时间可能会开始累加 ;) - Goz
@Goz：是的，说得好 - 我想当我说循环或迭代时，我真正意思是一个带有部分可预测分支的块，但在循环中可能会有多个这样的块。 - Paul R
这就是问题所在。循环累积得非常快，而当你每秒只有3亿次时，它们变得更加珍贵。 - Matt Wamboldt
1
在您的CPU文档中查找此信息。如果无法找到特定信息，则CPU流水线的长度是一个相当好的估计。
考虑到它是MIPS和300MHz系统，我猜测它的流水线应该相当短。可能是4-5个阶段，因此每次错误预测的成本可能是3-4个周期，这可能是一个合理的猜测。
- jalf
1
在顺序执行的CPU上，你可以通过将错误预测数与错误预测成本（通常是管道的某个部分的函数）相乘来计算近似的错误预测成本。
然而，在现代乱序执行的CPU上，这样的一般计算通常是不可能的。可能有大量指令正在运行，只有一些指令因错误预测而被清除。周围的代码可能受到一个或多个依赖指令链的延迟限制，也可能受到像执行单元、重命名吞吐量等资源的吞吐量限制，或者处于两者之间的某个位置。
在这样的核心上，即使借助性能计数器的帮助，误判的惩罚成本也很难确定。您可以找到专门探讨此主题的整篇论文：其中一篇发现惩罚大小在整个基准测试中平均范围从9到35个周期不等；如果您查看一些小的代码片段，则范围将更大：零惩罚易于证明，并且您可以创建一个惩罚在100个周期以上的场景。
那么，在二分搜索中确定误判成本该怎么办呢？嗯，一个简单的方法就是控制误判数量并测量差异！如果您设置基准测试输入具有各种行为，从始终遵循相同的分支模式开始，一直到具有随机模式，您可以绘制误判计数与运行时退化之间的关系图。如果您这样做了，请分享您的结果！
然而，在现代乱序执行的CPU上，这样的一般计算通常是不可能的。可能有大量指令正在运行，只有一些指令因错误预测而被清除。周围的代码可能受到一个或多个依赖指令链的延迟限制，也可能受到像执行单元、重命名吞吐量等资源的吞吐量限制，或者处于两者之间的某个位置。
在这样的核心上，即使借助性能计数器的帮助，误判的惩罚成本也很难确定。您可以找到专门探讨此主题的整篇论文：其中一篇发现惩罚大小在整个基准测试中平均范围从9到35个周期不等；如果您查看一些小的代码片段，则范围将更大：零惩罚易于证明，并且您可以创建一个惩罚在100个周期以上的场景。
那么，在二分搜索中确定误判成本该怎么办呢？嗯，一个简单的方法就是控制误判数量并测量差异！如果您设置基准测试输入具有各种行为，从始终遵循相同的分支模式开始，一直到具有随机模式，您可以绘制误判计数与运行时退化之间的关系图。如果您这样做了，请分享您的结果！
1数百条指令在现代大型核心中飞行，例如x86、ARM和POWER架构。
- BeeOnRope
0
查看您的规格以获取该信息，如果失败，请在程序外部运行一亿次并计时（使用秒表或其他工具）。然后再进行一次不出错的运行并进行比较。
- Michael Dorgan
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接