PACT '97

Optimally Synchronizing DOACROSS Loops on Shared Memory Multiprocessors

by Ramakrishnan Rajamony and Alan Cox, in the proceedings of the 1997 International Conference on Parallel Architectures and Compilation Techniques (PACT'97), November 1997.

Abstract

We present two algorithms to minimize the amount of synchronization added when parallelizing a loop with loop-carried dependences. In contrast to existing schemes, our algorithms add lesser synchronization, while preserving the parallelism that can be extracted from the loop. Our first algorithm uses an interval graph representation of the dependence ``overlap'' to find a synchronization placement in time almost linear in the number of dependences. Although this solution may be suboptimal, it is still better than that obtained using existing methods, which first eliminate redundant dependences and then synchronize the remaining ones. Determining the optimal synchronization is an NP-complete problem. Our second algorithm therefore uses integer programming to determine the optimal solution. We first use a polynomial-time algorithm to find a minimal search space that must contain the optimal solution. Then, we formulate the problem of choosing the minimal synchronization from the search space as a set-cover problem, and solve it exactly using 0-1 integer programming. We show the performance impact of our algorithms by synchronizing a set of synthetic loops on an 8-processor Convex Exemplar. The greedily synchronized loops ran between 7% and 22% faster than those synchronized by the best existing algorithm. Relative to the same base, the optimally synchronized loops ran between 10% and 22% faster.

Compressed postscript (88 KBytes)
[This version fixes a couple of typos in page 218 of the conference proceedings]

Here are the (color) slides from the presentation I gave at the conference.
Compressed postscript (61 KBytes)

Copyright 1997 IEEE.
Published in the Proceedings of PACT'97, November 11-15, 1997 in San Francisco, California. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works, must be obtained from the IEEE. Contact: Manager, Copyrights and Permissions, IEEE Service Center, 445 Hoes Lane, P.O. Box 1331, Piscataway, NJ 08855-1331, USA. Telephone: +Intl (908) 562-3966.

<- Back to publications page
Ramakrishnan Rajamony
E-mail: (MyLastName) at us.ibm.com [please do not e-mail me at cs.rice.edu]
Last updated at 15:56 CST on Thursday, January 08, 1998