Exploitation of parallelism to nested loops with dependence cycles |
| |
Authors: | Weng-Long Chih-Ping Michael |
| |
Affiliation: | aDepartment of Information Management, Southern Taiwan University of Technology, Tainan County 710, Taiwan, ROC bDepartment of Computer Science and Information Engineering, National Cheng Kung University, Tainan City 701, Taiwan, ROC |
| |
Abstract: | In this paper, we analyze the recurrences from the breakability of the dependence links formed in general multi-statements in a nested loop. The major findings include: (1) A sin k variable renaming technique, which can reposition an undesired anti-dependence and/or output-dependence link, is capable of breaking an anti-dependence and/or output-dependence link. (2) For recurrences connected by only true dependences, a dynamic dependence concept and the derived technique are powerful in terms of parallelism exploitation. (3) By the employment of global dependence testing, link-breaking strategy, Tarjan’s depth-first search algorithm, and a topological sorting, an algorithm for resolving a general multi-statement recurrence in a nested loop is proposed. Experiments with benchmark cited from Vector loops showed that among 134 subroutines tested, 3 had their parallelism exploitation amended by our proposed method. That is, our offered algorithm increased the rate of parallelism exploitation of Vector loops by approximately 2.24%. |
| |
Keywords: | Parallelizing compilers Vectorizing compilers Loop optimization Data dependence analysis Dependence cycle Parallelism exploitation |
本文献已被 ScienceDirect 等数据库收录! |
|