The MPI-3.0 standard introduced neighborhood collective to support sparse communication patterns used in many applications. In this paper, we propose a hierarchical and distributed graph topology that considers the physical topology of the system and the virtual communication pattern of processes to improve the performance of large message neighborhood collectives. Moreover, we propose two design alternatives on top of the hierarchical design: 1. LAG-H: assumes the same communication load for all processes, 2. LAW-H: considers the communication load of processes for fair distribution of load between them. We propose a mathematical model to determine the communication capacity of each process. Then, we use the derived capacity to fairly distribute the load between processes. Our experimental results on up to 28,672 processes show up to 9x speedup for various process topologies. We also observe up to 8.2% performance gain and 34x speedup for NAS-DT and SpMM, respectively.

Summary The Message Passing Interface (MPI) is the de facto standard for parallel programming in High Performance Computing (HPC). Asynchronous communications in MPI involve message matching semantics that must be satisfied by the conforming libraries. The matching performance is in the critical path of communications in MPI. However, the current message matching approaches suffer from scalability issues and/or do not consider the message queue characteristics of the applications. In this paper, we propose a new message matching mechanism for MPI that can speed up the operation by allocating dedicated queues for certain communications of an application. More specifically, we propose a design that categorizes communications into a set of partners and non‐partners based on the communication frequency in the corresponding queues. We propose a static and a dynamic approach for our message matching design. While the static approach works based on the information from a profiling stage, the dynamic approach utilizes the message queue characteristics at runtime. Our experimental evaluations show that the proposed design can provide up to 28x speedup in queue search time for long list traversals without degrading the performance for short list traversals. We can also gain up to 5x speedup for the FDS application, which is highly affected by the message matching performance.

Contemporary parallel scientific codes often rely on message passing for inter-process communication. However, inefficient coding practices or multithreading (e.g., via MPI_THREAD_MULTIPLE) can severely stress the underlying message processing infrastructure, resulting in potentially un-acceptable impacts on application performance. In this article, we propose and evaluate a novel method for addressing this issue: 'Fuzzy Matching'. This approach has two components. First, it exploits the fact most server-class CPUs include vector operations to parallelize message matching. Second, based on a survey of point-to-point communication patterns in representative scientific applications, the method further increases parallelization by allowing matches based on 'partial truth', i.e., by identifying probable rather than exact matches. We evaluate the impact of this approach on memory usage and performance on Knight's Landing and Skylake processors. At scale (262,144 Intel Xeon Phi cores), the method shows up to 1.13 GiB of memory savings per node in the MPI library, and improvement in matching time of 95.9%; smaller-scale runs show run-time improvements of up to 31.0% for full applications, and up to 6.1% for optimized proxy applications.

Neighborhood collectives are introduced in MPI3.0 standard to provide users with the opportunitv to define their own communication patterns through the process topologv interface of MPI. In this paper, we propose a collaborative communication mechanism based on common neighborhoods that might exist among groups of k processes. Such common neighborhoods are used to decrease the number of communication stages through message combining. We show how designing our desired communication pattern can be modeled as a maximum weighted matching problem in distributed hvpergraphs, and propose a distributed algorithm to solve it. Moreover, we consider two design alternatives: topologvagnostic and topologv-aware. The former ignores the phvsical topologv o7 the svstem and the mapping o7 processes, whereas the latter takes them into account to further optimize the communication pattern. Our experimental results show that we can gain up to 8x and 5.2x improvement for various process topologies and a SpMM kernel, respectivelv.

The performance critical path for MPI implementations relies on fast receive side operation, which in turn requires fast list traversal. The performance of list traversal is dependent on data-locality; whether the data is currently contained in a close-to-core cache due to its temporal locality or if its spacial locality allows for predictable pre-fetching. In this paper, we explore the effects of data locality on the MPI matching problem by examining both forms of locality. First, we explore spacial locality, by combining multiple entries into a single linked list element, we can control and modify this form of locality. Secondly, we explore temporal locality by utilizing a new technique called "hot caching", a process that creates a thread to periodically access certain data, increasing its temporal locality. In this paper, we show that by increasing data locality, we can improve MPI performance on a variety of architectures up to 4x for micro-benchmarks and up to 2x for an application.