hbchen@evax.uta.edu (Hsing B Chen) (03/05/91)
Two weeks ago, I posted a request for some reference material on load
balancing of Distributed computing systems. Here there are the
information that I got. I would like to thank the people who sent me these
materials. Also I would like to reference other related issues such as
load sharing , process scheduling and process migration of distributed
systems or heterogeneous systems. I appreciate any information that I
could get. Thanks again.
HB Chen hbchen@evax.uta.edu
CSE Dept. University of Texas at Arlington
[1]----------------------
From :
prash@hubcap.clemson.edu
(p.s. ignore the \item \em, etc!)
\item{[BrFi81]}
, Raymond M. Bryant, Raphael A. Finkel ``A Stable Distributed Scheduling Algorithm'',
{\em Proceedings 2nd Int. Conference on Distributed Computing},
Apr. 1981, pp.~314-323\\
{\em Keywords:} Load Balancing, Scheduling, Stability, Job-level
\item{[CaKu88a]}
Thomas L. Casavant, Jon G. Kuhl ``A Taxonomy of Scheduling in General-Purpose Distributed Computing Systems'',
{\em IEEE Transactions on Software Engineering},
vol.~SE-14, no.~2, Feb. 1988, pp.~141-154\\
{\em Keywords:} Distributed Systems, Scheduling, Load Balancing, Taxonomy
\item{[CaKu88b]}
Thomas L. Casavant, Jon G. Kuhl ``Effects of Response and Stability on Scheduling in Distributed Computing Systems'',
{\em IEEE Transactions on Software Engineering},
vol.~SE-14, no.~11, Nov. 1988, pp.~1578-1588\\
{\em Keywords:} Distributed Systems, Scheduling, Load Balancing, Stability
\item{[ChAb82]}
Timothy C. K. Chou, Jacob A. Abraham ``Load Balancing in Distributed Systems'',
{\em IEEE Transactions on Software Engineering},
vol.~SE-8, no.~4, Jul. 1982, pp.~401-412\\
{\em Keywords:} Distributed Systems, Static Load Balancing, Heterogeneous Processors,
Stochastic
\item{[ChAb86]}
Timothy C. K. Chou, Jacob A. Abraham ``Distributed Control of Computer Systems'',
{\em IEEE Transactions on Computers},
vol.~C-35, no.~6, Jun. 1986, pp.~564-567\\
{\em Keywords:} Job Scheduling, Distributed Control, Adaptive Control, Load Balancing,
Dynamic, Linear Predictive
\item{[ChKo79]}
Yuan-Chieh Chow, Walter H. Kohler ``Models for Dynamic Load Balancing in a Heterogeneous Multiple Processor System'',
{\em IEEE Transactions on Computers},
vol.~C-28, no.~5, May 1979, pp.~354-361\\
{\em Keywords:} Dynamic Load Balancing, Scheduling, Queuing Models, Heterogeneous Processors,
Adaptive deterministic
\item{[ChPa89]}
Alok N. Chaudhary, Janak H. Patel ``Load Balancing and Task Decomposition Techniques for Parallel Implementation of Integrated Vision Systems Algorithms'',
{\em Proceedings of Supercomputing 1989},
IEEE Computer Society, New York, Nov 13-17 1989, pp.~266-275\\
{\em Keywords:} Load Balancing, Distributed Systems, Static Balancing, Dynamic Balancing,
Image Processing, Weighted Static Balancing
\item{[Chow90]}
Shyamal Chowdhury ``The Greedy Load Sharing Algorithm'',
{\em Journal of Parallel and Distributed Computing},
vol.~9, no.~1, Jun. 1990, pp.~93-99\\
{\em Keywords:} Load Balancing, Dynamic, Simulation
\item{[Cybe89]}
George Cybenko ``Dynamic Load Balancing for Distributed Memory Multiprocessors'',
{\em Journal of Parallel and Distributed Computing},
vol.~7, no.~2, Oct. 1989, pp.~279-301\\
{\em Keywords:} Dynamic Load Balancing, Diffusion Scheme,
\item{[DrGu89]}
Karen M. Dragon, John L. Gustafson ``A Low-Cost Hypercube Load-Balance Algorithm'',
{\em Proceedings of Fourth Conference on Hypercubes, Concurrent Computers, and Applications},
Monterey, CA, Mar. 1989, pp.~583-589\\
{\em Keywords:} Load Balancing, Distributed, Hypercube, Dynamic, Perfect Balance,
Timestepping, Recursive Bisection
\item{[EaLZ86]}
Derek L. Eager, Edward D. Lazowska, John Zahorjan ``Adaptive Load Sharing in Homogeneous Distributed Systems'',
{\em IEEE Transactions on Software Engineering},
vol.~SE-12, no.~5, May 1986, pp.~662-675\\
{\em Keywords:} Load Balancing, Stochastic Analysis, Distributed Systems,
Homogeneous nodes, Threshold Policies
\item{[FFKS89]}
Geoffrey C. Fox, W. Furmanski, Jeff Koller, P. Simic ``Physical Optimization and Load Balancing Algorithms'',
{\em Proceedings of Fourth Conference on Hypercubes, Concurrent Computers, and Applications},
Monterey, CA, Mar. 1989, pp.~591-594\\
{\em Keywords:} Optimization, Load Balancing, Static
\item{[FJLO88]}
Geoffrey C. Fox, Mark A. Johnson, Gregory A. Lyzenga, Steve W. Otto, et al.{\em Solving Problems on Concurrent Processors, Vol. 1, General Techniques and Regular Problems},
Prentice Hall, Englewood Cliffs, N.J., 1988
\item{[Felt88]}
Edward W. Felten ``Best-First Branch-and-Bound on a Hypercube'',
{\em 3rd Conference on Hypercube Concurrent Computers and Applications},
Geoffrey Fox, Pasadena, CA, Jan. 1988, pp.~1500-1504\\
{\em Keywords:} Load Balancing, Random Distribution, Termination Detection,
Asynchronous, NCUBE, TSP
\item{[GrNR90]}
Dirk C. Grunwald, Bobby A. A. Nazief, Daniel A. Reed ``Empirical Comparison of Heuristic Load Distribution in Point-to-Point Multicomputer Networks'',
{\em DMCC5},
Charleston, SC, Apr. 1990, pp.~??\\
{\em Keywords:} Load Balancing, Simulation, Process-level
\item{[Hinz90]}
Didier Y. Hinz ``A Run-time Load Balancing Strategy for Highly Parallel Systems'',
{\em DMCC5},
Charleston, SC, Apr 1990, pp.~??\\
{\em Keywords:} Load Balancing, Dynamic, Distributed, Matrix-based
\item{[HoTC89]}
Jiawei Hong, Xiaonan Tan, Marina Chen ``Dynamic Cyclic Load Balancing on Hypercube'',
{\em Proceedings of Fourth Conference on Hypercubes, Concurrent Computers, and Applications},
Monterey, CA, Mar. 1989, pp.~595-598\\
{\em Keywords:} Load Balancing, Dynamic, Distributed, Hypercube, Periodic, Two Measures
of Load, Branch-and-Bound
\item{[Koll89]}
, Jeff Koller ``The MOOS II Operating System and Dynamic Load Balancing'',
{\em Proceedings of Fourth Conference on Hypercubes, Concurrent Computers, and Applications},
Monterey, CA, Mar. 1989, pp.~599-602\\
{\em Keywords:} Load Balancing, Dynamic, Centralized, Hypercube
\item{[KuRa89]}
Vipin Kumar, V. Nageshwara Rao ``Load Balancing on the Hypercube Architecture'',
{\em Proceedings of Fourth Conference on Hypercubes, Concurrent Computers, and Applications},
Monterey, CA, Mar. 1989, pp.~603-608\\
{\em Keywords:} Load Balancing, Distributed, Hypercube, Demand-driven
\item{[LiKe87]}
Frank C. H. Lin, Robert M. Keller ``The Gradient Model Load Balancing Method'',
{\em IEEE Transactions on Software Engineering},
vol.~SE-13, no.~1, Jan. 1987, pp.~32-38\\
{\em Keywords:} Dynamic Load Balancing, Gradient Model (Relaxation),
Demand Driven, Large-Diameter Multiprocessors, Loosely coupled
\item{[LiMe82]}
Miron Livny, Myron Melman ``Load Balancing in Homogeneous Broadcast Distributed Systems'',
{\em Proceedings ACM Computer Network Performance Symposium},
1982, pp.~47-55\\
{\em Keywords:} Load Balancing, Broadcast Medium, Ethernet
\item{[MaTM88]}
Richard P. Ma, Fu-Sheng Tsung, Mae-Hwa Ma ``A Dynamic Load Balancer for a Parallel Branch-and-Bound Algorithm'',
{\em 3rd Conference on Hypercube Concurrent Computers and Applications},
Geoffrey Fox, Pasadena, CA, Jan. 1988, pp.~1505-1513\\
{\em Keywords:} Dynamic Load Balancing, Inquiry, Ametek, Asynchronous, Depth First
\item{[NiAb81]}
Lionel M. Ni, Kaveh Abani ``Nonpreemptive Load Balancing in a Class of Local Area Networks'',
{\em Proceedings of the Computer Networking Symposium},
IEEE, New York, Dec. 1981, pp.~113-118\\
{\em Keywords:} Load Balancing, Local Area Networks, Non-Broadcast, Heterogeneous
\item{[NiHw81]}
Lionel M. Ni, Kai Hwang ``Optimal Load Balancing Strategies for a Multiple Processor System'',
{\em Proceedings of the 1981 International Conference on Parallel Processing},
Aug. 1981, pp.~352-357\\
{\em Keywords:} Load Balancing, Distributed Memory, Distributed Algorithm, Optimal,
Probabilistic Fixed Dynamic Balancing, Load Driven
\item{[NiXG85]}
Lionel M. Ni, Chong-Wei Xu, Thomas B. Gendreau ``A Distributed Drafting Algorithm for Load Balancing'',
{\em IEEE Transactions on Software Engineering},
vol.~SE-11, no.~10, Oct. 1985, pp.~1153-1161\\
{\em Keywords:} Distributed Systems, Dynamic Load Balancing, Drafting, Bidding, State
Change Broadcast
\item{[Plax89]}
C. Greg Plaxton ``Load Balancing, Selecting and Sorting on the Hypercube'',
{\em Proceedings of Fourth Conference on Hypercubes, Concurrent Computers, and Applications},
Monterey, CA, Mar. 1989, pp.~613-616\\
{\em Keywords:} Hamming Balls, Load Balancing, Token Balancing (uniform-sized processes)
\item{[Sale90]}
Vikram A. Saletore ``A Distributed and Adaptive Dynamic Load Balancing Scheme for Parallel Processing of Medium-Grain Tasks'',
{\em DMCC5},
Charleston, SC, Apr 1990, pp.~??\\
{\em Keywords:} Load Balancing,
Dynamic, Deterministic Non-fixed, Adaptive, Periodic,
Process-level, Infinite Migration Distance, iPSC/2
\item{[ShCh88]}
Kang G. Shin, Yi-Chieh Chang ``Load Sharing in Distributed Real-Time Systems with Broadcast of State Changes'',
International Computer Science Institute (ICSI) TR-88-006,
Oct. 31 1988 \\
{\em Keywords:} Distributed Real-Time Systems, Load Balancing, Deadlines, Missing
Probability (as against probability of hitting), Buddy Set, Preferred List,
State-Change Broadcast, Non-probing
\item{[ShCh89]}
Kang G. Shin, Yi-Chieh Chang ``Load Sharing in Hypercube Multicomputers for Real-time Applications'',
{\em Proceedings of Fourth Conference on Hypercubes, Concurrent Computers, and Applications},
Monterey, CA, Mar. 1989, pp.~617-621
\item{[ShKa89]}
Wei Shu, L. V. Kale ``A Dynamic Scheduling Strategy for the Chare-Kernel System'',
{\em Proceedings of Supercomputing 1989},
IEEE Computer Society, New York, Nov 13-17 1989, pp.~389-398\\
{\em Keywords:} Load Balancing, Dynamic, Adaptive
\item{[ShUp87]}
Eli Shamir, Eli Upfal ``A Probabilistic Approach to the Load-Sharing Problem in Distributed Systems'',
{\em Journal of Parallel and Distributed Computing},
vol.~, no.~4, 1987, pp.~521-530\\
{\em Keywords:} Load Balancing, Random Walk, Asynchronous, Synchronous, Trees
\item{[StSi84]}
, John A. Stankovic, Inderjit S. Sidhu ``An Adaptive Bidding Algorithm for Processes, Clusters and Distributed Groups'',
{\em Proceedings of the Fourth International Conference on Distributed Computing Systems},
San Francisco, CA, vol.~4, May 1984, pp.~49-59\\
{\em Keywords:} Load Balancing, Dynamic, Distributed, Adaptive, Bidding
\item{[Ston78]}
Harold S. Stone ``Critical Load Factors in Two-Processor Distributed Systems'',
{\em IEEE Transactions on Software Engineering},
vol.~SE-4, no.~3, May 1978, pp.~254-258\\
{\em Keywords:} Distributed Systems, Load balancing, Optimal Assignments at Run-time,
Critical Load Factor, Cutset
\item{[Ston87]}
Harold S. Stone{\em High-Performance Computer Architecture},
Addison Wesley, Reading, MA., 1987
\item{[SuBK89]}
, S. C. Su, P. Biswas, R. Krishnaswamy ``Experiments in Dynamic Load Balancing of Parallel Logic Programs'',
{\em Proceedings of Fourth Conference on Hypercubes, Concurrent Computers, and Applications},
Monterey, CA, Mar. 1989, pp.~623-626\\
{\em Keywords:} Load Balancing, Dynamic, Distributed, Logic Programming, Transputers,
Profiling
\item{[TaTo85]}
A. N. Tantawi, D. Towsley ``Optimal Static Load Balancing in Distributed Computer Systems'',
{\em Journal of the ACM},
vol.~32, no.~2, Apr. 1985, pp.~445-465\\
{\em Keywords:} Static Load Balancing, Stochastic Analysis
\item{[Vorn87]}
Oliver Vornberger ``Load Balancing in a Network of Transputers'',
{\em Second International Workshop on Distributed Algorithms},
J. van Leeuwen, Amsterdam, Jul. 1987, pp.~\\
{\em Keywords:} Branch-and-Bound, Transputers, Synchronous, Load Balancing, Random Choice
\item{[WaMo85]}
Yung-Terng Wang, Robert J. T. Morris ``Load Sharing in Distributed Systems'',
{\em IEEE Transactions on Computers},
vol.~C-34, no.~3, Mar. 1985, pp.~204-217\\
{\em Keywords:} Distributed Systems, Load Balancing, Scheduling, Taxonomy
\item{[Walk89]}
David W. Walker ``The Implementation of a 3-Dim PIC Code on a Hypercube Concurrent Processor'',
{\em Proceedings of Fourth Conference on Hypercubes, Concurrent Computers, and Applications},
Monterey, CA, Mar. 1989, pp.~1255-1261\\
{\em Keywords:} Global Communication, Irregular Communication, Slowly Changing
Communication/ Loosely Synchronous Communication, Crystalline
Environment, PIC (Particle In Cell), Quasi-Static, Load Balanced
\item{[WiRe89]}
Marc Willebeek-LeMair, Anthony P. Reeves ``Distributed Dynamic Load Balancing'',
{\em Proceedings of Fourth Conference on Hypercubes, Concurrent Computers, and Applications},
Monterey, CA, Mar. 1989, pp.~609-612\\
{\em Keywords:} Load Balancing, Dynamic, Distributed, Load-driven
[2] ---------------------------------------
From: Hiroyuki Miyata <miyata@cs.uiuc.edu>
This is a list of papers concerning with "Load Balancing". This was posted
on comp.parallel in the past.
Hiro
-------------------------------------
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.
[3]--------------------------------------------------
From: partridg@probitas.cs.utas.edu.au (Andrew Partridge)
I have written the following technical report:
Partridge, A., 'Load distribution with prioritised tasks',
University of Tasmania, Department of EE&CS, Technical Report
R90-1, May 1990.
The report informally describes a load distribution algorithm
designed to handle the prioritised tasks produced by a
speculative evaluation scheme for a functional language
implementation. The algorithm is very loosely based on
Keller and Lin's gradient load balancing model. It tries
to dynamically maximise the function:
sigma (max (priority of task t) )
p t
where p ranges over the processors, and
t ranges over the runnable tasks on processor p.
The algorithm assumes only a point-to-point network of
any topology connecting the processors. No shared memory is
needed, and there is no centralised control of the algorithm
(ie it is a truly distributed algorithm).
The report does not present any simulation results for the
algorithm - they are coming.
A copy of the report is yours for the asking.
I hope this is useful. No doubt others will swamp you with
references to the well-known published works.
Cheers,
Andrew Partridge
-----------------------------------------------------------------------
[4]-------------------------------------------------
Email: partridg@probitas.cs.utas.edu.au
Telephone: (002) 202908 Fax: (002) 202913 Telex: AA 58150
Department of Computer Science, University of Tasmania,
GPO Box 252C Hobart, Tasmania, AUSTRALIA 7001
From: "L. V. Kale'" <kale@cs.uiuc.edu>
If you mean dynamic load balancing, I have a few papers.
If you want a copy, send email to woodwort@m.cs.uiuc.edu.
[89--11] W. W. Shu and L. V. Kale, ``Dynamic Scheduling of
Medium grained processes on Multi-Computers'',
Submitted for possible publication to IEEE Transactions on Parallel
and Distributed Systems, May 1989.
[89--8] W. W. Shu and L. V. Kale, ``A Dynamic Load Balancing
Strategy for the Chare Kernel System'', Proc. of
Supercomputing '89, November 1989, pp.\ 389-398.
[88--4] L. V. Kale, ``Comparing the Performance
of Two Dynamic Load Distribution Methods'', Proceedings
of the International Conference on Parallel Processing,
August 1988, pp.\ 8-11.
Also, one of students, Vikram Saletore, had a paper on a different
load balancing scheme in DMCC conference in 1990.
Hope this helps.
Kale