Redundant synchronization elimination for DOACROSS loops

Cross-iterations data dependences in DOACROSS loops require explicit data s ynchronizations to enforce them. However, the composite effect of some data synchronizations may cover the other dependences and make the enforcement of those covered dependences redundant. In this paper, we propose an effici ent and general algorithm to identify redundant synchronizations in multipl y nested DOACROSS loops which may have multiple statements and loop-exit co ntrol branches. Eliminating redundant synchronizations in DOACROSS loops al lows more efficient execution of such loops. We also address the issues of enforcing data synchronizations in iterations near the boundary of the iter ation space. Because some dependences may not exist in those boundary itera tions, it adds complexity in determining the redundant synchronizations for those boundary iterations. The necessary and sufficient condition under wh ich the synchronization is uniformly redundant is also studied. These resul ts allow a parallelizing compiler to generate efficient data synchronizatio n instructions for DOACROSS loops.