Unroll-and-jam for imperfectly-nested loops in DSP applications
Yonghong Song, Yuan Lin · 2000
Unroll-and-jam, combined with scalar replacement, is a wellknown technique to balance memory operations and computations within a loop body, hence improving instructionlevel parallelism.Previous work on unroll-and-jam applies to perfectly-nested loops only.However, most loop nests in DSP applications are imperfectly-nested.In this paper, we p r e s e n t a framework to unroll-and-jam imperfectlynested loops.We d e v elop a graph-based algorithm to determine the maximum legal unroll factor.A simple heuristic is applied to compute a pro table unroll factor.Compared with a straightforward approach, which applies strip-mining, loop distribution and loop unrolling in order, our scheme is more eÆcient and allows a potentially larger legal unroll factor.To study the eectiveness of our technique, we hand-applied unroll-and-jam and scalar replacement t o s e veral typical DSP benchmarks.The results demonstrate the importance of unroll-and-jamming imperfectly-nested loops in performance improvement.Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page.To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific