关键词：
【中文标题】在随机算法中测量并行加速【英文标题】：Measure parallel speedup in randomized-algorithms 【发布时间】：2018-03-01 13:01:58 【问题描述】：我有一个包含顺序和并行变体的随机程序。该程序的本质是它的运行时间根据它的“运气”而变化很大。它通常以看似几何分布的模式在 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 个线程存在类似的数字。
我尝试以不同的方式可视化数据。 Plots
直方图显示了使用各种线程的运行时间分布，右侧的箱线图也是如此。可见一些加速是可见的。
如果我根据种子配对测量值，我会得到成对的时间：连续时间和并行时间。 我的第一个想法是通过计算回归线的斜率来计算加速，但是，回归线似乎没有正确“总结”数据并且价值有限。在右下角的图中，只显示了 4 个线程的点。
【问题讨论】：
我使用 unix/usr/bin/time 命令测量时间。但是，使用任何其他指标不会有太大变化：程序可能很幸运能够快速找到解决方案，或者可能需要更多时间来完成基于播种的任务。
【参考方案1】：
我建议您根据足够大的测量集的运行时间的算术平均值来计算加速比。确保正确传达数字代表的内容。可能很难确保您有足够大的设置测量值来以一定的置信度计算适当的平均值，尤其是因为您的样本不是正态分布的。包括你关于分布和置信度的发现。在计算加速比之前，请务必先总结运行时。
有一个很好的paper by Torsten Hoefler and Roberto Belli 详细介绍了您的问题。特别是第 2.1.1 和 3 节。
【讨论】：
算术平均值真的是正确的度量吗？请注意，在我的情况下，它是中位数的两倍左右。其他指标甚至返回其他值。哪一个是“最佳”加速数，为什么？ 将其视为将问题转换为 N 次执行的加速。 N 次执行的总时间。这个时间的分布要窄得多，因此适合比较和计算加速比。这个复合操作的加速与你通过平均运行时间计算它是一样的。如果串行/并行情况的分布不同，则中位数问题会更大。在特殊情况下可能会有其他指标的争论，但这是最通用的。在任何情况下，清楚地描述分布以及如何计算指标都很重要。【参考方案2】：如何衡量并行加速与纯[SERIAL] 代码？
始终做到量化和系统化。
这意味着至少：
1) 使用所有系统步骤来控制测试可重复性 2）比较苹果和苹果，包括。随机化器的受控种子设置 3) 最好，将所有测试电池生成为脚本化、可自动重复的实验 4) 在测试的 UUID#-distinguishable 日志中记录性能（整体和局部时间段） 5) 收集相当多的 1E+3 ~ 1E+4 大小的测试运行群体，而不仅仅是几个单位的个体试验
鉴于您的解决方案已经以纯 [SERIAL] 代码执行方式和其他一些[CONCURRENT] 甚至[PARALLEL] 方式实现，最准确的步骤是比较端到端测试持续时间。
使用单调时钟非常普遍，在[TIME]-domain 中具有比~ [us] 更好的分辨率。
有关内部性的更多详细信息，最好查看 re-formulated Amdahl's Law 和 parallel-speedup 初始无约束资源的批评使用配方。
【讨论】：
openmp并行编程应用—加速opencv图像拼接算法
...排斥的场合。OpenCV中使用Sift或者Surf特征进行图像拼接的算法。须要分别对两幅或多幅图像进行特征提取和特征描 查看详情
使用 OpenMP 进行并行加速
...nMP【发布时间】：2011-10-2805:30:08【问题描述】：我有两种测量指标的场景，例如计算时间和并行加速（sequential_time/parallel_time）。场景1：顺序时间测量：startTime=omp_get_wtime();forloopcomputationendTime=omp_get_wtime();seq_tim 查看详情
在 Macbook 中并行执行随机森林的小速度增益（使用 R，插入符号）
】在Macbook中并行执行随机森林的小速度增益（使用R，插入符号）【英文标题】：SmallspeedgainwithparallelexecutionofrandomforestinMacbook(usingR,caret)【发布时间】：2017-07-2319:12:52【问题描述】：我正在使用包caret和ranger拟合随机森林模型，... 查看详情
通过并行化加速随机数生成
】通过并行化加速随机数生成【英文标题】：Speedinguprandomnumbergenerationbyparallelizing【发布时间】：2021-12-2522:11:06【问题描述】：我需要使用来自标准正态分布的随机数创建许多大型numpy数组（4e6、100），我正在努力加快速度。我... 查看详情
水平集图像分割并行加速算法设计与实现(串行openmpcuda)——串行实现篇(代码片段)
本次水平集图像分割并行加速算法设计与实现包含：原理篇、串行实现篇、OpenMP并行实现篇与CUDAGPU并行实现篇四个部分。具体各篇章链接如下：水平集图像分割并行加速算法设计与实现——原理篇水平集图像分割并行加... 查看详情
bagging与随机森林算法原理小结
...依赖关系，可以并行拟合。本文就对集成学习中Bagging与随机森林算法做一个总结。 随机森林是集成学习中可以和梯度提升树GBDT分庭抗礼的算法，尤其是它可以很方便的并行训练，在如今大数据大样本的的时代很有诱惑... 查看详情
bagging与随机森林算法原理小结
...依赖关系，可以并行拟合。本文就对集成学习中Bagging与随机森林算法做一个总结。 随机森林是集成学习中可以和梯度提升树GBDT分庭抗礼的算法，尤其是它可以很方便的并行训练，在如今大数据大样本的的时代很有诱惑... 查看详情
bagging与随机森林算法原理小结
...依赖关系，可以并行拟合。本文就对集成学习中Bagging与随机森林算法做一个总结。 随机森林是集成学习中可以和梯度提升树GBDT分庭抗礼的算法，尤其是它可以很方便的并行训练，在如今大数据大样本的的时代很有诱惑... 查看详情
并行算法设计
...算与非数值计算同步算法和异步算法分布算法确定算法和随机算法并行算法的表达描述语言可以使用类Algol、类Pascal等。在描述语言中引入并行语句。并行算法的复杂性度量串行算法的复杂性度量最坏情况下的复杂度（Worst-CASECom... 查看详情
adam优化算法
...的学习速度和效果，Adam算法正为此而生！Adam优化算法是随机梯度下降算法的扩展式，进来其广泛的应用与深度学习的应用中，尤其是计算机视觉和自然语言处理等任务。本文分为 查看详情
数据与模型并行
...种常见的数据划分方法。其中，对于样本划分方法，又有随机采样和（全局/局部）置乱切分等方法。总体来说，进行数据划分时要考虑以下两个因素。一是数据量和数据维度与本地内存的相对大小，以此判断数据按照样本划分... 查看详情
Apache Spark：多机器学习算法的并行化
...行运行多种机器学习算法（朴素贝叶斯、人工神经网络、随机森林等）。1)使用10折交叉验证来验证每个算法B)在第二层机器学习算法 查看详情
在 Makefile 中随机化并行配方执行顺序
】在Makefile中随机化并行配方执行顺序【英文标题】：RandomizeParallelRecipeExecutionOrderInMakefile【发布时间】：2017-07-2516:08:35【问题描述】：我有一个包含大量子系统的makefile，并且能够使用-j标志构建它，以便它运行得更快并并行构... 查看详情
在并行程序中播种随机数生成器
】在并行程序中播种随机数生成器【英文标题】：Seedingrandomnumbergeneratorsinparallelprograms【发布时间】：2015-07-0311:10:38【问题描述】：我正在研究Python的多处理模块。我有两种情况：例如。1defFoo(nbr_iter):forstepinxrange(int(nbr_iter)):printr... 查看详情
如何在python中测量算法的运行时间[重复]
】如何在python中测量算法的运行时间[重复]【英文标题】：howtomeasurerunningtimeofalgorithmsinpython[duplicate]【发布时间】：2010-04-1812:01:18【问题描述】：可能的重复：Accuratetimingoffunctionsinpythonaccuratelymeasuretimepythonfunctiontakes我如何测量和... 查看详情
集成算法
...ion（说白了就是并行训练一堆分类器）最典型的代表就是随机森林啦随机：数据采样随机，特征选择随机森林：很多个决策树并行放在一起 构造树模型：由于二重随机性，使得每个树基本上都不会一样，最终的结果也会不一... 查看详情
有没有办法在并行随机森林构建过程中跟踪进度？
】有没有办法在并行随机森林构建过程中跟踪进度？【英文标题】：IsthereawaytotrackprogressduringparallelizedRandomForestbuilding?【发布时间】：2015-05-2101:47:03【问题描述】：我正在使用R的caret包为Coursera机器学习课程建模。我目前正在构... 查看详情
随机森林算法基础梳理(代码片段)
1.集成学习概念 在机器学习的有监督学习算法中，我们的目标是学习出一个稳定的且在各个方面表现都较好的模型，但实际情况往往不这么理想，有时我们只能得到多个有偏好的模型（弱监督模型，在某些方面表现的比较好... 查看详情