uu.seUppsala University Publications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • 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
A performance characterization of load balancing algorithms for parallel SAMR applications
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Division of Scientific Computing. Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Numerical Analysis. (Software Aspects of High-Performance Computing)
2006 (English)Report (Other academic)
Place, publisher, year, edition, pages
2006.
Series
Technical report / Department of Information Technology, Uppsala University, ISSN 1404-3203 ; 2006-047
National Category
Computer Science
Identifiers
URN: urn:nbn:se:uu:diva-83321OAI: oai:DiVA.org:uu-83321DiVA: diva2:111229
Available from: 2008-02-19 Created: 2008-02-19 Last updated: 2011-11-18Bibliographically approved
In thesis
1. Autonomic Management of Partitioners for SAMR Grid Hierarchies
Open this publication in new window or tab >>Autonomic Management of Partitioners for SAMR Grid Hierarchies
2009 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

Parallel structured adaptive mesh refinement methods decrease the execution time and memory usage of partial differential equation solvers by adaptively assigning computational resources to regions with large solution errors. These methods result in a dynamic grid hierarchy. To get good parallel performance, the grid hierarchy is frequently re-partitioned and distributed over the processors. Optimally, the partitioner should minimize all performance-inhibiting factors like load imbalance, communication volumes, synchronization delays, and data migration. No single partitioner performs well for all hierarchies and parallel computers. Because the partitioning conditions change during run-time, dynamically selecting a partitioner is non-trivial.

In this thesis, we present the Meta-Partitioner: a partitioning framework that autonomously selects, configures, invokes, and evaluates partitioning algorithms during run-time. For the implementation, we use component-based software-engineering. We predict the performance of the candidate partitioning algorithms with historical performance data for grid hierarchies similar to the current hierarchy. We focus the partitioning effort on the most performance-inhibiting factors — the load imbalance and the synchronization delays. At re-partitioning, a user-specified number of partitioning algorithms is selected and invoked. The performance of each partitioning is evaluated during run-time and the best one is selected.

The performance of the selected partitioning algorithms was compared both to the average performance of 768 algorithms and the global minimum at each re-partitioning. The results showed huge improvements both for the load imbalance and the synchronization delays. Compared to the average partitioning, the load imbalance was decreased by 28.2%. The synchronization delays were decreased by 21.5%. Compared to the global optimum, the load imbalance was increased by only 11.5%. For the synchronization delays, the increase was 13.6%. Often, the Meta-Partitioner selected the best algorithm among all candidate algorithms.

Place, publisher, year, edition, pages
Uppsala: Acta Universitatis Upsaliensis, 2009. 58 p.
Series
Digital Comprehensive Summaries of Uppsala Dissertations from the Faculty of Science and Technology, ISSN 1651-6214 ; 618
National Category
Software Engineering
Research subject
Scientific Computing
Identifiers
urn:nbn:se:uu:diva-99362 (URN)978-91-554-7455-3 (ISBN)
Public defence
2009-04-24, Room 2446, Polacksbacken, Lägerhyddsvägen 2D, Uppsala, 10:15 (English)
Opponent
Supervisors
Available from: 2009-04-02 Created: 2009-03-12 Last updated: 2011-10-26Bibliographically approved

Open Access in DiVA

No full text

Other links

http://www.it.uu.se/research/publications/reports/2006-047/

Authority records BETA

Johansson, Henrik

Search in DiVA

By author/editor
Johansson, Henrik
By organisation
Division of Scientific ComputingNumerical Analysis
Computer Science

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
Total: 610 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • 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