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
Autonomic Management of Partitioners for SAMR Grid Hierarchies
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.
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. , p. 58
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: urn:nbn:se:uu:diva-99362ISBN: 978-91-554-7455-3 (print)OAI: oai:DiVA.org:uu-99362DiVA, id: diva2:207771
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: 2018-01-13Bibliographically approved
List of papers
1. A performance characterization of load balancing algorithms for parallel SAMR applications
Open this publication in new window or tab >>A performance characterization of load balancing algorithms for parallel SAMR applications
2006 (English)Report (Other academic)
Series
Technical report / Department of Information Technology, Uppsala University, ISSN 1404-3203 ; 2006-047
National Category
Computer Sciences
Identifiers
urn:nbn:se:uu:diva-83321 (URN)
Available from: 2008-02-19 Created: 2008-02-19 Last updated: 2018-01-13Bibliographically approved
2. Design and implementation of a dynamic and adaptive meta-partitioner for parallel SAMR grid hierarchies
Open this publication in new window or tab >>Design and implementation of a dynamic and adaptive meta-partitioner for parallel SAMR grid hierarchies
2008 (English)Report (Other academic)
Series
Technical report / Department of Information Technology, Uppsala University, ISSN 1404-3203 ; 2008-017
National Category
Software Engineering
Identifiers
urn:nbn:se:uu:diva-17508 (URN)
Available from: 2008-06-29 Created: 2008-06-29 Last updated: 2018-01-12Bibliographically approved
3. A patch-based partitioner for parallel SAMR applications
Open this publication in new window or tab >>A patch-based partitioner for parallel SAMR applications
2008 (English)In: Proc. Parallel and Distributed Computing and Systems: 2008, Calgary, Canada: ACTA Press , 2008, p. 53-58Conference paper, Published paper (Refereed)
Place, publisher, year, edition, pages
Calgary, Canada: ACTA Press, 2008
National Category
Computer Sciences
Identifiers
urn:nbn:se:uu:diva-99354 (URN)978-0-88986-773-4 (ISBN)
Available from: 2009-03-12 Created: 2009-03-12 Last updated: 2018-01-13Bibliographically approved
4. Component infrastructure for managing performance data and runtime adaptation of parallel applications
Open this publication in new window or tab >>Component infrastructure for managing performance data and runtime adaptation of parallel applications
Show others...
2008 (English)Conference paper, Published paper (Refereed)
Place, publisher, year, edition, pages
Trondheim, Norway: Norwegian University of Science and Technology, 2008
National Category
Software Engineering
Identifiers
urn:nbn:se:uu:diva-99358 (URN)
Conference
PARA 2008: State of the Art in Scientific and Parallel Computing
Available from: 2009-03-12 Created: 2009-03-12 Last updated: 2018-01-13Bibliographically approved
5. Run-time selection of partitioning algorithms for parallel SAMR applications
Open this publication in new window or tab >>Run-time selection of partitioning algorithms for parallel SAMR applications
2009 (English)Report (Other academic)
Series
Technical report / Department of Information Technology, Uppsala University, ISSN 1404-3203 ; 2009-007
National Category
Computer Sciences
Identifiers
urn:nbn:se:uu:diva-99186 (URN)
Available from: 2009-03-10 Created: 2009-03-10 Last updated: 2018-01-13Bibliographically approved
6. A Meta-Partitioner for run-time selection and evaluation of multiple partitioning algorithms for SAMR grid hierarchies
Open this publication in new window or tab >>A Meta-Partitioner for run-time selection and evaluation of multiple partitioning algorithms for SAMR grid hierarchies
2009 (English)Report (Other academic)
Series
Technical report / Department of Information Technology, Uppsala University, ISSN 1404-3203 ; 2009-008
National Category
Software Engineering
Identifiers
urn:nbn:se:uu:diva-99359 (URN)
Available from: 2009-03-12 Created: 2009-03-12 Last updated: 2018-01-13Bibliographically approved

Open Access in DiVA

fulltext(875 kB)413 downloads
File information
File name FULLTEXT01.pdfFile size 875 kBChecksum SHA-512
89ce422da71ede2d4dd0d54901800d631ec27c48a62f1ceeb478d240d0bd656e8b3cf173a2d0cc3f1db6d617e64d7283574304a8f46da48b9a908c2e62b07b10
Type fulltextMimetype application/pdf
Buy this publication >>

Authority records BETA

Johansson, Henrik

Search in DiVA

By author/editor
Johansson, Henrik
By organisation
Division of Scientific ComputingNumerical Analysis
Software Engineering

Search outside of DiVA

GoogleGoogle Scholar
Total: 413 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 1155 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