Automatic parallelization of divide and conquer algorithms

ABSTRACT

Divide and conquer algorithms are a good match for modern parallel machines: they tend to have large amounts of inherent parallelism and they work well with caches and deep memory hierarchies. But these algorithms pose challenging problems for parallelizing compilers. They are usually coded as recursive procedures and often use pointers into dynamically allocated memory blocks and pointer arithmetic. All of these features are incompatible with the analysis algorithms in traditional parallelizing compilers.This paper presents the design and implementation of a compiler that is designed to parallelize divide and conquer algorithms whose subproblems access disjoint regions of dynamically allocated arrays. The foundation of the compiler is a flow-sensitive, context-sensitive, and interprocedural pointer analysis algorithm. A range of symbolic analysis algorithms build on the pointer analysis information to extract symbolic bounds for the memory regions accessed by (potentially recursive) procedures that use pointers and pointer arithmetic. The symbolic bounds information allows the compiler to find procedure calls that can execute in parallel without violating the data dependences. The compiler generates code that executes these calls in parallel. We have used the compiler to parallelize several programs that use divide and conquer algorithms. Our results show that the programs perform well and exhibit good speedup.

REFERENCES

• 1: S. Amarasinghe, J. Anderson, M. Lain, and C. Tseng. The SUIF compiler for scalable parallel machines. In Proceedings of the Eighth SIAM Conference on Parallel Processing for Scientific Computing, February 1995.
• 2: William Blume , Rudolf Eigenmann, Symbolic range propagation, Proceedings of the 9th International Symposium on Parallel Processing, p.357-363, April 25-28, 1995
• 3: Robert D. Blumofe , Christopher F. Joerg , Bradley C. Kuszmaul , Charles E. Leiserson , Keith H. Randall , Yuli Zhou, Cilk: an efficient multithreaded runtime system, Proceedings of the fifth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.207-216, July 19-21, 1995, Santa Barbara, California, United States
• 4: David R. Chase , Mark Wegman , F. Kenneth Zadeck, Analysis of pointers and structures, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.296-310, June 1990, White Plains, New York, United States
• 5: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 6: Maryam Emami , Rakesh Ghiya , Laurie J. Hendren, Context-sensitive interprocedural points-to analysis in the presence of function pointers, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.242-256, June 20-24, 1994, Orlando, Florida, United States
• 7: Jeremy D. Frens , David S. Wise, Auto-blocking matrix-multiplication or tracking BLAS3 performance from source code, Proceedings of the sixth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.206-216, June 18-21, 1997, Las Vegas, Nevada, United States
• 8: Rakesh Ghiya , Laurie J. Hendren, Is it a tree, a DAG, or a cyclic graph? A shape analysis for heap-directed pointers in C, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.1-15, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237724]
• 9: V. Guarna. A technique for analyzing pointer and structure references in parallel restructuring compilers. Proceedings of the 1988 international Conference on Parallel Processing, August 1988.
• 10: Mohammad R. Haghighat , Constantine D. Polychronopoulos, Symbolic Analysis: A Basis for Parallelization, Optimization, and Scheduling of Programs, Proceedings of the 6th International Workshop on Languages and Compilers for Parallel Computing, p.567-585, August 12-14, 1993
• 11: Mary H. Hall , Saman P. Amarasinghe , Brian R. Murphy , Shih-Wei Liao , Monica S. Lam, Detecting coarse-grain parallelism using an interprocedural parallelizing compiler, Proceedings of the 1995 ACM/IEEE conference on Supercomputing (CDROM), p.49-es, December 04-08, 1995, San Diego, California, United States [doi>10.1145/224170.224337]
• 12: P. Havlak , K. Kennedy, An Implementation of Interprocedural Bounded Regular Section Analysis, IEEE Transactions on Parallel and Distributed Systems, v.2 n.3, p.350-360, July 1991 [doi>10.1109/71.86110]
• 13: L. J. Hendren , A. Nicolau, Parallelizing Programs with Recursive Data Structures, IEEE Transactions on Parallel and Distributed Systems, v.1 n.1, p.35-47, January 1990 [doi>10.1109/71.80123]
• 14: J. R. Larus , P. N. Hilfinger, Detecting conflicts between structure accesses, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.24-31, June 20-24, 1988, Atlanta, Georgia, United States
• 15: Eric Mohr , David A. Kranz , Robert H. Halstead, Jr., Lazy task creation: a technique for increasing the granularity of parallel programs, Proceedings of the 1990 ACM conference on LISP and functional programming, p.185-197, June 27-29, 1990, Nice, France [doi>10.1145/91556.91631]
• 16: Sungdo Moon , Mary W. Hall , Brian R. Murphy, Predicated array data-flow analysis for run-time parallelization, Proceedings of the 12th international conference on Supercomputing, p.204-211, July 1998, Melbourne, Australia [doi>10.1145/277830.277874]
• 17: Martin C. Rinard , Pedro C. Diniz, Commutativity analysis: a new analysis framework for parallelizing compilers, Proceedings of the ACM SIGPLAN 1996 conference on Programming language design and implementation, p.54-67, May 21-24, 1996, Philadelphia, Pennsylvania, United States
• 18: Radu Rugina , Martin Rinard, Pointer analysis for multithreaded programs, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.77-90, May 01-04, 1999, Atlanta, Georgia, United States
• 19: Mooly Sagiv , Thomas Reps , Reinhard Wilhelm, Solving shape-analysis problems in languages with destructive updating, ACM Transactions on Programming Languages and Systems (TOPLAS), v.20 n.1, p.1-50, Jan. 1998 [doi>10.1145/271510.271517]
• 20: Rémi Triolet , Francois Irigoin , Paul Feautrier, Direct parallelization of call statements, Proceedings of the 1986 SIGPLAN symposium on Compiler construction, p.176-185, June 25-27, 1986, Palo Alto, California, United States
• 21: Robert P. Wilson , Monica S. Lam, Efficient context-sensitive pointer analysis for C programs, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.1-12, June 18-21, 1995, La Jolla, California, United States

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Algorithms, Design, Management