Commutativity analysis: a new analysis technique for parallelizing compilers

ABSTRACT

This article presents a new analysis technique, commutativity analysis, for automatically parallelizing computations that manipulate dynamic, pointer-based data structures. Commutativity analysis views the computation as composed of operations on objects. It then analyzes the program at this granularity to discover when operations commute (i.e., generate the same final result regardless of the order in which they execute). If all of the operations required to perform a given computation commute, the compiler can automatically generate parallel code. We have implemented a prototype compilation system that uses commutativity analysis as its primary analysis technique. We have used this system to automatically parallelize three complete scientific computations: the Barnes-Hut N-body solver, the Water liquid simulation code, and the String seismic simulation code. This article presents performance results for the generated parallel code running on the Stanford DASH machine. These results provide encouraging evidence that commutativity analysis can serve as the basis for a successful parallelizing compiler.

REFERENCES

• 1: Utpal K. Banerjee, Dependence Analysis for Supercomputing, Kluwer Academic Publishers, Norwell, MA, 1988
• 2: BANERJEE, W., EIGENMANN, R., NICOLAU, t., AND PADUA, D. 1993. Automatic program parallelization. Proceedings IEEE 81, 2 (Feb.), 211-243.
• 3: BARNES, J. AND HUT, P. 1986. A hierarchical O(NlogN) force calculation algorithm. Nature 324, 4 (Dec.), 446-449.
• 4: BERNSTEIN, A. J. 1966. Analysis of programs for parallel processing. IEEE Trans. Electron. Comput. 15, 5 (Oct.), 757-763.
• 5: BERRY, ~/{., CHEN, D., Koss, P., KUCK, D., Lo, S., PANG, Y., POINTER, L., ROLOFF, R., SAMEH, t., CLEMENTI, E., CHIN, S., SCHNEIDER, D., FOX, G., ~/{ESSINA, P., WALKER, D., HSIUNG, C., SCHWARZMEIER, J., LUE, K., ORSZAG, S., SEIDL, F., JOHNSON, O., GOODRUM, R., AND MARTIN, J. 1989. The Perfect Club benchmarks: Effective performance evaluation of supercomputers. ICASE Rep. 827, Center for Supercomputing Research and Development, Univ. of Illinois at Urbana-Champaign, Urbana, Ill., May.
• 6: W. Blume , R. Eigenmann, Performance Analysis of Parallelizing Compilers on the Perfect Benchmarks Programs, IEEE Transactions on Parallel and Distributed Systems, v.3 n.6, p.643-656, November 1992 [doi>10.1109/71.180621]
• 7: William Blume , Rudolf Eigenmann, Symbolic range propagation, Proceedings of the 9th International Symposium on Parallel Processing, p.357-363, April 25-28, 1995
• 8: BODIN, F., BECKMAN, P., GANNON, D., GOTWALS, J., NARAYANA, S., SRINIVAS, S., AND WINNICKA, B. 1994. Sage++: An object-oriented toolkit and class library for building Fortran and C++ structuring tools. In Proceedings of the Object-Oriented Numerics Conference.
• 9: David Callahan, Recognizing and Parallelizing Bounded Recurrences, Proceedings of the Fourth International Workshop on Languages and Compilers for Parallel Computing, p.169-185, August 07-09, 1991
• 10: Martin C. Carlisle , Anne Rogers, Software caching and computation migration in Olden, Proceedings of the fifth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.29-38, July 19-21, 1995, Santa Barbara, California, United States
• 11: Rohit Chandra , Anoop Gupta , John L. Hennessy, Data locality and load balancing in COOL, Proceedings of the fourth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.249-259, May 19-22, 1993, San Diego, California, United States
• 12: 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
• 13: CLARKE, L. AND RICHARDSON, D. 1981. Symbolic evaluation methods for program analysis. In Program Flow Analysis: Theory and Applications, S. Muchnick and N. Jones, Eds. Prentice- Hall, Englewood Cliffs, N.J., 79-101.
• 14: DARLINGTON, J. 1972. A semantic approach to automatic program improvement. Ph.D. thesis, Univ. of Edinburgh, Edinburgh, U.K.
• 15: DILLON, L. 1987a. Verification of Ada tasking programs using symbolic execution, Part I: Partial Correctness. Tech. Rep. TRCS87-20, Dept. of Computer Science, Univ. of California, Santa Barbara, Calif., Oct.
• 16: DILLON, L. 1987b. Verification of Ada tasking programs using symbolic execution, Part II: General Safety Properties. Tech. Rep. TRCS87-21, Dept. of Computer Science, Univ. of California, Santa Barbara, Calif., Oct.
• 17: Pedro C. Diniz , Martin C. Rinard, Lock Coarsening: Eliminating Lock Overhead in Automatically Parallelized Object-Based Programs, Proceedings of the 9th International Workshop on Languages and Compilers for Parallel Computing, p.285-299, August 08-10, 1996
• 18: Jeffrey Douglas , Richard A. Kemmerer, Aslantest: a symbolic execution tool for testing Aslan formal specifications, Proceedings of the 1994 ACM SIGSOFT international symposium on Software testing and analysis, p.15-27, August 17-19, 1994, Seattle, Washington, United States [doi>10.1145/186258.186487]
• 19: Rudolf Eigenmann , Jay Hoeflinger , Z. Li , David A. Padua, Experience in the Automatic Parallelization of Four Perfect-Benchmark Programs, Proceedings of the Fourth International Workshop on Languages and Compilers for Parallel Computing, p.65-83, August 07-09, 1991
• 20: 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
• 21: Allan L. Fisher , Anwar M. Ghuloum, Parallelizing complex scans and reductions, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.135-146, June 20-24, 1994, Orlando, Florida, United States
• 22: Anwar M. Ghuloum , Allan L. Fisher, Flattening and parallelizing irregular, recurrent loop nests, Proceedings of the fifth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.58-67, July 19-21, 1995, Santa Barbara, California, United States
• 23: GIFFORD, D., JOUVELOT, P., LUCASSEN, J., AND SHELDON, M. 1987. FX-87 Reference Manual. Tech. Rep. MIT/LCS/TR-407, MIT, Cambridge, Mass., Sept.
• 24: Susan L. Graham , Peter B. Kessler , Marshall K. Mckusick, Gprof: A call graph execution profiler, Proceedings of the 1982 SIGPLAN symposium on Compiler construction, p.120-126, June 23-25, 1982, Boston, Massachusetts, United States
• 25: 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]
• 26: R. T. Hammel , D. K. Gifford, FX-87 PERFORMANCE MEASUREMENTS: DATAFLOW IMPLEMENTATION, Massachusetts Institute of Technology, Cambridge, MA, 1988
• 27: HARRIS, J., LAZARATOS, S., AND MICHELENA, R. 1990. Tomographic string inversion. In the 60th Annual International Meeting, Society of Exploration and Geophysics, Extended Abstracts, 82-85.
• 28: Laurie J. Hendren , Joseph Hummell , Alexandru Nicolau, Abstractions for recursive pointer data structures: improving the analysis and transformation of imperative programs, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.249-260, June 15-19, 1992, San Francisco, California, United States
• 29: Joseph Hummel , Laurie J. Hendren , Alexandru Nicolau, A general data dependence test for dynamic, pointer-based data structures, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.218-229, June 20-24, 1994, Orlando, Florida, United States
• 30: Seema Hiranandani , Ken Kennedy , Chau-Wen Tseng, Compiling Fortran D for MIMD distributed-memory machines, Communications of the ACM, v.35 n.8, p.66-80, Aug. 1992 [doi>10.1145/135226.135230]
• 31: Oscar H. Ibarra , Pedro C. Diniz , Martin C. Rinard, On the Complexity of Commutativity Analysis, Proceedings of the Second Annual International Conference on Computing and Combinatorics, p.323-332, June 17-19, 1996
• 32: KEMMERER, R. AND ECKMANN, S. 1985. UNISEX: A UNix-based Symbolic EXecutor for Pascal. Softw. Pract. Exper. 15, 5 (May), 439-458.
• 33: James C. King, Symbolic execution and program testing, Communications of the ACM, v.19 n.7, p.385-394, July 1976 [doi>10.1145/360248.360252]
• 34: James C. King, Program reduction using symbolic execution, ACM SIGSOFT Software Engineering Notes, v.6 n.1, p.9-14, January 1981 [doi>10.1145/1005920.1005924]
• 35: KNUTH, D. 1971. An empirical study of FORTRAN programs. Softw. Pract. Exper. 1, 105-133.
• 36: Monica S. Lam , Martin C. Rinard, Coarse-grain parallel programming in Jade, Proceedings of the third ACM SIGPLAN symposium on Principles and practice of parallel programming, p.94-105, April 21-24, 1991, Williamsburg, Virginia, United States
• 37: Butler W. Lampson , David D. Redell, Experience with processes and monitors in Mesa, Communications of the ACM, v.23 n.2, p.105-117, Feb. 1980 [doi>10.1145/358818.358824]
• 38: William Landi , Barbara G. Ryder , Sean Zhang, Interprocedural modification side effect analysis with pointer aliasing, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.56-67, June 21-25, 1993, Albuquerque, New Mexico, United States
• 39: 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
• 40: LENGAUER, C. AND HEHNER, E. 1982. A methodology for programming with concurrency: An informal presentation. Sci. Comput. Program. 2, 1 (Oct.), 1-18.
• 41: Daniel Edward Lenoski, The design and analysis of DASH: a scalable directory-based multiprocessor, Stanford University, Stanford, CA, 1992
• 42: Ewing Lusk , James Boyle , Ralph Butler , Terrence Disz , Barnett Glickfeld , Ross Overbeek , James Patterson , Rick Stevens, Portable programs for parallel processors, Holt, Rinehart & Winston, Austin, TX, 1988
• 43: 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]
• 44: Shlomit S. Pinter , Ron Y. Pinter, Program optimization and parallelization using idioms, Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.79-92, January 21-23, 1991, Orlando, Florida, United States [doi>10.1145/99583.99597]
• 45: John Plevyak , Andrew A. Chien , Vijay Karamcheti, Analysis of Dynamic Structures for Efficient Parallel Execution, Proceedings of the 6th International Workshop on Languages and Compilers for Parallel Computing, p.37-56, August 12-14, 1993
• 46: C. D. Polychronopoulos , D. J. Kuck, Guided self-scheduling: A practical scheduling scheme for parallel supercomputers, IEEE Transactions on Computers, v.36 n.12, p.1425-1439, Dec. 1987 [doi>10.1109/TC.1987.5009495]
• 47: William Pugh , David Wonnacott, Eliminating false data dependences using the Omega test, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.140-151, June 15-19, 1992, San Francisco, California, United States
• 48: Martin C. Rinard, The design, implementation and evaluation of Jade: a portable, implicitly parallel programming language, Stanford University, Stanford, CA, 1994
• 49: RINARD, M. 1994b. Implicitly synchronized abstract data types: Data structures for modular parallel programming. In Proceedings of the 2nd International Workshop on Massive Parallelism: Hardware, Software and Applications, M. Furnari, Ed. World Scientific Publishing, Singapore, 259-274.
• 50: Martin C. Rinard, Communication optimizations for parallel computing using data access information, Proceedings of the 1995 ACM/IEEE conference on Supercomputing (CDROM), p.69-es, December 04-08, 1995, San Diego, California, United States [doi>10.1145/224170.224413]
• 51: Martin C. Rinard , Pedro C. Diniz, Commutativity Analysis: A Technique for Automatically Parallelizing Pointer-Based Computations, Proceedings of the 10th International Parallel Processing Symposium, p.14-22, April 15-19, 1996
• 52: John K. Salmon, Parallel hierarchical N-body methods, California Institute of Technology, Pasadena, CA, 1992
• 53: SCALES, D. AND LAM, M. S. 1994. The design and evaluation of a shared object system for distributed memory machines. In Proceedings of the 1st USENIX Symposium on Operating Systems Design and Implementation. USENIX Assoc., Berkeley, Calif.
• 54: Jaswinder Pal Singh, Parallel hierarchical N-body methods and their implications for multiprocessors, Stanford University, Stanford, CA, 1993
• 55: Jaswinder Pal Singh , Wolf-Dietrich Weber , Anoop Gupta, SPLASH: Stanford parallel applications for shared-memory, ACM SIGARCH Computer Architecture News, v.20 n.1, p.5-44, March 1992 [doi>10.1145/130823.130824]
• 56: Guy L. Steele, Jr., Making asynchronous parallelism safe for the world, Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.218-231, December 1989, San Francisco, California, United States [doi>10.1145/96709.96731]
• 57: 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
• 58: RSCHLER, G. 1974. Complete redundant expression elimination in flow diagrams. Research Rep. RC 4965, IBM, Yorktown Heights, N.Y., Aug.
• 59: W. E. Weihl, Commutativity-Based Concurrency Control for Abstract Data Types, IEEE Transactions on Computers, v.37 n.12, p.1488-1505, December 1988 [doi>10.1109/12.9728]
• 60: 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
• 61: Steven Cameron Woo , Moriyoshi Ohara , Evan Torrie , Jaswinder Pal Singh , Anoop Gupta, The SPLASH-2 programs: characterization and methodological considerations, Proceedings of the 22nd annual international symposium on Computer architecture, p.24-36, June 22-24, 1995, S. Margherita Ligure, Italy
• 62: Akinori Yonezawa , Jean-Pierre Briot , Etsuya Shibayama, Object-oriented concurrent programming ABCL/1, Conference proceedings on Object-oriented programming systems, languages and applications, p.258-268, September 29-October 02, 1986, Portland, Oregon, United States

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES

Keywords:
parallel computing