异构环境下的高并发图计算加速方法

发布时间：2021-01-18 05:16

　　图计算能够挖掘事物之间潜在不易洞察的行为和联系,广泛应用于服务推荐、欺诈检测、风投分析、市场营销、疾病建模等领域。随着互联网等领域的发展,图数据规模爆炸增长的同时,各种图分析算法不断涌现。在图处理平台上,大量图算法并发地对共享的图结构进行处理,形成了并发图分析任务。与CPU相比,GPU具有更强的并行计算能力,因此由CPU和GPU组成的异构环境更适合大规模图处理。然而,在当前的GPU图计算系统中,并发图分析任务独立地沿着不同的路径访问共享图,由于严重的数据带宽竞争和缓存干扰,导致较高的访存计算比,降低系统吞吐率。为解决上述问题,实现了数据驱动的并发图分析任务执行机制,支持高效的并发图计算。首先,为多GPU节点建立异步通信机制,实现图算法的异步执行模型,避免同步编程模型的大量同步开销;其次,在GPU的本地计算阶段实现数据驱动的并发图分析任务执行机制,将图数据划分成大小合适的块,按照一定的顺序载入缓存中,然后触发多个相关任务并发处理,减少总的数据访问需求;最后,实现了一个图划分块调度器,最大化并发图分析任务数据访问的关联性;此外,通过给待处理的顶点赋予优先级解决异步编程模型可能导致的冗余计算... 

【文章来源】：华中科技大学湖北省 211工程院校 985工程院校 教育部直属院校

【文章页数】：53 页

【学位级别】：硕士

【部分图文】：

同步（上）和异步（下）编程模型比较

理一个共享图，由图划分块 1 和图划分块 2 组成。用现存的解决方案，SSSP 能先访问划分块 1，接着访问划分块 2，而 PageRank 任务可能先访问划分块访问划分块 1。而且不同任务对每个划分块的处理是不同的，使得数据访问更规律性。结果，划分块 1 和 2 需要被重复地载入缓存，这导致严重的数据访竞争和缓存干扰。如图 2.3 是在某社交网路上对不同数目并发任务共享图的比例随时间进行采从图 2.3 可以发现，由于重复遍历共享图并发任务的数据访问有很强的空间和联性。这意味着并发图分析任务存在冗余访问，很多缓存空间被浪费于在不间存储相同图数据的拷贝。如图 2.3 展示的，每轮迭代中不同任务处理的图划分块的交集很大（平均超的所有活跃划分块），这叫做空间关联性。然而，在现存的系统中并发图分析不同的顺序访问共享图划分块。理想情况下，并发任务应该合并对共享图结问，在缓存中存储一份共享数据同时服务多个任务。

华 中 科 技 大 学 硕 士 学 位 论 文载进去。每载入一个图划分块，然后触发并发任务进行处理，避免各图别加载它。当一个图划分块被对应所有任务处理完之后才能载入下一个并发处理模块给待处理的图划分块设置优先级，每次调度最多图分析任的、拥有最高平均顶点度数的图划分块，从而最大化并发图分析任务数关性。

【参考文献】：
期刊论文
[1]并行原型系统上BFS算法设计实现与测试分析[J]. 衡冬冬,唐玉华,易晓东,刘向阳,周侗.  计算机工程与科学. 2017(01)
[2]工业控制系统信息安全审计系统分析与设计[J]. 陈庄,黄勇,邹航.  计算机科学. 2013(S1)
[3]相关任务图的均衡动态关键路径调度算法[J]. 石威,郑纬民.  计算机学报. 2001(09)

博士论文
[1]众核GPU体系结构相关技术研究[D]. 陈钢.复旦大学 2011



本文编号：2984347