kbreinho@peruvian.utah.edu (Keith L. Breinholt) (05/10/91)
Thanks to all who responded to my request for information on programming dataflow machines. Here is a summary of the information that I got. I edited out information that seemed redundant amoung the replys as a whole. If anyone wants to add to this, please do. I'd be interested in hearing about other dataflow architectures. Keith L. Breinholt (kbreinho@peruvian.utah.edu) -------------------------------------------------------------------------- Reply-To: jrbd@craycos.com (James Davies) Organization: Cray Computer Corporation I recently saw an announcement on the net for a dataflow programming class at MIT. The principal person behind it was Arvind (who apparently has returned from UC-Irvine). The announcement mentioned the Monsoon dataflow machine and implied that they have a working prototype. I would suggest contacting him for up-to-date references. For older references, try getting a copy of Eugene Miya's parallel processing reading list. It has several dataflow papers, and also has the seminal anti-dataflow paper from Kuck, Padua, etc. at Illinois. ------------------------------------------------------------------------- Reply-To: jamey@juicy-juice.lcs.mit.edu (Jamey Hicks) Hi, We in the Computational Structures Group (led by Prof. Arvind, Prof. Nikhil, and Prof. Papadopoulos) have done alot of work programming Dataflow machines. We choose to use Id, a functional language, or really, an implicitly parallel almost functional language, because it allows us to express parallel algorithms in parallel. In a normal imperative language, you have to write sequential programs to implement parallel algorithms, and either add annotations or have the compiler extract parallelism, or use the communicating sequential processes model of parallelism. I think those approaches are either ineffective (annotations and parallelizing compilers) or more difficult than necessary (CSP). We have a compiler that takes Id to dataflow graphs in two steps: first to program graphs which have dataflow instructions corresponding to language primitives: apply, if, while, make-tuple, select, make-array, i-fetch, etc. Most optimizations are performed at this level. This form of the graph has enough information to be executable by an abstract machine (unlike many dataflow graph intermediate forms that lack control flow information). Then the program graph is translated into a dataflow graph consisting of machine instructions (for TTDA abstract machine or Monsoon dataflow hardware). One of the biggest problems we have is restricting the parallelism present in our programs so that machine resources are used efficiently. There is also a compiler from Id to sequential code. This path yields execution times between that of C and Lisp for the same algorithms. So Id itself is not an exceedingly inefficient language. (See this year's ASPLOS proceedings --- the paper is by David Culler). Here is a reference for compiling C to dataflow machines: @InCollection(Veen90, Author = {Veen, Arthur H. and Reiner van den Born}, Title = {Compiling C for the DTN Dataflow Computer}, BookTitle = {Dataflow Computers}, Year = {1990}, Editor = {J. L. Gaudiot and L. Bic}, Note = {Preprint} ) Also, see work by Ferrante and Cytron at IBM about compiling Fortran to Static Single Assignment form (almost a dataflow graph), Pingali at Cornell about compiling Fortran to dataflow graphs and Ballance and Ottenstein at U. of New Mexico about compiling Fortran to program dependence webs. references: @InProceedings(choi91, Author = {Choi, Jong-Deok and Cytron, Ron and Ferrante, Jeanne}, Title = {Automatic Construction of Sparse Data Flow Evaluation Graphs}, Booktitle = popl91, Year = {1991}, Publisher = acm, Address = acmaddress, Month = jan ) @InProceedings(ballance90a, Author = {Ballance, Robert A. and Maccabe, Arthur B. and Ottenstein, Karl J.}, Title = {The Program Dependence Web: A Representation Supporting Control-, Data- and Demand-Driven Interpretation of Imperative Languages}, BookTitle = {SIGPLAN '90 Conference on Programming Language Design and Implementation}, Year = 1990, Organization = {ACM} ) Also, you might be interested in the Dataflow summer course at MIT: Jamey Hicks jamey@lcs.mit.edu Id Compiler Hacker MIT Computation Structures Group 545 Technology Square, room 226 Cambridge, MA 02142 ---------------------------------------------------------------------------- Reply-To: bobg@phx.mcd.mot.com (Bob Greiner) MIT and Motorola are building Monsoon (data flow hardware) and Id (Functional language). See the recent comp.arch posting <JAMEY.91Apr17175636@au-bon-pain.lcs.mit.edu> for some more details. The head of the project is Professor Arvind MIT Laboratory for Computer Science 545 Technology Square, Cambridge, MA 02139, USA arvind@lcs.mit.edu Tel: (617)-253-6090 Fax: (617)-253-6652 Compiler research on imperative languages for Monsoon is going on at Motorola's Cambridge Research Center. Contact Ken Traub (617) 621-0931 kt@mcrc.mot.com for more details. We don't have publishable results yet. Hope this helps. Bob Greiner, bobg@phx.mcd.mot.com -- Keith L. Breinholt ;; INTERNET: kbreinho@peruvian.utah.edu Unisys, Unix Systems Group ;; UUCP: {att,sun,uplherc}!unislc!klb -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request.