ITR/NGS: Graph Partitioning Algorithms for Complex Problems & Architectures

University Of Minnesota-Twin Cities, Minneapolis MN

Investigators

Abstract

Algorithms that find good partitionings of highly unstructured and irregular graphs are critical for developing efficient solutions of a wide range of problems including parallel execution of mesh-based scientific simulations. This research focuses on developing new serial and parallel graph-partitioning algorithms that can address the partitioning requirements of a number of key high-performance scientific computations and can correctly model the architectural characteristics of various emerging heterogeneous parallel computing platforms. The specific research tasks for the project are: (i) Development of partitioning algorithms for problem instances that lead to dynamic constraints and objectives; (ii) development of partitioning algorithms for contact/impact computations; and (iii) Development of architecture aware graph partitioning algorithms. These algorithms will be tested and validated on a wide range of problems obtained from academic, government, and industrial sources and on a variety of parallel computing platforms.