Path: utzoo!utgpu!watmath!att!pacbell!ames!mailrus!purdue!decwrl!decvax!ima!esegue!compilers-sender
From: jps@cat.cmu.edu (James Salsman)
Newsgroups: comp.compilers
Subject: Re: compiling for parallel machines
Message-ID: <1989Aug7.164416.1731@esegue.uucp>
Date: 7 Aug 89 16:44:16 GMT
References: <1989Aug6.113745.309@esegue.uucp>
Sender: compilers-sender@esegue.uucp
Reply-To: jps@cat.cmu.edu (James Salsman)
Organization: Carnegie Mellon
Lines: 39
Approved: compilers@esegue.segue.bos.ma.us

In article <1989Aug6.113745.309@esegue.uucp> eric@snark.uu.net (Eric S. Raymond) writes:
> The software end is nowhere near this well-evolved. There are formalisms
> like CSP that allow us to discuss the behavior of parallel systems in a
> rigorous way, but no one has even come up with a convincing general attack on
> the higher-level problem -- automatic parallelization of algorithms expressed
> for a uniprocessor abstract machine in real languages (i.e. in the presence
> of multiple assignment, side-effects and data aliasing).
> 
> There is the really *hard* problem!

Automatic parallelization under the conditions you describe is SO
difficult that the resulting code usually isn't sped up enough to overcome
the practical problems of the added cost of the parallel hardware and the
time spent doing the compile.

At CMU, the Ergo project is working on the compilation of languages into
combinator graphs.  The idea being that combinator graphs may be
automatically parallelized.

Combinators are related to the type-free lambda calculus, so in practice
the combinator graph reduction engine must suffer the efficiency blow of
some sort of type-tag system.  In addition, combinator graphs must not
have local state (assignment or destructive data structure operations) if
they are to be parallelized.  This is a *BIG* lose.

I think the real solution is to start the wide-spread instruction of
parallel programming languages such as Occam, Linda, and *Lisp at the
university level.

:JAmes

Disclaimer:  I have nothing to do with the Ergo project.
-- 
:James P. Salsman (jps@CAT.CMU.EDU)
-- 
--
Send compilers articles to compilers@ima.isc.com or, perhaps, Levine@YALE.EDU
{ decvax | harvard | yale | bbn }!ima.  Meta-mail to ima!compilers-request.
Please send responses to the author of the message, not the poster.