Summary of Dataflow compilers and architecture responses

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
--

Return to the comp.compilers page.
Search the comp.compilers archives again.