异构计算中一种图的非均衡划分算法

• 作者: 曾国荪 沈轶炜
• 来源期刊: 计算机科学
• 学科: 工学
• 关键词: 异构计算 非均衡的图划分 任务图 分布向量
• 年，卷（期）: 2006,（6）
• 所属期刊栏目: 软件工程
• 页码范围: 260-263
• 页数: 4页
• 分类号: TP3
• 字数: 5356字
• 语种: 中文
• DOI: 10.3969/j.issn.1002-137X.2006.06.070

摘要

现有的图的划分算法大多是均衡划分,要求划分块的权值相等,划分块之间的连接代价尽量最小.但是在异构计算环境中,不同的处理机的计算能力不尽相同,从而在并行任务调度时所分配的计算任务量也应随之不同.所以为了适应更广泛意义上的异构负载均衡,本文提出了异构计算中的一种任务图的非均衡划分算法.该算法根据任意给定的需求,使得划分好的各个子集权值不均等.其中划分子集的个数等于异构环境中处理机的个数,各子集的大小比例于不同处理机的计算能力.算法包括3步:粗化阶段、非均衡划分阶段以及精化还原阶段.本文通过用格林威治大学提供的系列开放图来测试该算法,实验结果表明算法是准确有效的.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	曾国荪	国家高性能计算机工程技术中心同济分中心	65	677	15.0	23.0
2	沈轶炜	同济大学计算机科学技术系	1	10	1.0	1.0