Title: Efficient construction of provably optimal MPI datatype representations
Language: English
Authors: Kalany, Martin 
Qualification level: Diploma
Advisor: Träff, Jesper Larsson  
Issue Date: 2015
Number of Pages: 111
Qualification level: Diploma
Derived datatypes are an integral part of the Message Passing Interface (MPI), the de-facto standard for programming massively parallel, high performance applications. The mechanism is essential for efficient and portable implementations of programs working with complex data layouts. MPI defines several type constructors that are capable of describing arbitrarily complex, heterogeneous and non-contiguous data layouts. The type constructors may be applied recursively, leading to tree-like representations of data layouts, also called type trees. Typically, multiple different representations of a given data layout exist. MPI implementations require concise representations to process derived datatypes efficiently. It is not easy to see for users which representation is the best for a given data layout, since many non-obvious factors need to be considered, such as machine specific hardware capabilities and optimizations. The problem of computing the most concise (or optimal) type tree representation for a given data layout was coined the Type Reconstruction Problem. It has been an open question whether this problem can be solved to optimality in polynomial time (w.r.t. to the size of the represented data layout). So far, heuristics have been used to improve a given representation, without providing any guarantees about the quality of the result. In this master's thesis, we present an algorithm that solves the Type Reconstruction Problem for arbitrarily complex data layouts in order n to the fourth time, where n is the size of the data layout. A recent work showed that optimal representations can be computed in sub-quadratic time if the set of considered type constructors is reduced to those with only one sub-type, i.e., if the type trees are restricted to type paths. For this special case, called the Type Path Reconstruction Problem, we improve the currently best known asymptotic bound significantly.
Keywords: Systeme mit verteiltem Speicher; Hochleistungsrechnen; Message Passing Interface
Distributed Memory Systems; High Performance Computing; Message Passing Interface
URI: https://resolver.obvsg.at/urn:nbn:at:at-ubtuw:1-79466
Library ID: AC12685267
Organisation: E184 - Institut für Informationssysteme 
Publication Type: Thesis
Appears in Collections:Thesis

Files in this item:

Page view(s)

checked on Feb 18, 2021


checked on Feb 18, 2021

Google ScholarTM


Items in reposiTUm are protected by copyright, with all rights reserved, unless otherwise indicated.