ALPHA
Alpha: A language based on polyhedra
presented by S. Rajopadhye, Dagstuhl, Feb 1997
Alpha a functional, data parallel language based on polyhedra was originally
designed by Mauras (1989) to serve as a tool for manipulating and transforming
systems of affine recurrence equations in the context of systolic array
synthesis. In this talk, I present the basic language, discuss the
motivations behind its design and describe how affine dependency functions,
polyhedral domains and unimodular transformations interact in a coherent
manner an empower two important properties of the language: normalization and
change-of-basis (transparencies).
The talk was actually part of a longer series of lectures described below:
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
Abstract:
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.
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:
Introduction (transparencies)
Alpha (my Dagstuhl transparencies)
Scheduling (transparencies)
Placement Compilation and Communication (transparencies)
Conclusions (transparencies)
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 the addition of reductions to the
language [Le Verge 1992] the development of subsystems
so that computations can be expressed in a modular and hierarchical
manner [DQR 95], definition of a (proper) subset called
AlpHard for defining regular (systolic) VLSI arrays [LeP+
96], development of a transformation system based on the
Mathematica software, tools for static analysis of Alpha programs,
compilation of Alpha [QRW 95] to sequential and parallel
general purpose machines, extensions of the language
[QRR96] to sparse domains (domains which are
defined as the
intersections of lattices and polyhedra), and some work on verification
by people in our group [DQ 94], and also by
Bougé and
Cachera at ENS Lyon [BC 97].
References:
[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.