基于应用运行特征的图数据布局与访问优化研究

发布时间：2020-05-31 09:51

【摘要】：图是一种很重要的非结构化数据,可以用于建模现实世界中的各种问题,被广泛应用到交通运输、金融、社交网络等重要领域。但由于图计算过程中严重的结构依赖性,导致应用执行时内存随机访问严重,内存带宽成为限制图计算系统性能的重要因素。并且不同类型图算法的内存访问特征差异明显,单一的内存图数据组织不足以应对各种图算法多样化的内存访问需求。针对上述问题,分析了常见图算法的动态运行特征和内存数据访问特点,将图算法分为遍历式和迭代式两类,研究不同运行特征下的高效的图数据组织策略。对于遍历式图算法,通过分析其运行过程,发现同一个顶点和不同邻居节点之间存在关联度的大小差异,对邻居节点的访问顺序是影响算法运行过程中缓存命中率的重要因素。基于此提出了基于关联度的图顶点重映射算法GDL-VC,并采用滑动窗口模型SW实现了内存图数据的合理布局。该布局结果能够体现出图的结构特性,使相关联的顶点ID分布呈现局部有序,减少图算法运行过程中的内存随机访问。对于迭代式图算法,通过分析其算法收敛特性,发现图结构中“超级顶点”长时间不能达到收敛状态而造成了迭代式图应用的长尾现象。针对于此,提出了基于影响力的图顶点重映射算法GDL-DR,该布局算法根据顶点的影响力(顶点度)完成图数据的布局。这样在图算法迭代后期,活跃顶点集执行状态更新时,与之相关联的邻居节点紧凑分布,可以减少内存随机访问,使顶点更快的达到收敛状态,缩短应用执行时间。测试结果表明:GDL-VC布局算法能够给遍历式图应用(连通分量、单源点最短路径)带来25.4%、27.5%的平均内存访问效率提升,部分数据集超过50%;GDL-DR布局算法能够给迭代式图应用(网页排名、标签传播)带来23.9%、17.1%的平均内存访问效率提升,最大提升百分比为42.9%。对于GraphChi测试平台,两种布局算法带来的系统加速比均达到1.5×以上,部分图数据超过2×;Cache命中率提高到90%以上。
【图文】：

图 1.4 典型图应用活跃顶点比例变化曲线可以看出，对于 BFS 遍历式图算法，其按照顺序层次遍历图结构，前期活例逐渐增大，随着大多数顶点都被访问，后续活跃顶点比例下降；但是整个过程活跃顶点比例整体上都维持在一个比较低的水平。而对于 PageRank 迭法，初始时由于所有顶点都要执行更新，因此活跃顶点比例很高；但是经过

图 1.6 图社区结构在对图数据重新布局的时候，如果能够预先准确的检测出图社一个社区单独执行顶点重映射。这样在分布式环境下，能够大大减量，，保持系统复杂均衡；而在单机环境下，亦可以保证内存中顶点体上呈现局部有序性。当前存在众多的图社区检测算法，如 M
【学位授予单位】：华中科技大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：TP311.12

【相似文献】

相关期刊论文 前10条

1 孙宏放;彭秀艳;赵希人;;改进周期图算法及在船舶运动预报中的应用[J];哈尔滨工程大学学报;2008年11期

2 徐耀东;杨华;魏大名;;计算机体表电位作图方法的研究[J];医疗器械;1987年04期

3 孙重春;;快速计算烟道尺寸的图算法[J];化肥设计;1988年02期

4 傅钟鹏;;建筑工人实用数学 第三十八讲 图算法[J];建筑工人;1988年02期

5 刘鲜京;;中医椎拿力学信息的处理方法[J];山东省科学院院刊;1988年02期

6 周庚生;;推件力、卸件力和顶件力的图算法[J];锻压技术;1988年02期

7 万新光;;一个面向边的图算法通用数据结构[J];哈尔滨科学技术大学学报;1988年02期

8 朱柏石,石维明,马云东;用图算法确定井巷工程的具体优化安排[J];阜新矿业学院学报;1989年02期

9 张亚光;图算法应用初探[J];中国环境监测;1989年02期

10 刘广宽,刘美轮;上界可控的门矩阵布图算法[J];计算机学报;1989年07期

相关会议论文 前9条

1 雷凯茹;赵海;朱宏博;朴春鹤;;基于导向半径参数自适应的数字抠图算法[A];第十二届沈阳科学学术年会论文集（理工农医）[C];2015年

2 朱更新;郑大钟;;一类离散事件系统的稳态控制与图算法[A];1995年中国控制会议论文集（下）[C];1995年

3 梁继;张新焕;王建;杨燕明;;基于NDVI背景场的雪盖制图算法探索[A];第十五届全国遥感技术学术交流会论文摘要集[C];2005年

4 王宇君;胡美琛;施伯乐;;外部闭包和3NF合成的快速图算法[A];第十一届全国数据库学术会议论文集[C];1993年

5 蒋长辉;陈帅;薄煜明;陈育伟;;基于因子图算法的惯性/卫星组合导航系统可行性研究[A];2018惯性技术发展动态发展方向研讨会文集[C];2018年

6 来永芳;;地下核爆炸沉降预报方法研究[A];第7届全国核电子学与核探测技术学术年会论文集（三）[C];1994年

7 宋鸿陟;区兆明;刘超彪;傅熠;;多焦点的鱼眼视图算法的研究与应用[A];第七届和谐人机环境联合学术会议（HHME2011)论文集【oral】[C];2011年

8 刘建;阎迪;官文涛;;基于模糊认知图算法的遥测智能推送平台设计[A];第九届中国卫星导航学术年会论文集——S08 测试评估技术[C];2018年

9 何正焱;王厚峰;;商品品牌名称挖掘[A];中国计算语言学研究前沿进展（2009-2011）[C];2011年

相关重要报纸文章 前1条

1 本报编辑部 整理;2018，科技将怎样改变世界？[N];中国经济导报;2018年

相关博士学位论文 前5条

1 孙巍;视觉感知特性指导下的自然图像抠图算法研究[D];北京交通大学;2015年

2 王强;频谱管理关键技术[D];北京交通大学;2009年

3 李一明;基于传导闭包图结构的布图算法研究[D];电子科技大学;2011年

4 杜文俊;基于几何的实时绘制反走样[D];浙江大学;2015年

5 张涛;高性能低能耗GPGPU计算技术研究[D];上海交通大学;2015年

相关硕士学位论文 前10条

1 易前旭;基于应用运行特征的图数据布局与访问优化研究[D];华中科技大学;2018年

2 肖军;基于GPU的图计算研究[D];湖南大学;2015年

3 李平凡;GPGPU上图处理算法的实现与优化[D];国防科学技术大学;2016年

4 梅珍杰;面向图计算的优化方法研究[D];华中科技大学;2017年

5 戚骏;自然图像抠图算法研究与优化[D];湖南大学;2015年

6 逄潇;基于概率图的最小独立图算法研究[D];青岛大学;2018年

7 骆名樊;概率路标图算法的无人机三维路径规划研究[D];华中科技大学;2016年

8 孙国星;全自动抠图技术的研究[D];山东师范大学;2017年

9 费炳超;数字图像抠图算法研究[D];电子科技大学;2012年

10 程宾洋;高光谱遥感蚀变矿物填图算法并行设计与实现[D];成都理工大学;2013年

本文编号：2689668