Using transitive closure and transitive reduction to extract coarse-grained parallelism in program loops

摘要

A technique for extracting coarse-grained parallelism available in loops is presented. It is based on splitting a set of dependence relations into rwo sets. The first one is to be used for generating code scanning slices while the second one permits us to insert send and receive functions to synchronize the slices execution. The paper presents a way demonstrating how to remove redundant synchronization in generated code by means of the transitive reduction operation. Results of experiments-how many synchronization points can be removed, speed-up and efficiency of examined parallel loops are discussed.