erspert@athena.mit.edu (Ellen R. Spertus) (03/11/91)
A month ago, I posted a message to this group looking for references
to papers on compiling loops for massively-parallel MIMD computers.
Several people expressed interest, so here is a summary.
Ellen Spertus
----------------
From: Jeff Martens <martens@cis.ohio-state.edu>
A good place to start is Wolfe's book (basically an update of his
dissertation). Here's a bibtex entry:
@book{Wol:89,
author = {Michael Wolfe},
title = {Optimizing Supercompilers for Supercomputers},
publisher = {MIT Press},
address = {Cambridge, MA},
year = {1989}
}
He has a fairly good bibliography. A couple paper-length introductions
are:
@article{Wol:88,
author = {Michael Wolfe},
title = {Multiprocessor Synchronization for Concurrent Loops},
journal = {IEEE Software},
year = {1988},
month = {January},
pages = {34 -- 42}
}
@article{PW:86,
author = {D. A. Padua and M. J. Wolfe},
title = {Advanced Compiler Optimizations for Supercomputers},
journal = {CACM},
year = {1986},
month = {December},
volume = {29},
number = {12},
pages = {1184 -- 1201}
}
Each of these papers have bibliographies. In a nutshell, there's good
work coming from:
Wolfe at OGI
Padua, Yew, & Zhu at Illinois
Ferrante, Cytron, & Allen at IBM TJ Watson
a parade of researchers at Rice
Krothapalli (now at Wisconsin-Oshkosh) and Sadayappan here at
Ohio State
----------------
From: rcosw@koel.co.rmit.oz.au
I am also working on a similar project. I am writing a Pascal compiler for
our dataflow machine - CSIRAC II. At the moment I am working on parallel
loop generation and have found several references listed below.
"The reduction of data dependencies in high level programs" - Ph.D Thesis,
Stephen J. Allan, Iowa State University. email : allan@steve.cs.usu.edu
"Parallelizing WHILE Loops" - Youfeng Wu & T.G. Lewis, Oregon State University.
email : lewis@mist.cs.orst.edu
"Dependence of Multi-Dimensional Array References" - Comm of ACM 1988, David R.
Wallace, Alliant Computer Systems.
"Interprocedural Dependence Analysis and Parallelization" - Comm of ACM 1986,
Michael Burke & Ron Cytron, IBM T.J. Watson Research Centre.
----------------
From: lee-chung lu <lu-lee-chung@CS.YALE.EDU>
We have three papers in this area:
L.C. Lu and M.C. Chen,
"New Loop Transformation Techniques for Massive parallelism",
Yale University Technical Report TR-833, October 1990.
L.C. Lu and M.C. Chen,
"Subdomain Dependence Test for Massively Parallel Computing",
in Proc. Supercomputing '90, 1990.
L.C. Lu,
"A Unified Framework for Systematic Loop Transformations",
to appear in Proc. of the Third ACM SIGPLAN Symposium on
Principles & Practice of Parallel Programming, 1991
----------------
From: jxr@max.ee.lsu.edu (J. Ramanujam)
I did my dissertation on compilation of loops for distributed
memory machines. Here are the references:
\bibitem{dmcc5} J. Ramanujam and P. Sadayappan,
``Nested Loop Tiling for Distributed Memory Machines,''
{\em Proc. 5th Distributed Memory Computing Conference (DMCC5),\/}
Charleston, S. Carolina, pages 1088--1096, April 1990.
\bibitem{icpp90} J. Ramanujam and P. Sadayappan,
``Tiling of Iteration Spaces for Multicomputers,''
{\em Proc. 1990 International Conference on Parallel Processing,}
Vol 2, pages 179-186, August 1990.
\bibitem{ramdiss} J. Ramanujam,
``Compile-time Techniques for Parallel Execution of Loops on
Distributed Memory Multiprocessors,''
Ph.D. Thesis, Dept. of Computer and Information Science,
The Ohio State University, Columbus, Ohio, September 1990.
----------------
From: bloom-beacon!think!rutgers!yrloc.ipsa.reuter.com!rbe (Robert Bernecky)
The work that Walter Schwarz and I did is not dead on your request,
but you might be interested in some ways to do it wrong on the CM:
a. ACM SIGAPL APL90 conference proceedings: APL Quote Quad Vol. 20, no. 4,
July 1990. "Acorn...", by yrs trly.
b. "Arrays, Functional Languages, and Parallel Systems", Kluwer Academic
1991. See papers by yrs trly and Walter Schwarz.
----------------
Additionally, some papers I found in the library or through
bibliographies are:
Midkiff, Samuel P. and David A. Padua. "Compiler Algorithms for
Synchronization." IEEE Transactions on Computers, Vol C-36, No. 12
(December 1987), 1485 -- 1495.
Midkiff, Samuel P. and David A. Padua. "Compiler Generated
Synchronization for Do Loops." Proceedings of the International
Conference on Parallel Processing, 1986, 544 -- 551.
Cytron, Ron. "Doacross: Beyond Vectorization for Multiprocessors."
Proceedings of the International Conference on Parallel Processing,
1986, 836 -- 844.
Polychronopoulos, Constantine D. and David J. Kuck. "Guided
Self-Scheduling: A Practical Scheduling Scheme for Parallel
Supercomputers." IEEE Transactions on Computers, Vol C-36, No. 12
(December 1987), 1425 -- 1439.
Rudolph, David C. and Constantine D. Polychronopoulos. "An Efficient
Message-Passing Scheduler Based on Guided Self Scheduling." [I have
this in the form of a University of Illinois technical report. I
don't know where it was published.]
Polychronopoulos, Constantine D., David J. Kuck., and David A. Padua.
"Execution of Parallel Loops on Parallel Processor Systems."
Proceedings of the International Conference on Parallel Processing,
1986, 519 -- 527.
Allen, John R. and Ken Kennedy. "A Parallel Programming Environment."
IEEE Software, July, 1985, 21 -- 29.
Allen, Frances, et al. "A Framework for Determining Useful
Parallelism." Supercomputing 1988, 207 -- 215.
Girka, Milind and Constantine D. Polychronopoulos. "Partitioning
Programs for Parallel Execution." Supercomputing 1988, 216 -- 229.
--
=========================== MODERATOR ==============================
Steve Stevenson {steve,fpst}@hubcap.clemson.edu
Department of Computer Science, comp.parallel
Clemson University, Clemson, SC 29634-1906 (803)656-5880.mabellerspert@athena.mit.edu (Ellen R. Spertus) (03/13/91)
I have a few references to add to my list. I apologize for not including
them in my first message:
Callahan, David and Ken Kennedy. "Compiling Programs for Distributed-
memory Multiprocessors." The Journal of Supercomputing, Vol. 2,
October 1988, 461 -- 469.
Wolfe, Michael. "Advanced Loop Interchanging." Proceedings of the
International Conference on Parallel Processing, 1986, 536 -- 543.
Wolfe, Michael, "More Iteration Space Tiling." Proceedings of Supercomputing
'89, 655 -- 664.
Kennedy, Ken and Kathryn S. McKinley, "Loop Distribution with Arbitrary
Control Flow", Proceedings of Supercomputing '90.
--
=========================== MODERATOR ==============================
Steve Stevenson {steve,fpst}@hubcap.clemson.edu
Department of Computer Science, comp.parallel
Clemson University, Clemson, SC 29634-1906 (803)656-5880.mabell