Atomic Power in Forks: A Super-Logarithmic Lower Bound for Implementing Butterfly Networks in the Nonatomic Binary Fork-Join Model
Atomic Power in Forks: A Super-Logarithmic Lower Bound for Implementing Butterfly Networks in the Nonatomic Binary Fork-Join Model
复制标题
分叉中的原子力：在非原子二元分叉连接模型中实现蝴蝶网络的超对数下界
DOI：
10.1137/1.9781611976465.128
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Sithinava, Nodari
中科院分区：
文献类型：
--
作者：
Goodrich, Michael T;Jacob, Riko;Sithinava, Nodari
我们证明了在非原子二进制叉连接模型中实现 theninput、logn 深度 FFT 电路（也称为蝴蝶网络）的跨度的 Ω (lognlog logn) 下界。在此模型中，内存访问同步仅通过 fork 操作（生成两个子线程）和 join 操作（在子线程终止时恢复父线程）进行。对于非原子二元分叉连接模型，我们的界限是渐近紧的，由于其概念优雅和捕获异步的能力，该模型最近引起了人们的兴趣。我们的界限意味着非原子二进制分叉连接模型中的超对数下界，用于实现所使用的蝴蝶合并网络，例如，在 Batcher 的双调和奇偶合并排序网络中。这个下界还意味着 fork-join 模型的原子和非原子版本的渐近分离结果，因为正如我们指出的，FFT 电路可以在原子二进制 fork-join 模型中实现，其跨度等于其电路深度。
We prove an Ω (lognlog logn) lower bound for the span of implementing theninput, logn-depth FFT circuit (also known as butterfly network) in the nonatomic binary fork-join model. In this model, memory-access synchronizations occur only through fork operations, which spawn two child threads, and join operations, which resume a parent thread when its child threads terminate. Our bound is asymptotically tight for the nonatomic binary fork-join model, which has been of interest of late, due to its conceptual elegance and ability to capture asynchrony. Our bound implies super-logarithmic lower bound in the nonatomic binary fork-join model for implementing the butterfly merging networks used, e.g., in Batcher's bitonic and odd-even mergesort networks. This lower bound also implies an asymptotic separation result for the atomic and nonatomic versions of the fork-join model, since, as we point out, FFT circuits can be implemented in the atomic binary fork-join model with span equal to their circuit depth.
登录
查看更多内容
点集和多边形问题的最优并行算法
影响因子：
1.1
作者：
R. Cole;M. Goodrich
通讯作者：
M. Goodrich
DOI：
--
发表时间：
2012
期刊：
IEEE International Parallel and Distributed Processing Symposium
影响因子：
--
作者：
R. Cole;V. Ramachandran
通讯作者：
V. Ramachandran
使用近似算法设计可能忽略处理器分配的并行算法
DOI：
10.1109/sfcs.1991.185439
发表时间：
1991
期刊：
[1991] Proceedings 32nd Annual Symposium of Foundations of Computer Science
影响因子：
--
作者：
M. Goodrich
通讯作者：
M. Goodrich
DOI：
10.1145/3210377.3210381
发表时间：
2018-05
期刊：
Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures
影响因子：
--
作者：
G. Blelloch;Phillip B. Gibbons;Yan Gu;Charles McGuffey;Julian Shun
通讯作者：
G. Blelloch;Phillip B. Gibbons;Yan Gu;Charles McGuffey;Julian Shun
fork 和 join 同步原语的性能评估
影响因子：
0.6
作者：
A. Duda;T. Czachórski
通讯作者：
T. Czachórski