GraphPulse: An Event-Driven Hardware Accelerator for Asynchronous Graph Processing
GraphPulse: An Event-Driven Hardware Accelerator for Asynchronous Graph Processing
复制标题
DOI：
10.1109/micro50266.2020.00078
复制
发表时间：
2020-10
期刊：
影响因子：
--
通讯作者：
Shafiur Rahman;N. Abu-Ghazaleh;Rajiv Gupta
中科院分区：
文献类型：
--
作者：
Shafiur Rahman;N. Abu-Ghazaleh;Rajiv Gupta
图形处理工作负载是记忆密集型的，具有不规则的访问模式，并且记忆足迹较大，导致数据位置较低。他们受欢迎的软件实现通常在遵循批量同步模型的多个迭代中采用了通过图的推动或拉动样式传播。这些算法在传统计算系统上的性能受到顶点值，同步开销的随机读取/写入的限制，以及用于跟踪跨迭代跨越顶点或边缘的活动集的其他开销。在本文中，我们介绍了GraphPulse，这是一个用于异步图处理的硬件框架，并通过事件驱动的调度来克服软件框架的性能限制。事件驱动的计算模型可以实现并行数据流式执行，其中原子更新和活动集跟踪是模型固有的；因此，调度复杂性降低并提高了可伸缩性。体系结构的数据流质还可以通过携带事件本身中的值来减少对顶点值的随机读取。我们利用图形算法中通常存在的更新属性，以合并飞行中事件，并大大减少事件存储需求和所产生的处理开销。 GraphPulse事件模型自然支持异步图处理，通过利用可用的并行性，减少工作并消除在迭代边界处的同步，从而实现了更快的收敛速度。该框架提供了易于使用的编程接口，以更快地开发硬件图加速器。一个Graphpulse Accelerator在Ligra上达到了高达74倍的加速度（平均28倍），Ligra是一个在12个核心CPU上运行的最先进的软件框架。它还比Graphicionado平均达到6.2倍的加速度，这是一个最先进的加速器的状态。
Graph processing workloads are memory intensive with irregular access patterns and large memory footprint resulting in low data locality. Their popular software implementations typically employ either Push or Pull style propagation of changes through the graph over multiple iterations that follow the Bulk Synchronous Model. The performance of these algorithms on traditional computing systems is limited by random reads/writes of vertex values, synchronization overheads, and additional overheads for tracking active sets of vertices or edges across iterations. In this paper, we present GraphPulse, a hardware framework for asynchronous graph processing with event-driven scheduling that overcomes the performance limitations of software frameworks. Event-driven computation model enables a parallel dataflow-style execution where atomic updates and active sets tracking are inherent to the model; thus, scheduling complexity is reduced and scalability is enhanced. The dataflow nature of the architecture also reduces random reads of vertex values by carrying the values in the events themselves. We capitalize on the update properties commonly present in graph algorithms to coalesce in-flight events and substantially reduce the event storage requirement and the processing overheads incurred. GraphPulse event-model naturally supports asynchronous graph processing, enabling substantially faster convergence by exploiting available parallelism, reducing work, and eliminating synchronization at iteration boundaries. The framework provides easy to use programming interface for faster development of hardware graph accelerators. A single GraphPulse accelerator achieves up to 74x speedup (28x on average) over Ligra, a state of the art software framework, running on a 12 core CPU. It also achieves an average of 6.2x speedup over Graphicionado, a state of the art graph processing accelerator.