Efficient Schemes for Parallel Communication
Efficient Schemes for Parallel Communication
复制标题
并行通信的高效方案
DOI：
10.1145/828.1892
复制
发表时间：
1984
期刊：
影响因子：
--
通讯作者：
E. Upfal
中科院分区：
文献类型：
--
作者：
E. Upfal
一个平衡的通信方案，用于将n处理器连接到只有恒定数量的线路或离开每个处理器的线路。事实证明，该网络拓扑使完全分布的概率算法能够有效地执行各种通信请求。特别地，它可以实现任意置换的实现，即最初位于不同处理器中的N数据包，并注定要在O（log/sub 2/n）步骤中的不同目的地。对于随机生成的通信请求，也证明了类似的结果。这些结果提出了对平行计算机设计中基本问题的有效解决方案。
A family of balanced communication schemes for connecting N processors with only a constant number of lines entering or leaving each processor is defined. It is proved that this network topology enables a fully distributed probabilistic algorithm to execute a variety of communication requests efficiently. In particular it enables implementation of an arbitrary permutation, that is, a set of N packets initially located in distinct processors and destined for distinct destinations in O(log/sub 2/N) steps. Similar results are proved for randomly generated communication requests. These results suggest an efficient solution to a fundamental problem in the design of parallel computers.