Summary of Dataflow compilers and architecture responses (Keith L. Breinholt)
Thu, 9 May 91 11:09:02 -0600

          From comp.compilers

Related articles
Summary of Dataflow compilers and architecture responses (1991-05-09)
| List of all articles for this month |

Newsgroups: comp.compilers
From: (Keith L. Breinholt)
Summary: Monsoon, Id...
Keywords: dataflow, architecture, summary
Organization: University of Utah, Computer Science Dept.
Date: Thu, 9 May 91 11:09:02 -0600

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 (


Reply-To: (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 Hicks)


  We in the Computational Structures Group (led by Prof. Arvind, Prof.
Nikhil, and Prof. Papadopoulos) have done alot of work programming Dataflow

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

            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

            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
  Id Compiler Hacker
  MIT Computation Structures Group
  545 Technology Square, room 226
  Cambridge, MA 02142


Reply-To: (Bob Greiner)

MIT and Motorola are building Monsoon (data flow hardware) and Id (Functional
language). See the recent comp.arch posting
for some more details. The head of the project is
        Professor Arvind

        MIT Laboratory for Computer Science
        545 Technology Square, Cambridge, MA 02139, USA
 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
for more details. We don't have publishable results yet.

Hope this helps.

Bob Greiner,

Keith L. Breinholt ;; INTERNET:
Unisys, Unix Systems Group ;; UUCP: {att,sun,uplherc}!unislc!klb

Post a followup to this message

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