论文标题
超级线性加速的重复递归在范围内
Repeated Recursion Unfolding for Super-Linear Speedup within Bounds
论文作者
论文摘要
重复的递归展开是一种新的方法，它反复展开递归，并简化了递归，同时保持所有展开的规则。每次展开的递归步骤数量翻了一番。这将递归规则申请的数量减少到其对数中，而牺牲了对对数的未展开规则的数量。效率至关重要地取决于不展开规则内的简化量。在最佳情况下，我们证明了超级线性加速定理，即速度超过恒定因素。我们的优化可以降低程序的时间复杂性类别。在本文中，超级线性加速位于范围内：它可以在递归步骤的数量上保持任意但选择的上限。我们还通过重复递归的原型实现进行了第一个结果报告。一个简单的程序转换完全将递归移至所选界限。实际的运行时改进很快达到了几个数量级。
Repeated recursion unfolding is a new approach that repeatedly unfolds a recursion with itself and simplifies it while keeping all unfolded rules. Each unfolding doubles the number of recursive steps covered. This reduces the number of recursive rule applications to its logarithm at the expense of introducing a logarithmic number of unfolded rules to the program. Efficiency crucially depends on the amount of simplification inside the unfolded rules. We prove a super-linear speedup theorem in the best case, i.e. speedup by more than a constant factor. Our optimization can lower the time complexity class of a program. In this paper, the super-linear speedup is within bounds: it holds up to an arbitrary but chosen upper bound on the number of recursive steps. We also report on the first results with a prototype implementation of repeated recursion unfolding. A simple program transformation completely removes recursion up to the chosen bound. The actual runtime improvement quickly reaches several orders of magnitude.
