ITR/NGS: Graph Partitioning Algorithms for Complex Problems & Architectures

ITR/NGS：复杂问题的图划分算法

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

Algorithms that find good partitionings of highly unstructured and irregular graphs are critical for developing efficient solutions of a wide range of problems including parallel execution of mesh-based scientific simulations. This research focuses on developing new serial and parallel graph-partitioning algorithms that can address the partitioning requirements of a number of key high-performance scientific computations and can correctly model the architectural characteristics of various emerging heterogeneous parallel computing platforms. The specific research tasks for the project are: (i) Development of partitioning algorithms for problem instances that lead to dynamic constraints and objectives; (ii) development of partitioning algorithms for contact/impact computations; and (iii) Development of architecture aware graph partitioning algorithms. These algorithms will be tested and validated on a wide range of problems obtained from academic, government, and industrial sources and on a variety of parallel computing platforms.

找到高度非结构化和不规则图形的良好划分的算法对于开发各种问题的有效解决方案至关重要，包括基于网格的科学模拟的并行执行。本研究的重点是开发新的串行和并行图划分算法，这些算法可以解决一些关键的高性能科学计算的划分需求，并可以正确地建模各种新兴异构并行计算平台的体系结构特征。该项目的具体研究任务是：(i)为导致动态约束和目标的问题实例开发划分算法；（ii）开发用于接触/冲击计算的划分算法；（iii）架构感知图划分算法的开发。这些算法将在学术、政府和工业来源以及各种并行计算平台上获得的广泛问题上进行测试和验证。