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

摘要：

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

关键词：异构计算、非均衡的图划分、任务图、分布向量

所属期刊栏目：33

分类号：TP3(计算技术、计算机技术)

资助基金：国家自然科学基金60173026;上海市科委资助项目03DZ15029;上海市高校网络技术E-研究院基金200301-1

在线出版日期：2006-09-25（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：260-263