Profiling Non-Numeric OpenSHMEM Applications with the TAU Performance System

The recent development of a unified SHMEM framework, OpenSHMEM, has enabled further study in the porting and scaling of applications that can benefit from the SHMEM programming model. In this paper we focus particularly on non-numerical graph algorithms, which typically have a low FLOPS/byte ratio. We provide an overview of the space and time complexity of Kruskal’s and Prim’s algorithms for generating a minimum spanning tree and present an OpenSHMEM implementation of Kruskal’s algorithm. The implementation uses the symmetric hierarchical memory to generate the minimum spanning tree without inter-node communication. Additionally, we describe the steps required to produce an in depth performance analysis of memory access patterns and load balancing within the symmetric heap using the TAU Performance System. Our performance evaluation includes measurements on the Cray XK7 “Titan” system at ORNL and a large, 48 core shared memory system at the University of Maryland Baltimore County.