Efficient Parallel Self-Adjusting Computation
Efficient Parallel Self-Adjusting Computation
复制标题
高效并行自调整计算
DOI：
10.1145/3409964.3461799
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Acar, Umut A.
中科院分区：
文献类型：
--
作者：
Anderson, Daniel;Blelloch, Guy E.;Baweja, Anubhav;Acar, Umut A.
自调整计算是一种从静态算法自动生成动态算法的方法。它的工作原理是跟踪控制和数据依赖关系，并在进行更新时通过依赖关系传播更改。在串行环境下进行了广泛的研究，目前已有一些关于并行自调整计算的结果，但只适用于有限的计算类型，或者是ad-hoc系统，没有对其性能进行理论分析。我们提出了第一个系统的并行自-调整计算，适用于广泛的一类嵌套并行算法，并提供理论界的工作和跨度的结果动态算法我们的界限涉及到一个“距离”的措施之间的计算不同的输入传播的update.The主要创新的成本是在使用串行并行树（SP树）跟踪顺序和并行控制的依赖关系，允许更改传播安全地应用于并行。我们演示了几个示例应用程序，包括动态序列和动态树的算法。最后，我们通过实验表明，我们的系统允许算法在大型数据集上产生更新的结果，比从头开始执行的速度要快得多，节省了工作和并行时间。
Self-adjusting computation is an approach for automatically producing dynamic algorithms from static ones. It works by tracking control and data dependencies, and propagating changes through the dependencies when making an update. Extensively studied in the sequential setting, some results on parallel self-adjusting computation exist, but are only applicable to limited classes of computations, or are ad-hoc systems with no theoretical analysis of their performance.In this paper, we present the first system for parallel self-adjusting computation that applies to a wide class of nested parallel algorithms and provides theoretical bounds on the work and span of the resulting dynamic algorithms. Our bounds relate a "distance" measure between computations on different inputs to the cost of propagating an update.The main innovation in the paper is in using Series-Parallel trees (SP trees) to track sequential and parallel control dependencies to allow change propagation to be applied safely in parallel. We demonstrate several example applications, including algorithms for dynamic sequences and dynamic trees. Lastly, we show experimentally that our system allows algorithms to produce updated results over large datasets significantly faster than from-scratch execution, saving both work and parallel time.
登录
查看更多内容
动态间隔良好的点集
DOI：
--
发表时间：
2010
期刊：
Computational geometry
影响因子：
--
作者：
Umut A. Acar;Andrew Cotter;Benoît Hudson;Duru Türkoglu
通讯作者：
Duru Türkoglu
一种并行自调整计算的建议
DOI：
--
发表时间：
2007
期刊：
Workshop on Declarative Aspects of Multicore Programming
影响因子：
--
作者：
Matthew A. Hammer;Umut A. Acar;M. Rajagopalan;Anwar M. Ghuloum
通讯作者：
Anwar M. Ghuloum
iThreads：用于并行增量计算的线程库
DOI：
--
发表时间：
2015
期刊：
International Conference on Architectural Support for Programming Languages and Operating Systems
影响因子：
--
作者：
Pramod Bhatotia;Pedro Fonseca;Umut A. Acar;Björn B. Brandenburg;R. Rodrigues
通讯作者：
R. Rodrigues
动态化静态算法，应用于动态树和历史独立性
DOI：
--
发表时间：
2004
期刊：
ACM-SIAM Symposium on Discrete Algorithms
影响因子：
--
作者：
Umut A. Acar;G. Blelloch;R. Harper;Jorge L. Vittes;Maverick Woo
通讯作者：
Maverick Woo
通过变更传播的并行批动态树
DOI：
10.4230/lipics.esa.2020.2
发表时间：
2020
期刊：
European Symposium on Algorithms (ESA
影响因子：
--
作者：
Umut Acar, Daniel Anderson
通讯作者：
Umut Acar, Daniel Anderson