Efficient race detection with futures
Efficient race detection with futures
复制标题
通过 future 进行高效种族检测
DOI：
10.1145/3293883.3295732
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Lee, I-Ting Angelina
中科院分区：
文献类型：
--
作者：
Utterback, Robert;Agrawal, Kunal;Fineman, Jeremy;Lee, I-Ting Angelina
本文研究了在使用期货的任务并行程序中可证明高效且实际良好的动态确定性竞争检测问题。先前关于确定性竞争检测的工作主要集中在遵循串并联依赖结构的任务并行程序或不受限制地使用生成任意依赖的未来的程序上。在这项工作中，我们考虑了期货的限制使用，并表明我们可以比一般使用期货更有效地检测种族。具体来说，我们提出了两种算法：MultiBags和MultiBags+。MultiBags的目标程序以受限的方式使用未来，并在timeO（T1α(m, n)）中运行，其中et1是程序的顺序运行时间，α是逆Ackermann函数，是内存访问的总数，是创建并行性的动态位置计数。由于α是一个增长非常缓慢的函数（对于所有实际目的，上限为4），因此可以将其视为接近常数的开销。MultiBags+是MultiBags的扩展，针对一般使用future的程序。它在时间0 (（T1+k2)α(m, n)）中运行，其中et1， α，与之前定义的一样，是计算中未来操作的次数。我们实现了这两种算法，并实证证明了它们的有效性。
This paper addresses the problem of provably efficient and practically good on-the-fly determinacy race detection in task parallel programs that use futures. Prior works on determinacy race detection have mostly focused on either task parallel programs that follow a series-parallel dependence structure or ones with unrestricted use of futures that generate arbitrary dependences. In this work, we consider a restricted use of futures and show that we can detect races more efficiently than with general use of futures.Specifically, we present two algorithms: MultiBags and MultiBags+. MultiBags targets programs that use futures in a restricted fashion and runs in timeO(T1α(m, n)), whereT1is the sequential running time of the program, α is the inverse Ackermann's function,mis the total number of memory accesses,nis the dynamic count of places at which parallelism is created. Since α is a very slowly growing function (upper bounded by 4 for all practical purposes), it can be treated as a close-to-constant overhead. MultiBags+ is an extension of MultiBags that target programs with general use of futures. It runs in timeO((T1+k2)α(m, n)) whereT1, α,mandnare defined as before, andkis the number of future operations in the computation. We implemented both algorithms and empirically demonstrate their efficiency.
登录
查看更多内容
使用管道编程模型的工作负载的特征
DOI：
10.1007/978-3-642-24322-6_14
发表时间：
2010
期刊：
2016 IEEE Hot Chips 28 Symposium (HCS)
影响因子：
--
作者：
Christian Bienia;Kai Li
通讯作者：
Kai Li
已证明良好且实用高效的 Fork-Join 程序并行竞争检测
DOI：
10.1145/2935764.2935801
发表时间：
2016
期刊：
Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures
影响因子：
--
作者：
Utterback, Robert;Agrawal, Kunal;Fineman, Jeremy T.;Lee, I-Ting Angelina
通讯作者：
Lee, I-Ting Angelina
有效检测使用Reducer超对象的Cilk程序中的竞争
DOI：
--
发表时间：
2015
期刊：
ACM Symposium on Parallelism in Algorithms and Architectures
影响因子：
--
作者：
I. Lee;T. Schardl
通讯作者：
T. Schardl
DOI：
10.1145/3178487.3178515
发表时间：
2018-02
期刊：
Proceedings of the 23rd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming
影响因子：
--
作者：
Yifan Xu;I. Lee;Kunal Agrawal
通讯作者：
Yifan Xu;I. Lee;Kunal Agrawal
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