As the scale of graph analytics continues to grow, many applications require identifying biconnected components (bccs) and cut vertices in graphs that exceed the memory capacity of a single gpu. This paper presents an out-of-core, gpu-based batch processing algorithm designed to efficiently compute bccs and cut vertices in massive graphs that do not fit entirely into device memory. We propose a novel batch technique to process the graph incrementally, and maintain a Biconnectivity Compressed Graph to compute bccs and cut vertices. Experimental results on a range of large-scale benchmark graphs demonstrate that our technique achieves competitive performance compared to state-of-the-art cpu solutions, enabling the handling of graph instances previously considered intractable on gpu platforms.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

External GPU Biconnected Components

  • Abhijeet Sahu,
  • Andaluri S. P. V. M. Aditya,
  • G. Ramakrishna,
  • Malleti Sai Nikhil,
  • Kishore Kothapalli,
  • Dip Sankar Banerjee

摘要

As the scale of graph analytics continues to grow, many applications require identifying biconnected components (bccs) and cut vertices in graphs that exceed the memory capacity of a single gpu. This paper presents an out-of-core, gpu-based batch processing algorithm designed to efficiently compute bccs and cut vertices in massive graphs that do not fit entirely into device memory. We propose a novel batch technique to process the graph incrementally, and maintain a Biconnectivity Compressed Graph to compute bccs and cut vertices. Experimental results on a range of large-scale benchmark graphs demonstrate that our technique achieves competitive performance compared to state-of-the-art cpu solutions, enabling the handling of graph instances previously considered intractable on gpu platforms.