Compact and Efficient Implementation of the MPI Group Operations

We describe a more compact representation of MPI

process groups

based on strided, partial sequences that can support all group and communicator creation operations in time proportional to the size of the argument groups. The worst case lookup time (to determine the global processor id corresponding to a local process rank) is logarithmic, but often better (constant), and can be traded against maximum possible compaction. Many commonly used MPI process groups can be represented in

constant space

with

constant lookup time

, for instance the process group of

MPI_COMM_WORLD

, and all consecutive subgroups of this group, but also many, many others). The representation never uses more than one word per process, but often much less, and is in this sense strictly better than the trivial, often used representation by means of a simple mapping array. The data structure and operations have all been implemented, and experiments show very worthwhile space savings for classes of process groups that are believed to be typical of MPI applications.