Towards an automated tupling strategy
Towards an automated tupling strategy
复制标题
走向自动化元组策略
DOI：
10.1145/154630.154643
复制
发表时间：
1993
影响因子：
--
通讯作者：
W. Chin
中科院分区：
文献类型：
--
作者：
W. Chin
裁剪转换策略可用于通过组合递归调用并消除针对一类程序的冗余呼叫来将循环合并在一起。这种转换策略的巧妙（且困难）的步骤是找到一个适当的呼叫元组，称为Eureka Tuple，这将使每组呼叫都可以从其先前的集合中递归计算。在许多情况下，这种转换会产生超级线性加速。
在本文中，我们提出了一种分析方法，该方法可以找到尤里卡（Eureka）的各种功能程序。我们的工作扩展了许多过去使用函数依赖图的过去技术来分析冗余模式。我们的主要贡献是使用基于递归参数的适当呼叫订购来系统地搜索依赖图中的尤里卡元组。它们使我们能够构造元素的序列，称为元组的连续序列，从而在序列中存在匹配的一对元组对应于合适的尤里卡元组。
还将提出使用树而不是序列的基本分析方法的扩展。基本和扩展分析方法将显示适用于广泛的程序。可以保证通过对搜索进行边界或对适用程序类应用适当的限制来终止它们。后一种方法产生了一个安全的自动化程序，用于裁剪转换。
The tupling transformation strategy can be used to merge loops together by combining recursive calls and also to eliminate redundant calls for a class of programs. The clever (and difficult) step of this transformation strategy is to find an appropriate tuple of calls, called the eureka tuple, which would allow each set of calls to be computed recursively from its previous set. In many cases, this transformation can produce super-linear speedup.
In this paper, we present an analysis method which could find eureka tuples for a wide range of functional programs. Our work extends that of a number of past techniques which have used dependency graphs of function calls for analysing redundancy patterns. Our main contribution is the use of appropriate call orderings based on recursion parameters to systematically search for eureka tuples in dependency graphs. They allow us to construct sequences of tuples, called the continuous sequences of tuples, whereby the existence of a matched pair of tuples in the sequence corresponds to a suitable eureka tuple.
An extension of the basic analysis method which uses trees, instead of sequences, of tuples will also be presented. The basic and extended analysis methods will be shown to be applicable to a wide range of programs. They can be guaranteed to terminate by either bounding the search or by applying suitable restrictions on the class of applicable programs. The latter approach yields a safe automated procedure for tupling transformation.