Optimal MPI Datatype Normalization for Vector and Index-block Types
Jesper Larsson Träff · 2014
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.