Vipin Kumar

Recently, a number of researchers have investigated a class of graph partitioning algorithms that reduce the size of the graph by collapsing vertices and edges, partition the smaller graph, and then uncoarsen it to construct a partition for the original graph [4, 26]. From the early work it was clear that multilevel techniques held great promise; however, it was not known if they can be made to consistently produce high quality partitions for graphs arising in a wide range of application domains. We investigate the effectiveness of many different choices for all three phases: coarsening, partition of the coarsest graph, and refinement. In particular, we present a new coarsening heuristic (called heavy-edge heuristic) for which the size of the partition of the coarse graph is within a small factor of the size of the final partition obtained after multilevel refinement. We also present a much faster variation of the Kernighan-Lin algorithm for refining during uncoarsening. We tes...

Introduction. What is Parallel Computing? The Scope of Parallel Computing. Issues in Parallel Computing. Organization and Contents of The Text. Bibliographic Remarks. Problems. References. Models of Parallel Computers. A Taxonomy of Parallel Architectures. An Idealized Parallel Computer. Dynamic Interconnection Networks. Static Interconnection Networks. Embedding Other Networks Into a Hypercube. Routing Mechanisms For Static Networks. Communication Costs in Static Interconnection Networks. Cost-Performance Tradeoffs. Architectural Models For Parallel Algorithm Design. Bibliographic Remarks. References. Basic Communication Operations. Simple Message Transfer Between Two Processors. One-To-All Broadcast. All-To-All Broadcast, Reduction, and Prefix Sums. One-To-All Personalized Communications. All-To-All Personalized Communications. Circular Shift. Faster Methods For Some Communication Operations. Summary. Bibliographic Remarks. Problems. References. Performance and Scalability of Parallel Systems. Performance Metrics For Parallel Systems. The Effect of Granularity and Data Mapping On Performance. The Scalability of Parallel Systems. The Isoefficiency Metric of Scalability. Sources of Parallel Overhead. Minimum Execution Time and Minimum Cost-Optimal Execution Time. Other Scalability Metrics and Bibliographic Remarks. Problems. References. Dense Matrix Algorithms. Mapping Matrices Onto Processors. Matrix Transpositon. Matrix-Vector Multiplication. Matrix Multiplication. Solving a System of Linear Equations. Bibliographic Remarks. Problems. References. Sorting. Issues in Sorting On Parallel Computers. Sorting Networks. Bubble Sort and Its Variants. Quicksort. Other Sorting Algorithms. Bibliographic Remarks. Problems. References. Graph Algorithms. Definitions and Representation. Minimum Spanning Tree: Prim's Algorithm. Single-Source Shortest Paths: Dijkstra's Algorithms. All-Pairs Shortest Paths. Transitive Closure. Connected Components. Algorithms For Sparse Graphs. Bibliographic Remarks. Problems. References. Search Algorithms For Discrete Optimization Problems. Definitions and Examples. Sequential Search Algorithms. Search Overhead Factor. Parallel Depth-First Search. Parallel Best-First Search. Speedup Anomalies in Parallel Search Algorithms. Bibliographic Remarks. Problems. References. Dynamic Programming. Serial Monadic Dp Formulations. Nonserial Monadic Dp Formulations. Serial Polyadic Dp Formulations. Nonserial Polyadic Dp Formulations. Summary and Discussion. Bibliographic Remarks. Problems. References. Fast Fourier Transform. The Serial Algorithm. The Binary-Exchange Algorithm. The Transpose Algorithm. Cost-Effectiveness of Meshes and Hypercubes For Fft. Bibliographic Remarks. Problems. References. Solving Sparse Systems of Linear Equations. Basic Operations. Iterative Methods. Finite Element Method. Direct Methods For Sparse Linear Systems. Multigrid Methods. Bibliographic Remarks. Problems. References. Systolic Algorithms and Their Mapping Onto Parallel Computers. Examples of Systolic Systems. General Issues in Mapping Systolic Systems Onto Parallel Computers. Mapping One-Dimensional Systolic Arrays. Bibliographic Remarks. Problems. References. Parallel Programming. Parallel Programming Paradigms. Primitive For The Message-Passing Programming Paradigm. Data-Parallel Languages. Primitives For The Shared-Address-Space Programming Paradigm. Fortran D. Bibliographic Remarks. References. Appendix A. Complexity of Functions and Order Analysis. Author Index. Subject Index. 0805331700T04062001

Metis is copyrighted by the regents of the University of Minnesota. This work was supponed by IST/BMDO through Army Research Office\ncontract DA/DAAH04-93-G-0080. and by Army High Performance Computing Research Center under the auspices of the Department of the Army.\nAnny Research Laboratory cooperative agreement number DAAH04-95-2-0003/contract number DAAH04-95-C-0008, the content of which does\nnot necessarily reflect the position or the policy of lhe government, and no official endorsement should be inferred. Access to computing facilities\nwere provided by Minnesota Supercomputer Institute, Cray Research Inc, and by the Pittsburgh Supercomputing Center.

In this paper, we present a new hypergraph-partitioning algorithm that is based on the multilevel paradigm. In the multilevel paradigm, a sequence of successively coarser hypergraphs is constructed. A bisection of the smallest hypergraph is computed and it is used to obtain a bisection of the original hypergraph by successively projecting and refining the bisection to the next level finer hypergraph. We have developed new hypergraph coarsening strategies within the multilevel framework. We evaluate their performance both in terms of the size of the hyperedge cut on the bisection, as well as on the run time for a number of very large scale integration circuits. Our experiments show that our multilevel hypergraph-partitioning algorithm produces high-quality partitioning in a relatively small amount of time. The quality of the partitionings produced by our scheme are on the average 6%-23% better than those produced by other state-of-the-art schemes. Furthermore, our partitioning algorithm is significantly faster, often requiring 4-10 times less time than that required by the other schemes. Our multilevel hypergraph-partitioning algorithm scales very well for large hypergraphs. Hypergraphs with over 100 000 vertices can be bisected in a few minutes on today's workstations. Also, on the large hypergraphs, our scheme outperforms other schemes (in hyperedge cut) quite consistently with larger margins (9%-30%).