On reducing synchronization costs in nested DOACROSS loops

The iteration space dependence graph (ISDG) of a loop captures the synchronization requirements of the execution of the loop on parallel machines. Some of the edges in an ISDG may correspond to redundant synchronization statements. We investigate the removal of such edges in the ISDG of a triply nested loop with constant dependences. We identify a class of triply nested loops with the property of uniform redundancy. In the case of a general triply nested loop, we characterize points in the iteration space at which a dependence is redundant