Collective Communications on a Bewoulf Project   Wi Bing Tan and Peter Strazdins

Updated: 29th August 2002

Abstract for ICPADS'02 paper:
Analysis and Optimisation of Collective Communications on a Beowulf Cluster

This paper gives a performance analysis of the All-Gather, All-Reduce and Reduce-Scatter collective communication operations on a Beowulf cluster. This cluster has a contention-free switch-based network with multiple network interface cards per node, permitting overlapping of message transmission under certain circumstances. As well as considering traditional algorithms developed previously for parallel computers with vendor-specific networks, we also examine simpler algorithms made up of repeated sub-operations, such as broadcasts. We find that for the kind of network on the Beowulf cluster, a somewhat different performance modeling of the algorithm is required, and that some simple simulation tools had to be developed in order to fully understand some of the algorithms' performance.

Our results indicate that the LAM MPI implementations for these operations may be significantly improved, and the algorithms with data exchange and potential contention perform well on the cluster. Furthermore, they indicate that algorithms permitting message overlap are slightly favoured, with a new and simple algorithm which modestly out-performs the best traditional algorithms in the case of Reduce-Scatter. With the exception that the degree of overlapping proved difficult to estimate, our performance models fitted closely with the results, and together with the simulation tools, permit a detailed understanding of the cluster's communication pattern performance.


Download ICPADS'02 Paper

Wi Bing Tan and Peter Strazdins. The Analysis and Optimization of Collective Communications on a Beowulf Cluster , In Proceedings of ICPADS'02: 2002 International Conference on Parallel and Distributed Systems, pp 659--666, IEEE Press, Taipei, Dec. 2002

IEEE Explore entry

paper (pdf 328 KB)

A copy of the related honours thesis can also be downloaded in Compressed Postscript (.ps.gz) - 229 kB format.

The slides for the ICPAD2002 presentation in pdf.


Download Companion Paper

<>This paper contains explanatory figures, omitted from the ICPADS'02 paper due to size contraints. The paper is available in a number of formats; Adobe Acrobat (.pdf) - 120 KB and Compressed Postscript (.ps.gz) 54 KB


Code and Implementations

There are a number of programs which which have been used to test and implement the various algorithms. Instructions and code can be downloaded from the respective links.

  • Implementation - The implementation of the algorithms for the various operations.
  • Simulator - Simulator related code and programs.
  • Fitting - Code to generate the theoretical program models.

For further enquiries, contact: Wi Bing Tan or Peter Strazdins