Transforming loops to recursion for multi-level memory hierarchies
Transforming loops to recursion for multi-level memory hierarchies
复制标题
DOI：
10.1145/349299.349323
复制
发表时间：
2000-05
期刊：
影响因子：
--
通讯作者：
Qing Yi;Vikram S. Adve;K. Kennedy
中科院分区：
文献类型：
--
作者：
Qing Yi;Vikram S. Adve;K. Kennedy
最近，已经有几个实验和理论结果，显示了递归算法在两种级记忆层次结构和共享内存系统上的显着性能益处。特别是，这种算法具有在许多不同级别上同时阻止的封闭算法的数据重用特征。但是，大多数现有的应用程序都是使用普通循环编写的。我们提出了一种新的编译器转换，可自动将循环巢转换为递归形式。我们表明该算法是快速有效的，可以用任意嵌套和控制流动来处理循环巢。即使在具有两个级别的高速缓存层次结构的当前系统上，转换也可以对几个线性代数代码进行实质性改进。作为这项工作的副作用，我们还开发了一种改进的算法，用于传递依赖性分析（一种在递归转换和其他循环转换中使用的强大技术），该算法比实践中最好的算法要快得多。
Recently, there have been several experimental and theoretical results showing significant performance benefits of recursive algorithms on bothmulti-level memory hierarchies and on shared-memory systems. In particular, such algorithms have the data reuse characteristics of a blocked algorithm that is simultaneously blocked at many different levels. Most existing applications, however, are written using ordinary loops. We present a new compiler transformation that can be used to convert loop nests into recursive form automatically. We show that the algorithm is fast and effective, handling loop nests with arbitrary nesting and control flow. The transformation achieves substantial performance improvements for several linear algebra codes even on a current system with a two level cache hierarchy. As a side-effect of this work, we also develop an improved algorithm for transitive dependence analysis (a powerful technique used in the recursion transformation and other loop transformations)that is much faster than the best previously known algorithm in practice.