Efficient Communication Algorithms for Pipeline Multicomputers

In this paper, we study the various communication algorithms on the pipeline multicomputer. We show how the three important communication functions (data distribution, data collection, and data broadcast) can be improved by reducing the propagation delay and using the right message size. Keywords: distributed-memory, pipeline multicomputer, communication algorithms, point-to-point routing. 1 Introduction The performance of distributed-memory MIMD (Multiple Instruction Multiple Data) applications depends to a large extent on the communication cost of the parallel systems. While significant advances have been accomplished in processor speed, the improvement in communication cost has lagged considerably. Therefore, in order to develop efficient parallel applications, we must use optimal communication patterns to offset the hardware communication cost. In this paper, we investigate the various communication algorithms for pipeline multicomputers. The pipeline architecture is a common sy..