基于混合着色算法的GPU异步图计算系统

小鱼儿 2024-04-03 11:39 35阅读 0赞

目 录  
摘 要 I  
Abstract II  
1 绪 论  
1.1 研究背景 (1)  
1.2 国内外研究现状 (3)  
1.3 主要研究内容 (7)  
1.4 文章框架结构 (8)  
2 Frog系统框架  
2.1 图计算编程模型 (10)  
2.2 编程模型问题分析 (12)  
2.3 Frog系统架构 (14)  
2.4 数据结构和编程接口 (17)  
2.5 小结 (19)  
3 数据划分策略  
3.1 数据划分策略分析 (20)  
3.2 混合着色算法 (22)  
3.3 预处理和数据流管理 (26)  
3.4 小结 (27)  
4 异步执行与迭代处理  
4.1 数据一致性与异步执行 (29)  
4.2 图算法迭代处理 (31)  
4.3 GPU调度优化 (33)  
4.4 小结 (34)  
5 系统测试与性能分析  
5.1 实验设置、测试数据集和算法 (35)  
5.2 Frog系统性能测试与分析 (36)  
5.3 小结 (42)  
6 总结与展望 (43)  
致 谢 (45)  
参考文献 (47)  
1.3 主要研究内容  
当前的GPU图计算系统，仍然按照分布式或者CPU单机的计算模式，基于BSP同步处理模型并结合GPU自身结构特点，尝试加速整个处理过程。但由于同步处理模型存在通信开销大、无法保证任务并发度等问题，该模型并不适合GPU系统。而GraphLab、PowerGraph等系统尝试使用的异步处理模型中，一种是基于分布式锁的使用，另一种是基于传统的着色数据划分策略，来保证异步处理模型中的数据一致性，然而GPU中使用锁的开销巨大\[38, 39\]，而传统的着色数据划分策略则无法高效利用GPU计算资源。  
本课题通过优化数据划分策略，基于异步编程模型，实现一个无锁的GPU图计算系统，提高GPU计算资源的利用率。首先，本课题提出了一种创新性的混合着色算法，解决传统数据划分策略中任务均衡性差的问题，使得划分结果能提高GPU的计算资源利用率；其次，设计了一种基于GPU的无锁、异步图计算系统，减少由于同步通信而带来的额外开销，通过加速图算法的收敛速度，提升图计算系统的性能。最后，对现有计算系统普遍无法处理的大规模图数据，本课题采用Stream处理模式，通过迭代处理、CPU和GPU及时交互的方法，解决超出GPU内存大小的图数据处理问题。  
1.4 文章框架结构  
本节介绍文章后续各章节的内容安排：  
第二章将首先分析同步处理模型的问题所在，总结了异步处理模型在图计算系统中的优势，进而给出了Frog系统的整体结构。然后介绍了Frog处理图数据的整个执行流程，并详细阐述了Frog系统中数据预处理、流式数据控制等阶段的具体工作。  
第三章介绍Frog系统预处理阶段的核心——基于混合着色算法的数据划分策略。首先分析和总结了当前计算系统中普遍使用的传统数据划分策略，并给出了Frog中采用的基于混合着色算法的新型数据划分策略，着重介绍了该划分策略的算法流程和工作原理。  
第四章介绍Frog系统异步执行和迭代处理的执行过程。首先介绍和分析了异步执行数据一致性问题和图算法迭代计算的特征，描述了Frog迭代计算控制的方法，然后分析和指出了Frog加快算法迭代收敛速度的优势。  
第五章给出Frog和当前GPU图计算系统、CPU图计算系统之间的实验对比分析。首先介绍实验环境，分析了Frog中数据划分策略的优势，并与其他系统的划分策略进行性能比较；然后，从系统角度展开实验，本文转载自http://www.biyezuopin.vip/onews.asp?id=16893通过对多个数据集、图算法的执行，分析总结了Frog系统的优势所在；最后，还展示了Frog系统在处理超出GPU内存大小的图数据时的效果。  
第六章为总结和展望。总结已完成的工作，并指出系统中还需完善的地方和未来工作的研究方向。  
文章最后为致谢和参考文献，以及本人在硕士期间发表的论文、参与的科研项目、申请的国家专利和系统的开源情况。  
![在这里插入图片描述][e089ea78baed40338353c609709669a4.png_pic_center]  
![在这里插入图片描述][7d2399810f8749588c3ce09729bc4c19.png_pic_center]  
![在这里插入图片描述][2bd201a0eb0349878f2a377d721baaaf.png_pic_center]  
![在这里插入图片描述][8080c964ee0642b6a274c59cea2da681.png_pic_center]  
![在这里插入图片描述][28514d4f17bd41edad1cb6145c1f7915.png_pic_center]  
![在这里插入图片描述][2d23ecb75db8401f8518310996105497.png_pic_center]  
![在这里插入图片描述][6fdc0ad8d22f447faae42605f84e3a2f.png_pic_center]  
![在这里插入图片描述][af5e9467b91649e0a2bc242c90552eed.png_pic_center]  
![在这里插入图片描述][3cbeea737b8c412dbeff7d3fc8a12f3b.png_pic_center]  
![在这里插入图片描述][a68e3275b48344febdaefe2d9bfdef09.png_pic_center]  
![在这里插入图片描述][47020ab8a9cf491ab22b0790520d2405.png_pic_center]  
![在这里插入图片描述][18bbd7283bca49f7a88895753af4f92c.png_pic_center]  
![在这里插入图片描述][48cdab8f50024fc9b6498443ea2c77c8.png_pic_center]

[e089ea78baed40338353c609709669a4.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/bf5762504e2f44bb97f3c8d34d72b0db.png
[7d2399810f8749588c3ce09729bc4c19.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/8ec0720c88a3482ca6fcd9b20ed7b3ce.png
[2bd201a0eb0349878f2a377d721baaaf.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/0f782d3643ce452bbd7bd08605a00a81.png
[8080c964ee0642b6a274c59cea2da681.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/f37e4143f5614553a5a8faf7b2291950.png
[28514d4f17bd41edad1cb6145c1f7915.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/9c6c3c5c1fe9462eb9052842cab27b67.png
[2d23ecb75db8401f8518310996105497.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/7ac61c976af34d0fa4c1783f1e413905.png
[6fdc0ad8d22f447faae42605f84e3a2f.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/4f1e7ace5e4f4f0abc49983f21dd02b5.png
[af5e9467b91649e0a2bc242c90552eed.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/a20586007e0242fda9abd6e4f36c97bf.png
[3cbeea737b8c412dbeff7d3fc8a12f3b.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/587268d880d749e590a0b9bfda47d4f6.png
[a68e3275b48344febdaefe2d9bfdef09.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/36a93e18694249028936e29b4faf2591.png
[47020ab8a9cf491ab22b0790520d2405.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/a15ab8cbe46341f3a02b6a7b792019b4.png
[18bbd7283bca49f7a88895753af4f92c.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/91de9cb051b540eb80aa4e2580bbba0d.png
[48cdab8f50024fc9b6498443ea2c77c8.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/e24d80c1ec444983ad430a427f4995c9.png