Loop striping: Maximize parallelism for nested loops

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

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

Abstract

The majority of scientific and Digital Signal Processing (DSP) applications are recursive or iterative. Transformation techniques are generally applied to increase parallelism for these nested loops. Most of the existing loop transformation techniques either can not achieve maximum parallelism, or can achieve maximum parallelism but with complicated loop bounds and loop indexes calculations. This paper proposes a new technique, loop striping, that can maximize parallelism while maintaining the original row-wise execution sequence with minimum overhead. Loop striping groups iterations into stripes, where a stripe is a group of iterations in which all iterations are independent and can be executed in parallel. Theorems and efficient algorithms are proposed for loop striping transformations. The experimental results show that loop striping always achieves better iteration period than software pipelining and loop unfolding, improving average iteration period by 50% and 54% respectively.
Original languageEnglish
Title of host publicationEmbedded and Ubiquitous Computing - International Conference, EUC 2006, Proceedings
PublisherSpringer Verlag
Pages405-414
Number of pages10
ISBN (Print)3540366792, 9783540366799
Publication statusPublished - 1 Jan 2006
EventInternational Conference on Embedded and Ubiquitous Computing, EUC 2006 - Seoul, Korea, Republic of
Duration: 1 Aug 20064 Aug 2006

Publication series

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

Conference

ConferenceInternational Conference on Embedded and Ubiquitous Computing, EUC 2006
Country/TerritoryKorea, Republic of
CitySeoul
Period1/08/064/08/06

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this