Graph Partitioning for High Performance Scienti c Simulations
Graph Partitioning for High Performance Scienti c Simulations
复制标题
用于高性能科学模拟的图形分区
DOI：
--
复制
发表时间：
2000
期刊：
影响因子：
--
通讯作者：
R. Engelen
中科院分区：
文献类型：
--
作者：
R. Engelen
1目录2图1：一个隔板的2D不规则网格，网格元素的阴影指示映射的处理器。在这些模拟中，高性能并行计算网格和信息在相邻的网格元素之间交换。在并行机器上需要将计算网格映射到处理器上通过求解图表分配算法，可以找到相邻元素之间的信息交换。已经对元素进行了阴影，以指示它们已在许多s c e n tiic模拟中映射到的处理器在模拟开始之前的网格的初始分解（如上所述），以及在模拟过程中要执行的定期载荷平衡（即，多相模拟）。通过同步步骤分开的计算阶段，每个阶段都可以单独负载平衡。简单的网格（即多网仿真），这些算法必须考虑到传统的图形分区算法，以确保这些类别的模拟对高性能平行计算机的执行不足。 。用于高性能平行计算机的科学模拟。
1 CONTENTS 2 Figure 1: A partitioned 2D irregular mesh of an airfoil. The shading of a mesh element indicates the processor to which i t is mapped. 0.1 Introduction Algorithms that nd good partitionings of unstructured and irregular graphs are critical for the eecient execution of scientiic simulations on high performance parallel computers. In these simulations, computation is performed iteratively on each element (and/or node) of a physical two-or three-dimensional mesh and then information is exchanged between adjacent mesh elements. For example, computation is performed on each triangle of the two-dimensional irregular mesh shown in Figure 1. Then information is exchanged for every face between adjacent triangles. The eecient execution of such s i m ulations on parallel machines requires a mapping of the computational mesh onto the processors such t h a t e a c h processor gets roughly an equal number of mesh elements and that the amount o f i n ter-processor communication required to perform the information exchange between adjacent elements is minimized. Such a mapping is commonly found by solving a graph partitioning problem. For example, a graph partitioning algorithm was used to decompose the mesh in Figure 1. Here, the mesh elements have been shaded to indicate the processor to which they have been mapped. In many s c i e n tiic simulations, the structure of the computation evolves from time-step to time-step. These require an initial decomposition of the mesh prior to the start of the simulation (as described above), and also periodic load balancing to be performed during the course of the simulation. Other classes of simulations (i. e., multi-phase simulations) consist of a number of computational phases separated by synchronization steps. These require that each of the phases be individually load balanced. Still other scientiic simulations model multiple physical phenomenon (i. e., multi-physics simulations) or employ m ultiple meshes simultaneously (i. e., multi-mesh simulations). These impose additional requirements that the partitioning algorithm must take i n to account. Traditional graph partitioning algorithms are not adequate to ensure the eecient execution of these classes of simulations on high performance parallel computers. Instead, generalized graph partitioning algorithms have been developed for such simulations. This chapter presents an overview of graph partitioning algorithms used for scientiic simulations on high performance parallel computers. Recent d e v elopments in graph partitioning for adaptive and dynamic simulations , as well as partitioning algorithms …