Improving Streaming Graph Processing Performance using Input Knowledge
Improving Streaming Graph Processing Performance using Input Knowledge
复制标题
DOI：
10.1145/3466752.3480096
复制
发表时间：
2021-10
期刊：
影响因子：
--
通讯作者：
Abanti Basak;Zheng Qu;Jilan Lin;Alaa R. Alameldeen;Zeshan A. Chishti;Yufei Ding;Yuan Xie
中科院分区：
文献类型：
--
作者：
Abanti Basak;Zheng Qu;Jilan Lin;Alaa R. Alameldeen;Zeshan A. Chishti;Yufei Ding;Yuan Xie
流图在当今的大数据时代无处不在。先前的工作已经提高了流图工作负载的性能，而没有考虑输入特性。在这项工作中，我们证明了输入知识驱动的软件和硬件协同设计是至关重要的优化性能的流图处理。为了提高图更新效率，我们首先描述了不经意输入批量重新排序的性能权衡。根据我们的研究结果，我们提出了输入感知的批量重排序，根据其度分布自适应地重新排序输入批次。为了补充自适应批量重新排序，我们建议动态更新图形，根据其输入特性，无论是在软件（通过更新搜索合并）或硬件（通过加速支持）。为了提高图的计算效率，我们提出了输入感知的工作聚合，自适应调整计算粒度的基础上，批间的局部性特征。在260个工作负载上进行评估，我们的输入感知技术为不同的输入类型提供了平均4.55倍和2.6倍的图形更新性能提升（除了消除输入无关的批量重新排序带来的性能下降之外）。图形计算性能提高了1.26倍（最高可达2.7倍）。
Streaming graphs are ubiquitous in today’s big data era. Prior work has improved the performance of streaming graph workloads without taking input characteristics into account. In this work, we demonstrate that input knowledge-driven software and hardware co-design is critical to optimize the performance of streaming graph processing. To improve graph update efficiency, we first characterize the performance trade-offs of input-oblivious batch reordering. Guided by our findings, we propose input-aware batch reordering to adaptively reorder input batches based on their degree distributions. To complement adaptive batch reordering, we propose updating graphs dynamically, based on their input characteristics, either in software (via update search coalescing) or in hardware (via acceleration support). To improve graph computation efficiency, we present input-aware work aggregation which adaptively modulates the computation granularity based on inter-batch locality characteristics. Evaluated across 260 workloads, our input-aware techniques provide on average 4.55 × and 2.6 × improvement in graph update performance for different input types (on top of eliminating the performance degradation from input-oblivious batch reordering). The graph compute performance is improved by 1.26 × (up to 2.7 ×).