Sound, fine-grained traversal fusion for heterogeneous trees
Sound, fine-grained traversal fusion for heterogeneous trees
复制标题
针对异构树的健全、细粒度的遍历融合
DOI：
10.1145/3314221.3314626
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Kulkarni, Milind
中科院分区：
文献类型：
--
作者：
Sakka, Laith;Sundararajah, Kirshanthan;Newton, Ryan R.;Kulkarni, Milind
许多领域的应用都是基于对树结构的一系列遍历，而将这些遍历融合在一起以减少遍历树的总次数是一种常见的、重要的优化技术。在编译器和渲染树等应用程序中，这些树是异构的：树的不同节点具有不同的类型。不幸的是，以前的工作融合遍历下降福尔斯短在不同的方式：他们不处理异质性;他们需要使用特定领域的语言来表达应用程序;他们依赖于程序员断言融合遍历是安全的，没有任何健全的保证;或者他们只能执行粗粒度融合，导致错过融合的机会。本文针对这些缺点，建立一个框架，融合遍历异构树，是自动的，声音，细粒度。我们通过几个案例研究表明，我们的方法能够让程序员编写简单，直观的遍历，然后自动融合它们，以大幅提高性能。
Applications in many domains are based on a series of traversals of tree structures, andfusingthese traversals together to reduce the total number of passes over the tree is a common, important optimization technique. In applications such as compilers and render trees, these trees are heterogeneous: different nodes of the tree have different types. Unfortunately, prior work for fusing traversals falls short in different ways: they do not handle heterogeneity; they require using domain-specific languages to express an application; they rely on the programmer to aver that fusing traversals is safe, without any soundness guarantee; or they can only perform coarse-grain fusion, leading to missed fusion opportunities. This paper addresses these shortcomings to build a framework for fusing traversals of heterogeneous trees that is automatic, sound, and fine-grained. We show across several case studies that our approach is able to allow programmers to write simple, intuitive traversals, and then automatically fuse them to substantially improve performance.
登录
查看更多内容
TreeFuser：分析和融合一般递归树遍历的框架
影响因子：
--
作者：
Laith Sakka;Kirshanthan Sundararajah;Milind Kulkarni
通讯作者：
Milind Kulkarni
Treelogy：树遍历的基准套件
DOI：
10.1109/ispass.2017.7975294
发表时间：
2017
期刊：
2017 IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS)
影响因子：
--
作者：
Nikhil Hegde;Jianqiao Liu;Kirshanthan Sundararajah;Milind Kulkarni
通讯作者：
Milind Kulkarni
通过融合和元组推导模块化程序
DOI：
10.1007/3-540-45821-2_9
发表时间：
2002
期刊：
J. Comput. Syst. Sci.
影响因子：
--
作者：
W. Chin;Zhenjiang Hu
通讯作者：
Zhenjiang Hu
扩展的自顶向下树传感器的组合
DOI：
10.1016/j.ic.2008.03.019
发表时间：
2008
期刊：
Inf. Comput.
影响因子：
--
作者：
A. Maletti
通讯作者：
A. Maletti
Miniphases：使用模块化和高效的树转换进行编译
DOI：
10.1145/3062341.3062346
发表时间：
2017
期刊：
Proceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation
影响因子：
--
作者：
Dmitry Petrashko;Ondřej Lhoták;Martin Odersky
通讯作者：
Martin Odersky