Title: Optimal all-to-all personalised exchange in a novel optical multistage interconnection network

Authors: Siu-Cheung Chau, Ada Wai-Chee Fu

Addresses: Department of Physics and Computer Science, Wilfrid Laurier University, Waterloo, Ontario N2L 3C5, Canada. ' Department of Computer Science and Engineering, Chinese University of Hong Kong, Shatin, Hong Kong

Abstract: An all-to-all personalised exchange is one of the most dense collective communication operations in parallel and distributed computing and communication applications. Each node in the network needs to send a different message to each of the other nodes. Advances in electro-optic switches have made optical communication a good networking choice that can satisfy the high channel bandwidth, low communication latency, low error rate, and gigabit transmission requirements of high performance computing and communication applications. Previously proposed optical multistage interconnection networks (MINs) require at least two passes to send a message from each node to a different node (to realise a permutation) in the network. In this paper, we propose an MIN that requires only one pass to realise a permutation. That is, the new MIN requires n–1 passes instead of 2n passes, the requirement for other optical MINs, for an all-to-all personalised exchange. The new network is optimal in terms of the number of passes that is required for an all-to-all personalised exchange.

Keywords: all-to-all personalised exchange; electro-optic switches; optical MIN; multistage interconnection networks; optical communication; networking; high performance computing; crosstalk avoidance; parallel computing; distributed computing; matrix transformation; fast Fourier transform; FFT.

DOI: 10.1504/IJHPCN.2005.007863

International Journal of High Performance Computing and Networking, 2005 Vol.3 No.1, pp.19 - 24

Published online: 28 Sep 2005 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article