A linear-time algorithm for optimal barrier placement

ABSTRACT

We want to perform compile-time analysis of an SPMD program and place barriers in it to synchronize it correctly, minimizing the runtime cost of the synchronization. This is the barrier minimization problem. No full solution to the problem has been given previously.Here we model the problem with a new combinatorial structure, a nested family of sets of circular intervals. We show that barrier minimization is equivalent to finding a hierarchy of minimum cardinality point sets that cut all intervals. For a single loop, modeled as a simple family of circular intervals, a linear-time algorithm is known. We extend this result, finding a linear-time solution for nested circular interval families. This result solves the barrier minimization problem for general nested loops.

REFERENCES

• 1: A. Agarwal , M. Cherian, Adaptive backoff synchronization techniques, Proceedings of the 16th annual international symposium on Computer architecture, p.396-406, April 1989, Jerusalem, Israel
• 2: Alexander Aiken , David Gay, Barrier inference, Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.342-354, January 19-21, 1998, San Diego, California, United States [doi>10.1145/268946.268974]
• 3: Co-Array Fortran. http://www.co-array.org/.
• 4: A. Darte and R. Schreiber. Nested circular intervals: A model for barrier placement in SPMD codes with nested loops. Technical Report RR2004-57, LIP, ENS-Lyon, Dec. 2004. http://www.ens-lyon.fr/LIP/Pub/Rapports/RR/RR2004/RR2004-57.pdf.
• 5: Philip J. Hatcher , Michael J. Quinn, Data-parallel programming on MIMD computers, MIT Press, Cambridge, MA, 1992
• 6: Wen-Lian Hsu , Kuo-Hui Tsai, Linear time algorithms on circular-arc graphs, Information Processing Letters, v.40 n.3, p.123-129, Nov. 1991 [doi>10.1016/0020-0190(91)90165-E]
• 7: John M. Mellor-Crummey , Michael L. Scott, Algorithms for scalable synchronization on shared-memory multiprocessors, ACM Transactions on Computer Systems (TOCS), v.9 n.1, p.21-65, Feb. 1991 [doi>10.1145/103727.103729]
• 8: Michael O'Boyle , Elena Stöhr, Compile Time Barrier Synchronization Minimization, IEEE Transactions on Parallel and Distributed Systems, v.13 n.6, p.529-543, June 2002 [doi>10.1109/TPDS.2002.1011394]
• 9: Chau-Wen Tseng, Compiler optimizations for eliminating barrier synchronization, Proceedings of the fifth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.144-155, July 19-21, 1995, Santa Barbara, California, United States
• 10: Unified Parallel C. http://upc.gwu.edu/.
• 11: Michael Joseph Wolfe , Carter Shanklin , Leda Ortega, High Performance Compilers for Parallel Computing, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 12: K. Yelick, L. Semenzato, G. Pike, C. Miyamoto, B. Liblit, A. Krishnamurthy, P. Hilfinger, S. Graham, D. Gay, P. Colella, and A. Aiken. Titanium: A high-performance Java dialect. Concurrency: Practice and Experience, 10(11-13):825--836, Sept-Nov 1998.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Concurrent programming structures

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers; Optimization

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

General Terms:
Algorithms, Languages, Theory

Keywords:
SPMD code, barrier synchronization, circular arc graph, nested circular interval graph, nested loops