Accelerating Parallel Applications Based on Graph Reordering for Random Network Topologies
Author:
Open Access
- 24 April 2023
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Access
- Vol. 11, 40373-40383
Abstract
The Message Passing Interface (MPI) is a crucial programming tool for enabling communication between processes in parallel applications. The goal of MPI users is to allocate tasks to processors in a way that maximizes both spatial and temporal locality in the network. However, this can be challenging, especially in large-scale networks where maximizing processor locality may not be feasible at runtime. To address this issue, we propose the use of Hamorder , an offline node reassignment approach that takes into account physical processor locations based on graph reordering for Random network topologies. Hamorder aims to optimize task mapping for improved performance in parallel applications, whether for multiple tasks or within a single task. Additionally, we investigate the potential of improving MPI applications through runtime parameter tuning based on Hamorder . Our evaluation results show that Hamorder provides a 27.3% improvement in performance compared to the Gorder algorithm on Random topologies, which is a state-of-the-art solution designed with the aim of enhancing cache locality and achieves this goal by rearranging the vertices of a graph in a way that places the vertices that are typically accessed together in close proximity. Moreover, our autotuning framework using Hamorder results in an average speedup of 1.38x for targeted MPI applications by searching through various runtime parameter combinations.Keywords
Funding Information
- Japan Society for the Promotion of Science (JSPS) Kakenhi (21K11859)
This publication has 25 references indexed in Scilit:
- Speedup Graph Processing by Graph Ordering2016
- Rabbit Order: Just-in-Time Parallel Reordering for Fast Graph Analysis2016
- PaCMap2015
- Augmenting low-latency HPC network with free-space optical links2015
- Versatile, scalable, and accurate simulation of distributed applications and platformsJournal of Parallel and Distributed Computing, 2014
- OpenTuner2014
- Optimization of MPI collective communication on BlueGene/L systems2005
- CC--MPI2003
- MagPIe1999
- Issues in the study of graph embeddings1981