Constructing and exploiting linear schedules with prescribed parallelism

ABSTRACT

We present two new results of importance in code generation for and synthesis of synchronously scheduled parallel processor arrays and multicluster VLIWs. The first is a new practical method for constructing a linear schedule for the iterations of a loop nest that schedules precisely one iteration per cycle on each of a prescribed set of processors. While this problem goes back to the era in which systolic computation was in vogue, it has defied practical solution until now. We provide a closed form solution that enables the enumeration of all such schedules. The second result is a new technique that reduces the cost of code or hardware whose function is to control the flow of data and predicate operations, and to generate memory addresses. The key idea is that by using the mathematical structure of any of the conflict-free schedules we construct, a very shallow recurrence can be developed to inexpensively update these quantities.

REFERENCES

• 1: 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
• 2: Alain Darte, Regular partitioning for synthesizing fixed-size systolic arrays, Integration, the VLSI Journal, v.12 n.3, p.293-304, Dec. 1991 [doi>10.1016/0167-9260(91)90026-H]
• 3: DARTE, A. AND DELOSME, J.-M. 1990. Partitioning for array processors. Tech. Rep. 90-23, LIP, ENS-Lyon.
• 4: DARTE, A., SCHREIBER, R., RAU, B. R., AND VIVIEN, F. 1999. A constructive solution to the juggling problem in systolic array synthesis. Tech. Rep. RR1999-15, LIP, ENS-Lyon.
• 5: HAJOS, G. 1942. Uber einfache und mehrfache Bedeckung des n-dimensionalen Raumes mit einem Wurfelgitter. Mathematische Zeitschrifte 47, 427-467.
• 6: Graham M. Megson , Xian Chen, A synthesis method of LSGP partitioning for given-shape regular arrays, Proceedings of the 9th International Symposium on Parallel Processing, p.234-238, April 25-28, 1995
• 7: NEWMAN, M. 1972. Integral Matrices. Academic, New York.
• 8: RAU, B. R. 1996. Iterative modulo scheduling. Int. J. Parallel Process. 24, 3-64. Also available as HP Labs Tech. Rep. HPL-94-115.
• 9: Robert Schreiber , Shail Aditya , B. Ramakrishna Rau , Vinod Kathail , Scott Mahlke , Santosh Abraham , Greg Snider, High-Level Synthesis of Nonprogrammable Hardware Accelerators, Proceedings of the IEEE International Conference on Application-Specific Systems, Architectures, and Processors, p.113, July 10-12, 2000
• 10: Alexandeer Schrijver, Theory of linear and integer programming, John Wiley & Sons, Inc., New York, NY, 1986

INDEX TERMS

Primary Classification:
  B. Hardware
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION
      B.5.2 Design Aids

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

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

General Terms:
Algorithms, Design, Experimentation, Performance, Reliability, Theory

Keywords:
Linear schedule, multicluster VLIW, systolic array