Finding Free Schedules for Parameterized Loops with Affine Dependences Represented with a Single Dependence Relation

Abstract:- An approach, permitting us to build free schedules for affine loops with affine dependences represented with a single dependence relation, is described. The iterations of each time under the free schedule can be executed as soon as their operands are available. This allows us to extract maximal fine-grained loop parallelism. The approach requires an exact dependence analysis. To describe the approach and carry out experiments, the dependence analysis by Pugh and Wonnacott has been chosen where dependences are represented in the form of tuple relations. The approach can be applied to both non-parameterized and parameterized loops. Problems to be resolved in the future to utilize the entire power of the presented technique are discussed