Free scheduling for statement instances of parameterized arbitrarily nested affine loops

摘要

An approach is presented permitting us to build free scheduling for statement instances of affine loops. Under the free schedule, loop statement instances are executed as soon as their operands are available. This allows us to extract maximal fine-grained loop parallelism and minimize the number of synchronization events. The approach is based on calculating the power k of a relation representing exactly all dependences in a loop. In general, such a relation is a union of simpler relations. When there are troubles with calculating free scheduling due to the large number of simpler dependence relations, another technique is discussed allowing for extracting free scheduling in an iteration subspace defined by indices of inner nests of this loop. We demonstrate that if we are able to calculate the power k of a dependence relation describing all dependences in the loop, then we are able also to produce free scheduling. Experimental results exposing the effectiveness, efficiency, and time complexity of the algorithms are outlined. Problems to be resolved in the future to utilize the entire power of the presented techniques are discussed.