Why Systolic Arrays: the Real Answer

S. Rajopadhye and P. Quinton, IRISA, Rennes

A tutorial given at IEEE High Performance Computing Conference
Trivandrum, India, Dec 1996


Seventeen years after Kung and Leiserson gave us a catchy name, what have we learnt from systolic arrays?

This tutorial describes a key contribution of the research on systolic array synthesis, namely the "polyhedral model". This model provides a unified framework for reasoning about massively parallel, regular (not just nearest neighbor) computations. Its influence goes beyond its original scope, which is itself seeing a resurgence, given the recent trends in FPGAs and programmable logic devices, and the exponential advances in VLSI technology (for example, it is now possible to implement a simple risc core on 1 square millimeter).

The tutorial introduces the foundations of the model, and discusses its impact on loop parallelization, data parallel functional languages and program transformation methods. It includes simple exercises to reinforce the ideas, and will be accompanied by a demonstration of the Alpha language (a functional data parallel language based on the polyhedral model) and transformation system (prototype tools for implementing Alpha programs, either as dedicated VLSI, or as sequential or parallel programs) currently being developed at IRISA.

The tutorial was organized as follows:

In addition, a brief survey (with a fairly extensive but not necessarily complete bibliography) of the work in this area may be found in Systolic Origins of the Polyhedral Model

For more Information

You may visit API (Architectures Parallèles Intégrés, or Parallel VLSI Architectures) at Irisa but be forewarned that (like the entire intenet :-) it is "under construction". The IRISA library is maintained and up to date, and will get you to our technical reports among other things. The development of the Alpha transformation system is currently being done in collaboration with Doran Wilde at BYU, Provo, Utah, who also maintains a nice Alpha page

Recent work on Alpha has involved:


  • [Le Verge 92] Un environnement de transformations de programmes pour la synthèse d'architectures régulières PhD thesis, Université de Rennes, Octobre 1992.
  • [DQR 95] Structuration of the Alpha Langage in Massively Parallel Programming Models, Berlin, 1995 (pages 18-24)
  • [LeP+ 96] Generating Regular Arithmetic Circuits with ALPHARD P. Le Moenner, L. Perraudeau, P. Quinton, S. Rajopadhye, T. Risset, IRISA Technical Report PI-1001, March 1996; in Massively Parallel Computing Systems (MPCS 96), Ischia, Italy, May 1996
  • [QRW 95] Deriving Imperative Code from Functional Programs P. Quinton, S. Rajopadhye and D. Wilde, IRISA Technical Report PI-905, January 1995, presented at FPCA 95: ACM Conference on Functional Programming and Computer Architecture, San Diego, CA, July 1995
  • [QRR 96] Extension of the Alpha Language to Recurrences on Sparse Periodic Domains, P. Quinton, S. Rajopadhye and T. Risset, IRISA Technical Report PI-1001, July 1996; in IEEE Application Specific Array Processing Conference, Chicago, July 1996.
  • [DQ 94] Verification of Regular Architectures using Alpha: a Case Study C. Dezan and P. Quinton, IRISA Technical Report PI-823; in Application Specific Array Processing Conference, San Francisco, CA 1994.
  • [BC 97] A Logical Framework Verification of Alpha Programs, L. Bougé and D. Cachera, ENS Lyon Research Report 96-32 (can be accessed at the LIP library site.