A Practical Solution to the Cactus Stack Problem
A Practical Solution to the Cactus Stack Problem
复制标题
仙人掌堆栈问题的实用解决方案
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
J. Mellor
中科院分区：
文献类型：
--
作者：
Chaoran Yang;J. Mellor
偷窃是一种流行平衡动态多线程计算的流行方法。从理论上讲，当计算具有足够的并行性并需要处理器数量线性的堆栈空间时，随机偷窃调度程序可以接近线性加速。但是，在实践中，窃取工作时间的时间用串行代码牺牲互操作性来达到这些界限。例如，CILK和CILK ++都禁止C函数调用Acilk函数。没有这种限制的其他偷走运行时系统要么缺乏强大的时间限制，因此在最坏的情况下，它们几乎没有速度或没有速度，或者缺乏强大的空间绑定，这可能会导致过度的内存足迹。此问题先前被描述为仙人掌堆栈问题。在本文中，我们提出了Fibril，这是一个新的多线程库，该库支持使用偷窃工作的叉-Join编程模型。 Fibril通过（1）在仙人掌堆栈上实现依符合串行代码的调用约定，以及（2）将悬挂式堆栈的未使用的存储页面返回操作系统以约束物理内存的消耗，以解决仙人掌堆栈问题。从理论上讲，原纤维在时间和内存使用方面都达到了强大的界限，而无需牺牲串行代码的互操作性。从经验上讲，原纤维最多可实现3倍的Intel Cilk Plus的性能，最高为8倍，是我们评估的12个基准测试基准的Intel螺纹构建块的性能。
Work-stealing is a popular method for load-balancing dynamic multithreaded computations on shared-memory systems. In theory, a randomized work-stealing scheduler can achieve near linear speedup when the computation has sufficient parallelism and requires stack space that is linear in the number of processors. In practice, however, work-stealing runtimes sacrifice interoperability with serial code to achieve these bounds. For example, both Cilk and Cilk++ prohibit a C function from calling aCilk function. Other work-stealing runtime systems that do not have this restriction either lack a strong time bound, which might cause them to deliver little or no speedup in the worst case, or lack a strong space bound, which might lead to an excessive memory footprint. This problem was previously described as the cactus stack problem. In this paper, we present Fibril, a new multithreading library that supports a fork-join programming model using work-stealing. Fibril solves the cactus stack problem by (1) implementing on a cactus stack that conforms to the calling conventions of serial code and (2) returning unused memory pages of suspended stacks to the operating system to bound consumption of physical memory. Theoretically, Fibril achieves strong bounds on both time and memory usage without sacrificing interoperability with serial code. Empirically, Fibril achieves up to 3x the performance of Intel Cilk Plus and up to 8x the performance of Intel Threading Building Blocks for the 12 benchmarks we evaluated.