A Performance and Recommendation System for Parallel Graph Processing Implementations: Work-In-Progress
A Performance and Recommendation System for Parallel Graph Processing Implementations: Work-In-Progress
复制标题
DOI：
10.1145/3302541.3313097
复制
发表时间：
2019-03
期刊：
影响因子：
--
通讯作者：
Samuel D. Pollard;Sudharshan Srinivasan;Boyana Norris
中科院分区：
文献类型：
--
作者：
Samuel D. Pollard;Sudharshan Srinivasan;Boyana Norris
有近百个并行和分布式图形处理包。为给定问题选择最佳程序包很困难；有些程序包需要GPU，有些程序包针对分布式或共享内存进行了优化，有些程序包需要专有编译器或在不同的硬件上执行得更好。此外，根据图形本身的不同，性能可能会有很大差异。这种复杂性使得手动选择最佳实现是不可行的。我们开发了一种方法，通过将配置标记为性能良好或不好，使用回归模型和二进制分类来预测并行图处理的性能。我们在六个图形处理包：GraphMat、Graph500、Graph算法平台基准套件、GraphBIG、Galois和PowerGraph上展示了我们的方法，并在四个算法上展示了我们的方法：PageRank、单源最短路径、三角形计数和宽度优先搜索。在给定图表的情况下，我们的方法可以估计执行时间，或者建议预期执行良好的实现和线程计数。我们的方法在97%的测试用例中正确识别了性能良好的配置。
There are nearly one hundred parallel and distributed graph processing packages. Selecting the best package for a given problem is difficult; some packages require GPUs, some are optimized for distributed or shared memory, and some require proprietary compilers or perform better on different hardware. Furthermore, performance may vary wildly depending on the graph itself. This complexity makes selecting the optimal implementation manually infeasible. We develop an approach to predict the performance of parallel graph processing using both regression models and binary classification by labeling configurations as either well-performing or not. We demonstrate our approach on six graph processing packages: GraphMat, the Graph500, the Graph Algorithm Platform Benchmark Suite, GraphBIG, Galois, and PowerGraph and on four algorithms: PageRank, single-source shortest paths, triangle counting, and breadth first search. Given a graph, our method can estimate execution time or suggest an implementation and thread count expected to perform well. Our method correctly identifies well-performing configurations in 97% of test cases.