GANIAN, Robert, Martin KALANY, Stefan SZEIDER and Jesper Larsson TRAFF. Polynomial-time Construction of Optimal MPI Derived Datatype Trees. In 2016 IEEE 30TH INTERNATIONAL PARALLEL AND DISTRIBUTED PROCESSING SYMPOSIUM (IPDPS 2016). NEW YORK: IEEE. p. 638-647. ISBN 978-1-5090-2140-6. doi:10.1109/IPDPS.2016.13. 2016.
Other formats:   BibTeX LaTeX RIS
Basic information
Original name Polynomial-time Construction of Optimal MPI Derived Datatype Trees
Authors GANIAN, Robert (203 Czech Republic, guarantor, belonging to the institution), Martin KALANY (40 Austria), Stefan SZEIDER (40 Austria) and Jesper Larsson TRAFF (40 Austria).
Edition NEW YORK, 2016 IEEE 30TH INTERNATIONAL PARALLEL AND DISTRIBUTED PROCESSING SYMPOSIUM (IPDPS 2016), p. 638-647, 10 pp. 2016.
Publisher IEEE
Other information
Original language English
Type of outcome Proceedings paper
Field of Study 10201 Computer sciences, information science, bioinformatics
Country of publisher United States of America
Confidentiality degree is not subject to a state or trade secret
Publication form electronic version available online
RIV identification code RIV/00216224:14330/16:00093947
Organization unit Faculty of Informatics
ISBN 978-1-5090-2140-6
ISSN 1530-2075
Doi http://dx.doi.org/10.1109/IPDPS.2016.13
UT WoS 000391251800066
Keywords in English MPI; derived datatypes; type reconstruction; dynamic programming
Tags core_A, firank_A
Tags International impact, Reviewed
Changed by Changed by: RNDr. Pavel Šmerk, Ph.D., učo 3880. Changed: 27/4/2017 07:09.
Abstract
The derived datatype mechanism is a powerful, integral feature of the Message-Passing Interface (MPI) for communicating arbitrarily structured, possibly non-consecutive and non-homogeneous application data. MPI defines a set of derived datatype constructors of increasing generality, which allows to describe arbitrary data layouts in a reasonably compact fashion. The constructors may be applied recursively, leading to tree-like representations of the application data layouts. Efficient derived datatype representations are required for MPI implementations to efficiently access and process structured application data. We study the problem of finding tree-like representations of MPI derived datatypes that are optimal in terms of space and processing cost. More precisely, we consider the so-called MPI TYPE TREE RECONSTRUCTION PROBLEM of determining a least-cost treelike representation of a given data layout for a given set of constructors. In an additive cost model that accounts for the space consumption of the constructors and lower-bounds the processing costs, we show that the problem can be solved in polynomial time for the full set of MPI datatype constructors. Our algorithm uses dynamic programming and requires the solution of a series of shortest path problems on an incrementally built, directed, acyclic graph.
PrintDisplayed: 28/3/2024 14:29