Adaptive and Dynamic Design for MPI Tag Matching

The Message Passing Interface (MPI) standard specifies the use of (source, tag, communicator) tuple to identify whether an incoming message is what the receiver process is expecting. The cost associated with this process, commonly known as "tag matching", is tightly coupled with the communication pattern of the application and the load it generates at each individual process. Although researchers have proposed several schemes to mitigate the cost of tag matching, they have all been static and do not adapt dynamically to the communication load at individual processes and can lead to degradation in tag matching times. Such static designs can also lead to unnecessary memory overheads for queue management at processes whose communication loads do not justify enhanced tag matching schemes. In this paper, we take up this challenge and propose a tag matching design which dynamically adapts to the communication load at each individual process at runtime. Our experimental evaluation shows that the proposed adaptive and dynamic tag matching scheme is able to deliver the best performance when compared with multiple state-of-the-art tag matching schemes while limiting the memory consumed to the absolute minimum necessary to deliver the desired performance benefits. For instance, with HPCG, the adaptive scheme delivers 20%, 32% and up to 2X improvements in tag matching performance when compared to the default, bin-based and rank-based schemes, respectively. To the best of our knowledge this is the first tag matching design that is capable of dynamically adapting to the communication requirements of end applications.