Polynomial-time Construction of Optimal MPI Derived Datatype
Trees

D 2016

Polynomial-time Construction of Optimal MPI Derived Datatype Trees

GANIAN, Robert; Martin KALANY; Stefan SZEIDER a Jesper Larsson TRAFF

Základní údaje

Originální název

Polynomial-time Construction of Optimal MPI Derived Datatype Trees

Autoři

GANIAN, Robert; Martin KALANY; Stefan SZEIDER a Jesper Larsson TRAFF

Vydání

NEW YORK, 2016 IEEE 30TH INTERNATIONAL PARALLEL AND DISTRIBUTED PROCESSING SYMPOSIUM (IPDPS 2016), od s. 638-647, 10 s. 2016

Nakladatel

IEEE

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Spojené státy

Utajení

není předmětem státního či obchodního tajemství

Forma vydání

elektronická verze "online"

Kód RIV

RIV/00216224:14330/16:00093947

Organizační jednotka

Fakulta informatiky

ISBN

978-1-5090-2140-6

ISSN

DOI

https://doi.org/10.1109/IPDPS.2016.13

UT WoS

000391251800066

EID Scopus

2-s2.0-84983287843

Klíčová slova anglicky

MPI; derived datatypes; type reconstruction; dynamic programming

Štítky

core_A, firank_A

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 27. 4. 2017 07:09, RNDr. Pavel Šmerk, Ph.D.

Anotace

V originále

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.

Citovat

GANIAN, Robert; Martin KALANY; Stefan SZEIDER a Jesper Larsson TRAFF. Polynomial-time Construction of Optimal MPI Derived Datatype Trees. Online. In 2016 IEEE 30TH INTERNATIONAL PARALLEL AND DISTRIBUTED PROCESSING SYMPOSIUM (IPDPS 2016). NEW YORK: IEEE, 2016, s. 638-647. ISBN 978-1-5090-2140-6. Dostupné z: https://doi.org/10.1109/IPDPS.2016.13.

@inproceedings{1376047,
   author = {Ganian, Robert and Kalany, Martin and Szeider, Stefan and Traff, Jesper Larsson},
   address = {NEW YORK},
   booktitle = {2016 IEEE 30TH INTERNATIONAL PARALLEL AND DISTRIBUTED PROCESSING SYMPOSIUM (IPDPS 2016)},
   doi = {https://doi.org/10.1109/IPDPS.2016.13},
   keywords = {MPI; derived datatypes; type reconstruction; dynamic programming},
   howpublished = {elektronická verze "online"},
   language = {eng},
   location = {NEW YORK},
   isbn = {978-1-5090-2140-6},
   pages = {638-647},
   publisher = {IEEE},
   title = {Polynomial-time Construction of Optimal MPI Derived Datatype Trees},
   year = {2016}
}

TY  - CONF
ID  - 1376047
AU  - Ganian, Robert - Kalany, Martin - Szeider, Stefan - Traff, Jesper Larsson
PY  - 2016
TI  - Polynomial-time Construction of Optimal MPI Derived Datatype Trees
PB  - IEEE
CY  - NEW YORK
SN  - 9781509021406
KW  - MPI
KW  - derived datatypes
KW  - type reconstruction
KW  - dynamic programming
N2  - 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.
ER  -

GANIAN, Robert; Martin KALANY; Stefan SZEIDER a Jesper Larsson TRAFF. Polynomial-time Construction of Optimal MPI Derived Datatype Trees. Online. In \textit{2016 IEEE 30TH INTERNATIONAL PARALLEL AND DISTRIBUTED PROCESSING SYMPOSIUM (IPDPS 2016)}. NEW YORK: IEEE, 2016, s.~638-647. ISBN~978-1-5090-2140-6. Dostupné z: https://doi.org/10.1109/IPDPS.2016.13.

Přehled o publikaci