A general approach for partitioning N-dimensional parallel nested loops with conditionals

ABSTRACT

Parallel loops account for the greatest amount of parallelism in scientific and numerical codes. For example, most of the DO loops in SPEC CFP2000 and SPEC OMPM2001 are of DOALL type and account for a large percentage of the total execution time. One of the ways to exploit parallelism is to partition the iteration space of a DOALL loop amongst different processors in a parallel processor system. Naturally, a good partitioning is of key importance to achieve high performance and for efficient use of multiprocessor systems. Although a significant amount of work has been done in partitioning and scheduling of loops with both rectangular and non-rectangular iteration spaces, the problem of partitioning loops with conditionals has not been addressed so far to the best of our knowledge. In this paper, we present a mathematical model for partitioning parallel nested loops, both perfect and non-perfect, with conditionals, where the expressions in a conditional are affine functions of the outer loop indices. We present a loop transformation based on elimination of redundant constraints bounding the iteration space of a nested loop. The transformation plays a critical role during the (static) partitioning process as it helps to capture the "exact" lower and upper bounds (can be either a constant or symbolic) of the loop indices. We generate a canonical form of the loop nest using the transformation and employ the geometric approach we proposed earlier (in [1, 2]) for partitioning the iteration space along an axis corresponding to the outermost loop. For cases in which such a transformation does not exist, we propose a general approach for loop canonicalization. We present several examples from the literature and numerical packages to illustrate the effectiveness of our approach.

REFERENCES

• 1: Arun Kejariwal , Alexandru Nicolau , Utpal Banerjee , Constantine D. Polychronopoulos, A novel approach for partitioning iteration spaces with variable densities, Proceedings of the tenth ACM SIGPLAN symposium on Principles and practice of parallel programming, June 15-17, 2005, Chicago, IL, USA [doi>10.1145/1065944.1065962]
• 2: A. Kejariwal, P. D'Alberto, A. Nicolau, and C. D. Polychronopoulos. A geometric approach for partitioning N-dimensional non-rectangular iteration spaces. In Proceedings of the 17th International Workshop on Languages and Compilers for Parallel Computing, pages 102--116, West Lafayette, IN, 2004.
• 3: Mohammad R. Haghighat , Constantine D. Polychronopoulos, Symbolic analysis for parallelizing compilers, ACM Transactions on Programming Languages and Systems (TOPLAS), v.18 n.4, p.477-518, July 1996 [doi>10.1145/233561.233568]
• 4: R. Sakellariou. On the Quest for Perfect Load Balance in Loop-Based Parallel Computations. PhD thesis, Department of Computer Science, University of Manchester, October 1996.
• 5: C. Polychronopoulos, D. J. Kuck, and D. A. Padua. Execution of parallel loops on parallel processor systems. In Proceedings of the 1986 International Conference on Parallel Processing, pages 519--527, August 1986.
• 6: E. H. D'Hollander, Partitioning and Labeling of Loops by Unimodular Transformations, IEEE Transactions on Parallel and Distributed Systems, v.3 n.4, p.465-476, July 1992 [doi>10.1109/71.149964 ]
• 7: S. Lundstrom and G. Barnes. A controllable MIMD architectures. In Proceedings of the 1980 International Conference on Parallel Processing, St. Charles, IL, August 1980.
• 8: C. Polychronopoulos. Loop coalescing: A compiler transformation for parallel machines. In Proceedings of the 1987 International Conference on Parallel Processing, pages 235--242, August 1987.
• 9: James D. Foley , Andries van Dam , Steven K. Feiner , John F. Hughes, Computer graphics: principles and practice (2nd ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 10: P. Anninos. Computational cosmology: From the early universe to the large scale structure. In Living Reviews in Relativity 4, 2001.
• 11: M. O'Boyle and G. A. Hedayat. Load balancing of parallel affine loops by unimodular transformations. Technical Report UMCS-92-1-1, Department of Computer Science, University of Manchester, January 1992.
• 12: 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
• 13: Hideki Saito , Nicholas Stavrakos , Constantine D. Polychronopoulos, Multithreading Runtime Support for Loop and Functional Parallelism, Proceedings of the Second International Symposium on High Performance Computing, p.133-144, May 26-28, 1999
• 14: J. B. J. Fourier. Solution d'une question particulière du calcul des inégalités. In Ouevres II, pages 317--328. 1826.
• 15: L. L. Dines. System of linear inequalities. Annals of Mathematics, 20:191--199, 1919.
• 16: L. L. Dines and N. H. McCoy. On linear inequalities. Transactions of the Royal Society of Canada, 27:217--232, 1933.
• 17: T. S. Motzkin. Beitrage zur theorie der linearen Ungleichungen. PhD thesis, University of Basel, 1936.
• 18: H. W. Kuhn. Solvability and consistency of linear inequalities and inequalities. American Mathematical Monthly, 63:217--232, 1956.
• 19: S. N. Chernikov. The solution of linear programming problems by elimination of unknowns. Doklady Akademii Nauk SSSR, 139:1314--1317, 1961.
• 20: G. Dantzig. Linear Programming and Extensions. Princeton University Press, Princeton, NJ, 1963.
• 21: G. B. Dantzig and B. C. Eaves. Fourier-Motzkin elimination and its dual. Journal of Combinatorial Theory (A), 14(3):288--297, 1973.
• 22: R. J. Duffin. On Fourier's analysis of linear inequality systems. In Mathematical Programming Study 1, pages 71--95. North-Holland, 1974.
• 23: H. P. Williams. Fourier-motzkin elimination extension to integer programming problems. Journal of Combinatorial Theory (A), 21(1):118--123, 1976.
• 24: Utpal K. Banerjee, Loop Transformations for Restructuring Compilers: The Foundations, Kluwer Academic Publishers, Norwell, MA, 1993
• 25: A. Bik and H. Wijshoff. Implementation of Fourier-Motzkin elimination. Technical Report TR94-42, Department of Computer Science, University of Leiden, The Netherlands, 1994.
• 26: William Pugh, A practical algorithm for exact array dependence analysis, Communications of the ACM, v.35 n.8, p.102-114, Aug. 1992 [doi>10.1145/135226.135233]
• 27: LEDAS Geometric Solver. http://lgs.ledas.com/features.php.
• 28: D. Kuck, A. H. Sameh, R. Cytron, A. Veidenbaum, C. D. Polychronopoulos, G. Lee, T. McDaniel, B. R. Leasure, C. Beckman, J. R. B Davies, and C. P. Kruskal. The effects of program restructuring, algorithm change and architecture choice on program performance. In Proceedings of the 1984 International Conference on Parallel Processing, pages 129--138, August 1984.
• 29: Michael Joseph Wolfe, Optimizing Supercompilers for Supercomputers, MIT Press, Cambridge, MA, 1990
• 30: David A. Padua , Michael J. Wolfe, Advanced compiler optimizations for supercomputers, Communications of the ACM, v.29 n.12, p.1184-1201, Dec. 1986 [doi>10.1145/7902.7904]
• 31: F. Irigoin , R. Triolet, Supernode partitioning, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.319-329, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73588]
• 32: Clyde P. Kruskal , Alan Weiss, Allocating independent subtasks on parallel processors, IEEE Transactions on Software Engineering, v.11 n.10, p.1001-1016, Oct. 1985 [doi>10.1109/TSE.1985.231547]
• 33: Mohammad R. Haghighat , Constantine D. Polychronopoulos, Symbolic Program Analysis and Optimization for Parallelizing Compilers, Proceedings of the 5th International Workshop on Languages and Compilers for Parallel Computing, p.538-562, August 03-05, 1992
• 34: 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 ]
• 35: Utpal K. Banerjee, Dependence Analysis for Supercomputing, Kluwer Academic Publishers, Norwell, MA, 1988
• 36: Corinne Ancourt , François Irigoin, Scanning polyhedra with DO loops, Proceedings of the third ACM SIGPLAN symposium on Principles and practice of parallel programming, p.39-50, April 21-24, 1991, Williamsburg, Virginia, United States
• 37: R. Triolet. Interprocedural analysis for program restructuring with Parafrase. CSRD Rpt. No. 538, Department of Computer Science, University of Illinois at Urbana-Champaign, December 1985.
• 38: 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
• 39: François Irigoin , Pierre Jouvelot , Rémi Triolet, Semantical interprocedural parallelization: an overview of the PIPS project, Proceedings of the 5th international conference on Supercomputing, p.244-251, June 17-21, 1991, Cologne, West Germany [doi>10.1145/109025.109086]
• 40: William Pugh, Counting solutions to Presburger formulas: how and why, ACM SIGPLAN Notices, v.29 n.6, p.121-134, June 1994

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming

General Terms:
Algorithms, Performance

Keywords:
Fourier-Motzkin elimination, affine, conditionals, parallel loops, partitioning