Shape cliques

ABSTRACT

We introduce shape cliques, a simple way to organize a subset of the arrays appearing in an array-language-based application into sets of identically shaped arrays - shape cliques - and show how a compiler can analyze an application to infer membership in those cliques. We describe an algorithm for performing shape clique inference (SCI), and demonstrate that shape cliques can improve the performance of generated code, by permitting extension of an optimization for removal of run-time checks, and by extending the set of arrays to which optimizations, such as Index Vector Elimination (IVE), can be applied. Implementation of SCI in the APEX APL compiler permitted removal of 25% of run-time checks remaining on 156 benchmarks remaining after other compiler optimizations had eliminated 72% of the 1251 checks present in the original code. In the SAC compiler, IVE using SCI produced typical speedups of 2-14X on benchmarks operating on arrays of non-fixed rank and shape, compared to the operation of IVE in a non-SCI environment. Shape clique inference data can be exploited to allow certain other optimizations, such as loop fusion and withloop folding, to be performed on arrays of statically unknown shape and rank, with the potential for significant reductions in execution time.

REFERENCES

• 1: International Standards Organization: International Standard for Programming Language APL. ISO N8485 edn. (1984).
• 2: Hui, R. K., Iverson, K. E.: J Dictionary. (1998).
• 3: Sven-Bodo Scholz, Single Assignment C: efficient support for high-level array operations in a functional setting, Journal of Functional Programming, v.13 n.6, p.1005-1059, November 2003 [doi>10.1017/S0956796802004458]
• 4: Clemens Grelck , Sven-Bodo Scholz, SAC: a functional array language for efficient multi-threaded execution, International Journal of Parallel Programming, v.34 n.4, p.383-427, August 2006 [doi>10.1007/s10766-006-0018-x]
• 5: Cann, D. C.: The optimizing SISAL compiler: Version 12.0. Technical Report UCRL-MA-110080, Lawrence Livermore National Laboratory (1992).
• 6: Thi Viet Nga Nguyen , François Irigoin, Efficient and effective array bound checking, ACM Transactions on Programming Languages and Systems (TOPLAS), v.27 n.3, p.527-570, May 2005 [doi>10.1145/1065887.1065893]
• 7: Dietmar Kreye, A Compilation Scheme for a Hierarchy of Array Types, Selected Papers from the 13th International Workshop on Implementation of Functional Languages, p.18-54, September 24-26, 2001
• 8: Shafarenko, A., Scholz, S. B., Herhut, S., Grelck, C., Trojahner, K.: Implementing a numerical solution for the KPI equation using Single Assignment C: lessons and experience. In Butterfield, A., ed.: Implementation and Application of Functional Languages, 17th International Workshop, IFL'05. Volume 4015 of LNCS., Springer (2006) to appear.
• 9: Bernecky, R.: APEX: The APL Parallel Executor. Master's thesis, University of Toronto (1997).
• 10: Bernecky, R., Herhut, S., Scholz, S. B., Trojahner, K., Grelck, C., Shafarenko, A.: Index Vector Elimination - making index vectors affordable. In Horváth, Z., Zsók, V., eds.: Proceedings of the 18th International Symposium on Implementation of Functional Languages (IFL'06), Budapest, Hungary, Eötvös Loránd University (2006) 23--43.
• 11: Roger K. W. Hui, Rank and uniformity, ACM SIGAPL APL Quote Quad, v.25 n.4, p.83-90, June 1995
• 12: R. Cytron , J. Ferrante , B. K. Rosen , M. N. Wegman , F. K. Zadeck, An efficient method of computing static single assignment form, Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.25-35, January 11-13, 1989, Austin, Texas, United States [doi>10.1145/75277.75280]
• 13: Robert Bernecky, Reducing computational complexity with array predicates, Proceedings of the APL98 conference on Array processing language, p.39-43, August 27-31, 1998, Rome, Italy
• 14: Sven-Bodo Scholz, WITH-Loop-Folding in SAC - Condensing Consecutive Array Operations, Selected Papers from the 9th International Workshop on Implementation of Functional Languages, p.72-91, September 10-12, 1997
• 15: Jay, C.: comp.lang.functional:11066 (1998).
• 16: Manish Gupta , Sam Midkiff , Edith Schonberg , Ven Seshadri , David Shields , Ko-Yang Wang , Wai-Mee Ching , Ton Ngo, An HPF compiler for the IBM SP2, Proceedings of the 1995 ACM/IEEE conference on Supercomputing (CDROM), p.71-es, December 04-08, 1995, San Diego, California, United States [doi>10.1145/224170.224422]
• 17: Shankar Ramaswamy , Eugene W. Hodges, IV , Prithviraj Banerjee, Compiling MATLAB Programs to ScaLAPACK: Exploiting Task and Data Parallelism, Proceedings of the 10th International Parallel Processing Symposium, p.613-619, April 15-19, 1996
• 18: Trojahner, K., Grelck, C., Scholz, S. B.: On Optimising Shape-Generic Array Language Programs using Symbolic Structural Information. In Horváth, Z., Zsók, V., eds.: Implementation and Application of Functional Languages, 18th International Workshop (IFL'06). Budapest, Hungary, September 4006, 2006, Revised Selected Papers. Lecture Notes in Computer Science, Springer-Verlag, Berlin, Heidelberg, New York (2006).

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph labeling

General Terms:
Algorithms, Design, Theory