Towards systolizing compilation

Summary A scheme for the compilation of imperative or functional programs into systolic programs is demonstrated on matrix composition/decomposition and Gauss-Jordan elimination. Using this scheme, programs for the processor network Warp and for several transputer networks have been generated. Christian Lengauer holds a Dipl. Math. (1976) from the Free University of Berlin, and an M.Sc (1978) and Ph.D. (1982) in Computer Science from the University of Toronto. He was an Assistant Professor of Computer Sciences at The University of Texas at Austin from 1982 to 1989 and is presently a Lecturer in Computer Science at the University of Edinburgh. His past research has been in the areas of systolic design, formal semantics and program construction, and automated theorem proving. Michael Barnett received a B.A. in Computer Science from Brooklyn College/City University of New York in 1985, and is currently a Ph.d. candidate at the University of Texas at Austin, where he has been since 1986. From 1985 to 1986 he worked at IBM's T.J. Watson Research Center. His current research interests include formal methods, programming methodology, and functional programming. Duncan G. Hudson III received the B.A. degree in computer sciences from The University of Texas at Austin in 1987 and the M.S.C.S. degree in computer sciences from The University of Texas at Austin in 1989. He has worked as a Graduate Research Assistant at The University of Texas at Austin in the areas of graphical parallel programming environments, parallel numerical algorithms, and objectoriented programming languages for parallel architectures and as a Software Design Engineer at Texas Instruments in the areas of objectoriented databases and parallel image understanding. He is currently a Ph.D. candidate in the Department of Computer Sciences at The University of Texas at Austin. His current research interests include parallel architectures and algorithms and parallelizing compilers.This research was supported in part by the following funding agencies: through Carnegie-Mellon University by the Defense Advanced Research Projects Agency monitored by the Space and Naval Warfare Systems Command under Contract N00039-87-C-0251 and by the Office of Naval Research under Contracts N00014-87-K-0385 and N00014-87-K-0533; through Oxford University by the Science and Engineering Research Council under Contract GR/E 63902; through the University of Texas at Austin by the Office of Naval Research under Contract N00014-86-K-0763 and by the National Science Foundation under Contract DCR-8610427