Navigating the maze of graph analytics frameworks using massive graph datasets
Navigating the maze of graph analytics frameworks using massive graph datasets
复制标题
DOI：
10.1145/2588555.2610518
复制
发表时间：
2014-06
期刊：
影响因子：
--
通讯作者：
N. Satish;N. Sundaram;Md. Mostofa Ali Patwary;Jiwon Seo;Jongsoo Park;M. A. Hassaan;Shubho Sengupta
中科院分区：
文献类型：
--
作者：
N. Satish;N. Sundaram;Md. Mostofa Ali Patwary;Jiwon Seo;Jongsoo Park;M. A. Hassaan;Shubho Sengupta
在许多领域，图算法在分析大型数据集方面变得越来越重要。现实世界的图形数据遵循稀疏性模式，即不一致，但高度偏向于少数项。以可扩展的方式在这些数据上实现图遍历、统计和机器学习算法是相当具有挑战性的。因此，出现了几个图形分析框架（GraphLab、CombBLAS、Giraph、SociaLite和Galois等），每个框架都提供了针对不同用户的不同编程模型的解决方案。不幸的是，对于常见的图算法，优化代码和大多数框架之间的“忍者性能差距”非常大（大多数框架的2-30倍，Giraph的高达560X），而且随着算法的不同而变化很大。这使得最终用户对图形框架的选择不仅取决于易用性，还取决于性能。在这项工作中，我们为改善所有这些框架的性能和弥合“忍者差距”提供了一个定量的路线图。我们首先提出了手动优化的基线，其性能接近硬件限制，并且高于这些图形算法的任何已发布的性能数据。我们描述了这种原生实现以及流行的图形框架在各种算法上的性能。这项研究帮助最终用户描述算法本身、编程模型抽象和框架实现之间产生的瓶颈。此外，通过分析这些框架的系统级行为，我们获得了与特定算法无关的瓶颈。我们建议进行更改以缓解这些瓶颈（并实现其中的一些瓶颈），并减少与本机代码之间的性能差距。这些变化将使最终用户能够主要根据易用性来选择框架。
Graph algorithms are becoming increasingly important for analyzing large datasets in many fields. Real-world graph data follows a pattern of sparsity, that is not uniform but highly skewed towards a few items. Implementing graph traversal, statistics and machine learning algorithms on such data in a scalable manner is quite challenging. As a result, several graph analytics frameworks (GraphLab, CombBLAS, Giraph, SociaLite and Galois among others) have been developed, each offering a solution with different programming models and targeted at different users. Unfortunately, the "Ninja performance gap" between optimized code and most of these frameworks is very large (2-30X for most frameworks and up to 560X for Giraph) for common graph algorithms, and moreover varies widely with algorithms. This makes the end-users' choice of graph framework dependent not only on ease of use but also on performance. In this work, we offer a quantitative roadmap for improving the performance of all these frameworks and bridging the "ninja gap". We first present hand-optimized baselines that get performance close to hardware limits and higher than any published performance figure for these graph algorithms. We characterize the performance of both this native implementation as well as popular graph frameworks on a variety of algorithms. This study helps end-users delineate bottlenecks arising from the algorithms themselves vs. programming model abstractions vs. the framework implementations. Further, by analyzing the system-level behavior of these frameworks, we obtain bottlenecks that are agnostic to specific algorithms. We recommend changes to alleviate these bottlenecks (and implement some of them) and reduce the performance gap with respect to native code. These changes will enable end-users to choose frameworks based mostly on ease of use.