Parallel Parsing and Compiling

Perhaps I can save some time by responding to Chou's (chou@cs.ucla.edu)
request about parallel parsing directly.


There has indeed been a great deal of work in parallel parsing and
in parallel execution of other phases of compilation as well. Here is
a brief overview:


Parallel lexing: this is well understood. A log time (i.e. time logarithmic
in the length of the input) algorithm was discovered by Schell and
implemented and popularised by Hillis and Steele. It is very generally
applicable.


Parallel parsing: this has been studied by practitioners and theoreticians.
Many results are known. CFL can be parsed in polylog time using an
impractical number of processors. Subclasses can be parsed on a linear
number of processors in polylog time -- many such subclasses are known.
Their mutual inclusions and the largest such subclass are not known.
Deterministic CFL can be practically parsed in log time with reasonable
numbers of processors -- pathological examples will take much longer.


Semantic analysis: this is well understood for moderately parallel
architectures (work by Wortman et al., Vandevoorde). Some attempts
to attack it using attribute grammars have been tried (see Paris WAGA
proceedings). No results using large scale parallelism.


Optimization: some work using moderate parallelism.


Parallelizing parsing will obviously not make a dramatic difference
to compiler performance by itself because it's a small part of where
the time goes. People began with it because it's formally understood.
In any case, a parallel compiler wouldn't sensibly have a sequential
parser, so something had to be done.


The opportunities for speeding up compilation lie mainly in the later
phases, particularly optimization which is becoming steadily more
important. There are many opportunities for research here.


David Barnard and I maintain an electronic mailing list at Queen's.
If you want to be added to the list, send your physical and email
address to compile-request@qucis.queensu.ca. To send a message to the
list, post to compile@qucis.queensu.ca.


We also maintain an on-line bibliography on parallel compilation which
you may want if you'd like to read about work in the area. It's in
BiBTeX format. To request a copy send me email (skill@qucis.queensu.ca).
We invite all researchers in the area to tell us when they publish a
paper or tech report that's relevant.


The first Workshop on Parallel Compilation took place last May. Proceedings
may be obtained by sending $C15 to:
                                        Heather Ball
                                        Rm 215 Richardson Hall
                                        Queen's University
                                        Kingston Ontario
                                        Canada K7L 3N6
A pro forma invoice may be requested from heather@qucis.queensu.ca for
those who need it.


We have recently completed a survey paper on the whole area of parallel
compilation. It will be available in the Queen's tech report series.
I'll post a further note when it's available.


                                                                    -David Skillicorn
--

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