liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Load balancing of irregular parallel divide-and-conquer algorithms in group-SPMD programming environments
Linköping University, Department of Computer and Information Science, PELAB - Programming Environment Laboratory. Linköping University, The Institute of Technology.
Linköping University, Department of Computer and Information Science, PELAB - Programming Environment Laboratory. Linköping University, The Institute of Technology.ORCID iD: 0000-0001-5241-0026
Linköping University, Department of Computer and Information Science, PELAB - Programming Environment Laboratory. Linköping University, The Institute of Technology.
2006 (English)In: 8th Workshop on Parallel Systems and Algorithms PASA 2006 / [ed] Wolfgang Karl, Jürgen Becker, Karl-Erwin Großpietsch, Christian Hochberger and Erik Maehle, Frankfurt/Main, Germany, 2006, 313-322 p.Conference paper, Published paper (Refereed)
Abstract [en]

We study strategies for local load balancing of irregular parallel divide-andconquer algorithms such as Quicksort and Quickhull in SPMD-parallel environments such as MPI and Fork that allow to exploit nested parallelism by dynamic group splitting. We propose two new local strategies, repivoting and serialisation, and develop a hybrid local load balancing strategy, which is calibrated by parameters that are derived off-line from a dynamic programming optimisation. While the approach is generic, we have implemented and evaluated our method for two very different parallel platforms. We found that our local strategy is superior to global dynamic load balancing on a Linux cluster, while the latter performs better on a tightly synchronised sharedmemory platform with nonblocking, cheap task queue access.

Place, publisher, year, edition, pages
Frankfurt/Main, Germany, 2006. 313-322 p.
Series
GI Lecture Notes in Informatics (LNI), vol. P-81
National Category
Computer Science
Identifiers
URN: urn:nbn:se:liu:diva-35761Local ID: 28492ISBN: 3-88579-175-7 (print)OAI: oai:DiVA.org:liu-35761DiVA: diva2:256609
Conference
8th Workshop on Parallel Systems and Algorithms (PASA 2006), March 16, 2006, Frankfurt/Main, Germany - in connection with the 19th International Conference on Architecture of Computing Systems (ARCS 2006), March 13-16, 2006, Frankfurt/Main, Germany
Available from: 2009-10-10 Created: 2009-10-10 Last updated: 2014-10-08Bibliographically approved

Open Access in DiVA

No full text

Authority records BETA

Eriksson, MattiasKessler, ChristophChalabine, Mikhail

Search in DiVA

By author/editor
Eriksson, MattiasKessler, ChristophChalabine, Mikhail
By organisation
PELAB - Programming Environment LaboratoryThe Institute of Technology
Computer Science

Search outside of DiVA

GoogleGoogle Scholar

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 177 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf