NetNews Usenet Archive 1992 #31/NN_1992_31.iso/spool/comp/compiler/2072

Internet Message Format | 1992-12-31 | 34.1 KB

Path: sparky!uunet!spool.mu.edu!wupost!emory!ogicse!das-news.harvard.edu!spdcc!iecc!compilers-sender
From: [e-mail] (Christian S. Collberg)
Newsgroups: comp.compilers
Subject: Parallelizing Compilers (Summary)
Keywords: parallel, architecture, bibliography, summary
Message-ID: <[e-mail]>
Date: 31 Dec 92 10:32:26 GMT
Article-I.D.: comp.92-12-105
References: <[e-mail]>
Sender: [e-mail]
Reply-To: [e-mail] (Christian S. Collberg)
Organization: Department of Computer Science, Lund University
Lines: 1013
Approved: [e-mail]

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. 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"}

    @InProceedings{KMT:A+T2,
        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"}

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

-------------------------------------------------------------------------------
Reply-To: [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.

-------------------------------------------------------------------------------
Reply-To: "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
--
Send compilers articles to [e-mail] or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.