A PRODUCT FORM SOLUTION FOR TREE NETWORKS WITH DIVISIBLE LOADS
Abstract
A product form solution for the optimal fractions of divisible load to distribute to processors in a multi-level tree network is described. Here optimality involves parallel processing the load in a minimal amount of time. This tractable solution is similar to the product form solution for equilibrium state probabilities arising in Markovian queueing networks. The existence of this product form solution answers a long standing open question for divisible load scheduling.
References
- Operations Research 5, 518 (1957), DOI: 10.1287/opre.5.4.518. Crossref, ISI, Google Scholar
- Operations Research 15, 254 (1967), DOI: 10.1287/opre.15.2.254. Crossref, ISI, Google Scholar
- Journal of the ACM 22, 248 (1975). Crossref, ISI, Google Scholar
- Journal of the ACM 27, 313 (1980), DOI: 10.1145/322186.322195. Crossref, ISI, Google Scholar
- Communications of the ACM 16, 527 (1973), DOI: 10.1145/362342.362345. Crossref, ISI, Google Scholar
- IEEE Trans. Computers 37, 1627 (1988), DOI: 10.1109/12.9739. Crossref, ISI, Google Scholar
- IEEE Trans. Aerospace and Electronic Systems 24, 700 (1988), DOI: 10.1109/7.18637. Crossref, ISI, Google Scholar
- Divisible Load Theory publication list at the author's web page at , www.ece.sunysb.edu . Google Scholar
- Cluster Computing 6, 7 (2003). Google Scholar
- Computer 36, 63 (2003), DOI: 10.1109/MC.2003.1198238. Crossref, ISI, Google Scholar
-
B. Veeravalli , Scheduling Divisible Loads in Parallel and Distributed Systems ( IEEE Computer Society Press , Los Alamitos CA USA , 1996 ) . Google Scholar -
M. Drozdowski , Scheduling for Parallel Processing ( Springer , New York, USA , 2009 ) . Crossref, Google Scholar -
H. Casanova , A. Legrand and Y. Robert , Parallel Algorithms ( CRC Press , FL USA , 2009 ) . Google Scholar -
T. G. Robertazzi , Networks and Grids: Technology and Theory ( Springer , New York , 2007 ) . Google Scholar - IEEE Transactions on Aerospace and Electronic Systems 32, 34 (1996), DOI: 10.1109/7.481247. Crossref, ISI, Google Scholar
- Foundations of Computing and Decision Sciences 21, 3 (1996). Google Scholar
- Discerte Applied Mathematics 94, 35 (1999), DOI: 10.1016/S0166-218X(99)00013-X. Crossref, ISI, Google Scholar
- Parallel Computing 25, 381 (1999), DOI: 10.1016/S0167-8191(99)00004-6. Crossref, ISI, Google Scholar
- Cluster Computing 6, 31 (2003). Crossref, Google Scholar
- IEEE Transactions on Aerospace and Electronic Systems 26, 511 (1990), DOI: 10.1109/7.106129. Crossref, ISI, Google Scholar
- Computers and Mathematics with Applications 52, 1529 (2006), DOI: 10.1016/j.camwa.2006.05.016. Crossref, ISI, Google Scholar
- J.-T. Hung, Scalable Scheduling in Parallel, Distributed and Grid Systems, Ph.D Thesis, Stony Brook University, 2003 . Google Scholar
- IEEE Transactions on Parallel and Distributed Systems 18, 608 (2007), DOI: 10.1109/TPDS.2007.1032. Crossref, ISI, Google Scholar


