A pipelined algorithm for large, irregular all-gather problems

Jesper Larsson Träff, Andreas Ripke, Christian Siebert, Pavan Siebert, Rajeev Siebert, William Gropp

Research output: Contribution to journalArticlepeer-review


We describe and evaluate a new pipelined algorithm for large, irregular all-gather problems. In the irregular allgather problem each process in a set of processes contributes individual data of possibly different size, and all processes have to collect all data from all processes. The pipelined algorithm is useful for the implementation of the MPI-Allgatherv collective operation of the Message-Passing Interface (MPI) for large problems. By conception, the new algorithm is well suited to implementation on clustered multiprocessors, such as symmetric multiprocessing (SMP) clusters. The new algorithm has been implemented within different MPI libraries. Benchmark results on NEC SX-8, Linux clusters with InfiniBand and Gigabit Ethernet, IBM Blue Gene/P, and SiCortex systems show huge performance gains in accordance with the expected behavior.

Original languageEnglish (US)
Pages (from-to)58-68
Number of pages11
JournalInternational Journal of High Performance Computing Applications
Issue number1
StatePublished - 2010


  • All-gather problem
  • Collective operations
  • IBM Blue Gene/P
  • Linux clusters
  • Message-passing interface
  • NEC SX-8
  • Pipelining
  • SiCortex

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture


Dive into the research topics of 'A pipelined algorithm for large, irregular all-gather problems'. Together they form a unique fingerprint.

Cite this