1

我有一个具有顺序和并行变体的随机程序。该程序的本质是它的运行时间根据它的“运气”而变化很大。它通常以看似几何分布的模式在 1 秒到 2 分钟之间取值。并行变体显示出具有不同数字的类似行为。

在这种情况下，衡量并行加速的“好”方法是什么？我有可能只使用测量值的平均值/中值作为“运行时间”的代表

我将如何解释这种方法，是否有（统计/数学）更好的方法来计算加速？

编辑：感谢 user3666197，它指出了获得良好数据所必需的一些非常重要的技术细节。我已经完成了这项作业，并想澄清我的问题。

我使我的基准测试过程尽可能可靠：

  • 基准测试是用种子运行的，结果是可重现的。
  • 每个配置都在脚本中使用不同的种子重复多次（~400 次）

我的问题仍然存在：如何计算该程序的加速比。

我做了什么：

平均顺序运行时间约为 8.38，中位数为 4.8，这是一个很大的差异。对于 2 个线程，平均运行时间为 4.36，而中值运行时间为 2.42。如果我将顺序除以并行，我会得到 1.92（平均值）和 1.992（中值）的加速。对于 4 个线程类似：意味着：2.25 运行时间和 3.72 加速，中位数：1.12 中位数和 4.3 加速（超线性）。8 个线程存在类似的数字。

我尝试以不同的方式可视化数据。情节

直方图显示了使用各种线程的运行时间分布，右侧的箱线图也是如此。可以看出一些加速是可见的。

如果我根据种子对测量值进行配对，我会得到成对的时间：顺序时间和并行时间。我的第一个想法是通过计算回归线的斜率来计算加速，但是，回归线似乎没有正确“总结”数据并且价值有限。在右下角的图中，只显示了 4 个线程的点。

4

2 回答 2

0

如何衡量并行加速与纯[SERIAL]代码？

始终是定量和系统的。

这至少意味着：

1) 使用所有系统步骤来控制测试重复性
2) 将苹果与苹果进行比较，包括。随机化器的受控种子设置
3) 最好，将所有测试电池生成为脚本化、可自动重复的实验
4) 在测试的 UUID#-可区分日志中记录性能（整体和局部时间段） 5) 收集相当 1E+ 3 ~ 1E+4 规模的试运行群体，而不仅仅是几个单位的个体试验

鉴于您的解决方案已经以纯 [SERIAL] 代码执行方式和其他方式实现，[CONCURRENT]甚至是[PARALLEL]，最准确的步骤是比较端到端测试持续时间。

使用单调时钟是很常见的，它比-domain具有更好的~ [us]分辨率。[TIME]

有关内部性的更多详细信息，最好查看重新制定的阿姆达尔定律和对并行加速初始、无约束资源使用公式的批评。

于 2018-03-01T18:30:09.290 回答
0

我建议您根据足够大的一组测量的运行时间的算术平均值来计算加速。确保正确传达数字代表的内容。可能很难确保您有足够大的设置测量值来以一定的置信度计算适当的平均值，尤其是因为您的样本不是正态分布的。包括你关于分布和置信度的发现。在计算加速比之前，请务必先总结运行时。

Torsten Hoefler 和 Roberto Belli有一篇出色的论文详细介绍了您的问题。特别是第 2.1.1 和 3 节。

于 2018-03-05T11:42:34.663 回答