| 异构计算中一种图的非均衡划分算法 |
| |
| 引用本文： | 沈轶炜,曾国荪.异构计算中一种图的非均衡划分算法[J].计算机科学,2006,33(6):260-263. |
| |
| 作者姓名： | 沈轶炜 曾国荪 |
| |
| 作者单位： | 1. 同济大学计算机科学技术系,上海200092
2. 国家高性能计算机工程技术中心同济分中心,上海200092 |
| |
| 基金项目： | 国家自然科学基金;上海市科委资助项目;上海市高校网络技术E-研究院基金 |
| |
| 摘 要： | 现有的图的划分算法大多是均衡划分，要求划分块的权值相等，划分块之间的连接代价尽量最小。但是在异构计算环境中，不同的处理机的计算能力不尽相同，从而在并行任务调度时所分配的计算任务量也应随之不同。所以为了适应更广泛意义上的异构负栽均衡，本文提出了异构计算中的一种任务图的非均衡划分算法。该算法根据任意给定的需求，使得划分好的各个子集权值不均等。其中划分子集的个数等于异构环境中处理机的个数，各子集的大小比例于不同处理机的计算能力。算法包括3步：粗化阶段、非均衡划分阶段以及精化还原阶段。本文通过用格林威治大学提供的系列开放图来测试该算法，实验结果表明算法是准确有效的。
|
| 关 键 词： | 异构计算 非均衡的图划分 任务图 分布向量 |
An Unbalanced Partitioning Scheme for Graphs in Heterogeneous Computing |
| |
| SHEN Yi-Wei,ZENG Guo-Sun.An Unbalanced Partitioning Scheme for Graphs in Heterogeneous Computing[J].Computer Science,2006,33(6):260-263. |
| |
| Authors: | SHEN Yi-Wei ZENG Guo-Sun |
| |
| Abstract: | Most existing graph partitioning algorithms produce good equivalent partitions. It means that the partitioned subsets have equal number of vertexes, and meanwhile, the edge-cuts are minimal. However, in the heterogeneous computing environment, the computing power of different proeessors or workstations is variant, so that the size of the tasks scheduled on them should not be the same as well. In order to meet the need of the load balance for heterogeneous computing, this paper presents a novel algorithm that partitions the original task graph into unbalanced subsets according to the arbitrarily given conditions. In usual case, the number of the partitions is equal to that of the proeessors and the size of each partition is set according to the computing power. The algorithm is consisted of three phases. Coarsen the original graph, then partition the coarsest graph and last project it hack to the original graph and conduct refinement. We test the algorithm using Greenwich Graph Partitioning Archive and get good experiment results. |
| |
| Keywords: | Heterogeneous computing Unbalanced partitioning Task graph Distribution vector |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
点击此处可从《计算机科学》下载全文 |
