A Survey on Graph Processing Accelerators: Challenges and Opportunities

论文传送门

作者

• 华中科技大学

  • Chuang-Yi Gui
  • Long Zheng
  • Xiao-Fei Liao
  • Hai Jin

• 新加坡国立大学

  • Bingsheng He
  • Xin-Yu Chen

• 中国科学院计算技术研究所

  • Cheng Liu

摘要

图作为一种广泛认知的数据结构，在描述不同领域中的关联关系时发挥着重要作用。例如，在数据科学及其学习领域中就可见这一特点。尽管在提升传统架构性能与能源效率方面已取得诸多相关工作[1-3]，专用硬件方案已成为实现图加速器的关键必要条件[4]。其带来的优势远超纯粹软件方案[5]。本文旨在探讨当前关于图处理加速器的研究进展及未来发展方向。具体而言，则是对以下三个核心组成部分的相关技术展开系统性分析：预处理机制、并行计算框架以及调度优化策略[6,7]。此外还需考察现有的加速器基准体系及其性能表现[8]。值得注意的是，在提升多维度性能方面，并无单一硬件方案能够占据绝对优势[9]。最后将深入探讨当前面临的技术挑战，并展望未来研究的主要机遇。

Introduction

• Preprocessing

  • 使数据能够放进内存
  • 与某些模型相配
  • 合适的图表达

• 该并行计算模型基于图结构。

  • 该系统采用循环模式。

  • 硬件平台为FPGA、ASIC和PIM。

  • 软硬件协同架构。

  • Runtime Scheduling

    • 保证正确性和有效性
    • 数据通信、执行模式、调度策略

Building blocks for graph processing accelerators

Preliminaries

Graph features

• Sparsity

  • 节点平均度数小

• Power-Law Distribution

  • 少部分节点关联了大多数边

• 小世界网络

• 任何两个节点经过有限步数可达

• 划分图带来了划分上的困难

Graph Algorithms

• 广度优先搜索(BFS)
  • 单源最短路径(SSSP)
  • 中间性中心性(BC)
  • 网页排名算法(PageRank)
  • 连通组件分析(CC)
  • 三角形计数(TC)
  • 图着色问题(GC)
  • 协同过滤技术(CF)
  • k核分解方法(kCore)
  • 最小生成树计算(MST)

Unique Features of Graph Processing

• 数据访问强度高
• 非规则计算
• 数据局部性差
• 数据依赖性高

A Concise Overview of Graph Processing Techniques for Modern General-Purpose Processors

• Graph Analytics on GPUs

  • distributed computing environments

  • leverages the processing power of individual nodes

  • Graph Processing on GPUs

Graph Preprocessing

• Graph Layout Reorganization

  • edge array
    • Coordinate List (COO)

• 压缩邻接表

  • 压缩稀疏行（CSR）

  • 压缩稀疏列（CSC）

    • Combining Information
    • Encoding Index
  • • Index-Aware Ordering
    • Degree-Aware Ordering
    • Conflict-Aware Ordering

  • Graph Partitioning

    • Source-oriented
    • Destination-oriented
    • Grid
    • Heuristic

Parallel Graph Computation

• Iterative Paradigm
  • Vertex-centric
  • Edge-centric
  • Hybrid

Dedicated Hardware Acceleration

* FPGA-Based Designs
* ASIC-Based Designs
* PIM-Enabled Designs

Large-Scale Graph Processing Acceleration

• 外存环境下的一种解决方案
• 多核心处理器的扩展方案
• 不均匀计算环境下的加速策略

Sophisticated Co-Designs

• 并行性增强

• 流水线复制

• 内核分割

• 采用数据流范式

• Memory Access Optimization

  • 提升内存层次的并行性（MLP）。
  • 提高带宽利用率。
  • 重新排列缓存层级结构。

• Energy Efficiency Optimization

  • Exploiting novel memory technologies
  • Power gating techniques, a key strategy for optimizing energy efficiency

Runtime Scheduling

• Runtime Considerations
  • Data Conflicts
  • Workload Balance

Communication Mechanism, Message-Driven Pattern, Shared Memory Mechanism

运行模式

• 调度方案 *
  • 基于块的调度方法 *
  • 前沿驱动型调度方案 *
  • 基于优先级的调度方法 *

Graph Accelerator Evaluation

• Evaluation Metrics

  • TEPS
  • TEPS/W

• 结果概述

• 图基准测试

• 平台参数设置

• 预处理步骤

• 图处理框架方案

• 编程模型说明

• 发展趋势分析

  • Case Study
    • AccuGraph

Challenges and Opportunities

Challenges

• 可编程性
• 大规模图的支持
• 动态图
• 复杂属性的图
• 基于图的机器学习方法
• 硬件接口设计
• 工具链构建
• 编译支持机制

Opportunities

• 广泛采用
  • 新型技术的发展
  • 云计算中的FPGA应用
  • 深度学习架构的多样化发展

思考

Critical thinking:
在不同任务中, 该基准关注重点有所区别
借助硬件加速, 大规模图像数据在数据库存取效率上的提升显著

Creative thinking:
比较一些工业界使用的图计算学习框架

Applying to our work requires a thorough understanding of the analysis process for large-scale graph data. In-depth analysis of large graph data necessitates careful attention to preprocessing steps and computational requirements; visualization can enhance the analytical process by providing intuitive insights. In the previous phase, the focus on graph reordering and graph partition was insufficient; future research can draw upon established methodologies in this domain.