An Analytical Study of Recursive Tree Traversal Patterns on Multi- and Many-Core Platforms
An Analytical Study of Recursive Tree Traversal Patterns on Multi- and Many-Core Platforms
复制标题
多核和众核平台上递归树遍历模式的分析研究
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
M. Becchi
中科院分区：
文献类型：
--
作者：
Hancheng Wu;M. Becchi
递归树遍历在数据挖掘、图形学、机器学习和科学模拟等领域有着广泛的应用。在过去的几年里，人们越来越关注在众核设备上部署基于图数据结构的应用程序。最近的一些工作集中在优化GPU上多个串行树遍历的执行，并报告了不同算法的性能趋势。在这项工作中，我们的目标是了解如何选择最适合给定的树遍历算法和数据集的实现和平台。为此，我们在CPU，GPU和Intel Phi处理器上进行了递归树遍历的系统研究。我们首先确定四种树遍历模式：其中三种并行执行多个串行遍历，最后一种执行单个并行级别的顺序遍历。对于这些模式中的每一个，我们考虑不同的代码变体，包括现有的和新的优化方法，我们描述他们的控制流和内存访问模式。我们实现这些代码变体，并在CPU、GPU和英特尔Phi上进行评估。我们的分析表明，没有一个单一的代码变体和平台，实现所有树遍历模式的最佳性能，它提供了最适合于一个给定的树遍历模式和输入数据集的实现的选择指南。
Recursive tree traversals are found in many application domains, such as data mining, graphics, machine learning and scientific simulations. In the past few years there has been growing interest in the deployment of applications based on graph data structures on many-core devices. A couple of recent efforts have focused on optimizing the execution of multiple serial tree traversals on GPU, and have reported performance trends that vary across algorithms. In this work, we aim to understand how to select the implementation and platform that is most suited to a given tree traversal algorithm and dataset. To this end, we perform a systematic study of recursive tree traversal on CPU, GPU and the Intel Phi processor. We first identify four tree traversal patterns: three of them performing multiple serial traversals concurrently, and the last one performing a single parallel level order traversal. For each of these patterns, we consider different code variants including existing and new optimization methods, and we characterize their control-flow and memory access patterns. We implement these code variants and evaluate them on CPU, GPU and Intel Phi. Our analysis shows that there is not a single code variant and platform that achieves the best performance on all tree traversal patterns, and it provides guidelines on the selection of the implementation most suited to a given tree traversal pattern and input dataset.