论文传送门
作者
华中科技大学
Chuang-Yi GuiLong ZhengXiao-Fei LiaoHai Jin 新加坡国立大学
Bingsheng HeXin-Yu Chen 中国科学院计算技术研究所
Cheng Liu
摘要
图是一种众所周知的数据结构，用于表示各种应用程序中的关联关系，例如数据科学和及其学习。尽管在开发图处理系统以改进传统架构的性能和能源效率方面已有大量的现有工作，专用硬件解决方案，也成为图加速器是必不可少的，其提供的好处远远超过那些纯软件解决方案。在本文中，我们对图处理加速器进行了系统的调查。具体来说，我们将对图处理加速器的三个核心组建中的相关技术进行回顾：预处理、并行图计算和运行时调度。我们还将检查基准和现有图处理加速器的结果。有趣的是，由于图处理的多样性和复杂性，我们发现没有在三个方面都是赢家的硬件配置。最后，我们详细介绍并讨论了几个挑战，并进一步探索了将来研究的机遇。
Introduction
Preprocessing
使数据能够放进内存与某些模型相配合适的图表达 Parallel Graph Computation
迭代范式硬件平台：FPGA、ASIC、PIM软硬件协同设计 Runtime Scheduling
保证正确性和有效性数据通信、执行模式、调度策略
Building blocks for graph processing accelerators
Preliminaries
Graph features
Sparsity
节点平均度数小 Power-Law Distribution
少部分节点关联了大多数边 Small-World Structure
任意两个节点在不多的跳数内可达对图的划分造成了困难
Graph Algorithms
Breadth-First Search (BFS)Single Source Shortest Path (SSSP)Betweenness Centrality (BC)PageRankConnected Components (CC)Triangle Counting (TC)Graph Coloring (GC)Collaborative Filtering (CF)k-core Decomposition (kCore)Minimal Spanning Tree (MST)
Unique Features of Graph Processing
Intensive Data AccessIrregular Computation.Poor LocalityHigh Data Dependency
Brief Introduction to Graph Processing on Modern Commodity Processors
Graph Processing on CPUs
distributed systemsexploits the potential of single machine Graph Processing on GPUs
Graph Preprocessing
Graph Layout Reorganization
edge array
Coordinate List (COO) compressed adjacency list
Compressed Sparse Row (CSR)Compressed Sparse Column (CSC) Combining InformationEncoding Index
Index-Aware OrderingDegree-Aware OrderingConflict-Aware Ordering Graph Partitioning
Source-orientedDestination-orientedGridHeuristic
Parallel Graph Computation
Iterative Paradigm
Vertex-centricEdge-centricHybrid
Dedicated Hardware Acceleration
FPGA-Based DesignsASIC-Based DesignsPIM-Enabled Designs
Large-Scale Graph Processing Acceleration
Out-of-Core SolutionMultiple Accelerators ExtensionHeterogeneous Acceleration
Sophisticated Co-Designs
Parallelism Extension
Pipeline DuplicationSplit KernelUsing Dataflow Paradigm Memory Access Optimization
Enhancing Memory-Level Parallelism (MLP).Improving Bandwidth UtilizationReshaping Cache Hierarchy Energy Efficiency Optimization
Leveraging Emerging Memory TechnologiesPower-Gating Schemes
Runtime Scheduling
Runtime Considerations
Data ConflictsWorkload Balance Communication Model
Message-Based PatternShared Memory Based Pattern Execution Mode
Synchronous ModeAsynchronous ModeInformation Flow Direction Scheduling Scheme
Block-Based SchedulingFrontier-Based SchedulingPriority-Based Scheduling
Graph Accelerator Evaluation
Evaluation Metrics
TEPSTEPS/W Summary of Results
Graph BenchmarkPlatform ParameterPreprocessingGraph Processing FrameworkProgramming Model.Development Trend Case Study
AccuGraph
Challenges and Opportunities
Challenges
ProgrammabilitySupporting Large GraphsTime-Evolving GraphsComplex Attributes of GraphsMachine Learning on GraphsHardware InterfacesTool ChainsCompiler Support
Opportunities
Widespread AdoptionEmerging TechnologiesFPGA on the CloudRise of Specialized Architectures in Artificial Intelligence
思考
Critical thinking: benchmark 对于不同任务的侧重程度不一 通过硬件加速大图数据的数据库存取效率
Creative thinking: 比较一些工业界使用的图计算学习框架
How to apply to our work: 对于大图数据的分析要注重预处理和计算，最后可以结合可视化进行分析。 graph reordering, graph partition 之前关注不足，之后的工作可以借鉴。
