图计算引擎分析--GridGraph
💡
原文中文，约10300字，阅读约需25分钟。
📝
内容提要
本文介绍了GridGraph系统的优化策略和二级分区划分方式，以及在PageRank算法中使用的双滑动窗口和选择调度等技术。该系统采用了Stream vertices and edges的图编程模型，以block为单位进行选择调度，并使用原子操作保证线程安全的方式更新顶点。文章还提到了其他相关研究，如X-Stream和GraphChi等。
🎯
关键要点
- GridGraph是一种单机核外图处理系统，能够在有限内存中高效完成大规模图计算。
- GridGraph采用Streaming-Apply方式减少计算中的IO请求数量，通过文件调入顺序减少不必要的IO开销。
- GridGraph的主要贡献包括网格划分、2级分区、流式处理模式和灵活的点边流式接口函数。
- 网格划分将顶点集划分成均匀的chunk，边集划分在P*P个block中。
- 选择调度通过bitmap记录block的访问状态，跳过不活跃的block以减少不必要的计算。
- 双滑动窗口模式保证顶点访问的局部性，减少IO总量，特别是写IO。
- GridGraph在内存和磁盘之间进行高效的数据置换，优化了图计算过程。
- GridGraph的二级分区划分方式提高了选择调度的效率，减少了IO访问。
- GridGraph能够在不涉及I/O访问的情况下访问内存中的顶点数据，提高算法执行效率。
🏷️
标签
➡️
