Violated dependence analysis

ABSTRACT

The polyhedral model is a powerful framework to reason about high level loop transformations. Yet the lack of scalable algorithms and tools has deterred actors from both academia and industry to put this model to practical use. Indeed, for fundamental complexity reasons, its applicability has long been limited to simple kernels. Recent developments broke some generally accepted ideas about these limitations. In particular, new algorithms made it possible to compute the target code for full SPEC benchmarks while this code generation step was expected not to be scalable.Instancewise array dependence analysis computes a finite, intensional representation of the (statically unbounded) set of all dynamic dependences. This problem has always been considered non-scalable and/or an overkill with respect to less expressive and faster dependence tests. On the contrary, this article presents experimental evidence of its applicability to full SPEC CPU2000 benchmarks. To make this possible, we revisit the characterization of data dependences, considering relations between time dimensions of the transformed space. Beyond algorithmic benefits, this naturally leads to a novel way of reasoning about violated dependences across arbitrary transformation sequences. Reasoning about violated dependences relieves the compiler designer from the cumbersome task of implementing specific legality checks for each single transformation. It also allows, in the case of invalid transformations, to precisely determine the violated dependences that need to be corrected. Identifying these violations can in turn enable automatic correction schemes to fix an illegal transformation sequence with minimal changes.

REFERENCES

• 1: Randy Allen , Ken Kennedy, Automatic translation of FORTRAN programs to vector form, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.4, p.491-542, Oct. 1987 [doi>10.1145/29873.29875]
• 2: Ken Kennedy , John R. Allen, Optimizing compilers for modern architectures: a dependence-based approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2001
• 3: U. Banerjee. Data dependence in ordinary programs. Master's thesis, Dept. of Computer Science, University of Illinois at Urbana-Champaign, November 1976.
• 4: Utpal K. Banerjee, Dependence Analysis for Supercomputing, Kluwer Academic Publishers, Norwell, MA, 1988
• 5: D. Barthou. Array Dataflow Analysis in Presence of Non-affine Constraints. PhD thesis, Université de Versailles, France, Feb. 1998. http://www.prism.uvsq.fr/~bad/these.html.
• 6: Cedric Bastoul, Code Generation in the Polyhedral Model Is Easier Than You Think, Proceedings of the 13th International Conference on Parallel Architectures and Compilation Techniques, p.7-16, September 29-October 03, 2004 [doi>10.1109/PACT.2004.11]
• 7: C. Bastoul and P. Feautrier. Adjusting a program transformation for legality. Parallel processing letters, 15(1):3--17, Mar. 2005.
• 8: F. Chow. Maximizing application performance through interprocedural optimization with the PathScale EKO compiler suite. http://www.pathscale.com/whitepapers.html, Aug. 2004.
• 9: Albert Cohen , Marc Sigler , Sylvain Girbal , Olivier Temam , David Parello , Nicolas Vasilache, Facilitating the search for compositions of program transformations, Proceedings of the 19th annual international conference on Supercomputing, June 20-22, 2005, Cambridge, Massachusetts [doi>10.1145/1088149.1088169]
• 10: J.-F. Collard. Parallélisation automatique des programmes à contrôle dynamique. PhD thesis, Université Pierre et Marie Curie (Paris 6), France, Jan. 1995. http://www.prism.uvsq.fr/~jfc/memoire.ps.
• 11: Alain Darte, On the complexity of loop fusion, Parallel Computing, v.26 n.9, p.1175-1193, Aug. 2000 [doi>10.1016/S0167-8191(00)00034-X]
• 12: Christine Eisenbeis , Jean-Claude Sogno, A general algorithm for data dependence analysis, Proceedings of the 6th international conference on Supercomputing, p.292-302, July 19-24, 1992, Washington, D. C., United States [doi>10.1145/143369.143422]
• 13: P. Feautrier, Array expansion, Proceedings of the 2nd international conference on Supercomputing, p.429-441, June 1988, St. Malo, France [doi>10.1145/55364.55406]
• 14: P. Feautrier. Parametric integer programming. RAIRO Recherche Opérationnelle, 22:243--268, Sept. 1988.
• 15: P. Feautrier. Dataflow analysis of scalar and array references. Intl. J. of Parallel Programming, 20(1):23--53, Feb. 1991.
• 16: Paul Feautrier, Some efficient solutions to the affine scheduling problem: I. One-dimensional time, International Journal of Parallel Programming, v.21 n.5, p.313-348, Oct. 1992 [doi>10.1007/BF01407835]
• 17: Sylvain Girbal , Nicolas Vasilache , Cédric Bastoul , Albert Cohen , David Parello , Marc Sigler , Olivier Temam, Semi-automatic composition of loop transformations for deep parallelism and memory hierarchies, International Journal of Parallel Programming, v.34 n.3, p.261-317, June 2006 [doi>10.1007/s10766-006-0012-3]
• 18: Gina Goff , Ken Kennedy , Chau-Wen Tseng, Practical dependence testing, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.15-29, June 24-28, 1991, Toronto, Ontario, Canada
• 19: M. Griebl. Automatic parallelization of loop programs for distributed memory architectures. Habilitation thesis. Facultät für Mathematik und Informatik, Universität Passau, 2004.
• 20: F. Irigoin and R. Triolet. Computing dependence direction vectors and dependence cones with linear systems. Technical Report ENSMP-CAI-87-E94, Ecole des Mines de Paris, Fontainebleau (France), 1987.
• 21: W. Kelly. Optimization within a unified transformation framework. Technical Report CS-TR-3725, University of Maryland, 1996.
• 22: X. Kong, D. Klappholz, and K. Psarris. The i test: A new test for subscript data dependence. In ICPP'90 International Conference on Parallel Processing, pages 204--211, St. Charles, Aug. 1990.
• 23: Leslie Lamport, The parallel execution of DO loops, Communications of the ACM, v.17 n.2, p.83-93, Feb. 1974 [doi>10.1145/360827.360844]
• 24: Vincent Lefebvre , Paul Feautrier, Automatic storage management for parallel programs, Parallel Computing, v.24 n.3-4, p.649-671, May, 1998 [doi>10.1016/S0167-8191(98)00029-5]
• 25: A. W. Lim and M. S. Lam. Communication-free parallelization via affine transformations. In 24th ACM Symp. on Principles of Programming Languages, pages 201--214, Paris, France, Jan. 1997.
• 26: Vincent Loechner , Doran K. Wilde, Parameterized polyhedra and their vertices, International Journal of Parallel Programming, v.25 n.6, p.525-549, Dec. 1997 [doi>10.1023/A:1025117523902]
• 27: Dror E. Maydan , Saman P. Amarasinghe , Monica S. Lam, Array-data flow analysis and its use in array privatization, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.2-15, March 1993, Charleston, South Carolina, United States [doi>10.1145/158511.158515]
• 28: Dror E. Maydan , John L. Hennessy , Monica S. Lam, Efficient and exact data dependence analysis, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.1-14, June 24-28, 1991, Toronto, Ontario, Canada
• 29: P. Petersen and D. Padua. Experimental evaluation of some data dependence tests. Technical Report CSRD 1080, University of Illinois at Urbana-Champaign, Feb. 1991.
• 30: Paul M. Petersen , David A. Padua, Static and Dynamic Evaluation of Data Dependence Analysis Techniques, IEEE Transactions on Parallel and Distributed Systems, v.7 n.11, p.1121-1132, November 1996 [doi>10.1109/71.544354]
• 31: K. Psarris and K. Kyriakopoulos. An experimental evaluation of data dependence analysis techniques. IEEE Transactions on Parallel and Distributed Systems, 15(3):196--213, Mar. 2004.
• 32: William Pugh, The Omega test: a fast and practical integer programming algorithm for dependence analysis, Proceedings of the 1991 ACM/IEEE conference on Supercomputing, p.4-13, November 18-22, 1991, Albuquerque, New Mexico, United States [doi>10.1145/125826.125848]
• 33: William Pugh, Uniform techniques for loop optimization, Proceedings of the 5th international conference on Supercomputing, p.341-352, June 17-21, 1991, Cologne, West Germany [doi>10.1145/109025.109108]
• 34: Fabien Quilleré , Sanjay Rajopadhye, Optimizing memory usage in the polyhedral model, ACM Transactions on Programming Languages and Systems (TOPLAS), v.22 n.5, p.773-815, Sept. 2000 [doi>10.1145/365151.365152]
• 35: Fabien Quilleré , Sanjay Rajopadhye , Doran Wilde, Generation of Efficient Nested Loops from Polyhedra, International Journal of Parallel Programming, v.28 n.5, p.469-498, Oct. 2000 [doi>10.1023/A:1007554627716]
• 36: Alexandeer Schrijver, Theory of linear and integer programming, John Wiley & Sons, Inc., New York, NY, 1986
• 37: N. Vasilache, C. Bastoul, and A. Cohen. Polyhedral code generation in the real world. In Proceedings of the International Conference on Compiler Construction (ETAPS CC'06), LNCS, pages 185--201, Vienna, Austria, Mar. 2006. Springer-Verlag.
• 38: F. Vivien. Détection de parallélisme dans les boucles imbriquées. PhD thesis, ENS - Lyon, 1997.
• 39: Michael Joseph Wolfe , Carter Shanklin , Leda Ortega, High Performance Compilers for Parallel Computing, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 40: Michael Wolfe , Utpal Banerjee, Data dependence and its application to parallel processing, International Journal of Parallel Programming, v.16 n.2, p.137-178, April 1987 [doi>10.1007/BF01379099]
• 41: M. Wolfe , C. W. Tseng, The Power Test for Data Dependence, IEEE Transactions on Parallel and Distributed Systems, v.3 n.5, p.591-601, September 1992 [doi>10.1109/71.159042]
• 42: David Glenn Wonnacott, Constraint-based array dependence analysis, University of Maryland at College Park, College Park, MD, 1996

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.2 Semantics of Programming Languages
          Subjects: Program analysis

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.3 Studies of Program Constructs
          Subjects: Control primitives

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.2 Automatic Programming
          Subjects: Program transformation

General Terms:
Design, Verification