科研之友
微信
新浪微博
Facebook
分享链接
摘要
大图数据的BFS算法作为一种基础算法，广泛受到工业界和学术界的重视。不同平台涌现出众多大图BFS算法的研究工作，其中多使用固态硬盘提高算法效率。在BFS算法遍历过程中，存储设备需要连续重复装载数据以满足遍历需求，而数据重复装载造成大量数据擦写操作，严重影响了固态硬盘的使用寿命。由此可见，减少BFS算法数据擦写操作可以有效延长固态硬盘的使用寿命。结合图结构的特点，提出数据重用模型，用于描述图遍历过程中的数据重用程度；提出了基于图顶点度的启发式优先访问方法，该方法判断图顶点之间的独立性，并根据判断结果选择优先访问的图顶点，增加数据重用的可能性，提高缓存的命中率，减少闪存颗粒磨损。提出的优化方法不修改BFS算法和大图数据，因此适用于各种BFS算法和数据集。最后，实验验证了所提数据重用模型的正确性，以及启发式优先访问方法的有效性。该优化方法应用于BFS-4K，B40C和Gunrock这3种常见的BFS算法上，能有效减少图遍历过程中的数据写入操作，固态硬盘的使用寿命可分别提高12%，15%，22%。
- 单位
