Generating Self-Scheduling Code for Nonloop Parallelism
Carl J. Beckmann · Journal of Parallel and Distributed Computing · 1996
This paper examines nonloop parallelism at both fine and coarse levels of granularity in ordinary Fortran programs. Dynamic self-scheduling algorithms are developed for acyclic task graphs containing both data- and control-dependences, along with the compiler optimizations necessary to make these practical. It is shown that practical algorithms based on atomicfetch-and-φ operations to a single shared variable, similar in spirit to dynamic loop dispatching algorithms, are possible for acyclic task graphs. Further, they generalize easily todoacrossloops. A key requirement is the use of compiler algorithms to optimize the task graphs. We show that although exact redundant dependence removal is theoretically NP-hard, the practical complexity on actual codes is small. Performance-related measurements are given to characterize the algorithms on a set of standard benchmark codes.