Multi-Constraint, Multi-Objective Graph Partitioning

找到高度非结构化和不规则图的良好划分的算法对于开发包括并行执行科学模拟在内的各种问题的有效解决方案至关重要。传统的图分区问题侧重于计算图的k-way分区，使边切最小化，每个分区具有相同数量的顶点（或者在加权图的情况下，每个分区中的顶点权重之和相同）。最小化边缘切割的任务可以被认为是目标，分区大小相同的要求可以被认为是约束。不幸的是，这种单约束单目标图划分问题不足以对许多当前和新兴应用程序的潜在需求进行建模，特别是在高性能科学模拟领域。特别是，在汽车发动机设计、耐撞性测试、流体力学、结构力学等领域中，多物理场、多阶段计算的有效并行解决，要求分区算法同时平衡每个阶段的计算，并使各种通信开销最小化，而这些都是目前的图模型和分区算法无法实现的。这些应用程序的关键特征是，它们需要分区算法来处理任意数量的平衡约束以及任意数量的优化（最小化或最大化）目标。该项目将为图划分开发新的通用模型，能够对当前框架内无法建模的高性能科学模拟中许多现有和新出现的问题的需求进行建模，以及解决这些问题的算法。图模型和划分算法将在从工业和政府来源获得的广泛问题上进行测试和验证。

Algorithms that find a good partitioning of highly unstructured and irregular graphs are critical for developing efficient solutions of a wide range of problems including parallel execution of scientific simulations. The traditional graph partitioning problem focuses on computing a k-way partition of a graph such that the edge-cut is minimized and each partition has an equal number of vertices (or in the case of weighted graphs, the sum of the vertex-weights in each partition are the same). The task of minimizing the edge-cut can be considered as the objective and the requirement that the partitions will be of the same size can be considered as the constraint. Unfortunately, this single-constraint single-objective graph partitioning problem is not sufficient to model the underlying requirements of many current and emerging applications, especially in the area of high performance scientific simulations. In particular, the effective parallel solution of multi-physics and multi-phase computations in areas such as automobile engine design, crash-worthiness testing, fluid dynamics, structural mechanics, etc., requires that the partitioning algorithm simultaneously balances the computations performed during each one of the phases and minimizes the various communication overheads--none of which can be accomplished by the current graph models and partitioning algorithms. The key characteristic of these applications is that they require the partitioning algorithm to handle an arbitrary number of balancing constraints as well as an arbitrary number of optimization (either minimization or maximization) objectives. This project will develop new generalized models for graph partitioning that are able to model the requirements of many existing and emerging problems in high-performance scientific simulations that cannot be modeled within the current framework, as well as algorithms for solving these problems. The graph models and partitioning algorithms will be tested and validated on a wide range of problems obtained from industrial and government sources.