[Back]


Talks and Poster Presentations (with Proceedings-Entry):

M. Kalany, J. Träff:
"Efficient, Optimal MPI Datatype Reconstruction for Vector and Index Types";
Talk: 22nd European MPI Users' Group Meeting, EuroMPI 2015, Bordeaux, France; 2015-09-21 - 2015-09-23; in: "Proceedings of the 22nd European MPI Users' Group Meeting, EuroMPI 2015", J. Dongarra, A. Denis, B. Goglin, E. Jeannot, G. Mercier (ed.); ACM, (2015), ISBN: 978-1-4503-3795-3; Paper ID 5, 10 pages.



English abstract:
Type reconstruction is the process of finding an efficient representation in terms of space and processing time of a data layout as an MPI derived datatype. Practically efficient type reconstruction and normalization is important for high-quality MPI implementations that strive to provide good performance for communication operations involving noncontiguous data. Although it has recently been shown that the general problem of computing optimal tree representations of derived datatypes allowing any of the MPI derived datatype constructors can be solved in polynomial time, the algorithm for this may unfortunately be impractical for datatypes with large counts. By restricting the allowed constructors to vector and index-block type constructors, but excluding the most general MPI_Type_create_struct constructor, the problem can be solved much more efficiently. More precisely, we give a new O(n log n/log log n) time algorithm for finding cost-optimal representations of MPI type maps of length n using only vector and index-block constructors for a simple but flexible, additive cost model. This improves significantly over a previous O(n√n) time algorithm for the same problem, and the algorithm is simple enough to be considered for practical MPI libraries.


"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)
http://dx.doi.org/10.1145/2802658.2802671



Related Projects:
Project Head Jesper Larsson Träff:
EPiGRAM