英特尔 TBB 流程图开销
Intel TBB flowgraph overhead
这是我尝试对英特尔 TBB 流程图的性能进行基准测试。
这是设置：
- 一个广播节点发送
continue_msg给N个后继节点
(一个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 微秒时，是否有比流程图更好的范例？
广告 1)
这是一个很好的例子，细节很重要。 Tpar(ideal) = N * t / C与其说是现实中可能发生的事情不如说是愿望。
英特尔在将其硬件知识重新构建为发布软件工具方面确实做得很好，这可以从他们对自己的处理器微体系结构魔法的超详细知识中受益。没有其他人可以为英特尔 CPU-s 做得更好，没有其他人可以轻易移植它，以在其他一些 CPU 微架构上提供任何类似的性能（所以要小心你的实际 CPU , 如果它是云抽象的则更多 )
为什么overhead-strict Amdahl's Law?
为什么？因为这些开销决定的不仅仅是核心数量。
重点是，随着 "usefull"-payload 大小变得越来越小，开销（即使是那些非常小的开销，就像在超级优化的工具中一样，就像毫无疑问的 TBB 一样）——这些开销总是累加到问题计算图的纯[SERIAL]部分。
因此，随着我们在 [PARALLEL] 有效载荷中继续变得越来越小，它们的主要非零成本 { setup | termination } 每核调度实际成本，将在某个时刻变得更高，比任何 "next" 受益于反比例因子 1 / numCOREs 仅适用于网络的线性持续时间 [PARALLEL]-计算路径，但所有这些附加开销加起来并扩展 [SERIAL]-计算路径的速度比任何增长的 numCOREs 可以补偿的速度都快，并且 加速增长低于 << 1x.
Q.E.D.
广告 2)
这个是在上面的游乐场设置中，一个最小痛苦的游戏。
鉴于一个人想要加速大约 ~ 4,000 CPU uops ~ <= 1 [us]，一个人 绝不能在所有延迟上花费一纳秒 并且如果尝试这样做会增加开销，假设最终加速仍至少保持 >= 1x
如果我们不相信童话，那么寻找 FPGA 进行 PoC 原型设计和ASIC/SoC 进行生产级部署。
如果您项目的经济无法承受所有相关成本，那就忘记免费获得任何魔法吧。它的成本。总是。但是如果你的业务领域或者研究经费能够应付的话，这是一个可以去的方向。
额外奖励：矢量化代码可能会在某些 CPU-s 上崩溃（最好避免这种情况）:
在 Quant 建模中，性能就是金钱，所以让我也分享一个最近的已知问题，来自微有效载荷的极其严格的性能调整（在装配中弄脏手）。如果在您的 Quant 建模工作中进行代码性能优化，希望它可以避免任何不必要的问题：
Intel Hyperthread corruption errata (SKZ7/SKW144/SKL150/SKX150/SKZ7/KBL095/KBW095)
Short Loops Which Use AH/BH/CH/DH Registers May Cause Unpredictable System Behavior.
Problem:
Under complex micro-architectural conditions, short loops of less than 64 instructions that use AH, BH, CH or DH registers as well as their corresponding wider register (e.g. RAX, EAX or AX for AH) may cause unpredictable system behavior. This can only happen when both logical
processors on the same physical processor are active.
Implication:
Due to this erratum, the system may experience unpredictable system behavior. This errata may impact the ... the guest OS.
References:
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
并行的开销
你的成本模型是错误的。
理想的并行计算时间为：
Tpar(ideal) = N * t / C + Pstart + Pend
其中 Pstart 是开始并行化所花费的时间，Pend 是完成并行化所花费的时间。 Pstart 在几十毫秒的数量级并不罕见。
我不确定您是否熟悉 OpenMP（尽管了解它是一件好事），但是，对于我们的目的而言，它是一种线程模型，可以在一组线程之间分配工作。下图显示了与线程组大小相关的一些命令的开销：
要点是让你的并行性（parallel for 行）可能很昂贵并且随着线程数量的增加而增长。结束并行性（barrier 行）具有相似的成本。
事实上，如果你看一下 TBB 的教程，第 3.2.2 节 ("Automatic Chunking") 说：
CAUTION: Typically a loop needs to take at least a million clock cycles for parallel_for to improve its performance. For example, a loop that takes at least 500 microseconds on a 2 GHz processor might benefit from parallel_for.
实现更快的速度
像这样加速代码的最佳方法是仅在有大量操作时才并行执行操作and/or以调整执行工作的线程数，以便每个线程都有足够的去做。在 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 还执行动态负载平衡（参见 here）。如果您希望循环 iterations/tasks 具有广泛的 运行 次分布，这很好，但如果预期的 运行 次相同，则表示不必要的开销。我不确定 TBB 是否有静态调度，但它可能值得研究。
如果人们在没有对 TBB 做出坚定承诺的情况下最终来到这里，在 OpenMP 中你会做类似的事情：
#pragma omp parallel for if(work_size>1000) num_threads(4) schedule(static)
@Richard 有正确的答案（TBB 教程讨论了调度开销摊销的概念），通常我会把它作为评论留下，但有一件事我想补充。
TBB 使用 "greedy scheduling," 来完成任务。如果有一个任务是由先前任务的执行创建的（从技术上讲，如果任务 returns 是一个任务指针），则该任务是线程上的下一个 运行。这有两个好处：
- 上一个任务可能已经加载或生成了下一个任务正在使用的数据，有助于数据局部性。
- 我们跳过选择下一个任务的过程 运行（无论它在本地线程的队列中是否可用于从另一个线程窃取）。这大大减少了调度开销。
tbb::flow_graph 使用相同的思路；如果一个节点有一个或多个后继者，在其执行完成时，其中一个后继者被选为 运行.
的下一个
这样做的缺点是，如果您想更改此行为（执行 "breadth-first" 中的节点而不是 "depth-first" 顺序），您必须跳过一些障碍。它还将花费您的调度开销和位置损失。
这是我尝试对英特尔 TBB 流程图的性能进行基准测试。 这是设置：
- 一个广播节点发送
continue_msg给N个后继节点
(一个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 微秒时，是否有比流程图更好的范例？
广告 1)
这是一个很好的例子，细节很重要。 Tpar(ideal) = N * t / C与其说是现实中可能发生的事情不如说是愿望。
英特尔在将其硬件知识重新构建为发布软件工具方面确实做得很好，这可以从他们对自己的处理器微体系结构魔法的超详细知识中受益。没有其他人可以为英特尔 CPU-s 做得更好，没有其他人可以轻易移植它，以在其他一些 CPU 微架构上提供任何类似的性能（所以要小心你的实际 CPU , 如果它是云抽象的则更多 )
为什么overhead-strict Amdahl's Law?
为什么？因为这些开销决定的不仅仅是核心数量。
重点是，随着 "usefull"-payload 大小变得越来越小，开销（即使是那些非常小的开销，就像在超级优化的工具中一样，就像毫无疑问的 TBB 一样）——这些开销总是累加到问题计算图的纯[SERIAL]部分。
因此，随着我们在 [PARALLEL] 有效载荷中继续变得越来越小，它们的主要非零成本 { setup | termination } 每核调度实际成本，将在某个时刻变得更高，比任何 "next" 受益于反比例因子 1 / numCOREs 仅适用于网络的线性持续时间 [PARALLEL]-计算路径，但所有这些附加开销加起来并扩展 [SERIAL]-计算路径的速度比任何增长的 numCOREs 可以补偿的速度都快，并且 加速增长低于 << 1x.
Q.E.D.
广告 2)
这个是在上面的游乐场设置中，一个最小痛苦的游戏。
鉴于一个人想要加速大约 ~ 4,000 CPU uops ~ <= 1 [us]，一个人 绝不能在所有延迟上花费一纳秒 并且如果尝试这样做会增加开销，假设最终加速仍至少保持 >= 1x
如果我们不相信童话，那么寻找 FPGA 进行 PoC 原型设计和ASIC/SoC 进行生产级部署。
如果您项目的经济无法承受所有相关成本，那就忘记免费获得任何魔法吧。它的成本。总是。但是如果你的业务领域或者研究经费能够应付的话，这是一个可以去的方向。
额外奖励：矢量化代码可能会在某些 CPU-s 上崩溃（最好避免这种情况）:
在 Quant 建模中，性能就是金钱，所以让我也分享一个最近的已知问题，来自微有效载荷的极其严格的性能调整（在装配中弄脏手）。如果在您的 Quant 建模工作中进行代码性能优化，希望它可以避免任何不必要的问题：
Intel Hyperthread corruption errata (SKZ7/SKW144/SKL150/SKX150/SKZ7/KBL095/KBW095) Short Loops Which Use AH/BH/CH/DH Registers May Cause Unpredictable System Behavior.
Problem:
Under complex micro-architectural conditions, short loops of less than 64 instructions that use AH, BH, CH or DH registers as well as their corresponding wider register (e.g. RAX, EAX or AX for AH) may cause unpredictable system behavior. This can only happen when both logical processors on the same physical processor are active.
Implication:
Due to this erratum, the system may experience unpredictable system behavior. This errata may impact the ... the guest OS.
References:
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
并行的开销
你的成本模型是错误的。
理想的并行计算时间为：
Tpar(ideal) = N * t / C + Pstart + Pend
其中 Pstart 是开始并行化所花费的时间，Pend 是完成并行化所花费的时间。 Pstart 在几十毫秒的数量级并不罕见。
我不确定您是否熟悉 OpenMP（尽管了解它是一件好事），但是，对于我们的目的而言，它是一种线程模型，可以在一组线程之间分配工作。下图显示了与线程组大小相关的一些命令的开销：
要点是让你的并行性（parallel for 行）可能很昂贵并且随着线程数量的增加而增长。结束并行性（barrier 行）具有相似的成本。
事实上，如果你看一下 TBB 的教程，第 3.2.2 节 ("Automatic Chunking") 说：
CAUTION: Typically a loop needs to take at least a million clock cycles for parallel_for to improve its performance. For example, a loop that takes at least 500 microseconds on a 2 GHz processor might benefit from parallel_for.
实现更快的速度
像这样加速代码的最佳方法是仅在有大量操作时才并行执行操作and/or以调整执行工作的线程数，以便每个线程都有足够的去做。在 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 还执行动态负载平衡（参见 here）。如果您希望循环 iterations/tasks 具有广泛的 运行 次分布，这很好，但如果预期的 运行 次相同，则表示不必要的开销。我不确定 TBB 是否有静态调度，但它可能值得研究。
如果人们在没有对 TBB 做出坚定承诺的情况下最终来到这里，在 OpenMP 中你会做类似的事情：
#pragma omp parallel for if(work_size>1000) num_threads(4) schedule(static)
@Richard 有正确的答案（TBB 教程讨论了调度开销摊销的概念），通常我会把它作为评论留下，但有一件事我想补充。
TBB 使用 "greedy scheduling," 来完成任务。如果有一个任务是由先前任务的执行创建的（从技术上讲，如果任务 returns 是一个任务指针），则该任务是线程上的下一个 运行。这有两个好处：
- 上一个任务可能已经加载或生成了下一个任务正在使用的数据，有助于数据局部性。
- 我们跳过选择下一个任务的过程 运行（无论它在本地线程的队列中是否可用于从另一个线程窃取）。这大大减少了调度开销。
tbb::flow_graph 使用相同的思路；如果一个节点有一个或多个后继者，在其执行完成时，其中一个后继者被选为 运行.
这样做的缺点是，如果您想更改此行为（执行 "breadth-first" 中的节点而不是 "depth-first" 顺序），您必须跳过一些障碍。它还将花费您的调度开销和位置损失。