General loop fusion technique for nested loops considering timing and code size

Meilin Liu, Qingfeng Zhuge, Zili Shao, Edwin H.M. Sha

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

9 Citations (Scopus)

Abstract

Loop fusion is commonly used to improve the instruction-level parallelism of loops for high-performance embedded computing systems. Loop fusion, however, is not always directly applicable because the fusion prevention dependencies may exist among loops. Most of the existing techniques still have limitations in fully exploiting the advantages of loop fusion, In this paper, we present a general loop fusion technique for loops or nested loops based on the loop dependency graph model, retiming, and multi-dimensional retiming concepts. We show that any "J+K" model loop can be legally fused using our legalizing fusion technique. Polynomial-time algorithms are developed to solve the loop fusion problem for "J+K" model loops considering both timing and code size of the final code. Our technique produces the final code and calculates the resultant code size directly from the retiming values. The experimental results show that our loop fusion technique always significantly reduces the schedule length.
Original languageEnglish
Title of host publicationCASES 2004
Subtitle of host publicationInternational Conference on Compilers, Architecture, and Synthesis for Embedded Systems
Pages190-201
Number of pages12
Publication statusPublished - 1 Dec 2004
Externally publishedYes
EventCASES 2004: International Conference on Compilers, Architecture, and Synthesis for Embedded Systems - Washington, DC, United States
Duration: 22 Sep 200425 Sep 2004

Conference

ConferenceCASES 2004: International Conference on Compilers, Architecture, and Synthesis for Embedded Systems
CountryUnited States
CityWashington, DC
Period22/09/0425/09/04

Keywords

  • Code size
  • Embedded DSP
  • Loop Fusion
  • Retiming
  • Scheduling

ASJC Scopus subject areas

  • Engineering(all)

Cite this