Sequential Random Permutation, List Contraction and Tree Contraction are Highly Parallel
Sequential Random Permutation, List Contraction and Tree Contraction are Highly Parallel
复制标题
顺序随机排列、列表收缩和树收缩是高度并行的
DOI：
10.1137/1.9781611973730.30
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Phillip B. Gibbons
中科院分区：
文献类型：
--
作者：
Julian Shun;Yan Gu;G. Blelloch;Jeremy T. Fineman;Phillip B. Gibbons
我们表明，针对随机排列、列表收缩和树收缩的简单顺序随机迭代算法具有高度并行性。特别是，如果算法的迭代在其所有依赖项都已解决后立即运行，那么所得计算很有可能具有对数深度（并行时间）。我们的证明在其中两个问题的依赖结构和随机二叉树之间建立了一种有趣的联系。在此分析基础上，我们针对这三个问题描述了线性工作量、多项对数深度的算法。尽管在渐近意义上并不比针对给定问题的许多先前的并行算法更好，但它们的优势包括非常简单和快速的实现，并且能返回与顺序算法相同的结果。在一台40核机器上进行的实验表明，相对于顺序算法，其性能相当不错。
We show that simple sequential randomized iterative algorithms for random permutation, list contraction, and tree contraction are highly parallel. In particular, if iterations of the algorithms are run as soon as all of their dependencies have been resolved, the resulting computations have logarithmic depth (parallel time) with high probability. Our proofs make an interesting connection between the dependence structure of two of the problems and random binary trees. Building upon this analysis, we describe linear-work, polylogarithmic-depth algorithms for the three problems. Although asymptotically no better than the many prior parallel algorithms for the given problems, their advantages include very simple and fast implementations, and returning the same result as the sequential algorithm. Experiments on a 40-core machine show reasonably good performance relative to the sequential algorithms.