An Examination of a Symmetric Memory Model's Impact on Performance in a Distributed Graph Algorithm

Over the last few decades, Message Passing Interface (MPI) has become the parallel-communication standard for distributed algorithms on high-performance platforms. MPI's minimal setup overhead and simple API calls give it a low barrier of entry, while still providing support for more complex communication patterns. Communication schemes that use physically or logically shared memory provide a number of improvements to HPC-algorithm parallelization. These models prioritize the reduction of synchronization calls between processors and the overlapping of communication and computation via strategic programming techniques. The OpenSHMEM specification developed in the last decade applies these benefits to distributed-memory computing systems by leveraging a Partitioned Global Address Space (PGAS) model and remote memory access (RMA) operations. Paired with non-blocking communication patterns, these technologies enable increased parallelization of existing apps. This research studies the impact of these techniques on the Multi-Node Parallel Boruvka's Minimum Spanning Tree Algorithm (MND-MST), which uses distributed programming for inter-processor communication. This research also provides a foundation for applying complex communication libraries like OpenSHMEM to large-scale parallel apps. To provide further context for the comparison of MPI to OpenSHMEM, this work presents a baseline comparison of relevant API calls as well as a productivity analysis for both imple- mentations of the MST algorithm. Through experiments performed on the National Energy Research Scientific Computing Center (NERSC), it is found that the OpenSHMEM-based app has an average of 33.9% improvement in overall app execution time scaled up to 16 nodes and 64 processes. The program complexity, measured as a combination of lines of code and API calls, increases from MPI to OpenSHMEM implementations by ~25%. These findings encourage further study into the use of distributed symmetric-memory architectures and RMA-communication models applied to scalable HPC apps