Constantine's Threadpool 线程池设计

线程池设计

线程池的设计很大程度上受到了 Weave，大量的准备 研究 和简化的 Weave，nim-taskpools 的启发。

目标是产生一个极高性能、低开销、节能的多线程运行时。 然而，作为加密库的后端，它需要是高保证的，特别是可审计和可维护的。

不幸的是，基于工作请求的 Weave 设计，相比于工作窃取，需要更多的机制，这意味着更多的状态。此外，它还包括一个自定义的内存池。

另一方面，nim-taskpools 不支持数据并行（并行 for 循环）。

此外，当它们想要完成的 future 没有完成并且没有剩余工作时，两者都不支持将等待线程置于休眠状态。

特性

关键特性设计

调度器开销/争用

分布式任务队列

为了启用细粒度并行，即并行化微秒范围内的任务，减少争用至关重要。 全局任务队列将被 N 个线程频繁访问，导致每个线程都频繁刷新彼此的缓存。 相比之下，具有随机受害者选择的分布式任务队列可以显著减少争用。

内存分配

另一个开销来源是分配器，分配器最糟糕的情况是在一个线程中分配，在另一个线程中释放，特别是当 分配线程始终相同时。不幸的是，这在生产者-消费者工作负载中很常见。 此外，多线程分配/释放将触发代价高昂的原子交换，并可能导致碎片。 最大限度地减少分配将显著有助于细粒度任务。

• Weave 通过拥有 2 个级别的缓存来解决这个问题：一个用于任务和 future 的内存池，以及一个缓存任务的 lookaside list，以进一步减少内存池的压力。
• Nim-taskpools 没有解决这个问题，它每个任务都有一个分配开销：1 个用于 std/tasks，1 个用于保存它们的链表，1 个用于结果通道/flowvar。 与 GCC OpenMP 在 fibonacci 40 基准测试中冻结不同，它仍然可以完成，但比 Weave 慢 20 倍。
• Constantine 的线程池通过使所有东西都侵入到任务来解决这个问题：任务 env、future、链表。 事实上，这个解决方案甚至比 Weave 的更快，可能是由于页面错误和缓存未命中显著减少。 请注意，当 future 不通过在堆栈上分配它们来逃脱其函数时，Weave 具有更快的模式，但没有编译器支持（堆分配省略）会限制你可以编写的程序。

任务并行的负载均衡

当一个 worker 耗尽任务时，它会从其他 worker 的任务队列中窃取。 它们可以窃取一个或多个任务。 在严重负载不平衡的情况下，窃取一半的策略可以快速地将 worker 队列重新平衡到全局平均水平。 这也有助于通过减少对数级的窃取尝试来减少调度器开销。 但是，如果 worker 生成的任务很少，则可能会导致更多的重新平衡。

Weave 实现了自适应工作窃取，并在运行时选择窃取一个/窃取一半

• 在工作窃取运行时系统中拥抱显式通信。\ Andreas Prell, 2016\ https://epub.uni-bayreuth.de/id/eprint/2990/

如果以下任务队列可以以低开销实现，Constantine 的线程池可能会采用相同的策略

• 非阻塞的窃取一半工作队列\ Danny Hendler, Nir Shavit, 2002\ https://www.cs.bgu.ac.il/~hendlerd/papers/p280-hendler.pdf

数据并行的负载均衡

HPC 中使用的大多数（全部？）运行时（尤其是 OpenMP 和 Intel TBB）中的一个关键问题是，它们提前拆分其并行 for 循环。 他们不知道有多少空闲线程，或者将要运行的工作负载的代价有多大。这导致了显著的低效率和性能不可移植性。 例如，这个 repo https://github.com/zy97140/omp-benchmark-for-pytorch 给出了元素数量的阈值，低于该阈值并行化对于常见的浮点运算来说是不划算的，甚至会损害性能：

CPU 型号	插槽	每个插槽的内核数	频率
Intel(R) Xeon(R) CPU E5-2699 v4	2	22	2.20GHz
Intel(R) Xeon(R) Platinum 8180 CPU	2	28	2.50GHz
Intel(R) Core(TM) i7-5960X CPU	1	8	3.00GHz

	Xeon(R) Platinum 8180 CPU	Xeon(R) CPU E5-2699 v4	i7-5960X CPU
copy	80k	20k	8k
add	80k	20k	8k
div	50k	10k	2k
exp	1k	1k	1k
sin	1k	1k	1k
sum	1k	1k	1k
prod	1k	1k	1k

关于 Xeon Platinum 的详细信息

张量大小	串行	并行	加速
1k	1.04	5.15	0.20X
2k	1.23	5.47	0.22X
3k	1.33	5.34	0.24X
4k	1.47	5.41	0.27X
5k	1.48	5.40	0.27X
8k	1.81	5.55	0.32X
10k	1.98	5.66	0.35X
20k	2.74	6.74	0.40X
50k	5.12	6.59	0.77X
80k	14.79	6.59	2.24X
100k	21.97	6.70	3.27X

相反，我们可以让每个线程开始工作，并使用背压来惰性地评估何时拆分是有利可图的：

• 惰性二进制拆分：运行时自适应工作窃取调度器 Tzannes, Caragea, Barua, Vishkin https://terpconnect.umd.edu/~barua/ppopp164.pdf

等待 future 时回退 worker

这个问题非常棘手：

• 为了延迟，我们希望 worker 在 future 完成后立即继续。这也可能会产生更多的工作并暴露更多的并行机会（例如，在递归分而治之算法中）。\ 请注意，通过超线程，兄弟线程仍然可以完全使用核心，因此吞吐量可能不受影响。
• 为了吞吐量，并且因为调度器只有在贪婪时才是最佳的（即在最佳调度的 2 倍以内，请参阅 Cilk 论文），我们希望空闲线程尽快接受任何可用的工作。
  • 但是如果该 worker 最终得到的工作会长时间阻塞它怎么办？这可能会导致工作饥饿。
• 没有健壮的、跨平台的 API 来唤醒在 futex 或条件变量上等待的特定线程。
  • 那么最简单的设计就是拥有一个 futex 数组，在回退时在这些 futex 上休眠。 问题在于，当提供工作时，你必须扫描该数组以找到要唤醒的 worker。 与空闲 worker 相反，唤醒器正在工作，因此这种扫描会损害吞吐量和延迟，并且由于许多 所需的原子操作，将完全刷新该 worker 的缓存。
  • 甚至更简单的方法是在 future 完成时唤醒所有 worker
  • 另一种潜在的数据结构是并发稀疏集，但设计并发数据结构很困难。 并且对于活动的 worker 来说，锁定会很昂贵。
• 替代设计将是：
  • 不休眠
  • 拥有保留线程： 在被 future 阻塞时休眠之前，线程会唤醒一个保留线程。由于硬件资源的数量得到维护，因此我们保持吞吐量。 当 future 完成时，等待线程也可以立即使用，因为它不会陷入工作中。 一个行为良好的程序将始终在 N 个线程中至少有 1 个线程取得进展，因此大小为 N 的保留就足够了。 不幸的是，此解决方案会受到唤醒的高延迟和/或内核上下文切换的影响。 对于细粒度任务，它具有相当大的影响：heat 基准测试慢 7 倍，fibonacci 慢 1.5 倍，深度优先搜索慢 2.5 倍。 对于实际的工作负载，椭圆曲线求和减少也明显较慢。
  • 使用延续： 我们可以只在 future 中存储一个延续，以便完成 future 的线程获取该延续。

除了设计问题外，还存在工程问题，因为我们无法在公共 futex 或条件变量上唤醒特定线程。

• 要么线程在其本地拥有的线程上休眠，但如何将其地址传递给窃取者？ 以及如何同步释放任务内存？ 特别是，如果我们使用任务作为媒介，如何避免竞争条件，其中： 任务由窃取者完成，任务内存由等待者释放，窃取者尝试获取等待者的 futex/条件变量 并触发 use-after-free。
• 或者它在全局上休眠，并且每个窃取完成的任务都会触发 wakeAll
• 或者我们创建一个回退数据结构，可以在其中唤醒特定的等待者。

我们的解决方案是将回退结构嵌入到任务中，并添加一个额外的标志来通知何时可以安全地释放任务。

• 原文链接： github.com/mratsim/const...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～