Loop distribution and fusion with timing and code size optimization for embedded DSPs

Meilin Liu, Qingfeng Zhuge, Zili Shao, Chun Xue, Meikang Qiu, Edwin H.M. Sha

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

4 Citations (Scopus)

Abstract

Loop distribution and loop fusion are two effective loop transformation techniques to optimize the execution of the programs in DSP applications. In this paper, we propose a new technique combining loop distribution with direct loop fusion, which will improve the timing performance without jeopardizing the code size. We first develop the loop distribution theorems that state the legality conditions of loop distribution for multi-level nested loops. We show that if the summation of the edge weights of the dependence cycle satisfies a certain condition, then the statements involved in the dependence cycle can be distributed; otherwise, they should be put in the same loop after loop distribution. Then, we propose the technique of maximum loop distribution with direct loop fusion. The experimental results show that the execution time of the transformed loops by our technique is reduced 21.0% on average compared to the original loops and the code size of the transformed loops is reduced 7.0% on average compared to the original loops.
Original languageEnglish
Title of host publicationEmbedded and Ubiquitous Computing - International Conference EUC 2005, Proceedings
Pages121-130
Number of pages10
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
CountryJapan
CityNagasaki
Period6/12/059/12/05

Keywords

  • Code Size
  • Embedded DSP
  • Loop Distribution
  • Loop Fusion
  • Scheduling

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this