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

计算机科学 ›› 2006, Vol. 33 ›› Issue (6): 260-263.

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

出版日期:2018-11-17 发布日期:2018-11-17
基金资助:
国家自然科学基金资助项目（60173026）、上海科委重大项目（03DZ15029）.上海高校网络技术E-研究院资助（200301-1）.

Online:2018-11-17 Published:2018-11-17

摘要/Abstract

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

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

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 computi

Key words: Heterogeneous computing, Unbalanced partitioning, Task graph, Distribution vector

. 异构计算中一种图的非均衡划分算法[J]. 计算机科学, 2006, 33(6): 260-263. https://doi.org/

参考文献

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed