An analysis of recurrence relations in Fortran Do-loops for vector processing
Chih‐Ping Chu, Doris L. Carver · 2002
Analyzes the recurrences from the breakability of the dependence links. The major findings include: (1) The node splitting algorithm cannot be used directly to break an essential antidependence link, of which the source variable that results in antidependence is itself the sink variable of another true dependence. (2) A sink variable renaming technique, which can reposition an undesired antidependence and/or output dependence link, is capable of breaking an antidependence and/or output-dependence link. (3) For recurrences connected by only true dependences, a dynamic dependence concept and the derived technique are powerful in terms of parallelism exploitation. (4) 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 multistatement recurrence is proposed.>