Loop striping : maximizing parallelism for nested loops

C. Xue, Zili Shao, M.L. Liu, M.L. Qiu, E.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 publicationLecture notes in computer science (including subseries Lecture notes in artificial intelligence and lecture notes in bioinformatics)
PublisherSpringer
Pages405-414
Number of pages10
ISBN (Electronic)9783540366812
ISBN (Print)9783540366799
DOIs
Publication statusPublished - 2006
EventInternational Conference on Embedded and Ubiquitous Computing [EUC] -
Duration: 1 Jan 2006 → …

Conference

ConferenceInternational Conference on Embedded and Ubiquitous Computing [EUC]
Period1/01/06 → …

ASJC Scopus subject areas

  • Computer Science(all)
  • Theoretical Computer Science

Cite this