Data Races and the Discrete Resource-time Tradeoff Problem with Resource Reuse over Paths
Data Races and the Discrete Resource-time Tradeoff Problem with Resource Reuse over Paths
复制标题
数据争用和路径上资源重用的离散资源时间权衡问题
DOI：
10.1145/3323165.3323209
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Skiena, Steven
中科院分区：
文献类型：
--
作者：
Das, Rathish;Tsai, Shih-Yu;Duppala, Sharmila;Lynch, Jayson;Arkin, Esther M.;Chowdhury, Rezaul;Mitchell, Joseph S.;Skiena, Steven
如果两个或多个逻辑上并行的指令访问同一个内存位置，并且其中至少有一个试图修改其内容，则会发生确定性竞争。竞争通常是不受欢迎的，因为它们会导致不确定性和不正确的程序行为。数据竞争是确定性竞争的一种特殊情况，可以通过将互斥锁与所讨论的内存位置相关联或允许对其进行原子访问来消除数据竞争。然而，这种解决方案可以通过串行化对该位置的所有访问来降低并行性。对于对存储器单元的关联和交换更新，可以改为使用reducer，其允许以使用一些额外空间为代价的并行无竞争更新。更多的额外空间通常会导致更多的并行更新，这反过来又有助于潜在地降低程序的总体执行时间。我们首先提出以下问题。给定一个固定的额外空间预算来减少并行程序中的竞争成本，哪些内存位置应该分配给reducer，以及应该如何在这些reducer之间分配空间，以最小化总运行时间？我们认为，在合理的条件下，一个程序的种族可以被捕获的有向无环图（DAG），节点代表内存单元和弧代表读写依赖细胞之间。然后，我们将原始问题公式化为这个DAG上的优化问题。我们专注于这个问题的一个变体，其中通过沿着DAG的（可能不同的）源到宿路径路由每个额外空间单元并将其用于沿着路径构造多个（可能为零）归约器来允许归约器之间的空间重用。我们考虑构造归约器和相应持续时间函数的两种不同方式（即，作为空间预算的函数的缩减时间）。我们推广我们的种族，避免空间-时间权衡问题的离散资源-时间权衡问题，一般不增加的持续时间函数和资源重用的路径上给定的DAG。对于一般的DAG，我们表明，即使整个DAG是离线的问题是强NP-困难的所有三个持续时间函数下，我们给出近似算法来解决相应的优化问题。我们还证明了一般的资源-时间权衡问题的近似困难，并给出了一个伪多项式时间算法的串并行DAG。
A determinacy race occurs if two or more logically parallel instructions access the same memory location and at least one of them tries to modify its content. Races are often undesirable as they can lead to nondeterministic and incorrect program behavior. A data race is a special case of a determinacy race which can be eliminated by associating a mutual-exclusion lock with the memory location in question or allowing atomic accesses to it. However, such solutions can reduce parallelism by serializing all accesses to that location. For associative and commutative updates to a memory cell, one can instead use a reducer, which allows parallel race-free updates at the expense of using some extra space. More extra space usually leads to more parallel updates, which in turn contributes to potentially lowering the overall execution time of the program. We start by asking the following question. Given a fixed budget of extra space for mitigating the cost of races in a parallel program, which memory locations should be assigned reducers and how should the space be distributed among those reducers in order to minimize the overall running time? We argue that under reasonable conditions the races of a program can be captured by a directed acyclic graph (DAG), with nodes representing memory cells and arcs representing read-write dependencies between cells. We then formulate our original question as an optimization problem on this DAG. We concentrate on a variation of this problem where space reuse among reducers is allowed by routing every unit of extra space along a (possibly different) source to sink path of the DAG and using it in the construction of multiple (possibly zero) reducers along the path. We consider two different ways of constructing a reducer and the corresponding duration functions (i.e., reduction time as a function of space budget). We generalize our race-avoiding space-time tradeoff problem to a discrete resource-time tradeoff problem with general non-increasing duration functions and resource reuse over paths of the given DAG. For general DAGs, we show that even if the entire DAG is available offline the problem is strongly NP-hard under all three duration functions, and we give approximation algorithms for solving the corresponding optimization problems. We also prove hardness of approximation for the general resource-time tradeoff problem and give a pseudo-polynomial time algorithm for series-parallel DAGs.
登录
查看更多内容
DOI：
--
发表时间：
2004
期刊：
影响因子：
--
作者：
P. Dutot;G. Mounié;D. Trystram
通讯作者：
D. Trystram
通过大型虚拟内存和全局数据结构进行快速、多核可扩展、低碎片内存分配
DOI：
10.1145/2814270.2814294
发表时间：
2015
期刊：
Proceedings of the 2015 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications
影响因子：
--
作者：
M. Aigner;C. Kirsch;Michael Lippautz;A. Sokolova
通讯作者：
A. Sokolova
一种在一般优先级约束下调度可延展任务的近似算法
影响因子：
5.3
作者：
K. Jansen;Hu Zhang
通讯作者：
Hu Zhang
具有自适应网格划分的海洋环流模型动态负载平衡
DOI：
--
发表时间：
1999
期刊：
European Conference on Parallel Processing
影响因子：
--
作者：
E. Blayo;L. Debreu;G. Mounié;D. Trystram
通讯作者：
D. Trystram
任意活动成本函数的CPM时间成本计算算法
DOI：
--
发表时间：
1977
期刊：
影响因子：
--
作者：
D. Panagiotakopoulos
通讯作者：
D. Panagiotakopoulos