Back to Search
Start Over
Exploitation of parallelism to nested loops with dependence cycles
- Source :
-
Journal of Systems Architecture . Dec2004, Vol. 50 Issue 12, p729-742. 14p. - Publication Year :
- 2004
-
Abstract
- 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 sink 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%. [Copyright &y& Elsevier]
- Subjects :
- *PARALLEL processing
*ALGORITHMS
*COMPUTER science
Subjects
Details
- Language :
- English
- ISSN :
- 13837621
- Volume :
- 50
- Issue :
- 12
- Database :
- Academic Search Index
- Journal :
- Journal of Systems Architecture
- Publication Type :
- Academic Journal
- Accession number :
- 15448370
- Full Text :
- https://doi.org/10.1016/j.sysarc.2004.06.001