Path: utzoo!news-server.csri.toronto.edu!cs.utexas.edu!asuvax!ncar!elroy.jpl.nasa.gov!usc!zaphod.mps.ohio-state.edu!sol.ctr.columbia.edu!emory!hubcap!hbchen From: hbchen@evax.uta.edu (Hsing B Chen) Newsgroups: comp.parallel Subject: Re: Call for papers: Special issue on Neural Computing on Massively Parallel Processors Keywords: Neural Computing, Neural Networks, Massively Parallel Processors Message-ID: <13404@hubcap.clemson.edu> Date: 4 Mar 91 16:12:25 GMT References: <13295@hubcap.clemson.edu> Sender: fpst@hubcap.clemson.edu Organization: Computer Science Engineering Univ. of Texas at Arlington Lines: 954 Approved: parallel@hubcap.clemson.edu Apparently-To: uunet!comp-parallel 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 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'" 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