Optimal Parallel Algorithms in the Binary-Forking Model
Optimal Parallel Algorithms in the Binary-Forking Model
复制标题
二分叉模型中的最优并行算法
DOI：
10.1145/3350755.3400227
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Sun, Yihan
中科院分区：
文献类型：
--
作者：
Blelloch, Guy E.;Fineman, Jeremy T.;Gu, Yan;Sun, Yihan
在本文中，我们开发的二进制分叉模型的各种基本问题，包括排序，半排序，列表排名，树收缩，范围极小值，有序集的联合，交集和差异的最佳算法。在二进制派生模型中，任务只能派生为两个子任务，但可以递归地异步执行。这些任务共享内存，支持读、写和测试和设置。成本以工作（指令总数）和跨度（最长依赖链）来衡量。二进制分叉模型旨在捕获许多现有多线程语言的算法性能和算法设计考虑因素，这些语言也是异步的，并且显式或隐藏地依赖于二进制分叉。与广泛研究的PRAM模型相比，它不假设任意方向的分叉或同步操作，这两者都很难在现代硬件中实现。虽然最佳的PRAM算法是已知的问题，在这里研究，事实证明，任意方式分叉和严格的同步是强大的，如果不切实际的，能力。这些PRAM算法在二进制分叉模型中的自然模拟（即，现有并行语言中的实现）在跨度上引起Ω（log n）开销。本文探讨了设计最佳算法时，限于二进制分叉和假设的技巧。本文所描述的所有算法都是二进制分叉模型中第一个具有最优工作和最优跨度的算法。大多数算法都很简单。许多人是随机的。
In this paper we develop optimal algorithms in the binary-forking model for a variety of fundamental problems, including sorting, semisorting, list ranking, tree contraction, range minima, and ordered set union, intersection and difference. In the binary-forking model, tasks can only fork into two child tasks, but can do so recursively and asynchronously. The tasks share memory, supporting reads, writes and test-and-sets. Costs are measured in terms of work (total number of instructions), and span (longest dependence chain).The binary-forking model is meant to capture both algorithm performance and algorithm-design considerations on many existing multithreaded languages, which are also asynchronous and rely on binary forks either explicitly or under the covers. In contrast to the widely studied PRAM model, it does not assume arbitrary-way forks nor synchronous operations, both of which are hard to implement in modern hardware. While optimal PRAM algorithms are known for the problems studied herein, it turns out that arbitrary-way forking and strict synchronization are powerful, if unrealistic, capabilities. Natural simulations of these PRAM algorithms in the binary-forking model (i.e., implementations in existing parallel languages) incur an Ω(log n) overhead in span. This paper explores techniques for designing optimal algorithms when limited to binary forking and assuming asynchrony. All algorithms described in this paper are the first algorithms with optimal work and span in the binary-forking model. Most of the algorithms are simple. Many are randomized.
登录
查看更多内容
DOI：
10.1109/ipdps.2018.00081
发表时间：
2017-10
期刊：
2018 IEEE International Parallel and Distributed Processing Symposium (IPDPS)
影响因子：
--
作者：
N. Ben-David;G. Blelloch;Jeremy T. Fineman;Phillip B. Gibbons;Yan Gu;Charles McGuffey;Julian Shun
通讯作者：
N. Ben-David;G. Blelloch;Jeremy T. Fineman;Phillip B. Gibbons;Yan Gu;Charles McGuffey;Julian Shun
在共享内存机器上生成随机排列的并行算法
DOI：
--
发表时间：
1990
期刊：
ACM Symposium on Parallelism in Algorithms and Architectures
影响因子：
--
作者：
Richard J. Anderson
通讯作者：
Richard J. Anderson
影响因子：
1.1
作者：
A. Czumaj;Przemyslawa Kanarek;Mirosław Kutyłowski;Krzysztof Lorys
通讯作者：
Krzysztof Lorys
只需加入并行有序集
DOI：
10.1145/2935764.2935768
发表时间：
2016
期刊：
Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures
影响因子：
--
作者：
G. Blelloch;Daniel Ferizovic;Yihan Sun
通讯作者：
Yihan Sun
DOI：
10.1145/3210377.3210380
发表时间：
2018-05
期刊：
Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures
影响因子：
--
作者：
G. Blelloch;Yan Gu;Yihan Sun;Julian Shun
通讯作者：
G. Blelloch;Yan Gu;Yihan Sun;Julian Shun