AN IMPROVED SPECTRAL GRAPH PARTITIONING ALGORITHM FOR MAPPING PARALLEL COMPUTATIONS
AN IMPROVED SPECTRAL GRAPH PARTITIONING ALGORITHM FOR MAPPING PARALLEL COMPUTATIONS
复制标题
DOI：
10.1137/0916028
复制
发表时间：
1995-03-01
影响因子：
3.1
通讯作者：
LELAND, R
中科院分区：
文献类型：
--
作者：
HENDRICKSON, B;LELAND, R
分布式存储器并行计算机的有效使用要求以最小化处理器间通信的方式在处理器之间平衡计算负载。提出了一种新的域映射算法，扩展了最近的工作中，从谱图理论的思想已被应用到这个问题。谱图二分法的推广涉及到多个特征向量的新颖使用，以允许在递归分解的每个阶段将计算划分为四个或八个部分。由此产生的方法是适合于科学计算，如不规则的有限元或差异上执行超立方体或网格架构的机器。实验结果证实，新方法提供了更好的分解达到更经济和鲁棒性比以前的光谱方法。该算法允许在顶点和边上使用任意非负权重来模拟非均匀计算和通信。给出了一个新的图二分的谱下界。
Efficient use of a distributed memory parallel computer requires that the computational load be balanced across processors in a way that minimizes interprocessor communication. A new domain mapping algorithm is presented that extends recent work in which ideas from spectral graph theory have been applied to this problem. The generalization of spectral graph bisection involves a novel use of multiple eigenvectors to allow for division of a computation into four or eight parts at each stage of a recursive decomposition. The resulting method is suitable for scientific computations like irregular finite elements or differences performed on hypercube or mesh architecture machines. Experimental results confirm that the new method provides better decompositions arrived at more economically and robustly than with previous spectral methods. This algorithm allows for arbitrary nonnegative weights on both vertices and edges to model inhomogeneous computation and communication. A new spectral lower bound for graph bisection is also presented.