A comprehensive approach to parallel data flow analysis

ABSTRACT

We present a comprehensive approach to performing data flow analysis in parallel. We first identify three types of parallelism inherent in the data flow solution process: independent-problem parallelism, separate-unit parallelism and algorithmic parallelism. We then describe a unified framework to exploit them. Our investigations of typical Fortran programs reveal an abundance of the last two types of parallelism. In particular, we illustrate the exploitation of algorithmic parallelism in the design of our parallel hybrid data flow analysis algorithm and report on its empirical performance.

REFERENCES

• ABC+88: Frances Allen , Michael Burke , Philippe Charles , Ron Cytron , Jeanne Ferreant, An overview for the PTRAN analysis system for multiprocessing, Journal of Parallel and Distributed Computing, v.5 n.5, p.617-640, October 1988 [doi>10.1016/0743-7315(88)90015-9]
• ASU86: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• Ban79: John P. Banning, An efficient way to find the side effects of procedure calls and the aliases of variables, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.29-41, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567756]
• Bar78: Jeffrey M. Barth, A practical interprocedural data flow analysis algorithm, Communications of the ACM, v.21 n.9, p.724-736, Sept. 1978 [doi>10.1145/359588.359596]
• BC86: Michael Burke , Ron Cytron, Interprocedural dependence analysis and parallelization, Proceedings of the 1986 SIGPLAN symposium on Compiler construction, p.162-175, June 25-27, 1986, Palo Alto, California, United States
• BS90: David Barnard and David Sldllicorn, editors. Proceedings o~ the Workshop on Parallel Compilation, Kingston, Ontario, Canada, May 1990. Queen's University.
• Bur90: Michael Burke, An interval-based approach to exhaustive and incremental interprocedural data-flow analysis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.3, p.341-395, July 1990 [doi>10.1145/78969.78963]
• Cal88: D. Callahan, The program summary graph and flow-sensitive interprocedual data flow analysis, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.47-56, June 20-24, 1988, Atlanta, Georgia, United States
• CCH+88: D. Callahan, K. Cooper, 1~. Hood, K. Kennedy, and L. Torczon. ParaScope: A parallel programming environment. The International Journal o/ Supercomputer Applications, 2(4):84-99, 1988.
• CK84: Keith D. Cooper , Ken Kennedy, Efficient computation of flow insensitive interprocedural summary information, Proceedings of the 1984 SIGPLAN symposium on Compiler construction, p.247-258, June 17-22, 1984, Montreal, Canada
• CK88: David Callahan and Ken Kennedy. Compiling programs for distributed-memory multiprocessors. The Journal of Supercomputing, pages 151-170, October 1988.
• CK89: K. D. Cooper , K. Kennedy, Fast interprocedual alias analysis, Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.49-59, January 11-13, 1989, Austin, Texas, United States [doi>10.1145/75277.75282]
• CKPK90: George Cybenko , Lyle Kipp , Lynn Pointer , David Kuck, Supercomputer performance evaluation and the Perfect Benchmarks, Proceedings of the 4th international conference on Supercomputing, p.254-266, June 11-15, 1990, Amsterdam, The Netherlands
• CKT86: Keith D. Cooper , Ken Kennedy , Linda Torczon, The impact of interprocedural analysis and optimization in the Rⁿ programming environment, ACM Transactions on Programming Languages and Systems (TOPLAS), v.8 n.4, p.491-523, Oct. 1986 [doi>10.1145/6465.6489]
• GPS90: Rajiv Gupta, Lori Pollock, and Mary Lou Sofia. Parallelizing data flow analysis. In Proceedings of the Workshop on Parallel Compilation, Kingston, Ontario, Canada, May 1990.
• GV91: Elana D. Granston , Alexander V. Veidenbaum, Detecting redundant accesses to array data, Proceedings of the 1991 ACM/IEEE conference on Supercomputing, p.854-865, November 18-22, 1991, Albuquerque, New Mexico, United States [doi>10.1145/125826.126714]
• GZZ89: T. Gross , A. Sobel , M. Zolg, Parallel compilation for a parallel machine, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.91-100, June 19-23, 1989, Portland, Oregon, United States
• Hec77: Matthew S. Hecht, Flow Analysis of Computer Programs, Elsevier Science Inc., New York, NY, 1977
• HHLS90: O. M. Lubeck , M. L. Simmons, On the use of diagnostic dependence-analysis tools in parallel programming, The Journal of Supercomputing, v.4 n.1, p.83-96, Mar. 1990 [doi>10.1007/BF00162344]
• HKT91: Seema Hiranandani , Ken Kennedy , Chau-Wen Tseng, Compiler optimizations for Fortran D on MIMD distributed-memory machines, Proceedings of the 1991 ACM/IEEE conference on Supercomputing, p.86-100, November 18-22, 1991, Albuquerque, New Mexico, United States [doi>10.1145/125826.125886]
• KGS91: Robert Kramer, Rajiv Gupta, and Mary Lou Sofia. The combining DAG: A technique tbr parallel data flow analysis. Technical Report 91-8, University of Pittsburgh, Pittsburgh, PA., March 1991.
• Lee92: Yong-Fong Lee, Performing data flow analysis in parallel, Rutgers University, New Brunswick, NJ, 1992
• LK78: J.K. Lenstra and A.H.G. Rinnooy Kan. Complexity o~ schedulin~ under precedence const~ralnts. Operations Research, 26(1):22-35, 1978.
• LMR91: Yong-Fong Lee , Barbara G. Ryder , Thomas J. Marlowe, Experiences with a parallel algorithm for data flow analysis, The Journal of Supercomputing, v.5 n.2-3, p.163-188, Oct. 1991 [doi>10.1007/BF00127842]
• MP90: S.P. Midldff and D.A. Padua. Issues in the optimization of parallel programs. In Proceedings of the 1990 International Conference on Parallel Processing, Vol.Ii, pages 105-113. The Penn State University Press, August 1990.
• MR90: Thomas J. Marlowe , Barbara G. Ryder, An efficient hybrid algorithm for incremental data flow analysis, Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.184-196, December 1989, San Francisco, California, United States [doi>10.1145/96709.96728]
• MR91: T. J. Marlowe , B. G. Ryder, Properties of data flow frameworks: a unified model, Acta Informatica, v.28 n.2, p.121-163, Dec. 1990 [doi>10.1007/BF01237234]
• Pol88: Constantine D. Polychronopoulos, Parallel Programming and Compilers, Kluwer Academic Publishers, Norwell, MA, 1988
• RP86: Barbara G. Ryder , Marvin C. Paull, Elimination algorithms for data flow analysis, ACM Computing Surveys (CSUR), v.18 n.3, p.277-316, Sept. 1986 [doi>10.1145/27632.27649]
• RW85: Sandra Rapps , Elaine J. Weyuker, Selecting software test data using data flow information, IEEE Transactions on Software Engineering, v.11 n.4, p.367-375, April 1985 [doi>10.1109/TSE.1985.232226]
• Ryd89: Barbara G. Ryder. ISMM: Incremental software maintenance manager. In Proceedings of the IEEE Computer Society Conference on Software Maintenance, pages 142-164. IEEE Computer Society Press, October 1989. Miami, Florida.
• Sar89: Vivek Sarkar, Partitioning and Scheduling Parallel Programs for Multiprocessors, MIT Press, Cambridge, MA, 1989
• SW91: V. Seshadri , D. B. Wortman, An investigation into concurrent semantic analysis, Software—Practice & Experience, v.21 n.12, p.1323-1348, Dec. 1991 [doi>10.1002/spe.4380211205]
• Wei84: Mark Weiser. Program slicing. IEEE Transactions on Software Engineering, SE-10(4):352- 357, July 1984.
• Wol89: Michael Joseph Wolfe, Optimizing Supercompilers for Supercomputers, MIT Press, Cambridge, MA, 1990
• YHR90: Wuu Yang , Susan Horwitz , Thomas Reps, A program integration algorithm that accommodates semantics-preserving transformations, Proceedings of the fourth ACM SIGSOFT symposium on Software development environments, p.133-143, December 03-05, 1990, Irvine, California, United States
• Zob90: Angelika Zobel. Parallel interval analysis of data flow equations. In Proceedings o~ the 1990 International Conference on Parallel Processing, Vol.II, pages 9-16. The Penn State University Press, August 1990.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization

Additional Classification:
  C. Computer Systems Organization
  C.5 COMPUTER SYSTEM IMPLEMENTATION
      C.5.1 Large and Medium ("Mainframe") Computers
          Subjects: Super (very large) computers

  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance

Keywords:
data flow analysis, parallel algorithms, parallel data flow analysis