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.