rst@cs.hull.ac.uk (Rob Turner) (11/07/90)
Thanks to all who responded to my request for information concerning the execution of functional languages on parallel machines. A summary of the mail I received (in vaguely alphabetical order) is as follows... ---------------------------------------------------------------------- >From bliss@sp64.csrd.uiuc.edu Sat Oct 27 09:18:45 1990 Our LISP guru here is Luddy Harrison (harrison@csrd.uiuc.edu). You can get a copy of his thesis (Master's & Phd) by sending mail to lybnn rubarts rubarts@csrd.uiuc.edu (obvious, internet), or writing to Center fro Supercomputing research & development 306 Talbot lab 104 S Wright St Urbana, IL 61801 He did get numerical scheme programs to parallelize/vectorize good enough to run faster on an Alliant FX/8 than they did on the Cray XM/P. bb ---------------------------------------------------------------------- >From briscoe-duke@cs.yale.edu Wed Oct 31 10:28:48 1990 There is a new book which I haven't seen, but which you would probably find helpful. "Parallel Functional Programming and Environments", McGraw Hill (Series in Supercomputing and Parallel Processing", 1990. You would probably also be helped by looking at some papers on compiling Scheme or Lisp. Mul-T and Multilisp are parallel extensions to Scheme, so most of the compilation problem is the same as Scheme with some extra stuff for parallelism. I'm working on a parallel version of Haskell (I'm one of Paul Hudak's students) which will produce Mul-T code for the Encore Multimax. Our usual Haskell compiler produces T code. I hope to be able to write this work up in a few months. About Mul-T, you should look at the paper by Mohr, Kranz, and Halstead on "Lazy task creation" in the 1990 ACM Lisp and Functional Programming proceedings. Duke ---------------------------------------------------------------------- >From Burnett@csvax.cs.ukans.edu Thu Nov 1 08:27:56 1990 You would probably be very interested in "The paralation model" by Gary Sabot, 1988, MIT Press, Cambridge, Mass, ISBN 0-262-19277-2, QA76.6.S216 1988. Based on his dissertation, he develops an architecture independent model both synchronous and asynchronous parallel processing, and then tests his theories on a version of Lisp. Margaret Burnett ---------------------------------------------------------------------- >From dwights@cse.ogi.edu Sun Oct 28 06:06:48 1990 I would suggest you get in touch with Clifford Walinsky at Dartmouth (an old OGI classmate of mine) who has recently presented his work at a major confernece this year on compilation of functional programs for parallel machines. - Dwight Spencer dwights@cse.ogi.edu ------------------------------------------------------------------------ >From ewright%convex@uxc.cso.uiuc.edu Fri Nov 2 11:52:41 1990 Dr. Peter Kogge has done a lot of research on this and discusses it in his book, Alternative Computer Concepts. I took his course two years ago and we used the manuscript as a text; I would assume it has been published by now. ------------------------------------------------------------------------ >From fernau%de.uka.ira%de.uka.ira.iraun1@relay.cs.net Sat Oct 27 16:52:44 1990 Pretty much work is done at Kiel University (FRG) by Prof. Dr. Alois Jammel. It might be interesting for you to get in contact with him: Prof. Dr. A. Jammel Institut f\"ur Informatik und Mathematik Christian-Albrechts-Universit\"at Kiel D - 2300 Kiel 1 ------------------------------------------------------------------------- >From forstall@boojum.berkeley.edu Sat Oct 27 12:59:56 1990 A local database dump on "functional parallel implementation": %A J.F. Giorgi %A D. Le M\'etayer %T Continuation-Based Parallel Implementation of Functional Programming Languages %K LISPFP LISP FP 1990 %J Symp. on LISP and Functional Prog. %D June 1990 %A P. H. Hartel\ et\ al. %T A PARALLEL FUNCTIONAL IMPLEMENTATION OF RANGE QUERIES %I Univ. of Amsterdam, Institute for Language, Logic and Information (ITLI) %R CT-89-05 %D 1989 %W SU lib. #112097 %A M. S. Joy %T PARALLEL EVALUATION OF FUNCTIONAL PROGRAMS - A BIBLIOGRAPHY %I Univ. of Warwick, Dept. of Comp. Sci., Functional Language Implementation Project %R Document 18 %D 1989 %W SU lib. #112902 %A T. J. W. Clarke %T IMPLEMENTING AGGREGATES IN PARALLEL FUNCTIONAL LANGUAGES %I Univ. of Cambridge, Comp. Laboratory %R 176 %D 1989 %W SU lib. #113285 %A Kennaway J. %A M. R. Sleep %T Parallel Implementation of Functional Languages %J 1982 International Conference on Parallel Processing %P 168-170 %D AUG 1982 --Bruce Forstall (forstall@sequoia.berkeley.edu) ----------------------------------------------------------------------- >From fst@doc.ic.ac.uk Wed Oct 31 19:30:41 1990 I'm a final year student here at Imperial. For my project I am implementing an intermediate functional language interpreter on a parallel machine (an ancient Sequent Balance -- multiprocessor, shared memory). Frank. ------------------------------------------------------------------------ >From geoff@cosc.canterbury.ac.nz Fri Nov 2 11:50:49 1990 "Multiprocessor Execution of Functional Programs" Benjamin Goldberg International Journal of Parallel Programming, Vol 17, No 5, 1988 (possibly '89) pp 425-473. (describes research to demonstrate feasibilty of parallel implementations) "Lazy Task Creation: A Technique for Increasing the Granuality of Parallel Programs" Eric Mohr, David A Kranz, Robert H Halsted Jr proceedings of the 1990 ACM Conference on Lisp and Functional Programming. The next few can be found in : E. Odijk, M. Rem, and J. -C. Syre, editors, { PARLE '89 Parallel Architectures and Languages Europe: Vol I: Parallel Architectures}, volume 365 of {Lecture Notes in Computer Science}, pp136-157, Eindhoven, The Netherlands, June 1989. Springer-Verlag "Distributed implementation of programmed graph reduction" R. Loogen, H. Kuchen, and W. Damm, pages 136--157. see also pp158-175 for "Parallel object-oriented descriptions of graph reduction machines" D.Bolton, C. Hankin, P.Kelly [BHK89] D. Bolton, C. Hankin, and P. Kelly. Parallel object-orientated descriptions of graph reduction machines. In Odijk et al. \cite{zparle89v1}, pages 158--175. [Bur89] G. L. Burn. Overview of a parallel reduction mechine project ii. In Odijk et al. \cite{zparle89v1}, pages 385--396. [HV89] L. O. Hertzberger and W. G. Vree. A course grain parallel architecture for functional languages. In Odijk et al. \cite{zparle89v1}, pages 269--285. [PJCS89] Simon L. Peyton Jones, C. Clack, and J. Salkild. High performance parallel graph reduction. In Odijk et al. \cite{zparle89v1}, pages 193--206. [CCC{\etalchar+}89] A. Contessa, E. Cousin, C. Coustet, M. Cubero-Castan, G. Durrieu, B. Lecussan, M. Lemaitre, and P. Ng. Ma{RS}, a combinator graph reduction multiprocessor. ================================================================ "A safe approach to parrallel combinator reduction." C.L. Hankin, G.L. Burn, S.L.Peyton-Jones vol 213 of Lecture Notes in Computer Science, pp 99-110 Saarbrucken, Germany, March 1986. Springer-Verlag [BGRJ89] D.J. Bevan, G.L.Burn, R.J.Karis, and J.D.Rodson. Principles for the design of the distributed memory architecture for parallel graph reduction. {\em The Computer Journal}, 32(5):461--469, October 1989. [MS89] G. Marino and G. Succi. Data structures for parallel execution of functional languages. In : E. Odijk, M. Rem, and J.-C. Syre, editors. {\em PARLE '89 Parallel Architectures and Languages Europe: Volume II: Parallel Languages}, volume 366 of {\em Lecture Notes in Computer Science}, Eindhoven, The Netherlands, June 1989. Springer-Verlag. pages 346--356. [PJ89] Simon L. Peyton Jones. Parallel implementations of functional programming languages. {\em The Computer Journal}, 32(2):175--186, April 1989. (NB: Published after his book that you mentioned) [Bur87] P. C. Burkimsher. Combinator reduction in a shared-memory multiprocessor. {\em The Computer Journal}, 30(3):214--222, 1987. Geoff McIlraith. ----------------------------------------------------------------------- >From IANNUCCI%watson%com.ibm@almaden.ibm.com Wed Oct 31 06:23:33 1990 My book, entitled "Parallel Machines: Parallel Machine Languages" Kluwer Academic Publishers April, 1990 ISBN 0-7923-9101-2 deals with code generation for a class of architectures known as "hybrid dataflow". I discuss specifically the issues of partitioning and translating data flow graphs derived from Id for such machines. Bob ------------------------------------------------------------------------- >From kale%edu.uiuc.cs@m.cs.uiuc.edu Mon Oct 29 09:32:33 1990 Me and my students (particularly: B. Ramkumar) have been working on parallel execution of Logic Programs. We have designed an abstract machine, implemented a compiler that compiles to it, and a parallel byte code interpreter (written using the chare kernel machine independent parallel programming system). There are several papers describing this, and a PhD thesis coming out soon (being defended tomorrow). I think many of the issues involved in this are similar to those in functional languages. (Note: we are NOT doing "commited choice languages"; rather it is parallel execution of and/or parallel Logic programs with don't know non-determinism). L.V.Kale ---------------------------------------------------------------------- >From kend%data%uucp.mcsun@mcsun.eu.net Thu Oct 25 21:40:11 1990 There is a Springer-Verlag lecture notes publication of a parallel lisp conference which you would find interesting. I forget the number, but have it on order as: > "Parallel Lisp: Languages and Systems", T. Ito and R. Halstead (eds), > ISBN 0-387-52782-6. The bibliographies should keep you busy for a while... Enjoy, -Ken kend@data.uucp ---------------------------------------------------------------------- >From kh@cs.gla.ac.uk Thu Oct 25 13:31:31 1990 Simon Peyton Jones, The Implementation of Functional Programming Languages, Prentice Hall International, 1987. (The standard text on graph reduction implementation techniques). Try also: Paul Kelly, Functional Programming for Loosely Coupled Multiprocessors, Pitman/MIT Resarch Monographs in Parallel and Distributed Computing, 1989. Kevin Hammond, Parallel SML: A Functional Language and its Implementation in Dactl, Pitman/MIT Resarch Monographs in Parallel and Distributed Computing, to appear November 1990. Paul's book describes Caliban, a functional language with process descriptions, but doesn't really get into low-level detail. My book gives a *detailed* semantics-derived description of a compiler from pure SML to Dactl, a parallel graph-rewriting based intermediate language. There is some discussion of Dactl implementations for real machines such as the transputer. Look at the work done at: Imperial College (Caliban -- Paul Kelly (Alice/SIMD -- John Darlington, Mike Reeve) Southampton (TUKI/FAST -- Hugh Glaser) Glasgow/UCL (GRIP -- Simon Peyton Jones, myself...) Edinburgh/Glasgow (Algorithmic Skeletons -- Murray Cole) UEA (Dactl -- John Glauert, Ronan Sleep, Richard Kennaway, myself...) Nijmegen (Clean -- Rinus Plasmeijer, Marko van Eekelen) Chalmers (nu-G Machine -- Lennart Augustsson) Yale (ALFL -- Ben Goldberg) (ParaFunctional Programming -- Paul Hudak) MIT (Monsoon -- Papadopoulos) (Id-Nouveau -- Arvind/Nikhil) Manchester (Dataflow -- Ian Watson, ...) (Flagship/EDS -- Ian Watson, ...) Aachen (FL languages -- Rita Loogen) GEC/Manchester/ (Evaluation Transformers -- Geoff Burns) Imperial (A parallel G-machine -- Geoff Burns/David Lester) The MIT work is dataflow rather than functional programming, but there's a lot to be learned from their systems. The Flagship machine supports a subset of Dactl. Looking through recent FPCAs and PARLEs should also help to get you started. Kevin ------------------------------------------------------------------------ >From kissell%com.ncube@cse.ogi.edu Sat Oct 27 18:53:17 1990 Chris Clack at UCL (clack@cs.ucl.ac.uk) was one of Peyton Jones' collaborators whom you may already know. I believe this is or was precisely his area of interest. Kevin Kissell >From kissell%com.ncube@cse.ogi.edu Mon Oct 29 02:44:49 1990 ---------------------------------------------------------------------- >From Marco.Zagha@enquirer.scandal.cs.cmu.edu Sun Oct 28 21:19:29 1990 I recommend "A Practical Functional Program for the CRAY X-MP" by James M. Boyle and Terence J. Harmer, July 1990, Mathematcis and Computer Science Division, Argonne National Laboratory, Preprint MCS-P159-0690. == Marco ------------------------------------------------------------------------ >From markf@altdorf.ai.mit.edu Sat Oct 27 23:08:56 1990 I have a book (which I haven't read yet) by Paul Kelly of the Imperial College of Science and Technology entitled "Functional Programming for Loosely-coupled Multiprocessors. By "loosely-coupled multiprocessors" he means "a collection of processing elements (PE's), linked by an interconnection network with the property that communication between neighboring PE's is much more efficient than communication between non-neighboring PE's". The language that he uses as an example is a subset of Miranda. It is published by Pitman Publishing (London) and available in the US through MIT press. The ISDN number is 0-262-61057-4 -Mark ---------------------------------------------------------------------- >From mic@lfcs.ed.ac.uk Thu Oct 25 09:37:10 1990 Paul Kelly's book on his "Caliban" language, "Functional Programming for Loosely Coupled MultiProcessors", Pitman 1989 is good. Also try to get hold of a copy of Ben Goldberg's Phd thesis, "Multiprocessor Execution of Functional Programs", Yale/DCS/RR-618, 1988, or a least take a look at his article in Int. journal of Parallel Programming vol 17 no 5. Murray Cole. ---------------------------------------------------------------------- >From mshute@r1.cs.man.ac.uk Wed Oct 31 13:57:58 1990 There are a large number ofpapers, proceedings, and books to draw from. There are a large number of people who you could contact on Janet alone (not least of all, Simon Peyton Jones in Glasgow, and Chris Hankin (co-author of a predecessor to Simon's book) at Imperial College). -- Malcolm SHUTE. (The AM Mollusc: v_@_ ) Disclaimer: all ----------------------------------------------------------------------- >From norman@d.cs.okstate.edu Sun Oct 28 13:08:11 1990 Try these dissertations: Vivek Sarkar "Partitioning and Scheduling Parallel Programs for Multiprocessors" The MIT Press 1989 ISBN 0-262-69130-2 (pbk.) Paul Kelly "Functional Programming for Loosely-coupled Multiprocessors" The MIT Press 1989 ISBN 0-262-61057-4 (pbk.) ---------------------------------------------------------------------- >From oliver@karakorum.berkeley.edu Thu Nov 1 00:10:28 1990 Well, there's been quite a lot of work on that in the research community. Not all that much has made it into books yet, since it is still very much a research issue. Some groups you might want to look into are: - MIT -- the ID project - Paul Hudak and co. at Yale -- serial combinators, array comprehensions - Lawrence-Livermore National Lab -- the SISAL project As one beginning, which would get you some citations, you could get David Culler's thesis from MIT. Also look at the 1989 ACM Design and Implementation conference for Anderson and Hudak's paper on compiling array comprehensions. I have lots of other citations, since my thesis topic is related to this issue. - Oliver Sharp ---------------------------------------------------------------------- >From pardo%edu.washington.cs@june.cs.washington.edu Mon Oct 29 09:50:28 1990 I'm including much more stuff than you asked for because it was easy. I'll leave it to you to look for things that match your desires (e.g., searchin for the words ``parallel'' or ``concurrent'' on the same line as ``functional''). The list is by no means complete. There was a paper at the 1990 PPoPP (Principles and Practice of Parallel Programming) by somebody doing parallel weather using a functional programming language. ["Functional" titles follow - Rob] %X /u1/rrh/bib/rrh.d/lisp90.ref %A Clifford Walinsky %A Deb Banerjee %T A Functional Programming Language Compiler for Massively Parallel Computers %K LISPFP LISP FP 1990 %J LISP90 %X /u1/rrh/bib/rrh.d/lisp90.ref %A J.F. Giorgi %A D. Le Metayer %T Continuation-Based Parallel Implementation of Functional Programming Languages %K LISPFP LISP FP 1990 %J LISP90 %X /u1/rrh/bib/rrh.d/graphmatch.ref %B PROC of a Workshop on Graph Reduction (LNCS 279) %E Joseph H. Fasel %E Robert M. Keller %D SEP 1986 %C Santa Fe, NM %K whole book %K term rewriting, G-machine, parallel %X this is graph reduction ala functional language interpretation %X /u1/rrh/bib/rrh.d/peterd.ref %T Partitioning Parallel Programs for Macro-Dataflow %A V. Sarkar %A J. Hennessey %J PROC ACM CONF on Lisp and Functional Programming %D AUG 1986 %P 202-211 %X From: rro@bizet.CS.ColoState.Edu (Rod Oldehoeft) SISAL bibliography 6/1/89 -peterd 8/8/89 %X /u1/rrh/bib/rrh.d/language.ref %A F. W. Burton %T Annotations to Control Parallelism and Reduction Order in the Distributed Evaluation of Functional Programs %J TOPLAS %P 159-174 %D Apr 1984 %X /u1/rrh/bib/rrh.d/language.ref %A J. Darlington %A M. Reeve %T ALICE: A Multi-processor Reduction Machine for the Parallel Evaluation of Applicative Languages %J PROC Functional Programming Languages Computer Architecture %P 65-75 %D 1981 %X /u1/rrh/bib/rrh.d/language.ref %A Kennaway J. %A M. R. Sleep %T Parallel Implementation of Functional Languages %J 1982 International Conference on Parallel Processing %P 168-170 %D AUG 1982 %X /u1/rrh/bib/rrh.d/hardware.ref %T Functionally Parallel Architecture for Array Processors %A Edmund U. Cohler %A James E. Storer %J Computer %V 14 %N 9 %D September 1981 %P 28-36 ---------------------------------------------------------------------- >From John.Pieper@b.gp.cs.cmu.edu Mon Oct 29 04:29:23 1990 in a few months you can look for alan sussman's thesis from Carnegie Mellon. als@cs.cmu.edu for more info. ----------------------------------------------------------------------- >From phjk@doc.ic.ac.uk Fri Oct 26 15:04:48 1990 You might find my book of interest: Functional Programming for Loosely-coupled Multiprocessors Paul HJ Kelly Pitman/MIT Press Paul Kelly ----------------------------------------------------------------------- >From daniel@eng.cam.ac.uk Thu Oct 25 09:49:02 1990 You might want to contact Eng Teng Ong at Oklahoma State University. He is a Ph.D. candidate there who has published an article on a parallel FP server for the Intel hypercube. I don't remember the title of the article, but it is supposed to appear in the Proceedings of DMCC5 (Distributed Memory Concurrent Computers). These proceedings have recently been mailed to the participants of the conference. I beleve Ong's e-mail addreses is: ong@a.cs.okstate.edu if that address does not work, you might get in touch with his advisor, Dr. George, at kmg@a.cs.okstate.edu. Ron Daniel --------------------------------------------------------------------- >From rpandey@mist.cs.orst.edu Wed Oct 31 13:54:49 1990 There is a lot of good stuff in the book "Masssively Parallel Computing" by Almasi and Gottlieb. I am working on an Intermediate form for compiling APL so that code generation for a variety of architectures is facilitated---this book had some good pointers for me. I believe the publisher is Benjamin-Cummings (but I'm not sure). Rajeev Pandey ----------------------------------------------------------------------- >From NN1%earn.AWIWUW11@earn-relay.ac.uk Tue Oct 30 20:42:40 1990 There is a book dealing with the parallel implementation of functional programming languages (especially for the PAM = Pamela Abstract Machine): Rita Loogen. Parallele Implementierung funktionaler Programmiersprachen. Springer, Informatik-Fachberichte 232, Berlin, 1990. Unfortunately, the book is written in German. However, maybe it is of any use for you. Wolfgang Schreiner -------------------------------------------------------------------- >From sjohnson@iuvax.cs.indiana.edu Sat Oct 27 19:05:41 1990 You'll undoubtedly be referred to the proceedings of the Functional Programming Languages and Computer Architectures conferences. -------------------------------------------------------------------- >From soerenop@daimi.aau.dk Thu Oct 25 19:46:53 1990 The book you mention (S.L. Peyton Jones) I consider being a very nice introduction to the area of implementing functional languages. A lot of the ideas from this book, especially concerning graph reduction and G-machines can be used for parallel implementations as well. If the G-machine way is the way you want to go, I can recommend the proposals for a parallel shared memory implementation by Geoffrey Burn[1]. Together with two other students here at DAIMI I have been involved in making an implementation of Burn's G-machine on a network of transputers. Another way to do things is to look into the ideas of Paul Kelly.[2] Or yet another: The GRIP project[3]. Or Benjamin Goldberg[3]. Of the four Burn's work is the one getting closest to an actual implementation, but both Kelly and Goldberg has also some interesting ideas of how to detect the parallelism. The GRIP project I don't know that much about. Soeren Refs: [1]: Geoffrey L. Burn "A Shared Memory Parallel G-Machine Based on the Evaluation Transformer Model of Computation" ESPRIT Project 415, Subproject B, Doc. No.114. [2]: Paul Kelly "Functional Programming for Loosely-Coupled Multiprocessors" Pitman, London 1989. [3]: Peyton Jones, Chris Clarck, Jon Sarklid & Mark Hardie "GRIP: a High Performance Architecture for Parallel Graph Reduction" Springer-Verlag LNCS 274, 1987. [4]: Benjamin Goldberg "Multiprocessor Execution of Functional Programs" International Journal of Parallel Programming, Vol. 17, No. 5, Okt. 1988 ------------------------------------------------------------------------- >From SUHLER%watson%com.ibm@almaden.ibm.com Sat Oct 27 19:06:11 1990 R. A. Iannucci, _Parallel Machines: Parallel Machine Languages_, Kluwer Academic Publishers, 1990. Arvind and K. Ekanadham, "Future Scientific Programming on Parallel Machines," _Journal of Parallel & Distributed Computing_, vol. 5, pp. 460 - 493, 1988. Paul A. Suhler ------------------------------------------------------------------------- >From waldman@robocop.nyu.edu Sat Oct 27 23:09:43 1990 There is a rather small book concerning Parallel Execution Of Functional Programs by Paul Kelly. It is published by the MIT PRESS. Marc -------------------------------------------------------------------------- Thanks again to everybody. I am sorry if I have forgotten anybody. I am still receiving the odd response, so if anything new comes to my notice I will pass it on. Rob ------------------------------------------------------------------ Robert Turner | rst@cs.hull.ac.uk Department of Computer Science | University of Hull | "In every real man a child is Hull HU6 7RX | hidden that wants to play" England | - Nietzsche