Polynomial-Time Construction of Optimal MPI Derived Datatype Trees
Polynomial-Time Construction of Optimal MPI Derived Datatype Trees
复制标题
最佳 MPI 派生数据类型树的多项式时间构造
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
J. Träff
中科院分区：
文献类型：
--
作者：
R. Ganian;Martin Kalany;Stefan Szeider;J. Träff
派生数据类型机制是消息传递接口 (MPI) 的一个强大的整体功能，用于通信任意结构的、可能不连续和非同质的应用程序数据。 MPI 定义了一组通用性不断增强的派生数据类型构造函数，它允许以相当紧凑的方式描述任意数据布局。可以递归地应用构造函数，从而产生应用程序数据布局的树状表示。 MPI 实现需要高效的派生数据类型表示来有效地访问和处理结构化应用程序数据。我们研究寻找在空间和处理成本方面最优的 MPI 派生数据类型的树状表示的问题。更准确地说，我们考虑所谓的 MPI 类型重构问题，即为给定的构造函数集确定给定数据布局的最低成本树状表示。在考虑了构造函数的空间消耗和处理成本下限的附加成本模型中，我们表明对于全套 MPI 数据类型构造函数，可以在多项式时间内解决该问题。我们的算法使用动态规划，并需要在增量构建的有向无环图上解决一系列最短路径问题。
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 Reconstruction Problem of determining a least-cost tree-like 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.