| 梁彦,聂娜,曹华伟,马丽娜,叶笑春,范东睿.基于数据压缩和异步通信策略的分布式图算法优化研究[J].高技术通讯(中文),2025,35(2):145~156 |
| 基于数据压缩和异步通信策略的分布式图算法优化研究 |
| Optimization of distributed graph algorithms based on data compression and asynchronous communication strategies |
| |
| DOI：10. 3772 / j. issn. 1002-0470. 2025. 02. 004 |
| 中文关键词: 宽度优先搜索； 图数据划分； 压缩编码； 异步环形通信； 并行优化 |
| 英文关键词: breadth first search (BFS), graph partition, date compression, asynchronous ring communication, parallel optimization |
| 基金项目: |
| 作者 | 单位 | | 梁彦 | （处理器芯片全国重点实验室（中国科学院计算技术研究所）北京 100190）
（中国科学院大学北京 100049） | | 聂娜 | | | 曹华伟 | | | 马丽娜 | | | 叶笑春 | | | 范东睿 | |
|
| 摘要点击次数: 10 |
| 全文下载次数: 10 |
| 中文摘要: |
| 图是一种非常重要的数据结构形式，被广泛用于社交网络、交通网络和搜索引擎等领域。随着图数据规模爆发式增长，存储容量受限，分布式图计算成为处理大规模图数据的焦点。宽度优先搜索(breadth first search，BFS)算法是图遍历和许多图分析算法的基础，而在分布式图计算过程中存在严重的通信开销。针对上述问题，本文提出了一种综合的数据压缩编码优化方案，结合位图和变长压缩数组，通过更高的压缩率来降低数据通信开销；此外，还提出了一种点对点异步环形通信策略，进一步降低分布式图计算中计算-通信的同步开销。通过这些优化手段，本文在8节点的分布式集群上对优化后BFS算法的性能进行了系统评估，结果表明，当图数据规模为28时，优化后的BFS算法平均性能为46.79亿条边每秒遍历(giga-traversed edges per second，GTEPS)，性能比优化前提升了接近7.82%。 |
| 英文摘要: |
| Graph is a very important form of data structure, which is widely used in fields such as social networks, transportation networks and search engines. With the explosive growth of graph data size and limited storage capacity, distributed graph computation has become the focal point for processing large-scale graph data. Breadth-first search (BFS) algorithm is the basis of graph traversal and many graph analysis algorithms. There is a serious communication overhead during distributed graph computation. To address the above problem, this paper proposes a comprehensive data compression optimization scheme, combining bitmap and varint compression array, to reduce data communication overhead by high compression ratio; in addition, it also proposes a point-to-point asynchronous ring communication strategy to further reduce the synchronization overhead of computation-communication in distributed graph computing. Through these optimizations, this paper systematically evaluates the performance of BFS algorithm on an 8-node distributed cluster. When the graph data scale is 28, the average performance of BFS algorithm is 46.79 giga-traversed edges per second(GTEPS), and the performance has been improved by nearly 7.82% compared with that before the optimization. |
|
查看全文
查看/发表评论 下载PDF阅读器 |
| 关闭 |
|
|
|
