异构计算中一种图的非均衡划分算法.pdf
版权申诉
30 浏览量
2022-07-11
17:05:28
上传
评论
收藏 318KB PDF 举报
定义 2（分布向量）! 非均衡的分布向量定义为 ! "（
!
#
，
!
$
，…，
!
"
），其中 " 为对象的个数，且
’
"
# " #
!
#
" #。特别当 % 为异
构任务分布向量时，
!
#
"
&’
#
’
"
$ " #
&’
$
，&’
#
为第 # 台处理机的计算能
力。而当
% 为图的划分分布向量时，
!
#
为划分子集大小的比
例。
定义
3（并行任务图）! 并行任务图可定义为 (%) "（%，
&），其中 % 为任务节点，& 为连接任务节点的通路。任务节
点的权值可视为计算量，通路的权值可视为通信代价。一般来
说，控制流图
&*) 结合数据流图 (*)，可以构造并行任务
图
［$］
。
定义
4（图的均衡划分的定义）! 给定一个 ’ "（%，&），%
为节点集合，& 为边集合，+ % + " (。把 % 划分成 " 个子集 %
#
，
%
$
，…，%
"
，%
#
/
%
$
"
"
，#
(
$，+ %
#
+ " ( ) "，
.
#
%
#
" %，并且把连接
不同子集的边的数量减至最小。
定义
5（图的非均衡划分的定义）! 给定一个 ’ "（%，&），
分布向量 ! "（
!
#
，
!
$
，… ，
!
"
），+ % + " (，把 % 划分成 " 个子集
%
#
，%
$
，…，%
"
，%
#
/
%
$
"
"
，#
(
$，+ %
#
+ , + %
$
+ , …, + %
"
+ "
!
#
,
!
$
, …,
!
"
，
.
#
%
#
" %，并且把连接不同子集的边的数量减至最
小。
比较二者的定义，其中最大区别在于：均衡划分中，
+ %
#
+ "
( ) "，即+ %
#
+ , + %
$
+ " #, #；而非均衡划分中，+ %
#
+ , + %
$
+ "
!
#
,
!
$
。
本文用大小为 ( 的一维数组 * 来表示节点的划分。* 实
际上是一个节点到划分块的映射函数。
-
+
$
%，*［+］" ,，,
$
｛-，…，" . #｝。
定义 6（连 接 代价）! 给定 一个 *，* 的 连 接代价 /&
,
（01203456）"
’
*［+］
(
*［-］
.（+，-），其中 +，-
$
%，（+，- ）
$
&，.（+，-
）为边（+，- ）的权值。
至此，本文给出了与所有非均衡划分有关的定义。给定一
个并行任务图，需要在异构环境下进行调度运行。通过计算参
与调度的处理机的计算能力，可以得到一个分布向量，也就是
划分的分布向量。从而按照这个划分分布向量对并行任务图
进行非均衡划分。下面具体介绍图的非均衡划分算法。
3 图的非均衡划分算法
图的非均衡算法的基本思想主要包括以下 7 步：粗化阶
段，图 ’
-
首先通过合并节点粗化为节点数较少的图 ’
#
，’
$
，
…，
’
/
；非均衡划分阶段，在粗化好的图 ’
/
上进行划分；精华
还原阶段，进一步调整各节点子集大小，同时尽可能减小连接
代价，然后借助 ’
/
，’
/ . #
，…，’
#
把划分映射回最初的图 ’
-
。
下面详细介绍每个阶段。
3! 1 粗化阶段
在粗化阶段，主要是基于原图 ’
-
构造一系列点集与边集
的大小逐渐减小的图
’
#
"（ %
#
，&
#
），其中 + %
#
+ 8 + %
# . #
+ ，通常一
部分 ’
#
的点结合成为 ’
# 9 #
的一个点。令 %
+
#
为 ’
#
中组成节点
+ 的节点的集合，+
$
’
# 9 #
。为保持原图的权值信息，节点 + 的
权值等于
%
+
#
中节点的权值的总和。同样，与 + 相连的边是与
%
+
#
中节点相连的所有的边的并集。如果在 %
+
#
中有多条边连接
同一个
’
# 9 #
中另一个点 -，边（+，-）的权值为这些边的权值的
总和。这样就保证了粗化的图与原图的连接代价相同。
算法中实现这种粗化的方法是秉承于“匹配”的思想
［:］
。
图 ’
#
的一个匹配 0
#
（;<64=>?2）为一个边的集合，
-
1
#
"（+
#
，
-
#
），1
$
"（+
$
，-
$
）
$
0
#
，满足 +
#
(
+
$
，+
#
(
-
$
，-
#
(
+
$
，-
#
(
-
$
。算
法构造图 ’
#
的一个匹配，把已匹配的两个节点合并成 ’
# 9 #
一
个节点，未匹配的点就直接复制到
’
# 9 #
，从而减小 ’
#
的大小。
72 #2 #! 最大权值边匹配算法
令
3（&）为 & 中所有的边的权值总和，显然 3（&
# 9 #
）" 3
（&
#
）. 3（0
#
）。为了最小化图的连接代价，要找一个 0
#
，使 3
（0
#
）尽量大。算法描述如下：
输入：图
’
#
"（%
#
，&
#
）
输出：图 ’
# 9 #
"（%
# 9 #
，&
# 9 #
）
;<@?5;
V
-；
A=>B0 ?C6
-
D
$
%
#
，D >E ;<64=01
D
V
)06F?;<64=01G0H60I（ ）；J
!
随机得到未匹配的节点 D
!
J
>K
-
-
$
%1L（D）>E ;<64=01 J
!
%1L（D）为 D 的邻接点
!
J
! ;<64=［D］
V
D；
0BE0
! *>?1 <? 5?;<64=01 5
$
%1L（D）<?1 A（D，5）>E 6=0 B<H20E6；
J
!
在 D 的未匹配的邻接点中找 A（D，5）最
大的点 5
!
J
;<64=［D］
V
5；;<64=［5］
V
D；
;<@［5］
V
;<@?5;；
M06 5 6C N0 ;<64=01；J
!
把 5 标记为已匹配
!
J
0?10BE0
! ;<@［D］
V
;<@?5;；
M06 D 6C N0 ;<64=01；
;<@?5;
V
;<@?5; 9#；
0?1A=>B0
不过对于那种所有的边的权值相同的图来说，没有所谓的
最大权值的边。把算法改进一下，可以得到更好的匹配结果：
从
+ 的所有尚未匹配的邻接点中找到一个节点 -，令 3
+ . -
为 -
连接 到 + 的 邻 接 点 的 边 的 权 值 的 总 和，即 3
+ . -
"
’
（-，4），（+，4），（+，-）
$
&
.（-，4），- 满足 3
+ . -
是所有未匹配中最大的。
算法在粗化阶段重复权重边匹配算法，直到粗化后图 ’
#
中的节点数小于 5"，" 为需要划分的子集数，5 为一个常数。根
据实验经验
［O］
，取 5 " #P 到 $-。若相继两个图 ’
#
和 ’
# 9 #
的节
点数相比，即+ %
# 9 #
+ ) + %
#
+ Q-2 R，也结束粗化阶段。至此，原图
被粗化为节点数和边数均大幅减小的图，在此基础上进行划
分，将大大减少划分所用时间。
3! 2 非均衡划分阶段
非均衡划分算法是个 " 步循环过程。在粗化阶段得到的
’
#
上划分 " 个指定大小的划分块 ，随后对划分产生的零碎块
进行处理，得到一个初步划分 *
#
。
72 $2 #! 非均衡划分增长算法
给定划分的分布向量 ! "（
!
#
，
!
$
，…，
!
"
），令 .67 为 ’
#
的
节点的权值总和，算法从一点开始，按广度优先次序逐一将邻
接点加入该划分，直到权值等于
!
#
!
.67，然后在余下的节点
继续上述过程。由于同一划分中的节点应该是连通的，所以在
划分过程中，难免会遇到这种情况。进行广度优先搜索邻接点
时，队列中已无邻接的节点，但该划分的权值尚未达到所需大
小。这称为划分的碎片问题。为了尽量避免碎片问题，同时使
划分大小满足需求，本文给出如下算法描述：
输入：图
’
#
（%
#
，&
#
），分布向量 ! "（
!
#
，
!
$
，…，
!
"
），误差变量
#
输出：划分映射数组 *
@?5;
V
-；KH<2?5;
V
S；J
!
@?5; 为划分标识，KH<2?5; 为碎片标识
!
J
A=>B0 @?5; 8 S <?1 ?C6
-
D
$
G
>
，D >E @<H6>6>C?01
@A26
V
-；J
!
@A26 为当前划分块的大小
!
J
D
V
)06F?@<H6>6>C?01G0H60I（）；J
!
得到一个未划分的节点 D
!
J
%11TCT<>B（D，U5050）；J
!
将 D 加入队列尾
!
J
A=>B0 ?C6 0;@6V（U5050）
D
V
)06*HC;W0<1（U5050）；J
!
从队列首取一点，赋值给 D
!
J
@A26
V
@A26 9 A（D）；
’［D］
V
@?5;；
>K @A26 N06A00?
!
@?5;
!
A26
!
（# .
"
）<?1
!
@?5;
!
A26
!
（# 9
"
）
@?5;
V
@?5; 9 #；
M06/;@6V（U5050）；J
!
将队列清空
!
J
0BE0 >K @A26 8
!
@?5;
!
A26
!
（# .
"
）
%11 %1L（D）A=>4= >E ?C6 @<H6>6>C?01 >?6C U5050；
·#X$·
资源评论
老帽爬新坡
- 粉丝: 83
- 资源: 2万+
最新资源
- 数据库管理工具:dbeaver-ce-23.0.3-macos-aarch64.dmg
- Delphi 12 控件之DEV自动安装程序.exe
- 数据库管理工具:dbeaver-ce-23.0.2-x86-64-setup.exe
- Delphi 12 控件之AnySQL-0.0.9.rar
- 俄罗斯引擎Yandex的进入.pdf
- 数据库管理工具:dbeaver-ce-23.0.2-stable.x86-64.rpm
- Dephi 12 控件FFVCL – Delphi FFmpeg VCL Components v7.8 for D6-D11
- 基于opencv识别车牌
- PCB三角波与方波发生电路，AD参考
- 数据库管理工具:dbeaver-ce-23.0.2-macos-x86-64.dmg
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
