Graph Partitioning And Its Applications To Scientific Computing

Author : Shad Kirmani
Publisher :
ISBN 13 :
Total Pages : pages
Book Rating : 4.:/5 (943 download)

DOWNLOAD NOW!

Download or read book Exploiting Graph Embedding for Parallelism and Performance written by Shad Kirmani and published by . This book was released on 2015 with total page pages. Available in PDF, EPUB and Kindle. Book excerpt: Problems in very large data scientific computing simulations and big data analytics employ large clusters to scale up the performance. Without a good partitioner and with naive mapping of the partitioned processes to the processors in the network, speedups are difficult to achieve on large HPC systems. The data in such simulations is usually in the form of matrices, which can be abstracted as graphs. We propose that considering the geometry of the application graphs as well as the underlying processor network is of vital importance when scaling up.As a first step, the data associated with the problem, abstracted as a graph, needs to be distributed on to the processors in the network. Parallel multilevel partitioners, such as Pt-Scotch and ParMetis, produce good quality partitions but their performance scales poorly. Coordinate bisection schemes such as those in Zoltan, which can be applied only to graphs with coordinates, scale well but partition quality is often compromised. We seek to address this gap by developing a scalable parallel scheme which imparts coordinates to a graph through a lattice-based multilevel embedding. Partitions are computed with a parallel formulation of a geometric scheme that has been shown to provide provably good cuts on certain classes of graphs. We analyze the parallel complexity of our scheme and we observe speed-ups and cut-sizes on large graphs. Our results indicate that our method is substantially faster than ParMetis and Pt-Scotch for hundreds to thousands of processors, while producing high quality cuts.We then consider the problem of mapping irregular applications to multiprocessor architectures whose interconnect topologies affect the latencies of data movement across processor nodes. The starting point for solutions to this problem concern suitable weighted graph representations of an irregular application and a processor topology. Prior works for this problem have demonstrated that graph partitioning approaches can provide high quality solutions. Additionally, when coordinate information is available for the weighted graph of the application, geometric mapping schemes can also provide high quality solutions. We develop and present a scheme that we call "embedded sectioning" that directly computes a locality enhancing embedding of the weighted graph representation which is then mapped to the processor topology using recursive coordinate bisection. Our scheme is specifically directed at gaining high quality mappings for highly irregular applications where the amount of communication can vary greatly. We evaluate the quality of mappings produced by embedded sectioning for mesh-based processor topologies using well accepted measures including congestion, dilation and their product, referred to as communication volume. For a test suite of unit-weight graphs mapped to 32 x 32 mesh of processors, our method improves congestion by 26%, dilation by 52% and communication volume by 64% relative to the best values of these measures from 9 other schemes. Additionally, we observe that these improvements increase with the increase in the skewness of communication in applications. For a test suite with skewness of 2, corresponding improvements for congestion, dilation and communication volume are 72%, 52% and 87% respectively.We also study the sensitivity of the geometric partitioning schemes for partitioning a graph whose vertices are embedded in 2D/3D space. These parallel schemes typically show high performance on larger number of processors, than other types of parallel partitioning schemes. We specifically consider Recursive Coordinate Bisection and its implementation in Zoltan and ScalaPart implementation of Geometric Mesh Partitioning. The problem of parallel geometric graph partitioning arises in many iterative schemes for finite element methods. The quality of partitions is measured in terms of edges crossing the partitions. Moreover, the partitions should be robust to perturbation of coordinates, bad mesh quality meshes and approximate embedding. Understanding the tradeoffs will help in better usage of the existing parallel geometric partitioning algorithms and also in the development of better parallel geometric partitioning algorithms. In this paper we study a very popular geometric partitioning scheme, Recursive Coordinate Bisection, from the Zoltan package and the recently developed parallel geometric scheme, ScalaPart, based on multiple 'sphere' cuts. We find that both ScalaPart and RCB are affected by the number of tries and refinement respectively. We also find that ScalaPart is more robust in terms of partition quality to perturbation of coordinates, mesh quality and approximate graph embedding. ScalaPart is slower than RCB but shows better speedup unto 32 cores.We conclude with a discussion on how the discovery of geometry for sparse application graphs can lead to the discovery of locality. When the application graph is laid out in a few dimensions, the structure is leveraged to speed and scale up algorithms on HPC systems.