Optimizing nested loops with iterational and instructional retiming

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

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

2 Citations (Scopus)

Abstract

Embedded systems have strict timing and code size requirements. Retiming is one of the most important optimization techniques to improve the execution time of loops by increasing the parallelism among successive loop iterations. Traditionally, retiming, has been applied at instruction level to reduce cycle period for single loops. While multi-dimensional (MD) retiming can explore the outer loop parallelism, it introduces large overheads in loop index generation and code size due to loop transformation. In this paper, we propose a novel approach, that combines iterational retiming with instructional retiming to satisfy any given timing constraint by achieving full parallelism for iterations in a partition with minimal code size. The experimental results show that combining iterational retiming and instructional retiming, we can achieve 37% code size reduction comparing to applying iteration retiming alone.
Original languageEnglish
Title of host publicationEmbedded and Ubiquitous Computing - International Conference EUC 2005, Proceedings
Pages164-173
Number of pages10
DOIs
Publication statusPublished - 1 Dec 2005
EventInternational Conference on Embedded and Ubiquitous Computing, EUC 2005 - Nagasaki, Japan
Duration: 6 Dec 20059 Dec 2005

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume3824 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceInternational Conference on Embedded and Ubiquitous Computing, EUC 2005
Country/TerritoryJapan
CityNagasaki
Period6/12/059/12/05

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this