The Grainger College of Engineering
Parallel Programming Laboratory

Topology Aware Mapping

Introduction

Petascale machines with hundreds of thousands of cores are being built. These machines have varying interconnect topologies and large network diameters. Computation is cheap and communication on the network is becoming the bottleneck for scaling of parallel applications. Network contention, specifically, is becoming an increasingly important factor affecting overall performance. The broad goal of this research is performance optimization of parallel applications through reduction of network contention.

Most parallel applications have a certain communication topology. Mapping of tasks in a parallel application based on their communication graph, to the physical processors on a machine can potentially lead to performance improvements. We have developed an automatic mapping framework and implemented a mapping library to map the communication graph for an application on to the interconnect topology of a machine while trying to localize communication.

A parallel quantum chemistry application, OpenAtom, runs twice as fast when its objects are mapped in a topology aware fashion on various machines (see figures below). NAMD, a molecular dynamics applications also sees performance improvements of 10-15% at the scaling end. Building on these ideas, we have developed algorithms and techniques for automatic mapping of parallel applications to relieve the application developers of this burden. We use the hop-bytes metric for the evaluation of mapping algorithms and suggest that it is a better metric than the previously used maximum dilation metric. The main focus of this research is on developing topology aware mapping algorithms for parallel applications with regular and irregular communication patterns. The automatic mapping framework is a suite of such algorithms with capabilities to choose the best mapping for a problem with a given communication graph.

       

Software available for download

Contributions of this research

Our work is among the first to discuss the effects of contention on Cray and IBM machines and to compare across multiple architectures. Contrary to popular belief that Cray machines do not stand to benefit from topology mapping, this research proves otherwise and provides detailed methods and results for performance improvements from topology mapping on them. Another contribution of this work is an API for topology discovery which works on both Cray and IBM machines.

We believe that the set of MPI benchmarks we have developed for quantifying message latencies would be useful for the HPC community to assess latencies on a supercomputer and to determine the message sizes for which number of hops makes a significant difference. The effective bandwidth benchmark in the HPC Challenge benchmark suite measures the total bandwidth available on a system but does not analyze the effects of distance or contention on message latencies. Results from MPI benchmarks re-establish the importance of mapping for the current supercomputers.

Our experience in developing mapping algorithms for production codes and insights discussed in this work will be useful to individual application writers trying to scale their codes to large supercomputers. We believe that the automatic mapping framework is applicable to a wide variety of communication scenarios and will relieve the application writers from the burden of finding good mapping solutions for their codes. Application developers can use this framework for mapping of their applications without any changes to their code base. Unlike most of the previous work, this research handles both cardinality and topological variations in the graphs. The framework provides scalable and fast, runtime solutions. Therefore, it will be useful to a large body of applications running on large parallel machines.

There has not been much research on mapping of unstructured mesh applications for performance optimizations and this research takes up at that task. We have also started developing scalable techniques for distributed load balancing in an effort to move away from centralized mapping decision algorithms.

Papers / Talks