Next: Other Optimizations
Up: Barrier Minimization
Previous: Implementation of dependence
The barrier implementation of the previous subsection can be summarized
as follows:
- Insert communication statements at the sink of each flow dependence
arc
- Insert calls to the request polling function at regular intervals
in the code
- Insert a (responsive) barrier somewhere between the source and sink
of each dependence arc of the synchronization graph
Since the same barrier can be used to enforce more than one dependence
arcs, it is desirable to find the minimum number of barriers needed
to implement a synchronization graph.
This problem can be solved in polynomial
time[Gav72]; a simple greedy algorithm devised by Quinn
and Hatcher[HQ91] extracts a minimal set of
barriers from a set of dependence arcs, which can be viewed as
a synchronization graph. At each step the algorithm selects, of
all arcs, the dependence arc whose head (sink) points to the earliest
point in the program. A barrier is inserted before this point
and the arc is removed from the graph.
Additionally, all arcs whose tail (source) is at a point before and the
head at a point after the barrier are removed from the
graph. The algorithm terminates when the
graph contains no more arcs.
The algorithm described above can be used for a single par statement.
If the par statement is tightly nested in sequential loops,
additional initial steps
must be taken. A synchronization barrier is inserted before the first assignment
of the par statement. This automatically enforces all dependences that
are carried across the iterations of the enclosing sequential loops.
The corresponding dependence arcs are subsequently removed.
The remaining arcs can be implemented using Hatcher and Quinn's algorithm.
Next: Other Optimizations
Up: Barrier Minimization
Previous: Implementation of dependence
Andy Kahn
Wed Jun 25 20:28:02 PDT 1997