Automated Mapping of Structured Communication Graphs onto Mesh Interconnects

Bhatele, Abhinav; Chung, I-Hsin; Kale, Laxmikant V.

Permalink

https://hdl.handle.net/2142/15407 Copy

Description

Title

Automated Mapping of Structured Communication Graphs onto Mesh Interconnects

Author(s)

• Bhatele, Abhinav
• Chung, I-Hsin
• Kale, Laxmikant V.

Issue Date

2010-04

Keyword(s)

• mapping
• regular graphs
• performance optimization
• communication
• network topology

Abstract

Network contention has an increasingly adverse effect on the performance of parallel applications with increasing size of parallel machines. Machines of the petascale era are forcing application developers to map tasks intelligently to job partitions to achieve the best performance possible. This paper presents a framework for automated mapping of parallel applications with structured communication graphs to two and three dimensional mesh networks. We present several heuristic techniques for mapping 2D object graphs to 2D and 3D processor graphs and compare their performance with other algorithms in literature. We use the hop-bytes metric to evaluate and compare across different mapping strategies and justify that it is more important to reduce the average hop-bytes than maximum dilation. We test our algorithms on three scientific applications, MILC, POP and WRF and present performance improvements of more than $15\%$ in some cases on IBM's Blue Gene/P machine. The main contribution of this paper, is the automated mapping framework for a wide class of MPI applications with structured communication graphs. This framework will save much effort on the part of application developers to generate mappings for their individual applications.

Type of Resource

text

Language

en

Permalink

http://hdl.handle.net/2142/15407

Owning Collections