Proactive work stealing for futures
Proactive work stealing for futures
复制标题
为未来主动窃取工作
DOI：
10.1145/3293883.3295735
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Lee, I-Ting Angelina
中科院分区：
文献类型：
--
作者：
Singer, Kyle;Xu, Yifan;Lee, I-Ting Angelina
期货的使用提供了一种灵活的方式来表示并行性，并且可以在并行子计算之间产生任意依赖关系。然而，期货提供的额外灵活性是有代价的。当使用经典的工作窃取进行调度时，与只使用fork-Join并行性的程序相比，使用Futures的程序可能会产生更多的“偏差”，这是评估并行执行性能的一个指标。然而，以前的所有工作都假定工作窃取调度器是独立的，其中工作线程(处理器的代理)只有在其本地队列变空时才窃取工作。在这项工作中，我们研究了一种称为PROWS的替代调度方法，在该方法中，工作线程在处理未来的操作时执行主动工作窃取。我们表明，对于使用期货的程序，PROWS可以提供被证明有效的执行时间，并且与经典的节俭的工作窃取相比，可以提供相等或更好的偏差数量的界。在给定具有T1work和T∞跨度的计算的情况下，Prows在预期时间o(T1/P+T∞lgp)内在P处理器上执行计算，与简约变体相比，在跨度项上具有额外的lg贫穷头。对于期货的结构化使用，其中每个未来都是一触即发的，未来句柄上没有竞争，算法会产生偏差，与节俭变体的偏差相匹配。对于期货的一般用途，该算法产生O(MKT∞+PT∞LGP)偏差，其中K是逻辑上平行的未来接触的最大数量。与简约变量的界O(KT∞+PT∞)相比，当K是整个计算中的总接触次数时，这个界更好地假设mk=Ω(PlgP)并且更小，这对我们检查的所有基准都成立。
The use of futures provides a flexible way to express parallelism and can generate arbitrary dependences among parallel subcomputations. The additional flexibility that futures provide comes with a cost, however. When scheduled using classic work stealing, a program with futures, compared to a program that uses only fork-join parallelism, can incur a much higher number of "deviations," a metric for evaluating the performance of parallel executions. All prior works assume aparsimoniouswork-stealing scheduler, however, where a worker thread (surrogate of a processor) steals work only when its local deque becomes empty.In this work, we investigate an alternative scheduling approach, called ProWS, where the workers performproactivework stealing when handling future operations. We show that ProWS, for programs that use futures, can provide provably efficient execution time and equal or better bounds on the number of deviations compared to classic parsimonious work stealing. Given a computation withT1work andT∞span, ProWS executes the computation onPprocessors in expected timeO(T1/P+T∞lgP), with an additional lgPoverhead on the span term compared to the parsimonious variant. For structured use of futures, where each future is single touch with no race on the future handle, the algorithm incurs deviations, matching that of the parsimonious variant. For general use of futures, the algorithm incursO(mkT∞+PT∞lgP) deviations, wheremkis the maximum number of future touches that are logically parallel. Compared to the bound for the parsimonious variant,O(kT∞+PT∞), withkbeing the total number of touches in the entire computation, this bound is better assumingmk= Ω(PlgP) and is smaller thank,which holds true for all the benchmarks we examined.
登录
查看更多内容
仙人掌堆栈问题的实用解决方案
DOI：
--
发表时间：
2016
期刊：
ACM Symposium on Parallelism in Algorithms and Architectures
影响因子：
--
作者：
Chaoran Yang;J. Mellor
通讯作者：
J. Mellor
Habanero 多核软件研究项目
DOI：
10.1145/1639950.1639989
发表时间：
2009
期刊：
Theor. Comput. Sci.
影响因子：
--
作者：
R. Barik;Zoran Budimlic;Vincent Cavé;S. Chatterjee;Yi Guo;David M. Peixotto;Raghavan Raman;J. Shirako;Sagnak Tasirlar;Yonghong Yan;Yisheng Zhao;Vivek Sarkar
通讯作者：
Vivek Sarkar
在 JCIlk 中进行异常编程
DOI：
10.1016/j.scico.2006.05.008
发表时间：
2006
期刊：
Sci. Comput. Program.
影响因子：
--
作者：
John S. Danaher;I. Lee;C. Leiserson
通讯作者：
C. Leiserson
DOI：
--
发表时间：
1978
期刊：
影响因子：
--
作者：
Jacobo Valdes Ayesta
通讯作者：
Jacobo Valdes Ayesta
并行处理应用程序编程的各个方面
影响因子：
3.7
作者：
Daniel P. Friedman;David S. Wise
通讯作者：
David S. Wise