Design and Performance Analysis of Heuristic Load-Balancing Strategies for Processing Divisible Loads on Ethernet Clusters

B. Veeravalli

References

  1. [1] J.A. Stankovic, M. Spuri, M. Di Natale, & G.C. Buttazzo,Implications of classical scheduling results for real-time systems,Computer, June 1995, 16–25. doi:10.1109/2.386982
  2. [2] C.-H. Lee & K.G. Shin, Optimal task assignment in homogeneous networks, IEEE Trans. on Parallel and Distributed Systems, 8(2), 1997, 119–129. doi:10.1109/71.577254
  3. [3] Y.C. Cheng & T.G. Robertazzi, Distributed computationwith communication delays, IEEE Trans. on Aerospace andElectronic Systems, 24, 1988, 700–712. doi:10.1109/7.18637
  4. [4] J.F. Jeng & S. Sahni, Reconfigurable mesh algorithms forthe Hough Transform, Journal of Parallel and DistributedComputing, 20, 1994, 69–77. doi:10.1006/jpdc.1994.1006
  5. [5] D. Ghose & H.J. Kim, Load partitioning and trade-off studyfor large matrix-vector computations in multicast bus networkswith communication delays, Journal of Parallel and DistributedComputing, 55(1), 1998, 32–59. doi:10.1006/jpdc.1998.1494
  6. [6] H.J. Siegel, J.B. Armstrong, & D.W. Watson, Mappingcomputer-vision-related tasks onto reconfigurable parallel-processing systems, IEEE Computer, 25(2), 1992, 54–63. doi:10.1109/2.121475
  7. [7] K. Ko & T.G. Robertazzi, Record search time evaluation,paper presented at 2000 Conf. on Information Sciences andSystems, Princeton University, Princeton, NJ, March 2000.
  8. [8] J. Sohn & T.G. Robertazzi, A multi-job load sharing strategy fordivisible jobs on bus networks, Proc. 1994 Conf. on InformationSciences and Systems, Princeton University, Princeton, NJ,March 1994.
  9. [9] V. Bharadwaj, D. Ghose, V. Mani, & T.G. Robertazzi, Scheduling divisible loads in parallel and distributed systems (Los Alamitos, CA: IEEE Computer Society Press, 1996).
  10. [10] M. Drozdowski, Selected problems of scheduling tasks in multi-processor computer systems (Poznan, Poland: WydawnictwaPolitechniki Poznanskiej, 1997) (in English).
  11. [11] M.M. Eshaghian (Ed.), Heterogeneous computing (Artech House, 1996).
  12. [12] C.C. Han & K.G. Shin, On load balancing in multicomputer/distributed systems equipped with circuit or cut-throughswitching capability, IEEE Trans. on Computers, 49(9), 2000, 947–957. doi:10.1109/12.869325
  13. [13] J. Sohn & T.G. Robertazzi, Optimal divisible load sharingon bus networks, IEEE Trans. on Aerospace and ElectronicSystems, 32(1), January 1996, 34–40. doi:10.1109/7.481247
  14. [14] J. Blazewicz, M. Drozdowski, & M. Markiewicz, Divisible taskscheduling: Concept and verification, Parallel Computing, 25,January 1999, 87–98. doi:10.1016/S0167-8191(98)00104-5
  15. [15] G.D. Barlas, Collection-aware optimum sequencing ofoperations and closed-form solutions for the distribution of adivisible load on arbitrary processor trees, IEEE Trans. onParallel and Distributed Systems, 9(5), 1998, 429–441. doi:10.1109/71.679214
  16. [16] D.A.L. Piriyakumar & C.S.R. Murthy, Distributed computation for a hypercube network of sensor-driven processors with communication delays including setup time, IEEE Trans. on Systems, Man and Cybernetics, Part A: Systems and Humans, 28(2), 1998, 245–251. doi:10.1109/3468.661152
  17. [17] J. Sohn & T.G. Robertazzi, A multi-job load sharing strategyfor divisible jobs on bus networks, CEAS Technical Report 665,State University of New York at Stony Brook, April 1993.
  18. [18] V. Bharadwaj & B. Gerassimos, Efficient scheduling strategiesfor processing multiple divisible loads on bus networks, Journalof Parallel and Distributed Computing, 62, 2002, 132–151. doi:10.1006/jpdc.2001.1778
  19. [19] V. Bharadwaj, H.F. Li, & T. Radhakrishnan, Schedulingdivisible loads in bus networks with arbitrary processor releasetimes, International Journal of Computers and Mathematicswith Applications, 32(7), 1996.
  20. [20] J. Blazewicz & M. Drozdowski, Distributed processing of divisible jobs with communication startup costs, Discrete Applied Mathematics, 76(1–3), 1997, 21–41. doi:10.1016/S0166-218X(96)00115-1
  21. [21] V. Bharadwaj, X. Li & C.C. Ko, On the influence of start-upcosts in scheduling divisible loads on bus networks, IEEE Trans.on Parallel and Distributed Systems, 11(12), 2000, 1288–1305. doi:10.1109/71.895794
  22. [22] X. Li, V. Bharadwaj, & C.C. Ko, Scheduling divisible taskson heterogeneous single-level tree networks with finite-sizebuffers, IEEE Trans. on Aerospace and Electronic Systems,36(4), October 2000, 1298–1308. doi:10.1109/7.892677
  23. [23] M. Drozdowski & P. Wolniewicz, Experiments with schedulingdivisible tasks in clusters of workstations, Euro-Par 2000,LNCS 1900, Springer-Verlag, 2000, 311–319. doi:10.1007/3-540-44520-X_40
  24. [24] S.K. Chan, V. Bharadwaj, & D. Ghose, Large matrix-vectorproducts on distributed bus networks with communicationDelays using the divisible load paradigm: Performance Analysis and Simulation, Mathematics and Computers in Simulation, 58, 2001, 71–92. doi:10.1016/S0378-4754(01)00329-9
  25. [25] J.-T. Hung, H.J. Kim, & T.G. Robertazzi, Scalable scheduling in parallel processors, Proc. 2002 Conf. on Information Sciences and Systems, Princeton University, Princeton, NJ, March 2002, 20–22.
  26. [26] K. Li, Scheduling divisible loads on heterogeneous lineararrays with applications to layered networks, Proc. 16th Int.Parallel and Distributed Processing Symp. (IPDPS) 2002, FortLauderdale, FL, March 2002, 20–22.
  27. [27] J. Sohn, T.G. Robertazzi, & S. Luryi, Optimizing computingcosts using divisible load analysis, IEEE Trans. on Paralleland Distributed Systems, 9(3), 1998, 225–234. doi:10.1109/71.674315
  28. [28] V. Bharadwaj, D. Ghose, & V. Mani, Multi-installment loaddistribution in tree networks with delays, IEEE Trans. onAerospace and Electronic Systems, 31, 1995, 555–567. doi:10.1109/7.381944
  29. [29] H. Attiya & J. Welch, Distributed computing: Fundamentals, simulations and advanced topics (UK: McGraw Hill, 1998)

Important Links:

Go Back