NetNews Usenet Archive 1992 #31/NN_1992_31.iso/spool/comp/parallel/2845

Text File | 1992-12-31 | 33.8 KB | 1,022 lines

Newsgroups: comp.parallel
Path: sparky!uunet!zaphod.mps.ohio-state.edu!swrinde!gatech!hubcap!fpst
From: [e-mail] (Christian S. Collberg)
Subject: Parallelizing Compilers (Summary)
Message-ID: <[e-mail]>
Sender: [e-mail]
Organization: Department of Computer Science, Lund University
Date: Thu, 31 Dec 1992 10:33:48 GMT
Approved: [e-mail]
Lines: 1010


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 <[e-mail]>
      [e-mail] (Sachit R. Nadkarni)
      Qiang Alex Zhao <[e-mail]>
      [e-mail]
      [e-mail] (Lorie Liebrock)
      [e-mail] (Subhas Roy)
      Christian Lengauer <[e-mail]>
      Joe Hummel <[e-mail]>
      [e-mail]
      [e-mail] (David R. Good)
      [e-mail] (Jean Louis Pazat)
      [e-mail] (Uli Kremer)
      [e-mail] (Pankaj Kumar)
      <[e-mail]>
      [e-mail] (David Lilja)
      [e-mail] (Lee Chia Ling)
      Rudi Hackenberg <[e-mail]>
      Gholamali Hedayat (JRG ra) <[e-mail]>
      [e-mail]
      Suresh Damodaran Kamal <[e-mail]>
      Steven Collins <[e-mail]>
      [e-mail] (Paul Havlak)
      Ramakumar Kosuru <[e-mail]>
      [e-mail] (Roland Wismueller)
      Roger Peel <[e-mail]>

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

    @InProceedings{Parafrase2,
        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}

    @InCollection{ABCC:Overview,
        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},
        Publisher={Springer-Verlag},
        Address={Athens, Greece},
        Year={1987}}

    @Article{AlKe:Automatic,
        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}

    @InProceedings{AlCK:Automatic,
        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"}

    @Article{Hend:PTOOL,
        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"}

    @Article{PEDJ2,
        Author = {K. Kennedy and K. S. M\raisebox{.2em}{c}Kinley 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"}

    @InProceedings{KMT:A+T2,
        Author = {K. Kennedy and K. S. M\raisebox{.2em}{c}Kinley 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"}

    @InProceedings{HKK:Overview,
        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}

    @InCollection{HKT:icase,
        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
        Multiprocessors},
        Editor = {J. Saltz and P. Mehrotra},
        Publisher = {Elsevier},
        Address = Amsterdam,
        Year = {to appear 1991}}

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

    Proceedings{HKT:SC91,
    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}

@Article{Nickhil89,
  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"
}
@InProceedings{Rogers89,
  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"
}

@TechReport{Reeves89,
  author =     "A. P. Reeves",
  title =     "Paragon: A Programming Paradigm for Multicomputer Systems",
  institution =     "Cornell University",
  year =     "1989",
  number =     "EE-CEG-89-3",
  month =     "January"
}
@TechReport{Reeves89b,
  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"
}
@TechReport{Reeves90,
  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"
}

@article{Hatcher88,
    AUTHOR=    "M. J. Quinn and P. J. Hatcher and K. C. Jourdenais",
    TITLE =    "Compiling {C}$^*$ Programs for a Hypercube Multicomputer",
        BOOKTITLE="ICCL90",
    YEAR=    1990
    }
@InProceedings{Hatcher90,
  author =     "M. J. Quinn and P. J. Hatcher",
  title =     "Compiling {SIMD} Programs for {MIMD} Architectures",
  booktitle =     "ACM Sigplan (PPEALS)",
  year =     "1990",
  OPTpages =     "57--65"
  }
@article{Hatcher90b,
    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"
    }

@InProceedings{Rosing88,
  author =      "M. Rosing and R. B. Schnabel and R. Weaver",
  title =       "Dino: Summary and Examples",
  booktitle =   "3' Conference on Hypercubes Concurrent Computers and
                 Applications",
  year =        "1988",
  pages =       "472--481"
}
@inproceedings{Rosing90,
    AUTHOR=    "M. Rosing and R. P. Weaver",
    TITLE =    "Mapping Data to Processors in Distributed Memory
        Computations",
    BOOKTITLE= "5' International Conference on Distributed Memory
        Computing",
    YEAR=    1990,
    month=    "April"
    }
@techreport{Rosing90b,
    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"
    }
@techreport{Rosing92,
    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"
    }

@techreport{Mehrotra89,
    AUTHOR=    "P. Mehrotra and J. {Van Rosendale}",
    TITLE =    "Parallel Language Constructs for Tensor Product
        Computations on Loosely Coupled Architectures",
    INSTITUTION= "ICASE",
    YEAR=    1989,
    number=    "89-41",
    month=    "September"
    }
%KALI90a
@Techreport{Koelbel90,
  author =    "C. Koelbel and P. Mehrotra",
  title =    "Supporting Shared Data Structures on Distributed Memory
        Architectures",
  institution=    "Department of Computer Science, Purdue University",
  year=        1990,
  number=    "csd-tr 915"
}
% KALI90b
@inproceedings{Koelbel90b,
    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
        Computing",
    YEAR=    1990,
    month=    "April"
    }
% KALI90c
@techreport{Mehrotra90,
    AUTHOR=    "P. Mehrotra, J. {Van Rosendale}",
    TITLE =    "Programming Distributed Memory Architectures Using Kali",
    INSTITUTION= "ICASE",
    YEAR=    "1990",
    number=    " ",
    note=    "Draft"
    }
@article{Saltz90,
    AUTHOR=    "J. Saltz and K. Crowley and R. Mirchandaney and H.
        Berryman",
    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"
    }

%Kennedy88,
@article{Callahan88,
    AUTHOR=    "D. Callahan and K. Kennedy",
    TITLE =    "Compiling Programs for Distributed-Memory Multiprocessors",
    JOURNAL="Journal of Supercomputing",
    YEAR=    "1988",
    volume=    2,
    pages=    "151--169"
    }
@TechReport{FortranD91,
  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"
}

%SUPERB88,
@Article{Zima88,
  author =     "H. P. Zima and H.-J. Bast and M. Gerndt",
  title =     "{SUPERB}: A Tool for Semi-Automatic {MIMD/SIMD}
         Parallelization",
  journal =     "Parallel Computing",
  year =     "1988",
  volume =      " ",
  number =     "6",
  pages =     "1-18"
}
@article{Gerndt90b,
   author = {Michael Gerndt},
   journal = {Concurrency Practice and Experience},
   title = {Updating Distributed Variables in Local Computations},
   year = {1990}
}
@TechReport{Vienna91,
  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"
}

%BOOSTER90,
@inproceedings{Paalvast90,
    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"
    }
%Booster90b,
@techreport{Paalvast90b,
   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"
}

@Misc{poster-ifip89,
  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"
}

@InProceedings{dmcc5-90,
  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"
}

@TechReport{publi-inria90,
  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"
}

@TechReport{publi-interne90,
  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"
}


@InProceedings{amsterdam90,
  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"
}

@InProceedings{amsterdam90b,
  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"
}


@InProceedings{icase90,
  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"
}


@InProceedings{paris90,
  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"
}


@InProceedings{munich91,
  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 =     ""
}

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

@TechReport{publi-interne91,
  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"
}


@InProceedings{londres91,
  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"
}

@TechReport{publi-interne92,
  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"
}


@phdthesis{Tseng89,
    AUTHOR=    "P.-S. Tseng",
    TITLE="A Parallelizing Compiler for Distributed-Memory Parallel
           Computers",
    SCHOOL=    "CMU",
    YEAR=    1989
    }
%POSC90,
@inproceedings{Sarkar90,
    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"
    }
%OXYGEN90,
@inproceedings{Ruhl90,
    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"
    }
%ASPAR90,
@inproceedings{Ikudome90,
    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"
    }
%SPOT90,
@inproceedings{Socha90,
    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"
    }
%HYPERTASKING90,
@inproceedings{Barber90,
    AUTHOR=    "M. Barber",
    TITLE =    "Hypertasking: Automatic Data Parallel Domain Decomposition
        on the Intel Supercomputer",
    BOOKTITLE="5' Distributed Memory Computing Conference",
    YEAR=    1990,
    month=    "April"
    }
%MIMDIZER90,
@inproceedings{Sawdayi90,
    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"
    }


@InProceedings{pri92a,
  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"
}

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

@InProceedings{bod92,
  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"
}

@book{zima:compilers,
   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"
}

@Book{szymanski:91,
  editor =      "B. K. Szymanski",
  title =       "Parallel Functional Programming Languages and Environments",
  publisher =   "ACM Press",
  address =     "New York",
  year =         1991
}


@Unpublished{mckenney:szymanski,
  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
}


@Article{szymanski:prywes:88,
  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"
}


@TechReport{sinharoy:szymanski:91,
  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
}

@Book{szymanski:91,
  editor =    "B. K. Szymanski",
  title =    "Parallel Functional Programming Languages and Environments",
  publisher =    "ACM Press",
  address =    "New York",
  year =      1991
}

@InProceedings{lu:chen:90,
  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"
}

@Article{li:chen:91a,
  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"
}

@Article{le:chen:91b,
  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"
}

@InBook{chen:choo:li,
  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"
}

@InProceedings{yang:choo:91,
  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
}

@InProceedings{chen:choo:91,
  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"
}

@InProceedings{yang:choo:92a,
  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
         Symposium",
  year =     1992,
  publisher =     "IEEE Computer Society Press",
  month =     "March"
}

@InProceedings{yang:choo:92b,
  author =     "Allan Yang and Young-il Choo",
  title =     "Metalinguistic Features for Formal Parallel-Program
         Transformation",
  booktitle =     "Proceedings of the 4th IEEE International Conference on
         Computer Languages",
  year =     1992,
  publisher =     "IEEE Computer Society Press",
  month =     "April"
}

@TechReport{li:chen:89,
  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
}

@TechReport{gilbert:schreiber:90,
  author =    "J. R. Gilbert and R. Schreiber",
  title =    "Optimal Expression Evaluation for Data parallel Architectures",
  institution =    "RIACS",
  number =     "90.15",
  month =    "April",
  year =    1990
}

@Article{knobe:lukas:steele:90,
  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 [e-mail] 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 [e-mail]
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 [e-mail] 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 [e-mail] 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), ([e-mail]) 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), ([e-mail])is working
with Claude Jard ([e-mail]) on this subject.

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 [e-mail] 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 [e-mail] 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 ([e-mail]) 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 [e-mail] 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.

-------------------------------------------------------------------------------
From: [e-mail] (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
representations.

    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 [e-mail] 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.

-------------------------------------------------------------------------------
From: "Qiang Alex Zhao" <[e-mail]>

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

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

FTP: cs.arizona.edu: /sr

----------------------------------------------------------------------------
--
[e-mail]
Department of Computer Science, Lund University, BOX 118, S-221 00 LUND, Sweden