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.