Treelogy: A benchmark suite for tree traversals
Treelogy: A benchmark suite for tree traversals
复制标题
Treelogy：树遍历的基准套件
DOI：
10.1109/ispass.2017.7975294
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Milind Kulkarni
中科院分区：
文献类型：
--
作者：
Nikhil Hegde;Jianqiao Liu;Kirshanthan Sundararajah;Milind Kulkarni
一类有趣的不规则算法是树遍历算法，它们反复遍历各种树以执行有效的计算。在科学计算，计算机图形学，生物信息学和数据挖掘等重要应用中，树木遍历算法形成了算法内核。了解树木遍历算法，对它们进行优化，并将它们应用于各种各样的兴趣，并将其应用于多种多样设置。至关重要的是，尽管对树遍历算法有许多可能的优化，但优化适用于算法取决于算法特征。在这项工作中，我们介绍了一套从称为Treelogy的不同领域绘制的树木遍历内核，以探索树遍历算法和最新优化之间的连接。我们通过基于本体的结构特性来开发这些算法来表征这些算法。对于给定的遍历内核，通过我们的本体论提取的属性可以帮助快速分析平台和特定于应用程序的适用性以及独立的优化。我们为三个平台提供这些内核的参考实现：共享内存多孔，分布式内存系统和GPU，并评估它们的可扩展性。
An interesting class of irregular algorithms is tree traversal algorithms, which repeatedly traverse various trees to perform efficient computations. Tree traversal algorithms form the algorithmic kernels in an important set of applications in scientific computing, computer graphics, bioinformatics, and data mining, etc. There has been increasing interest in understanding tree traversal algorithms, optimizing them, and applying them in a wide variety of settings. Crucially, while there are many possible optimizations for tree traversal algorithms, which optimizations apply to which algorithms is dependent on algorithmic characteristics. In this work, we present a suite of tree traversal kernels, drawn from diverse domains, called Treelogy, to explore the connection between tree traversal algorithms and state-of-the-art optimizations. We characterize these algorithms by developing an ontology based on their structural properties. The attributes extracted through our ontology, for a given traversal kernel, can aid in quick analysis of the suitability of platform- and application-specific as well as independent optimizations. We provide reference implementations of these kernels for three platforms: shared memory multicores, distributed memory systems, and GPUs, and evaluate their scalability.