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

Direct link
Domain-based partitioning 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)
2001 (English)Licentiate thesis, comprehensive summary (Other academic)
Abstract [en]

This thesis presents a study of domain-based partitioning techniques for dynamic structured grid hierarchies, occuring in structured adaptive mesh refinement (SAMR) methods. Such methods for obtaining the numerical solution to partial differential equations yield highly advantageous ratios for cost/accuracy as compared to methods based upon static uniform approximations. Distributed implementations of these techniques have the potential for enabling realistic simulations of complex systems. These implementations however, present significant challenges in dynamic data-distribution and load balancing. That is, when SAMR is executed on a parallel computer, the work load will change dynamically. Thus, there is need for dynamic load balancing in order to efficiently utilize the resourses of the parallel computer. Inverse space-filling curve partitioning (ISP) is appealing for load balancing in parallel SAMR, because of its speed. In this work, ISP is considered as part of a partitioning approach, which combines structured and unstructured techniques.

Various design decisions for the structured partitioning are considered. Different design choices lead to graphs with different properties. One objective is to investigate how these differences affect the behavior of ISP. This thesis contributes by identifying certain design choices as being advantageous, and by presenting four new partitioning algorithms that correspond to these design decisions.

An experimental comparison of dynamic partitioning techniques for blockwise parallel structured adaptive mesh refinement applications is presented. It is shown that an ISP-based technique can compete with other approaches for certain classes of applications. Moreover, an extended experimental characterization of dynamic partitioning/load-balancing techniques for general adaptive grid hierarchies is presented. Techniques studied include newly proposed as well as existing approaches. It was found that two of the proposed algorithms were particularly useful: pBD-ISP for the more communication dominated applications, and G-MISP+SP for the computation dominated applications.

Policies for the automatic selection of partitioner based on application and system state are outlined. Recommendations for appropriate partitioning techniques, given application and system state, are given. The overall motivation is the formulation of policies required to drive a dynamically adaptive meta-partitioner for SAMR grid hierarchies capable of selecting the most appropriate partitioning strategy at runtime, based on current application and system state. Such a partitioner may significantly decrease application execution time.

Place, publisher, year, edition, pages
Uppsala universitet, 2001.
Information technology licentiate theses: Licentiate theses from the Department of Information Technology, ISSN 1404-5117 ; 2001-002
National Category
Software Engineering
Research subject
Numerical Analysis
URN: urn:nbn:se:uu:diva-86009OAI: oai:DiVA.org:uu-86009DiVA: diva2:116818
Available from: 2001-03-16 Created: 2006-05-14 Last updated: 2014-08-13Bibliographically approved

Open Access in DiVA

No full text

By organisation
Division of Scientific ComputingNumerical Analysis
Software Engineering

Search outside of DiVA

GoogleGoogle Scholar
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

Total: 240 hits
ReferencesLink to record
Permanent link

Direct link