Partitioning the statement per iteration space using non-singular matrices

ABSTRACT

In this paper we generalize the framework of linear loop transformations: we consider loop alignment as a new component in the transformation process. The aim is to exploit the additional inherent statement-level parallelism and reduce the amount of interprocessor synchronization and communication when a coarse-grain MIMD execution model is considered. The transformation process is modelled with non-singular matrices and we use the ideas recently proposed in this field to generate an efficient transformed code. However, additional aspects have to be studied when statements are considered in the process. We try to reduce the overhead due to conditionals that appear in the loop body of the transformed loops.

REFERENCES

• 1: Constantine D. Polychronopoulos, Parallel Programming and Compilers, Kluwer Academic Publishers, Norwell, MA, 1988
• 2: Michael Joseph Wolfe, Optimizing Supercompilers for Supercomputers, MIT Press, Cambridge, MA, 1990
• 3: Banerjee U., Unimodular Transforlnations of Double Loops, chapter 10 of Advances in Languages and Compilers for Parallel Processing, The MIT Press, 1991.
• 4: Wei Li , Keshav Pingali, A Singular Loop Transformation Framework Based on Non-Singular Matrices, Proceedings of the 5th International Workshop on Languages and Compilers for Parallel Computing, p.391-405, August 03-05, 1992
• 5: M. E. Wolf , M. S. Lam, A Loop Transformation Theory and an Algorithm to Maximize Parallelism, IEEE Transactions on Parallel and Distributed Systems, v.2 n.4, p.452-471, October 1991 [doi>10.1109/71.97902]
• 6: Fernandez A., Systematic Transformation of Systolic Algorithms for Programming Distribated Memory Multiprocessors, Ph.D. Thesis, Department of Computer Architecture, Polytechnic University of Catalunya (Spain), November 1992.
• 7: Michael Barnett , Christian Lengauer, Unimodularity Considered Non-Essential, Proceedings of the Second Joint International Conference on Vector and Parallel Processing: Parallel Processing, p.659-664, September 01-04, 1992
• 8: Utpal K. Banerjee, Dependence Analysis for Supercomputing, Kluwer Academic Publishers, Norwell, MA, 1988
• 9: Lu L. and Chen M., New Loop Transformation Techniques for Massive Parallelism, Research Report TR-833, Department of Computer Science, Yale University, October 1990.
• 10: Alexandeer Schrijver, Theory of linear and integer programming, John Wiley & Sons, Inc., New York, NY, 1986
• 11: Dan I Moldovan , Jose A. B Fortes, Partitioning and mapping algorithms into fixed size systolic arrays, IEEE Transactions on Computers, v.35 n.1, p.1-12, Jan. 1986 [doi>10.1109/TC.1986.1676652]
• 12: Liu L.S., Ho C.W. and Sheu J.P., On the Parallelism of Nested For-loops Using Index Shift Method, in Proceedings the 1090 Int. Conference on Parallel Processing, vo. II, St. Charles (IL), August 1990.
• 13: Darte A. and Robert Y., Scheduling Uniform Loop Nests, Research Report no. 92-10, Laboratoire de l'Informatique du Parallelisme, Ecole Normale Superieure de Lyon (France), February 1992.
• 14: Wayne Kelly , William Pugh, Generating schedules and code within a unified reordering transformation framework, University of Maryland at College Park, College Park, MD, 1992
• 15: Ayguade E., Labarta J., Torres J., Llaberia J.M. and Valero M., Parallelism Evaluation and Partitioning of Nested Loops for Shared Memory Multiprocessors, chapter 11 of Advances in Langmtges cmd Compilers for Parallel Processing, The MIT Press, 1991.
• 16: Wei Li , Keshav Pingali, Access normalization: loop restructuring for NUMA compilers, Proceedings of the fifth international conference on Architectural support for programming languages and operating systems, p.285-295, October 12-15, 1992, Boston, Massachusetts, United States

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Multiple-instruction-stream, multiple-data-stream processors (MIMD)

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

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices

General Terms:
Algorithms, Design