IDEALS Home University of Illinois at Urbana-Champaign logo The Alma Mater The Main Quad

Automating Topology Aware Mapping for Supercomputers

Show full item record

Bookmark or cite this item: http://hdl.handle.net/2142/16578

Files in this item

File Description Format
PDF thesis.pdf (6MB) Main Document PDF
Title: Automating Topology Aware Mapping for Supercomputers
Author(s): Bhatele, Abhinav
Subject(s): mapping, interconnect topology, communication optimizations, performance, graph embedding
Abstract: 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 dissertation 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. Mapping of the communication graph for an application on to the interconnect topology of a machine while trying to localize communication is the research problem under consideration. The farther different messages travel on the network, greater is the chance of resource sharing between messages. This can create contention on the network for networks commonly used today. Evaluative studies in this dissertation show that on IBM Blue Gene and Cray XT machines, message latencies can be severely affected under contention. Realizing this fact, application developers have started paying attention to the mapping of tasks to physical processors to minimize contention. Placement of communicating tasks on nearby physical processors can minimize the distance traveled by messages and reduce the chances of contention. Performance improvements through topology aware placement for applications such as NAMD and OpenAtom are used to motivate this work. Building on these ideas, the dissertation proposes algorithms and techniques for automatic mapping of parallel applications to relieve the application developers of this burden. The effect of contention on message latencies is studied in depth to guide the design of mapping algorithms. The hop-bytes metric is proposed for the evaluation of mapping algorithms as a better metric than the previously used maximum dilation metric. The main focus of this dissertation 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. The dissertation also briefly discusses completely distributed mapping techniques which will be imperative for machines of the future.
Issue Date: 2010-08
Genre: Dissertation / Thesis
Type: Text
Language: English
URI: http://hdl.handle.net/2142/16578
Publication Status: published or submitted for publication
Peer Reviewed: not peer reviewed
Date Available in IDEALS: 2010-07-13
 

This item appears in the following Collection(s)

Show full item record

Item Statistics

  • Total Downloads: 242
  • Downloads this Month: 2
  • Downloads Today: 2

Browse

My Account

Information

Access Key