Browsing by Author "Schloegel, Kirk"

Now showing 1 - 6 of 6
  • Thumbnail Image
    Item
    A New Algorithm for Multi-objective Graph Partitioning
    (1999-02-15) Kumar, Vipin; Karypis, George; Schloegel, Kirk
    Recently, a number of graph partitioning applications have emerged with addtional requirements that the traditional graph partitioning model alone cannot effectively handle. One such class of problems is those in which multiple objectves, each of which can be modeled as a sum of weights of the edges of a graph, must be simultaneously optimized. This class of problems must be solved utilizing a multi-objective graph partitioning algorithm. In this paper, we describe a new algorithm for computing partitionings for multi-objective graphs. We explain how this scheme is able to handle the class of problems in which the objectives represent similar quantities, as well as, the class of problems in which the objectives represent dissimilar quantitites. We show that our multi-objective graph partitioning algorithm is better able to compute partitionings based on a user-supplied preference vector than partitioning with respect to a single objective only. We also show that by modifyig the input preference vector, the multi-objective graph partitioning algorithm is able to gracefully tradeoff increases in one or more objectives for decreases in ther objectives. This gives the user a fine-tuned control of the tradeoffs among the objectives.
  • Thumbnail Image
    Item
    A Unified Algorithm for Load-Balancing Adaptive Scientific Simulations
    (2000-05-22) Schloegel, Kirk; Karypis, George; Kumar, Vipin
    Adaptive scientific simulations require that periodic repartitioning occur dynamically throughout the course of the simulation. The computed repartitionings should minimize both the inter-processor communications incurred during the iterative mesh-based computation and the data redistribution costs required to balance the load. Recently developed schemes for computing repartitionings provide the user with only a limited control of the tradeoffs among these objectives. This paper describes a new Unified Repartitioning Algorithm that can gracefully tradeoff one objective for the other dependent upon a user-defined parameter describing the relative costs of these objectives. We show that the Unified Repartitioning Algorithm is able to minimize the precise overheads associated with repartitioning as well as or better than other repartitioning schemes for a variety of problems, regardless of the relative costs of performing inter-processor communication and data redistribution. Our experiments show that the Unified Repartitioning Algorithm is extremely fast and scalable to very large problems.
  • Thumbnail Image
    Item
    Graph Partitioning for High Performance Scientific Simulations
    (2000-03-14) Schloegel, Kirk; Karypis, George; Kumar, Vipin
    Algorithms that find good partitionings of unstructured and irregular graphs are critical for the efficient execution of scientific simulations on high performance parallel computers. This paper presents an overview of graph partitioning algorithms. Recent developments in graph partitioning for adaptive and dynamic simulations, as well as partitioning algorithms for sophisticated simulations such as multi-phase, multi-physics, and multi-mesh computations are also discussed.
  • Thumbnail Image
    Item
    Parallel Multilevel Algorithms for Multi-Constraint Graph Partitioning
    (1999-09-15) Kumar, Vipin; Karypis, George; Schloegel, Kirk
    Recently, serial multi-constraint graph partitioning algorithms have been developed that are able to compute high-quality partitionings for emerging multi-phase, multi-mesh, and multi-physics problems. While these results are promising, the fact that these algorithms are serial limits the problem size that can be solved due to both solution time and memory requirements. A parallel multi-constraint graph partitioner will allow the partitioning of larger multi-constraint graphs, and therefore, is key to the efficient execution of large multi-phase, multi-mesh, and multi-physics problems. In this paper, we present a parallel multi-constraint graph partitioning algorithm based on the multilevel graph partitioning paradigm. We describe this algorithm and give experimental results conducted on a 128-processor Cray T3E. We show that our parallel algorithm is able to robustly compute balanced partitionings of similar quality to serial multi-constraint algorithms, while being scalable to very large graphs. We show that the run time of our algorithm is very fast. Our parallel multi-constraint graph partitioner is able to compute a three-constraint 128-way partitioning of a 7.5 million node graph in about 7 seconds on 128 processors of a Cray T3E.
  • Thumbnail Image
    Item
    Parallel Multilevel Diffusion Algorithms for Repartitioning of Adaptive Meshes
    (1997) Schloegel, Kirk; Karypis, George; Kumar, Vipin
    Graph partitioning has been shown to be an effective way to divide a large computation over an arbitrary number of processors. A good partitioning can ensure load balance and minimize the communication overhead of the computation by partitioning an irregular mesh into p equal parts while minimizing the number of edges cut by the partition. For a large class of irregular mesh applications, the structure of the graph changes from one phase of the computation to the next. Eventually, as the graph evolves, the adapted mesh has to be repartitioned to ensure good load balance. Failure to do so will lead to higher parallel run time. This repartitioning needs to maintain a low edge-cut in order to minimize communication overhead in the follow-on computation. It also needs to minimize the time for physically migrating data from one processor to another since this time can dominate overall run time. Finally, it must be fast and scalable since it may be necessary to repartition frequently. Partitioning the adapted mesh again from scratch with an existing graph partitioner can be done quickly and will result in a low edge-cut. However, it will lead to an excessive migration of data among processors. In this paper, we present new parallel algorithms for robustly computing repartitionings of adaptively refined meshes. These algorithms perform diffusion of vertices in a multilevel framework and minimize data movement without compromising the edge-cut. Furthermore, our parallel repartitioners include parameterized heuristics to specifically optimize edge--cut, total data migration, or the maximum amount of data migrated into and out of any one processor. Our results on a variety of synthetic meshes show that our parallel multilevel diffusion algorithms are highly robust schemes for repartitioning adaptive meshes. The resulting edge-cuts are close to those resulting from partitioning from scratch with a state-of-the-art graph partitioner, while data migration is substantially reduced. Furthermore, repartitioning can be done very fast. Our experiments show that meshes with around eight million vertices can be repartitioned on a 256-processor Cray T3D in only a couple of seconds.
  • Thumbnail Image
    Item
    PARMETIS: Parallel Graph Partitioning and Sparse Matrix Ordering Library
    (1997) Karypis, George; Schloegel, Kirk; Kumar, Vipin