Efficient Communication Operations in Reconfigurable Parallel Computers

Reconfiguration is largely an unexplored property in the context of parallel models of computation. However, it is a powerful concept as far as massively parallel architectures are concerned, because it overcomes the constraints due to the bissection width arising in most of distributed memory machines. In this paper, we show how to use reconfiguration in order to improve communication operations that are widely used in parallel applications. We propose quasi-optimal algorithms for broadcasting, scattering, gossiping and multi-scattering. Keywords: Reconfiguration, broadcast, scattering, gossiping, communications, distributed memory parallel computers 1 Introduction For massively parallel architectures, the hardware complexity of the interconnection network is much higher than that of the processing units: "the interconnection network employs 99% of the hardware involved" [JMM92]. Moreover, due to the communication-intensive nature of most computational tasks, their performance depen..