Transforming loops to recursion for multi-level memory hierarchies

Qing Yi, Vikram Adve, Ken Kennedy

Research output: Contribution to journalArticlepeer-review


Recently, there have been several experimental and theoretical results showing significant performance benefits of recursive algorithms on both multi-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.

Original languageEnglish (US)
Pages (from-to)169-181
Number of pages13
JournalSIGPLAN Notices (ACM Special Interest Group on Programming Languages)
Issue number5
StatePublished - May 2000

ASJC Scopus subject areas

  • Software
  • Computer Graphics and Computer-Aided Design


Dive into the research topics of 'Transforming loops to recursion for multi-level memory hierarchies'. Together they form a unique fingerprint.

Cite this