A simple, pipelined algorithm for large, irregular all-gather problems

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We present and evaluate a new, simple, pipelined algorithm for large, irregular all-gather problems, useful for the implementation of the MPI_Allgatherv collective operation of MPI. The algorithm can be viewed as an adaptation of a linear ring algorithm for regular all-gather problems for single-ported, clustered multiprocessors to the irregular problem. Compared to the standard ring algorithm, whose performance is dominated by the largest data size broadcast by a process (times the number of processes), the performance of the new algorithm depends only on the total amount of data over all processes. The new algorithm has been implemented within different MPI libraries. Benchmark results on NEC SX-8, Linux clusters with InfiniBand and Gigabit Ethernet, Blue Gene/P, and SiCortex systems show huge performance gains in accordance with the expected behavior.

Original languageEnglish (US)
Title of host publicationRecent Advances in Parallel Virtual Machine and Message Passing Interface - 15th European PVM/MPI Users' Group Meeting, Proceedings
Pages84-93
Number of pages10
DOIs
StatePublished - 2008
Event15th European PVM/MPI Users' Group Meeting, EuroPVM/MPI 2008 - Dublin, Ireland
Duration: Sep 7 2008Sep 10 2008

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5205 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other15th European PVM/MPI Users' Group Meeting, EuroPVM/MPI 2008
CountryIreland
CityDublin
Period9/7/089/10/08

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

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

Cite this