Graph partitionong for high performance computing

计算密集型计算机程序通常将其数据分解成多个部分，以便在多台计算机上并发执行。这些程序中的许多都采用图形数据结构来描述底层网格的计算和通信需求，例如偏微分方程（PDE）的有限元求解器。当程序在并行计算机上执行时，图划分是用于产生这些图的平衡分解并实现通信需求最小化的技术。已经开发了许多图分区技术，包括我的研究小组创建的PaGrid分区器。该项目将为传统的同构并行计算机和异构计算机集群和计算网格提供图形划分的新方法。它还将提供工具来实现图分区的比较分析。基于网格的并行程序在科学和工程仿真中扮演着越来越重要的角色。随着计算资源层次的不断提高，从多核处理器到多处理器集群和微网格（集群的集群），异构计算平台越来越不可避免。异构图分区器（如PaGrid）对于确保基于网格的程序在这些平台上的有效执行至关重要。这项工作将加强已经在PaGrid上完成的工作，并将使用基准程序展示其质量。

Computationally intensive computer programs often decompose their data into parts to enable concurrent execution on multiple computers. Many of these programs employ a graph data structure to describe the computation and communication requirements of an underlying mesh, such as for finite element solvers for partial differential equations (PDE). Graph partitioning is the technique used to produce a balanced decomposition of these graphs and achieve a minimization of the communication requirement when theprogram is executed on a parallel computer. A number of graph partitioning techniques have been developed, including work by my research group which has created the PaGrid partitioner. This project will contribute new approaches to graph partitioning, both for traditional homogeneous parallel computers and for heterogeneous computer clusters and computational grids. It will also contribute tools to enable the comparative analysis of graph partitioners.Mesh-based parallel programs form a large part of the increasing role of simulation in science and engineering. Heterogeneous computational platforms are increasingly unavoidable, with the increasing hierarchical levels of computational resources, from multicore processors to clusters of multiprocessors and mini-grids (clusters of clusters). Heterogeneous graph partitioners such as PaGrid are vital in order to ensure the efficient execution of mesh-based programs on these platforms. This work will strengthen the work already accomplished on PaGrid, and will demonstrate its qualities using benchmark programs.