Iterational retiming: Maximize iteration-level parallelism for nested loops

Chun Xue, Zili Shao, Meilin Liu, Edwin H.M. Sha

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

5 Citations (Scopus)

Abstract

Nested loops are the most critical sections in many scientific and Digital Signal Processing (DSP) applications. It is important to study effective and efficient transformation techniques to increase parallelism for nested loops. In this paper, we propose a novel technique, iterational retiming, that can satisfy any given timing constraint by achieving full parallelism for iterations in a partition. Theorems and efficient algorithms are proposed for iterational retiming. The experimental results show that iterational retiming is a promising technique for parallel embedded systems. It can achieve 87% improvement over software pipelining and 88% improvement over loop unfolding on average.
Original languageEnglish
Title of host publicationCODES+ISSS 2005 - International Conference on Hardware/Software Codesign and Systems Synthesis
Pages309-314
Number of pages6
Publication statusPublished - 11 Nov 2005
Externally publishedYes
Event3rd IEEE/ACM/IFIP International Conference on Hardware/Software Codesign and Systems Synthesis CODES+ISSS 2005 - Jersey City, NJ, United States
Duration: 18 Sep 200521 Sep 2005

Conference

Conference3rd IEEE/ACM/IFIP International Conference on Hardware/Software Codesign and Systems Synthesis CODES+ISSS 2005
CountryUnited States
CityJersey City, NJ
Period18/09/0521/09/05

Keywords

  • Nested Loops
  • Optimization
  • Partition
  • Retiming

ASJC Scopus subject areas

  • Engineering(all)

Cite this