Efficient optical communication in parallel computers
Efficient optical communication in parallel computers
复制标题
并行计算机中的高效光通信
DOI：
10.1145/140901.140906
复制
发表时间：
1992
影响因子：
3.1
通讯作者：
Thanasis Tsantilas
中科院分区：
文献类型：
--
作者：
Mihály Geréb;Thanasis Tsantilas
我们研究的问题，处理器间通信的并行计算机模型建议在光学技术的最新进展。计算机的各个单元（带有本地存储器的处理器）通过传输信息相互通信。一个处理器可以向任何其他处理器发送消息，并且传输需要恒定的时间。如果两个或多个处理器试图向同一个处理器发送消息，则传输不会成功，必须进行重传。我们展示了如何在这个模型中实现一个非常简单和有效的形式的随机路由。我们研究，特别是，实现任意h关系的问题。在h关系中，每个处理器是最多h个消息的源和目的地。我们提出了一个简单而实用的分布式随机算法实现任意h-关系的n处理器，这样的网络在O（h + log n log log n）并行通信步骤。我们的算法是纯粹的，在这个意义上说，没有信息除了实际的消息是在处理器之间传输。安德森和米勒[1]和Valiant [19]已经为相同的问题导出了一个@（h + log n）算法，该算法在略大的h范围内达到最优。他们的算法很复杂，而我们的算法却很实用。并行计算机的现实模型中的最佳处理器间通信算法不仅本身有趣，而且是最佳模拟PRAM以及实现Valiant的批量同步并行模型的主要组成部分之一[13，19，18]。1引言光学已被用于特殊用途的计算设备的设计相当一段时间了，特别是在信号处理领域。最近的技术进步使它也成为通用计算机设计中电子产品的一种有吸引力的替代品。光学的使用已经被建议在诸如存储、处理和提供与第二作者WVM的通信等不同的领域中使用。允许免费复制本材料的全部或部分，前提是复制品不是为了直接的商业利益而制作或分发的，ACM版权声明和出版物的标题及其日期出现，并注意到，复制是由计算机协会的许可。复制或再版，需要付费和/或特别许可。在计算机系统中的不同模块之间进行通信。光互连的使用…
We study the problem of interprocessor communication in a parallel computer model suggested by recent advances in optical technology. The units of the computer (processors with local memory) communicate with each other by transmitting messages. A processor can transmit a message to any other processor, and transmission takes constant time. If two or more processors try to send a message to the same processor no transmission is successful and retransmission must occur. We show how to implement an extremely simple and efficient form of randomized routing in this model. We study, in particular, the problem of realizing arbitrary h-relations. In an h-relation, each processor is the source as well as the destination of at most h messages. We propose a simple and practical distributed randomized algorithm for realizing arbitrary h-relations on an n-processor such network within O(h + log n log log n) parallel communication steps. Our algorithm is pure in the sense that no information aside from actual messages is transmitted between processors. Anderson and Miller [1] and Valiant [19] have derived a @(h + log n) algorithm for the same problem, which achieves optimality for a slightly larger range of h. Their algorithm is complicated as opposed to ours that we believe to be practical. Optimal interprocessor communication algorithms in realistic models of parallel computers are not only interesting in their own sake, they are one of the main components in optimally simulating PRAMs as well aa implementing Valiant's bulk-synchronous parallel model [13, 19, 18]. 1 Introduction Optics has been used in the design of special purpose computing devices for quite some time now, especially in the field of signal processing. Recent technological advances make it also an appealing alternative to electronics in the design of general purpose computers. The use of optics has been suggested in such diverse areas as storage, processing, and for providing communica-t put of this ~e~e=ch wss done ~hile the second author WVM Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice k given that copying is by permission of the Association for Computing Machinery. To copy otherwise , or to republish, requires a fee andlor specific permission. tion between different modules within computer systems. The use of optical interconnects …