Multi-Constraint, Multi-Objective Graph Partitioning

多约束、多目标图划分

• 批准号: 9972519
• 负责人: George Karypis
• 金额: $ 28.65万
• 依托单位: University of Minnesota-Twin Cities
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1999
• 资助国家: 美国
• 起止时间: 1999-09-01 至 2003-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9972519&HistoricalAwards=false
• 关键词: Multi; Constraint; Objective; Graph; Partitioning

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.

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