rwolski@lll-crg.llnl.gov (Richard Wolski) (09/28/90)
Greetings once again.
About a week ago I posted a request for reference information on
partitioning and scheduling for heterogeneous systems. I am pleased to say
the the response has been almost overwhelming. While I haven't completely
digested everything I have received, here is a summary of what I think
is pertinent.
BTW, I'm including the name of the contributor for each of the entries --
I hope that this does not violate some aspect of netiquette that I am
unaware of. Please forgive the faux pas otherwise.
Thank you all for responding to my request -- your input has been invaluable.
Rich
Rich Wolski
rwolski@lll-lcc.llnl.gov
LLNL
P.O. Box 808, L-60
Livermore, CA 94550
(415)423-8594
P.S. For what it is worth, I have annotated articles that I have read and can
recommend. A lack of a recommendation should probably be construed as I
have yet to read the article and not that it is not worth examining.
Since the field seems to be somewhat unexplored, however, many of
these articles deal primarily with the homogeneous version of partitioning
and scheduling.
--------------------------------------------------------------------------------
Dr. Shahid Bokhari at icase suggests:
-------------------------------------
Author = "Shahid H. Bokhari",
Year = "July 1979",
Journal = "IEEE Transactions on Software Engineering",
Number = "5",
Pages = "341-349",
Title = "Dual processor scheduling with dynamic reassignment",
Volume = "SE-5",
Author = "Shahid H. Bokhari",
Year = "November 1981",
Journal = "IEEE Transactions on Software Engineering",
Number = "6",
Pages = "583-589",
Title = "A shortest tree algorithm for optimal assignments across space and time in a distributed processor system",
Volume = "SE-7",
Author = "Shahid H. Bokhari", *** RECOMMENDED ***
Title = "Partitioning problems in parallel, pipelined and distributed computing",
Journal = "IEEE Transactions on Computers",
Year = "January, 1988",
Number ="1",
Volume="C-37",
Pages="48-57"
Author = "Shahid H. Bokhari",
Title = "Assignment problems in parallel and distributed computing",
Publisher = "Kluwer",
Address = "Boston",
Year = "1987"
Author = "Patricia J. Carstensen",
Title = "The Complexity of Some Problems in Parametric Linear and Combinatorial Programming",
Year = "1983",
Institution = "Department of Mathematics,
University of Michigan",
Author = "K. W. Doty",
Author = "P. L. McEntire",
Author = "J. G. O'Reilly",
Title = "Task allocation in a distributed
computer system",
Journal = "Proceedings of the IEEE Infocom 82",
Pages = "33-38",
Year = "1982",
Author = "Dan Gusfield",
Title = "Parametric combinatorial computing and a problem of program module distribution",
Journal = "Journal of the ACM",
Volume = "30",
Number = "3",
Pages = "551-563",
Year = "July 1983",
Author = "Robert E. Larson",
Author = "Paul E. McIntyre",
Author = "John G. O'Reilly",
Title = "Tutorial: Distributed Control",
Publisher = "IEEE Computer Society Press", Address = "Silver Spring, MD",
Year = "1982",
Author = "Virginia M. Lo", **** RECOMMENDED ****
Title = "Heuristic algorithms for task assignments in distributed systems",
Journal = "Proceedings of the 4th International Conference on Distributed Processing Systems",
Pages = "30-39",
Year = "May 1984",
Author = "Janet Michel",
Author = "Andries van Dam",
Title = "Experience with distributed processing on a host/satellite system",
Journal = "Computer Graphics (SIGGRAPH Newsletter)",
Volume = "10",
Number = "2",
Year = "1976",
Author = "Camille C. Price",
Author = "Udo W. Pooch",
Title = "Search Techniques for a nonlinear multiprocessor scheduling problem",
Journal = "Naval Research Logistics Quarterly",
Volume = "29",
Number = "2",
Pages = "213-233",
Year = "June 1982",
Author = "Gururaj S. Rao",
Author = "Harold S. Stone",
Author = "T. C. Hu",
Title = "Assignment of tasks in a distributed processor system with limited memory",
Journal = "IEEE TC",
Volume = "C-28",
Number = "4",
Pages = "291-299",
Year = "April 1979",
Author = "Harold S. Stone", **** RECOMMENDED ****
Title = "Multiprocessor scheduling with the aid of network flow algorithms",
Journal = "IEEE Transactions on Software Engineering",
Volume = "SE-3",
Number = "1",
Pages = "85-93",
Year = "January 1977",
Author = "Harold S. Stone",
Year = "1977",
Number = "ECE-CS-77-7",
Institution = "Department of Electrical & Computer Engineering, University of Massachusetts, Amherst",
Title = "Program assignment in three-processor systems and tricutset partitioning of graphs"
Author = "Harold S. Stone",
Title = "Critical load factors in two-processor distributed systems",
Journal = "IEEE Transactions on Software Engineering",
Volume = "SE-4",
Number = "3",
Pages = "254-258",
Year = "May 1978",
Author = "Donald F. Towsley",
Title = "Allocating programs containing branches and loops within a multiple processor system",
Journal = "IEEE Transactions on Software Engineering",
Volume = "SE-12",
Pages = "1018-1024",
Year = "October 1986",
Author = "Andries van Dam",
Author = "George M. Stabler",
Author = "Richard J. Harrington",
Title = "Intelligent satellites for interactive graphics",
Journal = "Proceedings of the IEEE",
Volume = "62",
Number = "4",
Pages = "483-492",
Year = "April 1974",
>From Alessandro Forin at CMU:
@article ( IEEECOMP,
key = "Agora" ,
author = "Bisiani, R. and Forin, A." ,
title = "Multilanguage Parallel
Programming on Heterogeneous Systems" ,
journal = "IEEE Transactions on Computers",
publisher= "IEEE-CS" ,
month = "August" ,
year = "1988" ,
)
inproceedings ( BISI87G,
key = "bisi87g" ,
author = "Bisiani,R. and Lecouat,F." ,
title = "A Planner for the Automatization of Programming
Environment Tasks" ,
booktitle= "21st Hawaii International Conference on System
Sciences" ,
publisher= "IEEE" ,
month = "January" ,
year = "1988" ,
bibdate = "Fri Aug 28 09:44:54 1987" ,
)
@inproceedings ( DBGWKSHP,
key = "Agora" ,
author = "Forin, Alessandro" ,
title = "Debugging of Heterogeneous Parallel Systems" ,
booktitle= "Intl. Workshop on Parallel and Distributed Debugging",
publisher= "SIGPLAN Notices, V24-1 Jan. 1989",
address = "Madison, WI",
month = "May" ,
year = "1988" ,
pages = "130-141",
)
@techreport ( ASMREPORT,
key = "Agora" ,
author = "R. Bisiani, F. Alleva, F. Correrini, A. Forin, F. Lecouat, R. L
erner",
title = "Heterogeneous Parallel Processing, The Agora
Shared Memory" ,
institution= "Carnegie-Mellon University" ,
address = "Comp. Science Dept." ,
type = "Tech. Report" ,
number = "CMU-CS-87-112" ,
month = "March" ,
year = "1987" ,
)
Dr Michael Coffin at Unoiversity of Waterloo suggests:
------------------------------------------------------
AUTHOR = "Michael H. Coffin",
TITLE = "Par: {A}n Approach to Architecture-Independent Parallel
Programming",
SCHOOL = "Department of Computer Science, The University of
Arizona",
MONTH = aug,
YEAR = "1990",
ADDRESS = "Tucson, Arizona"
}
Dr. David Skillicorn at Queens University suggests:
---------------------------------------------------
TITLE = {The Purdue Dual {MACE} Operating System},
INSTITUTION = {Purdue University},
KEYWORDS = {Abell1},
YEAR = {1978},
MONTH = {NOV},
}
@ARTICLE{bib:002,
AUTHOR = {Guy T. Almes and Andrew P. Black and Edward D.
Lazowska and Jerre D. Noe},
TITLE = {The Eden System: A Technical Review},
JOURNAL = {IEEE Transactions on Software Engineering},
PAGES = {43--59},
KEYWORDS = {Almes1},
YEAR = {1985},
MONTH = {JAN},
}
@INPROCEEDINGS{bib:003,
AUTHOR = {D.E. Bailey and J.E. Cuny},
TITLE = {An Approach to Programming Process Interconnection
Structures: Aggregate Rewriting Graph Grammars},
BOOKTITLE = {Proceedings of PARLE '87 Parallel Architectures
and Languages Europe, Volume II},
PAGES = {112--123},
ORGANIZATION = {Springer-Verlag, Lecture Notes in Computer
Science},
ADDRESS = {Eindhoven, The Netherlands},
YEAR = {1987},
MONTH = {June},
}
@ARTICLE{bib:004,
AUTHOR = {A. Barak and A. Litman},
TITLE = {{MOS}: a Multicomputer Distributed Operating System},
JOURNAL = {Software: Practice and Experience},
KEYWORDS = {Barak1},
LENGTH = {725},
YEAR = {1985},
MONTH = {AUG},
}
@ARTICLE{bib:005,
AUTHOR = {A. Barak and A. Shiloh},
TITLE = {A Distributed Load Balancing Policy for a
Multicomputer},
JOURNAL = {Software: Practice and Experience},
KEYWORDS = {Barak2},
LENGTH = {901},
YEAR = {1985},
MONTH = {SEP},
}
@ARTICLE{bib:006,
AUTHOR = {? Bartlett and et al},
TITLE = {A NonStop Kernel},
JOURNAL = {PROC of the 8th SOSP},
KEYWORDS = {Bartle1},
YEAR = {1981},
MONTH = {OCT},
}
@ARTICLE{bib:007,
AUTHOR = {M.J. Berger and S.H. Bokhari},
TITLE = {A Partitioning Strategy for Nonuniform Problems on
Multiprocessors},
JOURNAL = {IEEE Transactions on Computers},
VOLUME = {C-36, No.5},
PAGES = {570--580},
KEYWORDS = {rectangular partition with uniform workload},
YEAR = {1987},
MONTH = {May},
}
@INPROCEEDINGS{bib:008,
AUTHOR = {Andrew P. Black},
TITLE = {Supporting Distributed Applications: Experience with
Eden},
JOURNAL = {PROC of the 10th SOSP},
KEYWORDS = {Black1},
YEAR = {1985},
MONTH = {DEC},
}
@ARTICLE{bib:011, ***** RECOMMENDED *****
AUTHOR = {Shahid H. Bokhari},
TITLE = {On the Mapping Problem},
JOURNAL = {IEEE Transactions on Computers},
VOLUME = {C-30},
NUMBER = {3},
PAGES = {207--214},
KEYWORDS = {grecommended,},
YEAR = {1981},
MONTH = {March},
ABSTRACT = {This paper is important because it points out that
the mapping problem is akin to graph traversal and is at
least P-complete. Also see ICPP79. Reproduced in the
1984 tutorial: Interconnection Networks for
parallel and distributed processing by Wu and
Feng.},
}
@ARTICLE{bib:015,
AUTHOR = {W.W. Chu and L.J. Holloway and M.T. Lan and K. Efe},
TITLE = {Task Allocation in Distributed Data Processing},
JOURNAL = {Computer},
PAGES = {57--69},
YEAR = {1980},
MONTH = {November},
}
@INPROCEEDINGS{bib:018,
AUTHOR = {J.G. Donnett and M. Starkey and D.B. Skillicorn},
TITLE = {Effective Algorithms for Partitioning Distributed
Programs},
BOOKTITLE = {Proceedings of the Seventh Annual International
Phoenix Conference on Computers and Communications},
PAGES = {363--369},
YEAR = {1988},
MONTH = {March 16--18},
}
@MISC{bib:025, **** RECOMMENDED ****
AUTHOR = {D.A. Hornig},
TITLE = {Automatic Partitioning and Scheduling on a Network of
Personal Computers},
INSTITUTION = {Carnegie Mellon University, Department of
Computer Science,},
YEAR = {1984},
MONTH = {November},
ABSTRACT = {This Ph.D thesis describes the development of a
language Stardust in which indications are given of the
running time of each function. The run-time evironment
then schedules the functions based on the costs of
message passing and load balancing. There is some
discussion of granularity. The language contains no
explicit partitioning.},
}
@ARTICLE{bib:027,
AUTHOR = {P. Hudak and B. Goldberg},
TITLE = {Distributed Execution of Functional Programs Using
Serial Combinators},
JOURNAL = {IEEE Transactions on Computers},
VOLUME = {C34, No.10},
PAGES = {881--891},
YEAR = {1985},
MONTH = {October},
}
@ARTICLE{bib:031, **** RECOMMENDED ****
AUTHOR = {F.C.H. Lin and R.M. Keller},
TITLE = {The Gradient Model Load Balancing Method},
JOURNAL = {IEEE Transactions on Software Engineering},
VOLUME = {SE-13, No.1},
PAGES = {32--38},
YEAR = {1987},
MONTH = {January},
}
@INPROCEEDINGS{bib:037,
AUTHOR = {L.J. Miller},
TITLE = {A Heterogeneous Multiprocessor Design and the
Distributed Scheduling of its Task Group
Workload},
BOOKTITLE = {Proceedings of 9th Annual Symposium on Computer
Architecture},
PAGES = {283--290},
YEAR = {1982},
MONTH = {April},
}
@ARTICLE{bib:042,
AUTHOR = {D.A. Padua and M.J. Wolfe},
TITLE = {Advanced Compiler Optimizations for Supercomputers},
JOURNAL = {Communications of the ACM},
VOLUME = {29, No.12},
PAGES = {1184--1201},
YEAR = {1986},
MONTH = {December},
}
@ARTICLE{bib:043,
AUTHOR = {Michael L. Powell and Barton P. Miller},
TITLE = {Process Migration in DEMOS/MP},
JOURNAL = {PROC of the 9th SOSP},
KEYWORDS = {Powell1},
LENGTH = {110},
YEAR = {1983},
MONTH = {DEC},
}
@ARTICLE{bib:044,
AUTHOR = {G.S. Rao and H.S. Stone and T.C. Hu},
TITLE = {Assignment of Tasks in a Distributed Processor System
with Limited Memory},
JOURNAL = {IEEE Transactions on Computers},
VOLUME = {C-28, No.4},
PAGES = {291--299},
YEAR = {1979},
MONTH = {April},
}
@ARTICLE{bib:046, **** RECOMMENDED ****
AUTHOR = {C.-C Shen and W.-H. Tsai},
TITLE = {A Graph Matching Approach to Optimal Task Assignment
in Distributed Computing Systems Using a Minimax
Criterion},
JOURNAL = {IEEE Transactions on Computers},
VOLUME = {C-34, No.3},
PAGES = {197--203},
YEAR = {1985},
MONTH = {March},
}
@ARTICLE{bib:054,
AUTHOR = {H. Widjaja},
TITLE = {An Effective Structured Approach to Finding Optimal
Partitions},
JOURNAL = {Computing},
VOLUME = {29, No.3},
PAGES = {241--262},
YEAR = {1982},
}
@INPROCEEDINGS{bib:055,
AUTHOR = {E. Williams},
TITLE = {Assigning Processes to Processors in Distributed
Systems},
BOOKTITLE = {Proceedings of 1983 International Conference on
Parallel},
PAGES = {404--406},
YEAR = {1983},
MONTH = {August},
}
@INPROCEEDINGS{bib:056,
AUTHOR = {F. Ercal and J. Ramanujam and P. Sadayappan},
TITLE = {Task Allocation onto a Hypercube by Recursive Mincut},
BOOKTITLE = {Hypercube Conference},
YEAR = {1988},
}
@article{,
author = {J.-L. Gaudiot and J.I. Pi and M.L. Campbell},
title = {Program Graph Allocation in Distributed Multicomputers},
journal = {Parallel Computing},
volume = {7},
year = {1988},
pages = {227 -- 247},
}
David Hudak at the University of Michigan writes:
-------------------------------------------------
"Performance Evaluation and Prediction for Parallel Algorithms on the
BBN GP1000", F. Bodin, D. Windheiser, W. Jalby, etc., ACM International
Conference on Supercomputing, 1990, pp. 401 - 413.
"The Impact of Synchronization and Granularity on Parallel Systems",
Ding-Kai Chen, Hong-Men Su, and Pen-Chung Yew, International Symposium on
Computer Architecture, 1990, p. 239 - 248
Also: for interesting work on dynamic partitioning, check Polychronopou
los'
article, (IEEE Computer, '86 I think) on Guided Self-Scheduling
Really, the guys you want to read about are: Jalby, Polychronopoulos,
Dennis Gannon, Sameh, Windheiser, and, of course, me. (Oh, Reed
had an IEEE paper '87 on stencils and program partitioning, and
Vrsalovic had a good tech report from CMU.)
Bill Schilit at Columbia suggests:
----------------------------------
Parallel Processing: the Cm* experience, Edward F. Gehringer,
et. al. Digital Press
Dr. David Finkel at Worcester Polythecnic Institute writes:
-----------------------------------------------------------
"Evaluating Dynamic Load Sharing in Distributed Computer
Systems", Computer Systems: Science and Engineering
5 (1990), 89 - 94.
"Load Indices for Load Sharing in Heterogeneous Distributed Computing Systems",
with David Hatch,Proceedings of the 1990 UKSC Conference on
Computer Simulation, Brighton, 1990, 202 - 206.
Zbigniew Chamski (Zbigniew.Chamski@irisa.fr) suggests:
------------------------------------------------------
@string{IEEES = "IEEE Software"} **** RECOMMENDED ****
@string{ECEDOSU = "Electrical and Computer Engineering Department, Oregon State
University"}
@article{
KrLe88,
author = "Kruatrachue, B. and Lewis, T.",
title = "Grain Size Determination for Parallel Processing",
journal = IEEES,
year = 1988,
volume = 5,
number = 1,
pages = "23--32",
month = jan}
@phdthesis{ **** RECOMMENDED ****
Krua87,
author = "Kruatrachue, B.",
title = "Static Task Scheduling and Grain Packing in
Parallel Processing Systems",
school = ECEDOSU,
year = 1987,
address = "{Corvallis, OR, USA}"}
@PhdThesis{ElRe89,
author = "El-Rewini, H.",
title = "Architecture-Independent Task Partitioning and
Scheduling on Arbitrary Parallel Processing Systems",
school = "Department of Computer Science, Oregon State Universi
ty",
year = "1989",
address = "{Corvallis, OR, USA}",
month = nov}
I would also add the following recommendations:
McCreary, C., and Gill, H., "Automatic Determination of Grain Size for
Efficient Parallel Processing", CACM, September 1989, pp. 1073-1078.
Van Tilborg, A., Wittie, L., "Wave Scheduling -- Decentralized Scheduling
of Task Forces in Multicomputers", IEEE Transactions on Computers, 33:835-844,
September 1984.
Berman, F., "Why is Mapping Hard for Parallel Computers?", Proceedings of
the IEEE Parallel/Distributed Computing Networks Seminar, Jan. 31, 1990.
Sarkar, V., "Partitioning and Scheduling for Execution on Multiprocessors",
Ph.D. dissertation, Stanford Tech. Report No. CSL-TR-87-328, April 1987.