A Lower Bound Technique for Communication in BSP
A Lower Bound Technique for Communication in BSP
复制标题
DOI：
10.1145/3181776
复制
发表时间：
2018-04-01
影响因子：
1.6
通讯作者：
Silvestri, Francesco
中科院分区：
文献类型：
--
作者：
Bilardi, Gianfranco;Scquizzato, Michele;Silvestri, Francesco
通信是决定当前计算系统上算法性能的主要因素；因此，提供计算的通信复杂性的严格下界是有价值的。本文给出了一类给定DAG计算的批量同步并行(BSP)模型中通信复杂性的下界估计方法。导出界用DAG的开关电势来表示，即当被视为开关网络时，DAG可以实现的排列的数目。所提出的技术为快速傅立叶变换(FFT)以及任何排序和置换网络提供了严格的下界。通过将该技术应用于适当的子网络，还得到了周期平衡排序网络的一个较强的界。最后，我们证明了即使在不同于BSP的计算模型中，例如I/O模型和LPRAM，开关电势也能捕获通信需求。
Communication is a major factor determining the performance of algorithms on current computing systems; it is therefore valuable to provide tight lower bounds on the communication complexity of computations. This article presents a lower bound technique for the communication complexity in the bulk-synchronous parallel (BSP) model of a given class of DAG computations. The derived bound is expressed in terms of the switching potential of a DAG, that is, the number of permutations that the DAG can realize when viewed as a switching network. The proposed technique yields tight lower bounds for the fast Fourier transform (FFT), and for any sorting and permutation network. A stronger bound is also derived for the periodic balanced sorting network, by applying this technique to suitable subnetworks. Finally, we demonstrate that the switching potential captures communication requirements even in computational models different from BSP, such as the I/O model and the LPRAM.