Published Articles >> Table of Contents >> Abstract

1997 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '97)   p. 376
A method for estimating optimal unrolling times for nested loops
A. Koseki, Sch. of Sci. & Eng., Waseda Univ., Tokyo, Japan
H. Komastu, Sch. of Sci. & Eng., Waseda Univ., Tokyo, Japan
Y. Fukazawa, Sch. of Sci. & Eng., Waseda Univ., Tokyo, Japan

Full Article Text:

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ISPAN.1997.645123
Send link to a friend

Abstract
Loop unrolling is one of the most promising parallelization techniques, because the nature of programs causes most of the processing time to be spent in their loops. Unrolling not only the innermost loop but also outer loops greatly expands the scope for reusing data and parallelizing instructions. Nested-loop unrolling is therefore a very effective way of obtaining a higher degree of parallelism. However, we need a method for measuring the efficiency of loop unrolling that takes account of both the reuse of data and the parallelism between instructions. This paper describes a heuristic algorithm for deciding the number of times and the directions in which loops should be unrolled, through the use of information such as dependence, reuse, and machine resources. Our method is evaluated by applying benchmark tests.
Back to Top Additional Information
Index Terms- heuristic programming; nested loops; parallelization; loop unrolling; reuse of data; parallelism; heuristic algorithm; benchmark tests Citation:  A. Koseki, H. Komastu, Y. Fukazawa, "A method for estimating optimal unrolling times for nested loops," ispan, p. 376,  1997 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '97),  1997