Parallelizing Compilers (Summary) (Christian S. Collberg)
Thu, 31 Dec 1992 10:32:26 GMT

          From comp.compilers

Related articles
Parallelizing Compilers for Distributed Memory (1992-11-20)
Parallelizing Compilers (Summary) (1992-12-31)
| List of all articles for this month |

Newsgroups: comp.compilers
From: (Christian S. Collberg)
Organization: Department of Computer Science, Lund University
Date: Thu, 31 Dec 1992 10:32:26 GMT
Keywords: parallel, architecture, bibliography, summary
References: 92-11-118

Here is a (belated) summary of the replies I received to my request for
information on parallelizing compilers. Thanks to the following people who
provided information:

            Simon N Smith <>
   (Sachit R. Nadkarni)
            Qiang Alex Zhao <>
   (Lorie Liebrock)
   (Subhas Roy)
            Christian Lengauer <>
            Joe Hummel <jhummel@esp.ICS.UCI.EDU>
   (David R. Good)
   (Jean Louis Pazat)
   (Uli Kremer)
   (Pankaj Kumar)
   (David Lilja)
   (Lee Chia Ling)
            Rudi Hackenberg <>
            Gholamali Hedayat (JRG ra) <>
            Suresh Damodaran Kamal <>
            Steven Collins <>
   (Paul Havlak)
            Ramakumar Kosuru <>
            wismuell@Informatik.TU-Muenchen.DE (Roland Wismueller)
            Roger Peel <>

Here's the original request:

|> I have found lots of articles on vectorizing compilers. I have not,
|> however, been able to find any information on compilers which try to
|> discover parallelizable code and then attempt to map it to processes
|> on a distributed memory machine. Can someone help me to find the
|> relevant references?

And here are the replies. The first section contains concrete
bibliographic references, mostly in BibTeX format. I have not checked for
duplicates. The subsequent sections contain general comments. They have
been edited down for brevity.


"Compile Time Techniques for Data Distribution in Distributed Memory
Machines," Ramanujam and Sadayappan, IEEE PDS, vol2,No.4, October 1991.

/A/ Chapman, B. M.
/A/ Herbeck, H.
/A/ Zima, H. P.
Automatic Support for Data Distribution
Proceedings of the Sixth Distributed Memory Computing Conference, April 28 -
May 1, 1991, Portland, Oregon, IEEE Computer Society Press, 51-57

/A/ Zima, H. P.
/A/ Bast, H. J.
/A/ Gerndt M.
SUPERB: A tool for semi-automatic MIMD/SIMD parallelization
Parallel Computing, No. 6, 1988, 1-18

/A/ Gerndt, M.
Parallelization of Multigrid Programs in SUPERB
Proc. of the International Workshop on Compilers for Parallel Computers,
Dec. 3-5, 1990, Paris, France, 347 - 356

On the Serialisation of Parallel Programs
P.H. Welch & G.R.R. Justo,
in "Occam and the Transputer - Current Developments",
(proceedings of the 14th World Occam and Transputer User Group
Technical Meeting, Loughborough, September 1991).
J. Edwards (ed),
IOS Press (Amsterdam) 1991.
ISBN 90 5199 063 4

                Author = {C. Polychronopoulos and M. Girkar and M. Haghighat
                                and C. Lee and B. Leung and D. Schouten},
                Title = {The structure of {Parafrase-2}: An advanced
                                parallelizing compiler for {C} and {Fortran}},
                BookTitle = LCPC,
                Editor = {D. Gelernter and A. Nicolau and D. Padua},
                Year = 1990,
                Publisher = MIT-P}

                Author={F. Allen and M. Burke and P. Charles and R. Cytron and
J. Ferrante},
                Title={An Overview of the {PTRAN} Analysis System for Multiprocessing},
                BookTitle={Proceedings of the First
                                International Conference on Supercomputing},
                Address={Athens, Greece},

                Author = {J. R. Allen and K. Kennedy},
                Title = {Automatic Translation of {Fortran} Programs to Vector Form},
                Journal = TOPLAS,
                Volume = 9,
                Number = 4,
                Pages = {491--542},
                Month = Oct,
                Year = 1987}

                Author = {J. R. Allen and D. Callahan and K. Kennedy},
                Title = {Automatic Decomposition of Scientific
                                Programs for Parallel Execution},
                BookTitle = POPL87,
                Address = {Munich, Germany},
                Month = Jan,
                Year = 1987}

@string {JOS = "The Journal of Supercomputing"}

                Author = {L. Henderson and R. Hiromoto and O. Lubeck and M. Simmons},
                Title = {On The Use of Diagnostic Dependency-Analysis Tools in
Parallel Programming: Experiences Using {PTOOL}},
                Journal = JOS,
                Volume = 4,
                Pages = {83-96},
                Year = 1990}

@string {TOPDS = "{IEEE} Transactions on Parallel and
Distributed Systems"}

                Author = {K. Kennedy and K. S. McKinley and C. Tseng},
                Title = {Interactive Parallel Programming Using the
{ParaScope Editor}},
                Journal = TOPDS,
                Volume = 2,
                Number = 3,
                Pages = {329--341},
                Month = Jul,
                Year = 1991}

@string {ICS91 = "Proceedings of the 1991 ACM International Conference
                                on Supercomputing"}

                Author = {K. Kennedy and K. S. McKinley and C. Tseng},
                Title = {Analysis and Transformation in the {ParaScope Editor}},
                BookTitle = ICS91,
                Address = Cologne,
                Month = Jun,
                Year = 1991}

@string {LCPC91 = "Proceedings of the Fourth Workshop on Languages
                                and Compilers for Parallel Computing"}

                Author = {S. Hiranandani and K. Kennedy and C. Koelbel
                                and U. Kremer and C. Tseng},
                Title = {An Overview of the {Fortran D} Programming System},
                BookTitle = LCPC91,
                Address = SC,
                Month = Aug,
                Year = 1991}

                Author = {S. Hiranandani and K. Kennedy and C. Tseng},
                Title = {Compiler Support for Machine-Independent Parallel
                                Programming in {Fortran D}},
                BookTitle = {Compilers and Runtime Software for Scalable
                Editor = {J. Saltz and P. Mehrotra},
                Publisher = {Elsevier},
                Address = Amsterdam,
                Year = {to appear 1991}}

@string {SC91 = "Proceedings of Supercomputing '91"}

Author = {S. Hiranandani and K. Kennedy and C. Tseng},
Title = {Compiler Optimizations for {Fortran D} on {MIMD}
                 Distributed-Memory Machines},
BookTitle = SC91,
Address = Albuquerque,
Month = Nov,
Year = 1991}

    author = "A. S. Nickhil and R. S. Nickhil and K. K. Pingali",
    title = "{I}-structures: Data Structures for Parallel Computing",
    journal = "ACM trans. on Programming Languages and Systems",
    year = "1989",
    volume = "11",
    number = "4",
    pages = "598--632"
    author = "A. Rogers and K. Pingali",
    title = "Process Decomposition Through Locality of Reference",
    booktitle = "Conference on Programming Language Design
     and Implementation",
    year = "1989",
    pages = "69--80",
    organization = "ACM",
    month = "June 21--23"

    author = "A. P. Reeves",
    title = "Paragon: A Programming Paradigm for Multicomputer Systems",
    institution = "Cornell University",
    year = "1989",
    number = "EE-CEG-89-3",
    month = "January"
    author = "A. L. Cheung and A. P. Reeves",
    title = "The Paragon Multicomputer Environment: A First Implementation",
    institution = "Cornell University",
    year = "1989",
    number = "EE-CEG-89-9",
    month = "July"
    author = "A. P. Reeves",
    title = "The Paragon Programming Paradigm and Distributed
Memory Multicomputers",
    institution = "Cornell University",
    year = "1990",
    number = "EE-CEG-90-7",
    month = "June"

AUTHOR= "M. J. Quinn and P. J. Hatcher and K. C. Jourdenais",
TITLE = "Compiling {C}$^*$ Programs for a Hypercube Multicomputer",
YEAR= 1990
    author = "M. J. Quinn and P. J. Hatcher",
    title = "Compiling {SIMD} Programs for {MIMD} Architectures",
    booktitle = "ACM Sigplan (PPEALS)",
    year = "1990",
    OPTpages = "57--65"
AUTHOR= "M. J. Quinn and P. J. Hatcher",
TITLE = "Data Parallel Programming on Multicomputers",
JOURNAL="IEEE Trans. on Software Engineering",
                volume= " ",
                number= " ",
YEAR= 1990,
                month= "September"

    author = "M. Rosing and R. B. Schnabel and R. Weaver",
    title = "Dino: Summary and Examples",
    booktitle = "3' Conference on Hypercubes Concurrent Computers and
    year = "1988",
    pages = "472--481"
AUTHOR= "M. Rosing and R. P. Weaver",
TITLE = "Mapping Data to Processors in Distributed Memory
BOOKTITLE= "5' International Conference on Distributed Memory
YEAR= 1990,
month= "April"
AUTHOR= "M. Rosing and R. B. Schnabel and R. P. Weaver",
TITLE = "The {DINO} Parallel Programming Language",
INSTITUTION= "University of Colorado at Boulder",
YEAR= 1990,
number= "CU-CS-457-90"
AUTHOR= "M. Rosing and R. B. Schnabel",
TITLE = "Efficient Language Constructs for Large Parallel
Programs - An Overview of Dino2",
INSTITUTION= "University of Colorado at Boulder",
YEAR= 1992,
number= "CU-CS-578-92"

AUTHOR= "P. Mehrotra and J. {Van Rosendale}",
TITLE = "Parallel Language Constructs for Tensor Product
Computations on Loosely Coupled Architectures",
YEAR= 1989,
number= "89-41",
month= "September"
    author = "C. Koelbel and P. Mehrotra",
    title = "Supporting Shared Data Structures on Distributed Memory
    institution= "Department of Computer Science, Purdue University",
    year= 1990,
    number= "csd-tr 915"
% KALI90b
AUTHOR= "C. Koelbel and P. Mehrotra and J. Saltz and H. Berryman",
TITLE = "Parallel Loops on Distributed Machines",
BOOKTITLE= "5' International Conference on Distributed Memory
YEAR= 1990,
month= "April"
% KALI90c
AUTHOR= "P. Mehrotra, J. {Van Rosendale}",
TITLE = "Programming Distributed Memory Architectures Using Kali",
YEAR= "1990",
number= " ",
note= "Draft"
AUTHOR= "J. Saltz and K. Crowley and R. Mirchandaney and H.
TITLE = "Run-Time Scheduling and Execution of Loops on Message
Passing Machines" ,
JOURNAL="Journal of Parallel and Distributed Computing",
YEAR= "1990",
volume= 8,
month= "April"

AUTHOR= "D. Callahan and K. Kennedy",
TITLE = "Compiling Programs for Distributed-Memory Multiprocessors",
JOURNAL="Journal of Supercomputing",
YEAR= "1988",
volume= 2,
pages= "151--169"
    author = "S. Hirananandani and K. Kennedy and C. Koelbel and U.Kremer
                                  and C-W. Tseng",
    title = "{An Overview of Fortran D Programming System}",
    year = "1991",
    number = "TR91121",
    institution = "CRPC",
    address = "RICE University",
    month = "March"

    author = "H. P. Zima and H.-J. Bast and M. Gerndt",
    title = "{SUPERB}: A Tool for Semi-Automatic {MIMD/SIMD}
    journal = "Parallel Computing",
    year = "1988",
    volume = " ",
    number = "6",
    pages = "1-18"
      author = {Michael Gerndt},
      journal = {Concurrency Practice and Experience},
      title = {Updating Distributed Variables in Local Computations},
      year = {1990}
    author = "B. Chapman and P. Mehrotra and H. Zima",
    title = "{Vienna Fortran: A Fortran Language Extension for
Distributed Memory Multiprocessors}",
    institution = "ICASE",
    year = "1991",
    number = "91-72",
    month = "September"

AUTHOR= "E. M. Paalvast and A. J. {Van Gemund}",
TITLE = "A Method for Parallel Program Generation with an
Application to the {\sl Booster} Language",
BOOKTITLE="International Conference on Supercomputing",
pages= "457--469",
YEAR= 1990,
month= "June"
      author = "Edwin M.R. Paalvast and Leo C. Breebaart and Henk J. Sips",
      address = "Delft University of Tecnology -- The Netherlands",
      institution = "TNO Institute of applied science",
      number = "90 ITI 1864",
      title = "The {\sc {Booster}} Language: a User Language Reference",
      year = "1990"

    author = "Fran{\c c}oise Andr{\'e} and Henry Thomas",
    title = "{The Pandore System}",
    howpublished = "IFIP working conference on Decentralized Systems",
    year = "1989",
    month = "December",
    note = "Poster Presentation"

    author = "Fran{\c c}oise Andr{\'e} and Jean-Louis Pazat and
Henry Thomas",
    title = "{Data Distribution with Pandore}",
    booktitle = "The Fifth Distributed Memory Computing Conference",
    year = "1990",
    month = "April"

    author = "Fran{\c c}oise Andr\'{e} and Jean-Louis Pazat and
Henry Thomas",
    title = "{Pandore: A System to Manage Data Distribution}",
    institution = "INRIA",
    year = "1990",
    type = "Rapport de Recherche",
    number = "1195",
    month = "March"

    author = "Fran{\c c}oise Andr\'{e} and Jean-Louis Pazat and
Henry Thomas",
    title = "{Pandore: A System to Manage Data Distribution}",
    institution = "IRISA",
    year = "1990",
    number = "519",
    month = "February"

    author = "Fran{\c c}oise Andr\'{e} and Jean-Louis Pazat and
Henry Thomas",
    title = "{Pandore: A System to Manage Data Distribution}",
    booktitle = "International Conference on Supercomputing",
    year = "1990",
    organization = "ACM",
    month = "June 11-15"

    author = "F. Andr\'{e} and J.L. Pazat and
H. Thomas",
    title = "{Pandore: A System to Manage Data Distribution}",
    booktitle = "International Conference on Supercomputing",
    year = "1990",
    organization = "ACM",
    month = "June 11-15"

    author = "Fran\c{c}oise Andr\'e and Jean-Louis Pazat and Henry Thomas",
    title = "{PANDORE}: A System to Manage Data Distribution",
    booktitle = "Workshop on Compiler for Distributed Memory Machines",
    year = "1990",
    organization = "ICASE (NASA Langley Research Center)",
    month = "May"

    author = "Fran\c{c}oise Andr\'e and Claude Jard and Jean-Louis Pazat
and Henry Thomas",
    title = "Data-driven Distribution of Programs",
    booktitle = "International Workshop on Compiler for Parallel Computers",
    year = "1990",
    organization = "Ecoles des Mines de Paris",
    month = "December"

    author = "Jean-Louis Pazat",
    title = "Code Generation for Data Parallel Programs on DMPCs",
    booktitle = "European Distributed Memory Computers Conference",
    year = "1991",
    OPTorganization = "",
    OPTpublisher = "",
    OPTaddress = "",
    OPTmonth = "April",
    OPTnote = ""

    author = "H. Thomas",
    title = "Une approche de la compilation de programmes
s\'{e}quentiels pour machines \`{a} m\'{e}moire
    school = "IFSIC/Universit\'{e} de Rennes I",
    year = "1991",
    month = "June"

    author = "Fran{\c c}oise Andr\'{e} and Olivier Ch\'{e}ron and
                                  Jean-Louis Pazat and Henry Thomas",
    title = "Efficient Code Generation for Distributed Memory Machines",
    institution = "IRISA",
    year = "1991",
    number = "596",
    month = "July"

    author = "Fran{\c c}oise Andr\'{e} and Olivier Ch\'{e}ron and
                                    Jean-Louis Pazat and Henry Thomas",
    title = "Efficient Code Generation for Distributed Memory Machines",
    booktitle = "Parallel Computing '91",
    year = "1992",
    organization = "Parallel Computing Society",
    publisher = "Elsevier Science Publishers B.V.",
    month = "September"

    author = "Fran{\c c}oise Andr\'{e} and Olivier Ch\'{e}ron and
                                  Jean-Louis Pazat",
    title = "Compiling Sequential Programs for Distributed Memory
                                  Parallel Computers with Pandore II",
    institution = "IRISA/INRIA",
    year = "1992",
    number = "651",
    month = "April"

AUTHOR= "P.-S. Tseng",
TITLE="A Parallelizing Compiler for Distributed-Memory Parallel
YEAR= 1989
AUTHOR= "V. Sarkar and D. Cann",
TITLE = "A Partitioning and Optimizing {{\large S}ISAL} Compiler",
BOOKTITLE="Int. Conf. on Supercomputing",
YEAR= 1990,
pages= "148--163",
month= "June"
AUTHOR= "R. Ruhl and M. Annaratone",
TITLE = "Parallelization of {FORTRAN} {C}ode on Distributed
Memory Parallel Processors",
BOOKTITLE="Int. Conf. on Supercomputing",
pages= "342--353",
YEAR= 1990,
month= "June"
AUTHOR= "K. Ikudome and G. C. Fox and A. Kolawa and J. W. Flower",
TITLE = "An Automatic and Symbolic Parallelization System for
Distributed Memory Parallel Computers",
BOOKTITLE="5' Distributed Memory Computing Conference",
YEAR= 1990,
month= "April"
AUTHOR= "D. G. Socha",
TITLE = "An Approach to Compiling Single-point Iterative Programs
for Distributed Memory Computers",
BOOKTITLE="5' Distributed Memory Computing Conference",
YEAR= 1990,
month= "April"
AUTHOR= "M. Barber",
TITLE = "Hypertasking: Automatic Data Parallel Domain Decomposition
on the Intel Supercomputer",
BOOKTITLE="5' Distributed Memory Computing Conference",
YEAR= 1990,
month= "April"
AUTHOR= "R. Sawdayi and G. Wagenbreth and J. Williamson",
TITLE = "{MIMD}izer: Functional and Data Decomposition; Creating
Parallel Programs from Scratch, Transforming Existing Fortran
   Programs to Parallel ",
BOOKTITLE="Icase Workshop",
YEAR= 1990,
month= "May"

    author = "T. Priol and Z. Lahjomri",
    title = "Experiments With Shared Virtual Memory and
                                  Message-Passing on iPSC/2 Hypercube",
    booktitle = "International Conference on Parallel Processing",
    year = "1992",
    pages = "To appear",
    month = "August"

    author = "Z. Lahjomri and T. Priol",
    title = "KOAN: a Shared Virtual Memory for the iPSC/2 hypercube",
    booktitle = "CONPAR/VAPP92",
    year = "1992",
    month = "September"

    author = "F. Bodin and T. Priol",
    title = "Overview of the KOAN Programming Environment for the
     iPSC/2 and Performance evaluation of the BECAUSE Test Program 2.5.1",
    booktitle = "Because Workshop",
    year = "1992",
    month = "October"

      author = "Barbara Chapman and Hans Zima",
      publisher = "Addison-{W}esley",
      series = "Frontier Series",
      title = "Supercompilers for {P}arallel and {V}ector {C}omputers",
      year = "1990",
      isbn = "0-201-17560-6"

    editor = "B. K. Szymanski",
    title = "Parallel Functional Programming Languages and Environments",
    publisher = "ACM Press",
    address = "New York",
    year = 1991

    author = "B. McKenney and B. K. Szymanski",
    title = "Generating Parallel Code for SIMD Machines",
    note = "Submitted to ACM LOPAS" % may be published by now, check

    author = "Szymanski, B. and Prywes, N.",
    title = "Efficient Handling of Data Structures in
Definitional Languages",
    journal = "Science of Computer Programming",
    number = 3,
    year = 1988,
    pages = "221-45"

    author = "B. Sinharoy and B. K. Szymanski",
    title = "Complexity Issues of the Alignment Problem and the
Closest Vectors in a Lattice",
    institution = "Dept. of Comp. Sc., Rensselaer Polytechnic Institute",
    number = "91-10",
    month = "May",
    year = 1991

    editor = "B. K. Szymanski",
    title = "Parallel Functional Programming Languages and Environments",
    publisher = "ACM Press",
    address = "New York",
    year = 1991

    author = "Lee-Chung Lu and Marina C. Chen",
    title = "Subdomain Dependence Test for Massive Parallelism",
    booktitle = "Proceedings of the Supercomputing '90 Conference",
    year = 1990,
    publisher = "IEEE Computer Society Press",
    address = "Los Alamitos, CA"

    author = "Jinke Li and Marina Chen",
    title = "The Data Alignment Phase in Compiling Programs for
Distributed Memory Machines",
    journal = "J. of Parallel and Distributed Computing",
    year = 1991,
    volume = 13,
    pages = "213--221"

    author = "Jinke Li and Marina Chen",
    title = "Compiling Communication-Efficient Programs for
Massively Parallel Machines",
    journal = "IEEE Transactions on Parallel and Distributed Systems",
    year = 1991,
    volume = 2,
    number = 3,
    pages = "361--376",
    month = "July"

    author = "Marina Chen and Young-il Choo and Jingke Li",
    title = "Parallel Functional Programming Languages and Environments",
    chapter = "Crystal: Theory and Pragmatics of Compiling Efficient
Parallel Code",
    publisher = "ACM Press",
    year = 1991,
    editor = "B. Szymanski"

    author = "Allan Yang and Young-il Choo",
    title = "Parallel-Program Transformation Using a Metalanguage",
    booktitle = "Proc.~of the Third ACM SIGPLAN Symposium on Principles and
Practice of Parallel Programming",
    year = 1991

    author = "Marina Chen and Young-il Choo",
    title = "Compiling Crystal for Massively Parallel Machines",
    booktitle = "Proceedings of the Workshop on Compilation of (Symbolic)
Languages for Parallel Computers",
    year = 1991,
    publisher = "Argonne National Laboratory Report ANL-91/34",
    month = "November"

    author = "Allan Yang and Young-il Choo",
    title = "Formal Derivation of an Efficient Parallel Gauss-Seidel
Method on a Mesh of Processors",
    booktitle = "Proceedings of the 6th International Parallel Processing
    year = 1992,
    publisher = "IEEE Computer Society Press",
    month = "March"

    author = "Allan Yang and Young-il Choo",
    title = "Metalinguistic Features for Formal Parallel-Program
    booktitle = "Proceedings of the 4th IEEE International Conference on
Computer Languages",
    year = 1992,
    publisher = "IEEE Computer Society Press",
    month = "April"

    author = "J. Li and M. Chen",
    title = "Index Domain Alignment: Minimizing Cost of Cross-Referencing
                 Between Distributed Arrays",
    institution = "Dept. of Comp. Sc., Yale, Univ.",
    number = "YALEU/DCS/TR-725",
    month = "Nov.",
    year = 1989

    author = "J. R. Gilbert and R. Schreiber",
    title = "Optimal Expression Evaluation for Data parallel
    institution = "RIACS",
    number = "90.15",
    month = "April",
    year = 1990

    author = "K. Knobe, J. D. Lukas and G. L. Steele Jr.",
    title = "Data Optimization: Allocation of Arrays to Reduce
Communication on SIMD Machines",
    journal = "Journal of Parallel and Distributed Computing",
    volume = 8,
    year = 1990,
    pages = "102-118"


>From Fri Nov 20 23:05:24 1992

What you probably need to look for is automatic alignment and distribution
for distributed memory architectures.

There are a number of parallel compilers that require alignment and
distribution information then convert the program to SPMD form. For
example the Rice distributed memory compiler does this. If you want a
reference on this compiler send email to and ask for the
tech reports CRPC-TR91121 and CRPC-TR91132.

My dissertation deals with automatic alignment and distribution in Fortran
D for a large class of applications. An early description of the work
(before we really started into the guts of the research) is available in
CRPC-TR91166 from the above source.

You will find in these references pointers to other related work.


>From jhummel@esp.ICS.UCI.EDU Sun Nov 22 00:35:08 1992

    1. Look at Fortran D work by Kennedy, et al., at Rice University.
            This is fortran for distributed memory machines (now called
            high-performance fortran or HPF).
    2. Rogers and Pingali at Cornell did some compiler work.
    3. A system called Kali, authors ?.
    4. A system called Pandore, authors ?.

You should be able to look in ICPP, Supercomputing, or Sigplan
PLDI conferences for this and related stuff.


>From Mon Nov 23 17:06:15 1992

There are many projects about "parallelizing compilers" for distributed
memory machines. Ther are two kinds of compilers:
Data distribution directed compilers (DDD): FortranD, Pandore, Vienna Fortran,
HPF compilers
Code distribution directed compilers: (CDD)

DDD Compilers parallelize and distribute sequential code according to a
data distribution specified by the user; CDD compilers try to distribute
independent iterations among processors, most of them use a global memory;
but this memory can be a virtual memory (see KOAN for example).

At IRISA, we are working on a DDD Compiler PANDORE II (see the bib. part of
this message)

2) About profiling information:

We are also working in this area. Yves MAHEO (PhD student),
( is working with me in this field. We have used profiling
techniques to find why in some cases the parallelization is not efficient.
Informations are collected by the run-time designed for our compiler
(PANDORE II -> C (NX/2) ) on an iPSC/2.

We also use a sophisticated trace analysis system (ECHIDNA) wich uses the
ESTELLE language. (We also have a code generator for the ESTELLE
language). Theses informations are of interest to find where are tight
synchronizations in the generated code. Cyrille Bareau (PhD student),
( working with Claude Jard ( on this

We think that it seems very difficult to have a precise enough feed back
from theses tools to drive a compiler. Work is in progress to show some
global information to the user, driving the compiler is the next step.


>From Mon Nov 23 19:00:24 1992

    you might want to look at work done here at Rice in the
    context of the Fortran D programming system.

    Several other groups are/have been looking at the problem of compiling
    programs for distributed memory multiprocessors. Just go
    through the Proceedings of the following conferences:
        - International Conference of Supercomputing (ICS)
        - Supercomputing
        - HCCA4, DMCC5, DMCC6, ...
        - Sigplan PLDI
        - Sigplan PPOPP

>From Mon Nov 23 20:36:10 1992

In the most recent conference on supercomputing "SUPERCOMPUTING 92" just
held in Minnesota, USA there was a paper on compiling fortran programs for
distributed memory machines. The paper is from NPAC, Syracuse University,
Syracuse NY 13210 USA.

We at Syracuse University are developing a Fortran compiler for MIMD
machines. There are lot of technical reports, and you should get in touch
with Lisa Deo ( to get the technical reports and
their listings.

Other places which are also working is CRPC, Rice University, Houston,
Texax, USA. Contact Ken Kennedy or Charles Koelbel.

Also, you can contact Piyush Mehrotra or Joel Saltz at ICASE, NASA Langley
Research Center, Hampton, VA 23665, USA.

Most of the papers for compiling techniques for MIMD parallel computers
are from these people only.


>From Mon Nov 23 21:36:58 1992

      I suggest you try looking at stuff relating to the SUPRENUM (spelling?)
machine - I think it is a parallel vector-processor machine. Hence its
compilers need just about every technique you can think of.
      I recall there is a book by H. Zima and B. Chapman on the subject of
vector and parallel compilers (Supercompilers for parallel and vector
computers??), so you could start searching on their names. The book is
heavily into dependence relations etc., covers vector machines, but for
parallel machines I think it only considers loop-parallelism.

Reply-To: (Paul Havlak)

        Parafrase is a vectorizing/parallelizing Fortran-to-Fortran compiler
developed at the University of Illinois CSRD. Subsequent projects at CSRD
include Parafrase-2 (an interactive programming environment), Cedar (a
parallel computer with shared-memory clusters, with its own KAP-based
compiler), and several Lisp-oriented projects.
        Parafrase-2 (at least) has some PDG-based intermediate

        The PTRAN group at IBM Watson Research Center also uses a PDG-based
representation for partitioning.

        Of the two major projects at Rice, PFC did not use control
dependences, but ParaScope uses the PDG and additional information.
        In the early-to-mid 1980s, Kennedy and Allen's group at Rice developed
a vectorizing/parallelizing Fortran-to-Fortran compiler (Parallel Fortan
Converter == PFC) and a dependence browser (PTOOL), running on IBM
mainframes. PTOOL is now defunct. PFC relied on IF-conversion to convert
control dependences to data dependences.
        The ParaScope programming environment builds control and data
dependences for interactive transformation of sequential and parallel
Fortran. The ParaScope editor can use dependence graphs from PFC/PSERVE.
        Recent work at Rice on compilation of Fortran D (a precursor to High
Performance Fortran) uses the same ParaScope infrastructure.

>From Fri Dec 4 01:04:44 1992

  IEEE transactions on Distributed Systems is a good starting place to look
  for articles on parallel Comp on Distributed architectures. There are
  several articles on this topic.

  There exists good books:
        Parallel Programming and Compilers (Polychronopolous)
        SuperCompilers for Parallel and Vector Computers
                      (Hans Zima and Barbara Chapman)
  Both are good Summary books.

Reply-To: "Qiang Alex Zhao" <>

Have you tried SR? Here's a description of SR:

SR (Synchronizing Resources) is a language for writing concurrent
programs. It is described in "The SR Programming Language: Concurrency in
Practice" by Gregory R. Andrews and Ronald A. Olsson (Benjamin/Cummings,
1993, ISBN 0-8053-0088-0). An overview of Version 1 of the language and
implementation appeared in the January, 1988, issue of TOPLAS (ACM
Transactions on Programming Languages and Systems 10,1, 51-86).

The main language constructs are resources and operations. Resources
encapsulate processes and variables they share; operations provide the
primary mechanism for process interaction. SR provides a novel
integration of the mechanisms for invoking and servicing operations.
Consequently, all of local and remote procedure call, rendezvous, message
passing, dynamic process creation, multicast, and semaphores are

New features in Version 2 include shared global variables and operations,
circular imports, real numbers and math functions, formatted I/O, a more
general syntax with fewer special cases, a more robust system with better
error checking, true multiprocessing when run on a Silicon Graphics Iris
or Sequent Symmetry, and many additional enhancements.

SR has been used at a number of universities and labs for course work and
research projects involving concurrent programming. It has been used in
concurrent programming courses to reinforce concepts with small
programming projects and with larger projects such as experiments with
parallel algorithms, replicated databases, distributed simulations, and
parts of distributed operating systems such as file systems and command
interpreters. SR has also been used as a tool in several masters theses
and doctoral dissertations to conduct experiments in parallel and
distributed programming and to implement larger systems such as a system
for mixed language programming, one for distributed implementation of
graph algorithms, experiments with load balancing algorithms, and
experiments with upcall program structures.

Version 2 is tested on Sun4, Sun3, DECstation, SGI Iris, HP RISC and
9000/300, NeXT, and Sequent Symmetry platforms. Code is also included for
the DG AViiON, IBM RS/6000, DEC VAX, Encore Multimax, Apollo DN, and

FTP: /sr

Department of Computer Science,
Lund University, BOX 118, S-221 00 LUND, Sweden

Post a followup to this message

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