load balancing references
Bhaskar Ghosh
from the many responses i got from kind netland folks. hope it helps.
- bhaskar.
============================================================
E. Biagioni, J. Prins, Scan-directed Load Balancing for Highly-Parallel
Mesh-Connected Computers, in Unstructured Scientific Computation on
Scalable Multiprocessors, Mehrotra, et al., eds. MIT Press 1992.
%A L. V. Kale
%T Comparing the Performance of Two Dynamic Load Distribution Methods
%D August 1988
%J Proceedings of the International Conference on Parallel Processing, Vol I
%P 8-11
%C St. Charles
%K icpp
%A Wei Wennie Shu
%A L.V. Kale
%T A Dynamic Load Balancing Strategy for small-grained processes
%R Proc. of Supercomputing '89
%D November 1989
%K 89 acwn
%A V. A. Saletore
%T A dynamic, distributed and adaptive load balancing for parallel
processing of medium-grained tasks.
%R Proc. of the 5th Distributed Memory Computing Conference (DMCC5)
%D Apr. 1990
%C Charleston, NC
%A Amitabh Sinha
%A L. V. Kale
%T A Load Balancing Strategy for Prioritized Execution of Tasks
%R Proceedings of the Workshop on Dynamic Object Placement and Load Balancing, ECOOP'92,
%D June 28
%C Utrecht, The Netherlands.
From: els...@cs.cornell.edu (Anne C. Elster)
Marc Willebeek LaMair wrote a thesis on the topic here at Cornell
with his advisor Tony Reeves in 1990. Remembering he considered
hypercubes, among others. Try contacting Prof Reeves
at "ree...@ee.cornell.edu" for further info.
ICPP 1992
%A Emile Haddad
%T Optimal Distribution of Random Workloads Over Heterogeneous Processors
with Contrasting Loads
%P II-58--II-65
%K load distribution/balancing,
ICPP 1992
%A James M. Conrad
%A Dharma P. Agrawal
%T A Graph Partitioning-Based Load Balancing Strategy for
a Distributed Memory Machine
%P II-74--II-81
%K load distribution/balancing,
From: ni...@cs.wm.edu (David Nicol)
I presented a paper "Communication Efficient Global Load Balancing"
at the Scalable High Performance Computing Conference, April 92,
see the proceedings, pp. 292-299. The simple idea was to perfectly
balance the load moving as little as possible around. One's ability
to move things around depends, I suppose, on the network topology,
but I view that issue as largely academic in this brave new world
of circuit-switched routing.
@inproceedings{berman84,
author = {Francine Berman and Lawrence Snyder},
booktitle = {International Conference on Parallel Processing},
month = aug,
pages = {307-309},
title = {On Mapping Parallel Algorithms Into Parallel Architectures},
year = {1984}
}
@inproceedings{berman88,
author = {Francine Berman and Bernd Stramm},
booktitle = {ACM/SIGPLAN PPEALS 1988},
month = sep,
number = {9},
pages = {222-234},
title = {Communication-Sensitive Heuristics and Algorithms for Mapping Compilers},
volume = {23},
year = {1988}
}
@article{bokhari79,
author = {S. H. Bokhari},
journal = {IEEE Transactions on Software Engineering},
month = jul,
number = {4},
pages = {341-349},
title = {Dual Processor Scheduling with Dynamic Reassignment},
volume = {SE-5},
year = {1979}
}
@inproceedings{chen88,
author = {Woei-Kae Chen and Edward F. Gehringer},
booktitle = {International Conference on Hypercube Concurrent Computers and Applications},
month = jan,
pages = {200-209},
title = {A Graph-Oriented Mapping Strategy for a Hypercube},
volume = {1},
year = {1988}
}
@article{chou82,
author = {T. C. K. Chou and J. A. Abraham},
journal = {IEEE Transactions on Software Engineering},
month = jul,
number = {4},
pages = {401-412},
title = {Load Balancing in Distributed Systems},
volume = {SE-8},
year = {1982}
}
@article{chu80,
author = {W. W. Chu and L. J. Holloway and M. Lan and K. Efe},
journal = {IEEE Computer},
month = nov,
number = {11},
pages = {57-69},
title = {Task Allocation in Distributed Data Processing},
volume = {13},
year = {1980}
}
@article{eager86,
author = {Derek L. Eager and Edward D. Lazowska and John Zahorjan},
journal = {IEEE Transactions on Software Engineering},
month = may,
number = {5},
pages = {662-675},
title = {Adaptive Load Sharing in Homogeneous Distributed Systems},
volume = {SE-12},
year = {1986},
keywords = {design, load sharing, local area networks, performance, queueing models, threshold policies}
}
@article{eager88,
author = {D. L. Eager and E. D. Lazowska and J. Zahorjan},
journal = {ACM SIGMETRICS Perfomances Evaluation Review},
month = may,
number = {1},
pages = {63-72},
title = {The Limited Performance Benefits of Migrating Active Processes for Load Sharing},
volume = {16},
year = {1988}
}
@inproceedings{iqbal86,
author = {M. A. Iqbal and J. H. Saltz and S. H. Bokhari},
booktitle = {Proceedings of the 1986 International Conference on Parallel Processing},
pages = {1040-1047},
title = {A Comparative Analysis of Static and Dynamic Load Balancing Strategies},
year = {1986}
}
@article{leland86,
author = {W.E. Leland and T.J. Ott},
journal = {ACM SIGMETRICS Performance Evaluation Review},
month = may,
number = {1},
pages = {54-69},
title = {Load-balancing Heuristics and Process Behavior},
volume = {14},
year = {1986}
}
@article{lin87,
author = {Frank C. H. Lin and Robert M. Keller},
journal = {IEEE Transactions on Software Engineering},
month = jan,
number = {1},
pages = {32-38},
title = {The Gradient Model Load Balancing Method},
volume = {13},
year = {1987}
}
@inproceedings{lo81,
author = {Virginia Mary Lo and J. W. S. Liu},
booktitle = {International Conference on Parallel Processing},
pages = {358-360},
title = {Task Assignment in Distributed Multiprocessor Systems},
year = {1981}
}
@inproceedings{lo84,
author = {V. M. Lo},
booktitle = {International Conference on Distributed Computer Systems},
pages = {30-39},
title = {Heuristic Algorithms for Task Assignment in Distributed Systems},
year = {1984}
}
@inproceedings{lo85,
author = {V. M. Lo},
address = {Denver},
booktitle = {Proceedings of the 5th International Conference on Distributed Computing Systems},
month = may,
pages = {329-336,},
title = {Task Assignment to Minimize Completion Time},
year = {1985}
}
@inproceedings{lo88a,
author = {V. M. Lo},
booktitle = {Proceedings of the 1988 International Conference on Parallel Processing},
pages = {239-244},
title = {Algorithms for Static Task Assignment and Symmetric Contraction in Distributed Computing Systems},
volume = {2},
year = {1988}
}
@article{lo88b,
author = {V. M. Lo},
journal = {IEEE Transactions on Computers},
month = nov,
number = {11},
pages = {1384-1397},
title = {Heuristic Algorithms for Task Assignment in Distributed Systems},
volume = {37},
year = {1988},
keywords = {load balancing, task assignment}
}
@inproceedings{ni81,
author = {Lionel M. Ni and Kai Hwang},
booktitle = {International Conference on Parallel Processing},
month = aug,
pages = {352-357},
title = {Optimal Load Balancing Strategies for a Multiple Processor System},
year = {1981}
}
@article{nicol88,
author = {David D. Nicol and Joel S. Saltz},
journal = {IEEE Transactions on Computers},
month = sep,
number = {9},
pages = {1073-1087},
title = {Dynamic Remapping of Parallel Computations with Varying Resource Demands},
volume = {37},
year = {1988}
}
@book{sadayappan87a,
author = {Ponnuswamy Sadayappan and Fikret Ercal},
booktitle = {International Conference on Supercomputing},
month = jul,
pages = {475-497},
publisher = {Springer Verlag},
series = {LNCS 297},
title = {Cluster-partioning Approaches to Mapping Parallel Programs onto a Hypercube},
year = {1987}
}
@article{sadayappan87b,
author = {Ponnuswamy Sadayappan and Fikret Ercal},
journal = {IEEE Transactions on Computers},
month = dec,
number = {12},
pages = {1408-1424},
title = {Nearest-Neibhbor Mapping of Finite Element Graphs onto Processor Meshes},
volume = {36},
year = {1987}
}
@article{sinclair87,
author = {J. B. Sinclair},
journal = {Journal of Parallel and Distributed Computing},
pages = {342-362},
title = {Efficient Computation of Optimal Assignments for Distributed Tasks},
volume = {4},
year = {1987},
keywords = {load balancing}
}
@ARTICLE{Baden91,
AUTHOR = "Baden, S. B.",
TITLE = "Programming Abstractions for dynamically partitioning and coordinating
localized scientific calculations running on multiprocessors",
JOURNAL = "SIAM J. Sci. Stat. Comput.",
VOLUME = 12,
NUMBER = 1,
PAGES = "145-157",
YEAR = 1991
}
@ARTICLE{WilliamsCPE2,
AUTHOR = "Williams, R. D.",
TITLE = "Performance of Dynamic Load Balancing Algorithms for Unstructured Mesh
Calculations",
JOURNAL = "Concurrency: Practice and Experience",
VOLUME = 3,
PAGES = "457-481",
YEAR = 1991
}
@INPROCEEDINGS{DeKeyserDMCC6,
AUTHOR = "De Keyser, J. and Roose, D.",
TITLE = "A Software Tool for Load Balanced Adaptive Multiple Grids on Distribute
d Memory Computers",
BOOKTITLE = "Proceedings of the 6th Distributed Memory Computing Conference",
PUBLISHER = "IEEE Computer Society Press",
PAGES = "122-128",
YEAR = 1991
}
@INPROCEEDINGS{DeKeyserSHPCC7,
AUTHOR = "De Keyser, J. and Roose, D.",
TITLE = "Incremental Mapping for Solution-Adaptive Multigrid Hierarchies",
BOOKTITLE = "Proceedings of the Scalable High Performance Computing Conference '
92",
PUBLISHER = "IEEE Computer Society Press",
PAGES = "401-408",
YEAR = 1992,
}
@article{Cyb89,
author = {G. Cybenko},
title = {Dynamic Load Balancing for Distributed Memory Multiprocessors},
journal = {Journal of Parallel and Distributed Computing},
volume = {7},
pages = {279-301},
year = 1989,
annote = {in hangmap},
annote = {rutger.ref}}
@inproceedings{Hac87,
author = {Anna Hac and Xiaowei Jin},
title = {Dynamic Load Balancing in a Distributed System Using a Decentralized Algorithm},
booktitle = {The 7th International Conference on Distributed Computing Systems},
publisher = {IEEE},
pages = {170-177},
month = {Sep},
year = 1987,
annote = {rutger.ref}}
@article{Hac89,
author = {A. Hac},
title = {Load Balancing in Distributed Systems: A Summary},
journal = {Performance Evaluation Review},
volume = {16},
number = {2},
pages = {17-19},
month = {feb},
year = 1989,
annote = {in hangmap},
annote = {rutger.ref}}
@article{Hac90,
author = {Anna Hac and Theodore J. Johnson},
title = {Sensitivity Study of the Load Balancing Algorithm in a Distributed System},
journal = {Journal of Parallel and Distributed Computing},
volume = {10},
pages = {85-89},
year = 1990,
annote = {dynamic allocation},
annote = {in hangmap},
annote = {rutger.ref}}
@techreport{Hai88,
author = {Max Hailperin},
title = {Load Balancing for Massively-Parallel Soft-Real-Time Systems},
institution = {Stanford University, Dept of Computer Science},
type = {Int Report},
number = {STAN-CS-88-1222, also KSL-88-62},
month = {Sept},
year = 1988,
annote = {dynamic allocation},
annote = {in hangmap},
annote = {rutger.ref}}
@inproceedings{Ham80,
author = {Dan Hammerstrom},
title = {Dynamic, Decentralized Load Leveling},
booktitle = {Euromicro 80},
address = {London, England},
month = {Oct},
year = 1980,
annote = {rutger.ref}}
@article{Kum89,
author = {Anurag Kumar},
title = {Adaptive Load Control of the Central Processor in a Distributed System with a Star Topology},
journal = {IEEE Transactions on Computers},
volume = {38},
number = {11},
pages = {1502-1512},
month = {nov},
year = 1989,
annote = {dynamic allocation},
annote = {in hangmap},
annote = {rutger.ref}}
@article{Ni85b,
author = {Lionel M. Ni and Chong-Wei Xu and Thomas B. Gendreau},
title = {Distributed Drafting Algorithm for Load Balancing},
journal = {IEEE Transactions on Software Engineering},
volume = {SE-11},
number = {10},
pages = {1153-1161},
month = {Oct},
year = 1985,
annote = {rutger.ref}}
@techreport{Pas87a,
author = {Douglas M. Pase},
title = {Load Balancing Heuristics and Network Topologies for Distributed Evaluation of {Prolog}},
institution = {Oregon Graduate Center},
type = {Technical Report},
number = {CS/E 87-005},
address = {Beaverton, OR},
year = 1987,
annote = {rutger.ref}}
@article{She88a,
author = {Sheldon Shen},
title = {Cooperative Distributed Dynamic Load Balancing},
journal = {Acta Informatica},
volume = {25},
pages = {663-676},
year = 1988,
annote = {dynamic allocation},
annote = {in hangmap},
annote = {rutger.ref}}
From: vn...@eola.cs.ucf.edu (Nageshwara Rao Vempaty)
We had worked on dynamic load redistribution algorithms when it is
difficult to asses the total amount of work available in each node.
THere is a paper by myself and Vipin Kumar in Dist. Mem. Multiprocessor
Conference 89 titled "Load balancing on the Hypercube Arch.". If
you find it *informative*, there is an updated paper "Load balancing on
Multiprocessors" by Ananth, Vipin Kumar and me, available as a TR
from Univ. of Minnesota. The algorithms we analyze redistribute load
on demand (when free procs. are available) and can be implemented on
most MIMD machines. We had experimented with backtrack search problems.
\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.
\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.
\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.
\item{[DrGu89]}
Karen M. Dragon, John L. Gustafson, ``A Low-Cost Hypercube Load-Balance Algorithm'',
{\em Proceedings of the Fourth Conference on Hypercubes, Concurrent Computers, and Applications},
Monterey, CA, Mar. 1989, pp.~583-589.
\item{[Sale90]}
Vikram A. Saletore, ``A Distributed and Adaptive Dynamic Load Balancing Scheme for Parallel Processing of Medium-Grain Tasks'',
{\em Proceedings of the Fifth Distributed Memory Computing Conference},
Charleston, SC, Apr. 1990, pp.~994-999.
\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.~4, no.~4, 1987, pp.~521-530.
\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.
\item{[Vorn87]}
Oliver Vornberger, ``Load Balancing in a Network of Transputers'',
{\em Second International Workshop on Distributed Algorithms},
Amsterdam, Jul. 1987.
\item{[WiRe89]}
Marc Willebeek-LeMair, Anthony P. Reeves, ``Distributed Dynamic Load Balancing'',
{\em Proceedings of the Fourth Conference on Hypercubes, Concurrent Computers, and Applications},
Monterey, CA, Mar. 1989, pp.~609-612.
@TechReport{barak-shiloh84,
author = {A. Barak and A. Shiloh},
title = {A distributed load balancing policy for a multicomputer},
institution = {Hebrew University of Jerusalem},
year = {1984} }
@Article{barak-shiloh85,
author = {A. Barak and A. Shiloh},
title = {A Distributed Load Balancing Policy for a Multicomputer},
journal = {Software - Practice and Experience},
year = {1985},
volume = {15},
pages = {901-913},
month = {September},
keywords = {load balancing} }
@InProceedings{baumgartner-wah88,
author = {Katherine M. Baumgartner and Benjamin W. Wah},
title = {A Global Load Balancing Strategy for a Distributed Computer System},
booktitle = {Proceedings of the Workshop on the Future Trends of Distributed Computing Systems in the 1990's},
year = {1988},
pages = {93-102},
month = {September} }
@Article{baumgartner-wah89,
author = {Katherine M. Baumgartner and Benjamin W. Wah},
title = {GAMMON: A Load Balancing Strategy for Local Computer Systems with Multiaccess Networks},
journal = {IEEE Transactions on Computers},
year = {1989},
volume = {38},
number = {8},
pages = {1098-1109},
month = {August},
keywords = {distributed systems, load balancing, broadcast, collision detection, multiaccess networks} }
@InProceedings{ezzat86,
author = {A. K. Ezzat},
title = {Load Balancing in NEST: A Network of Workstations},
booktitle = {Proc. 1986 ACM/IEEE-CS Fall Joint Computer Conference},
year = {1989},
pages = {1138-1149},
month = {November} }
@InProceedings{ferguson-yemini-nikolaou88,
author = {Donald Ferguson and Yechiam Yemini and Christos Nikolaou},
title = {Microeconomic Algorithms for Load Balancing in Distributed Computer Systems},
booktitle = {8th International Conference on Distributed Computing Systems},
year = {1988},
pages = {491-499},
month = {June} }
@InProceedings{ferrari-zhou86,
author = {D. Ferrari and S. Zhou},
title = {A Load Index for Dynamic Load Balancing},
booktitle = {Proceedings of the Fall Joint Computer Conference},
year = {1986},
pages = {684-690},
month = {November} }
@InProceedings{gopinath-gupta91,
author = {Prabha Gopinath and Rajiv Gupta},
title = {A Hybrid Approach to Load Balancing in Distributed Systems},
booktitle = {Symposium on Experiences with Distributed and Multiprocessor Systems},
year = {1991},
pages = {133-147},
organization = {Usenix},
month = {March} }
@InProceedings{goswami-iyer-devarakonda89,
author = {Kumar K. Goswami and Ravishankar K. Iyer and Murthy V. Devarakonda},
title = {Load Sharing Based on Task Resource Prediction},
booktitle = {Proc. 22nd Annual Hawaii Info. Conf on System Sciences, Vol. II: Software Track},
year = {1989},
pages = {921-27},
month = {January} }
@TechReport{kreuger-finkel84,
author = {P. Kreuger and R. A. Finkel},
title = {An Adaptive Load Balancing Algorithm for a Multicomputer},
institution = {Department of Computer Science},
year = {1984},
number = {Tech Rep. 539},
address = {University of Wisconsin, Madison},
month = {April} }
@TechReport{kreuger-finkel87,
author = {P. Kreuger and R. A. Finkel},
title = {When is the best load sharing algorithm a load balancing algorithm?},
institution = {Department of Computer Science},
year = {1987},
number = {Tech Rep. 694},
address = {University of Wisconsin, Madison},
month = {April} }
@InProceedings{livny-melman82,
author = {M. Livny and M. Melman},
title = {Load Balancing in Homogeneous Broadcast Distributed Systems},
booktitle = {Proc. Modeling Perform. Eval. Comput. Syst., ACM SIGMETRICS},
year = {1982},
pages = {47-55},
month = {April} }
@Article{lo88,
author = {Virginia Mary Lo},
title = {Heuristic Algorithms for Task Assignment in Distributed Systems},
journal = {IEEE Transactions on Computers},
year = {1988},
volume = {37},
number = {11},
pages = {1384-1397},
month = {November},
keywords = {distributed systems, load balancing, resource allocation, task assignment, task scheduling, interference costs} }
--
===============================================================================
Bhaskar Ghosh "Tomar pujar chholey,
gh...@cs.yale.edu @yalecs.bitnet Tomay bhulei thaki"- Robithakur
===============================================================================