Intel TBB flowgraph overhead

Question

Intel TBB flowgraph overhead

multithreadingparallel-processingintelparallelism-amdahltbb-flow-graph

3

这里是我对英特尔TBB流图性能基准测试的尝试。以下是设定：

一个广播节点向N个后继节点发送continue_msg （即一个 broadcast_node<continue_msg>）
每个后继节点执行一项需要t秒的计算。
串行执行这些计算所需的总时间为Tserial = N * t
如果所有核心都在使用，理想的计算时间为Tpar(ideal) = N * t / C，其中C是核心数。
加速比定义为Tpar(actual) / Tserial
我在一台16核PC上使用gcc5测试了代码。

以下是以单个任务（即主体）处理时间为函数的加速比结果：

t = 100 microsecond  ,   speed-up =  14
t  = 10 microsecond  ,   speed-up =   7
t  =  1 microsecond  ,   speed-up =   1

对于轻量级任务（计算时间小于1微秒的任务），并行代码实际上比串行代码更慢。

以下是我的问题：

1) 这些结果是否符合英特尔TBB基准测试结果？
2) 如果有成千上万个任务，每个任务仅需要少于1微秒的时间，是否有比流程图更好的编程范例？

- motam79

3个回答

2

广告1)

这是一个很好的例子，细节确实很重要。Tpar(ideal) = N * t / C更像是一个愿望，而不是现实中可能发生的事情。

英特尔确实在将其硬件专业知识重新制造成软件工具方面做得非常出色，可以从他们对自己处理器微架构魔法的超级详细了解中受益。没有人能够为英特尔CPU做得比他们更好，也没有人能够轻松地将其移植，以在其他CPU微架构上提供任何类似的性能（因此请注意您实际使用的CPU，尤其是如果它被云抽象化）

为什么要超额开销Amdahl定律？

为什么？因为这些开销决定的不仅仅是核心数量。

问题在于，随着“有用”负载大小变得越来越小，开销（即使是像TBB这样的超级优化工具中那些非常小的开销） - 这些开销总是累积到问题计算图的纯[SERIAL]部分。

因此，随着我们在[并行]负载中变得越来越小，每个核心调度的设置和终止实际上会产生一些非零成本。在某个时刻，这些额外开销的总和将比仅适用于净[并行]计算路径的线性持续时间的反比例因子1 / numCOREs的任何“下一个”收益更高，但是所有这些附加开销都会快速延长[串行]计算路径，超过任何不断增长的numCOREs可以补偿的速度提升增长速度低于<<1x。证毕。

广告2)

这款游戏是在上述游乐场设置中的，是一款最小疼痛游戏。

假设想要加速约~ 4,000 CPU uops ~ <= 1 [us]，如果想要实现此目标，则不能花费任何延迟和附加开销的时间，前提是最终加速度仍然至少为>= 1x

如果我们不相信童话故事，寻找方法是为PoC原型设计获取FPGA，为生产级部署获取ASIC / SoC。

如果您的项目经济无法承受所有相关成本，那就别指望免费得到任何魔法。它总是有代价的。但是，如果您的业务领域或研究资金能够应对，这是一个可行的方向。

一个额外的提示：向量化代码可能会在某些CPU上崩溃（最好避免这种情况）：

在量化建模中，性能就是金钱，因此让我分享一个最近的已知问题，来自于微型负载的极度紧密的性能调整（涉及汇编语言）。希望它可以避免任何不必要的问题，如果您正在进行代码性能优化的量化建模工作。

英特尔超线程错误勘误表（SKZ7 / SKW144 / SKL150 / SKX150 / SKZ7 / KBL095 / KBW095）

使用AH、BH、CH或DH寄存器及其对应的更宽寄存器（例如AH的RAX、EAX或AX）的短循环，当同一物理处理器上的两个逻辑处理器都处于活动状态时，可能导致不可预测的系统行为，这只会在复杂的微体系结构条件下发生。 问题：
由于此勘误表，系统可能会遇到不可预测的系统行为。此勘误表可能会影响...客户操作系统。 参考资料：
https://caml.inria.fr/mantis/view.php?id=7452 http://metadata.ftp-master.debian.org/changelogs/non-free/i/intel-microcode/unstable_changelog https://www.intel.com/content/www/us/en/processors/core/desktop-6th-gen-core-family-spec-update.html https://www.intel.com/content/www/us/en/processors/core/7th-gen-core-family-spec-update.html https://www.intel.com/content/www/us/en/processors/xeon/xeon-e3-1200v6-spec-update.html https://www.intel.com/content/www/us/en/processors/xeon/xeon-e3-1200v5-spec-update.html https://www.intel.com/content/www/us/en/products/processors/core/6th-gen-x-series-spec-update.html

- user3666197

2

请问什么是“Ad”？ - Mark Setchell

:o) 这是我在60年后第一次听到这个词。经典的拉丁遗产 - 在教育中经常使用，也常见于像“ad-hoc”，“ad absurdum”，“ad informandum”，“ad infimum”这样的术语中。 - user3666197

所以你只是在使用它的拉丁意义上的“朝向”或“朝着”的意思 - 抱歉，我没有想到会用到拉丁语。我必须承认我也不知道“ad infinimum”的意思 - 对我来说听起来像一个超重的母亲。 - Mark Setchell

数学，初等术语 {上确界，下确界，..} N/P。我每天都听到它，所以你的第一个问题确实让我有些措手不及。 - user3666197

2

@Richard已经给出了正确的答案（TBB教程讨论了调度开销摊销的概念），通常我会将此作为评论留下，但我想补充一点。

TBB对任务使用“贪婪调度”。如果先前任务的执行创建了一个任务（技术上，如果任务返回任务指针），那么该任务是在线程上运行的下一个任务。这有两个好处：

1. 上一个任务可能已经加载或生成了下一个任务正在使用的数据，有助于提高数据局部性。 2. 我们跳过了选择要运行的下一个任务的过程（无论它是否在本地线程的队列中或者是否可以从另一个线程中窃取）。这大大减少了调度开销。

tbb::flow_graph使用相同的思路；如果一个节点有一个或多个后继节点，在其执行完成后，其中一个后继节点将被选择为下一个要运行的节点。

缺点是，如果您想更改此行为（按“广度优先”而不是“深度优先”顺序执行节点），则必须跳过一些麻烦。这也会导致调度开销和局部性损失。

- cahuson

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Richard · Accepted Answer

并行计算的开销

你的成本模型是错误的。

理想的并行计算时间为：

Tpar(ideal) = N * t / C + Pstart + Pend

Pstart表示启动并行处理所需的时间，Pend表示完成并行处理所需的时间。通常情况下，Pstart需要数十毫秒的时间。

不知道您是否熟悉OpenMP（虽然了解它是一件好事），但对于我们来说，它是一种将工作分配给团队线程的线程模型。以下图表显示了某些命令与线程团队大小相关的开销：

结论是启动并行处理（parallel for）可能很昂贵，并且随着线程数量增加而增加。结束并行处理（barrier）也有类似的成本。

实际上，如果您查看TBB的教程，第3.2.2节（“自动块划分”）中写道：

注意：通常，循环至少需要花费100万个时钟周期才能使parallel_for提高其性能。例如，在2 GHz处理器上至少需要500微秒的循环可以从parallel_for中受益。

实现更快的速度

加速此类代码的最佳方法是仅在存在大量操作和/或调整执行工作的线程数量，以便每个线程都有足够的工作量时才并行执行操作。在TBB中，可以通过以下方式实现类似的行为：

#include <tbb/parallel_for.h>

// . . .
if(work_size>1000)
  tbb::serial::parallel_for( . . . );
else
  tbb::parallel_for( . . . );
// . . .

您需要调整的是1000这个数字，使其足够高，以便从并行性中获得收益。

您还可以减少线程数，因为这会在一定程度上减少开销：

tbb::task_scheduler_init init(nthread);

TBB 还可以执行动态负载平衡(详见这里)。如果你期望循环迭代/任务的运行时间分布广泛，那么这会很好，但如果预期运行时间相同，则会造成不必要的开销。我不确定 TBB 是否具有静态调度功能，但值得研究一下。

如果人们在没有强烈承诺使用 TBB 的情况下到达这里，在 OpenMP 中，您可以这样做：

#pragma omp parallel for if(work_size>1000) num_threads(4) schedule(static)