c - C/x64 ASM 中的实用定界延续

Question

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

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

An import design choice is which branch to offer to thief threads. Using Figure 1, the choices are:

Child Stealing:

• f() is made available to thief threads.
• The thread that executed e() executes g().

Continuation Stealing:

• Also called “parent stealing”.
• The thread that executed e() executes f().
• The continuation (which will next call g()) becomes available to thief threads.

我听说保存延续需要保存两组寄存器( volatile /非 volatile /FPU)。在我所做的光纤实现中，我最终实现了 child 偷窃。我读到了有关 child 偷窃的(理论上的)负面影响(无限数量的可运行任务，有关更多信息，请参阅论文)，所以我想改用延续。

我在想两个函数，shift 和 reset，其中 reset 分隔当前的延续，而 shift 具体化了当前的延续。我的要求在 C 环境中是否合理？

编辑:我正在考虑为当前函数调用(=第 3 行)制作 reset 保存返回地址/NV GPR，并制作 shift 将控制转移到向 reset 的调用者返回一个值后的下一个继续。

Answer 1

我已经实现了 work stealing for a HLL called PARLANSE而不是 x86 上的 C。 PARLANSE 每天都用于构建百万行规模的生产符号并行程序。

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

但是，具体来说，如果您的编译器理解 spawn 的含义，它可以在调用 spawn 之前将寄存器设置为空。那么延续或 child 都不必保留寄存器。 (PARLANSE 编译器实际上就是这样做的)。

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

您本地友好的 C 编译器可能不知道 您 spawn 的实现。因此，要么你做一些事情来强制刷新寄存器(不要问我，它是你的编译器)，要么你忍受这样一个事实，即你个人不知道寄存器中有什么，并且你的实现会保护它们都是安全的。

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

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

你会发现这很有趣。

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