一种应用驱动的图划分调整方法和系统_樊文飞 靳若春 刘沐阳 陆平 罗小简 许瑞琦 尹强 于文渊_CN 111737531 B_崖山数据库
免费下载
(19)中华人民共和国国家知识产权局
(12)发明专利
(10)授权公告号
(45)授权公告日
(21)申请号 202010536216.5
(22)申请日 2020.06.12
(65)同一申请的已公布的文献号
申请公布号 CN 111737531 A
(43)申请公布日 2020.10.02
(73)专利权人 深圳计算科学研究院
地址 518000 广东省深圳市龙华区龙华街
道清泉路锦华发工业区硅谷大院T1栋
2楼D225室
(72)发明人 樊文飞 靳若春 刘沐阳 陆平
罗小简 许瑞琦 尹强 于文渊
(74)专利代理机构 深圳市精英专利事务所
44242
代理人 武志峰
(51)Int.Cl.
G06F
16/901
(2019.01)
G06F
16/906
(2019.01)
G06F
9/50
(2006.01)
(56)对比文件
CN 111198977 A,2020.05 .26
CN 106970779 A,2017.07 .21
CN 107122248 A,2017.09 .01
CN 108319698 A,2018.07.24
CN 111158918 A,2020.05 .15
CN 106250563 A,2016.12 .21
CN 105610992 A,2016.05 .25
US 2015169304 A1,2015.06.18
US 2015293751 A1,2015.10.15
Zainab Abbas等.Streaming graph
partitioning: an experimental study .
《Proceedings of the VLDB Endowment》.2018,
第1590-1603页.
审查员 夏雪
(54)发明名称
一种应用驱动的图划分调整方法和系统
(57)摘要
本发明公开了一种应用驱动的图划分调整
方法和系统，该方法会判断已有的图划分类型，
若为点划分，则对应工作机使用并行E2H算法进
行调整；若为边划分，则对应工作机使用并行V2H
算法进行调整根据用户的应用进行图划分调整，
该方法通过均衡应用的计算代价和通信代价，更
好的对于图划分进行负载均衡，图划分效率也更
高。同时，由于采用了并行化技术，图调整的速度
较快，平均时间为传统图划分算法的11％左右。
本发明可以快速调整现有的图划分，并进行较大
的加速。
权利要求书3页 说明书10页 附图2页
CN 111737531 B
2021.05.28
CN 111737531 B
1 .一种应用驱动的图划分调整方法，其特征在于，包括：
对于应用A和图G＝(V ,E)中的点v，将代价函数分为计算代价函数hA(X(v))和通信代价
函数gA(X(v))，其中，X(v)为点v的测量变量；
在预定数据集上运行用户给定的图算法，获得该图算法的训练样本，所述训练样本包
括各个点的计算时间和通信时间；
在训练样本上，使用多项式回归拟合该图算法的代价函数，并将代价函数发送到各个
工作机；
各个工作机加载已有的图划分，若已有的图划分为点划分，则对应工作机使用并行E2H
算法进行调整；若已有的图划分为边划分，则对应工作机使用并行V2H算法进行调整；
其中，所述并行E2H算法包括：
EMigrate的并行化：首先计算各图片段的计算代价预算；基于计算代价预算，将图片段
分为两类：载荷高的图片段和载荷低的图片段；对于每个载荷高的图片段，选择一系列点作
为候选点；不断从候选点中选择一个点及其全部临边，移动至载荷低的图片段中；
ESplit的并行化：当没有点及其临边可以被移动时，不断从候选点中选择一个点及其
一条临边，将这条临边移动到载荷低的图片段中；
MAssign的并行化：重新分配各个点的主点，均衡通信负载；
所述并行V2H算法包括：
VMigrate的并行化：首先计算各图片段的计算代价预算；基于计算代价预算，将图片段
分为两类：载荷高的图片段与载荷低的图片段；对于每个载荷高的图片段，选择一系列点作
为候选点；不断从候选点中选择一个点及其全部临边，移动至载荷低的图片段中；
VMerge的并行化：不断选择载荷最小的图片段中的边切分的点转化为点切分的点；
MAssign的并行化：重新分配各个点的主点，均衡通信负载。
2.根据权利要求1所述的应用驱动的图划分调整方法 ，其特征在于，所述在训练样本
上，使用多项式回归拟合该图算法的代价函数，并将代价函数发送到各个工作机，包括：
将 计 算 代 价 函 数 建 模 为 多 项 式 函 数 其 中 Γ 是
的展开式中项的集合，ω
j
是γ
j
(v)的权重，自然数p是多项式的最高
阶；
将训练样本表示为[X(v
k
) ,t
k
]，其中t
k
为运行应用A时点v
k
的计算时间；
通过随机梯度下降算法不断调整权重ω
j
，使得X(v
k
)和t
k
尽量接近。
3.根据权利要求2所述的应用驱动的图划分调整方法，其特征在于，调整权重过程中，
使用相对均方误差作为损失函数：
其中， 为计算代价函数h
A
(X(v))的训练样本， 为训练样本数量，Ω＝{ω
1
,… ,
ω
n
}， 为惩罚函数，用于防止训练结果过拟合。
4 .根据权利要求1所述的应用驱动的图划分调整方法，其特征在于，所述对于每个载荷
权 利 要 求 书
1/3 页
2
CN 111737531 B
2
of 16
免费下载
【版权声明】本文为墨天轮用户原创内容，转载时必须标注文档的来源（墨天轮），文档链接，文档作者等基本信息，否则作者和墨天轮有权追究责任。如果您发现墨天轮中有涉嫌抄袭或者侵权的内容，欢迎发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。
下载排行榜
评论