Back to Search
Start Over
Maximize Parallelism Minimize Overhead for Nested Loops via Loop Striping
- Source :
- The Journal of VLSI Signal Processing Systems for Signal, Image, and Video Technology. 47:153-167
- Publication Year :
- 2007
- Publisher :
- Springer Science and Business Media LLC, 2007.
-
Abstract
- 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 all iterations in a stripe 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.
- Subjects :
- For loop
Loop counter
Recursion
Computer science
Loop inversion
Data parallelism
Loop fusion
Task parallelism
Parallel computing
Loop tiling
Scalable parallelism
Loop splitting
Loop fission
Software pipelining
Signal Processing
Loop nest optimization
Loop interchange
Electrical and Electronic Engineering
Instruction-level parallelism
Nested loop join
Information Systems
Subjects
Details
- ISSN :
- 1573109X and 09225773
- Volume :
- 47
- Database :
- OpenAIRE
- Journal :
- The Journal of VLSI Signal Processing Systems for Signal, Image, and Video Technology
- Accession number :
- edsair.doi...........6782539b32ed77245b5e2b3eefe7bc91
- Full Text :
- https://doi.org/10.1007/s11265-006-0034-5