Multi-Constraint, Multi-Objective Graph Partitioning

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

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.