SI2-SSE: Software Infrastructure For Partitioning Sparse Graphs on Existing and Emerging Computer Architectures

University Of Minnesota-Twin Cities, Minneapolis MN

Investigators

Abstract

Algorithms that find good partitionings of large, sparse, and unstructured graphs represent an important technique for developing effective and computationally efficient approaches for problems that need to process and analyze such graphs. As a result, they have found extensive applications in many diverse areas such as high-performance computing, scientific computing, VLSI design, data mining, pattern recognition, computer graphics, network analysis, database and geographical information systems, operations research, optimization, and scheduling. This project will develop and make available a software infrastructure that provides a broad range of graph partitioning tools for large, sparse, and unstructured graphs. This infrastructure will be built using modern object-oriented software engineering principles that will facilitate their modularity, user-extensibility, maintainability, and community development; and incorporate novel graph partitioning algorithms that can scale to graphs containing billions of nodes and facilitate the partitioning of different types of graphs on different computing architectures. This software infrastructure will enable the efficient execution of scientific numerical simulations on parallel systems containing tens of thousands of processing nodes and billions of mesh elements, the development of divide-and-conquer approaches for synthesizing very large VLSI circuits on different chip architectures, the clustering and analysis of very large graphs and networks, and the solution of a wide-range of partitioning problem instances involving different objectives and constraints. This will positively impact numerous science & engineering disciplines, commercial companies, non-profit organizations, and individuals that benefit from the results of the computations that are enabled and facilitated by the various application domains that rely on graph partitioning. Finally, the project integrates the research with an educational plan focused on undergraduate and graduate education and mentoring through courses, software engineering projects, summer institutes, and research opportunities; and a community development and an outreach plan designed to promote broad adoption of the resulting software infrastructure by providing extensive documentation, online tutorials, and organizing meetings at relevant conferences and workshops.