4

我看过一篇名为A Primer on Scheduling Fork-Join Parallelism with Work Stealing的论文。我想实现持续窃取，调用后的其余代码spawn有资格被窃取。这是论文中的代码。

1 e();
2 spawn f(); 
3 g();
4 sync;
5 h();

一个重要的设计选择是向窃贼线程提供哪个分支。使用图 1，选择是：

偷孩子：

  • f() 可用于窃贼线程。
  • 执行 e() 的线程执行 g()。

持续偷窃：

  • 也称为“偷父母”。
  • 执行 e() 的线程执行 f()。
  • 延续（接下来将调用 g()）对窃贼线程可用。

我听说保存延续需要保存两组寄存器（易失性/非易失性/FPU）。在我所做的光纤实现中，我最终实现了儿童窃取。我读到了关于偷孩子的（理论上的）负面信息（无限数量的可运行任务，请参阅论文以获取更多信息），所以我想改用延续。

我正在考虑两个函数，shift和reset，其中reset界定了当前的延续，并shift具体化了当前的延续。我的要求在 C 环境中是否合理？

编辑：我正在考虑reset为当前函数调用（= 第 3 行）制作保存返回地址/NV GPR，并shift在将值返回给reset.

4

1 回答 1

3

我已经在 x86 上为名为 PARLANSE 而不是 C的 HLL 实现了工作窃取。PARLANSE 每天用于构建百万行规模的生产符号并行程序。

通常，您保留了延续或“子”的寄存器。考虑到您的编译器可能会在 f() 中看到计算并在 g() 中看到相同的计算，并且可能会将计算提升到生成之前的点，并将计算结果放在 f() 和 g 的寄存器中() 用作隐含参数。是的，这假设了一个复杂的编译器，但是如果你使用的是一个没有优化的愚蠢编译器，你为什么要尝试并行速度呢？

但是，具体而言，如果编译器理解 spawn 的含义，则可以在调用 spawn 之前将寄存器设置为空。然后，延续或孩子都不必保留寄存器。（PARLANSE 编译器实际上就是这样做的）。

所以要节省多少取决于你的编译器愿意提供多少帮助，这取决于它是否知道 spawn 真正做了什么。

您本地友好的 C 编译器可能不知道您的 spawn 实现。因此，要么你做一些事情来强制寄存器刷新（不要问我，它是你的编译器），要么你忍受你个人不知道寄存器中有什么的事实，并且你的实现将它们全部保留以确保安全。

如果产生的工作量很大，可以说保存所有寄存器都没关系。然而，x86（和其他现代架构）似乎有大量的状态，主要是在向量寄存器中，可能正在使用中；上次我看它远远超过 500 字节 ~~ 100 次写入内存以保存这些，恕我直言，这是一个过高的价格。如果您不相信这些寄存器会从父线程传递到派生线程，那么您可以在没有寄存器的情况下强制派生。

如果您使用您发明的标准延续机制唤醒例程，那么您也会担心您的延续是否通过大寄存器状态。与 spawn 相同的问题，相同的解决方案；编译器必须提供帮助，否则您必须亲自干预。

你会发现这很有趣。

[如果你想让它变得非常有趣，请尝试对线程进行时间切片，以防它们进入深度计算，而不会偶尔出现导致线程饥饿的问题。现在你肯定已经保存了整个状态。我设法让 PARLANSE 在不保存任何寄存器的情况下实现生成，但有时间切片保存/恢复完整的寄存器状态，方法是在时间片上保存完整状态，并继续在一个特殊的地方重新填充所有寄存器，然后再将控制权传递给时间分片的 PC 位置]。

于 2018-07-02T01:54:24.327 回答