[Back]

J. Träff:
"Optimal MPI Datatype Normalization for Vector and Index-block Types";
Talk: 21st European MPI Users' Group Meeting, EuroMPI/ASIA 2014, Kyoto, Japan; 2014-09-09 - 2014-09-12; in: "Proceedings of the 21st European MPI Users' Group Meeting", J. Dongarra, Y. Ishikawa, A. Hori (ed.); ACM, New York, NY, USA (2014), ISBN: 978-1-4503-2875-3; 33 - 38.

The derived datatypes of MPI is an extremely powerful mechanism for specifying the layout of data in communication operations. It is desirable that MPI libraries internally simplify complex datatype descriptions into representations that are efficient for the communication operations in which they are used. This process is called datatype normalization, and MPI libraries typically employ simple heuristics for this task. In this paper we embark on a study of the inherent complexity of datatype normalization, and show that the problem with a specific, but flexible cost model can be solved cost-optimally for MPI vector and index-block types in polynomial time. For a type map consisting of n displacement-basetype pairs, we first give a type reconstruction algorithm running in O(n√n) time steps. We then use this algorithm for datatype normalization of given derived datatypes.

http://dx.doi.org/10.1145/2642769.2642771

Project Head Jesper Larsson Träff:
EPiGRAM