×

Grid scheduling divisible loads from two sources. (English) Zbl 1189.68028

Summary: To date closed form solutions for optimal finish time and job allocation are largely obtained only for network topologies with a single load originating (root) processor. However in large-scale data intensive problems with geographically distributed resources, load is generated from multiple sources. This paper introduces a new divisible load scheduling strategy for single level tree networks with two load originating processors. Solutions for an optimal allocation of fractions of load to nodes in single level tree networks are obtained via linear programming. A unique scheduling strategy that allows one to obtain closed form solutions for the optimal finish time and load allocation for each processor in the network is also presented. The tradeoff between linear programming and closed form solutions in terms of underlying assumptions is examined. Finally, a performance evaluation of a two source homogeneous single level tree network with concurrent communication strategy is presented.

MSC:

68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
65Y05 Parallel numerical computation
68M10 Network design and communication in computer systems
PDF BibTeX XML Cite
Full Text: DOI Link

References:

[1] J. Schopf, A general architecture for scheduling on the grid, Argonne National Laboratory preprint ANL/MCS, Argonne, IL 1000-1002, 2002
[2] Spooner, D., Local grid scheduling techniques using performance prediction, IEEE proceedings—computers and digital techniques, 150, 87-96, (2003)
[3] Smith, W.; Taylor, V.; Foster, I., Using run-time predictions to estimate queue wait times and improve scheduler performance, (), 202-219
[4] Yang, L.; Schopf, J.; Foster, I., Conservative scheduling: using predicted variance to improve scheduling decisions in dynamic environments, (), 558-664
[5] K. Ranganathan, I. Foster, Decoupling computation and data scheduling in distributed data-intensive applications, Proceedings of the 11th IEEE International Symposium on High Performance Distributed Computing (HPDC02), Edinburgh, Scotland, 2002, p. 352
[6] V. Subramani, R. Kettimuthu, S. Srinivasan, P. Sadayappan, Distributed job scheduling on computational grids using multiple simultaneous requests, Proceedings of the 11th IEEE International Symposium on High Performance Distributed Computing (HPDC02), Edinburgh, Scotland, 2002, pp. 359-366
[7] M. Wu, X. Sun, Memory conscious task partition and scheduling in grid environments, Proceedings of the Fifth IEEE/ACM International Workshop on Grid Computing, Pittsburgh, USA, 2004, pp. 138-145
[8] J. Abawajy, Fault-tolerant scheduling policy for grid computing systems, Proceedings of the 18th International Parallel and Distributed Processing Symposium, Santa Fe, New Mexico, 2004, pp. 238-245
[9] L. Xiao, Y. Zhu, L. Ni, Z. Xu, GridIS: An incentive-based grid scheduling, Proceedings of the 19th International Parallel and Distributed Processing Symposium, 65b, 2005
[10] A. Chakravarti, G. Baumgartner, M. Lauria, Application-specific scheduling for the organic grid, Proceedings of the Fifth IEEE/ACM International Workshop on Grid Computing, 2004, pp. 146-155
[11] E. Huedo, R. Montero, I. Llorente, Experiences on adaptive grid scheduling of parameter sweep applications, Proceedings of the 12th Euromicro Conference on Parallel, Distributed and Network-based Processing, A Coruna, Spain, 2004, pp. 28-33
[12] N. Fujimoto, K. Hagihara, A comparison among grid scheduling algorithms for independent coarse-grained tasks, Proceedings of the 2004 International Symposium on Applications and the Internet, Tokyo, Japan, 2004, pp. 674-680
[13] Bharadwaj, V.; Ghose, D.; Mani, V.; Robertazzi, T.G., Scheduling divisible loads in parallel and distributed systems, (1996), IEEE Computer Society Press Los Alamitos, CA
[14] Bharadwaj, V.; Ghose, D.; Robertazzi, T.G., Divisible load theory: A new paradigm for load scheduling in distributed systems, Cluster computing, 6, 7-18, (2003)
[15] Robertazzi, T.G., Ten reasons to use divisible load theory, Computer, 36, 63-68, (2003)
[16] Cheng, Y.C.; Robertazzi, T.G., Distributed computation with communication delays, IEEE transactions on aerospace and electronic systems, 22, 60-79, (1988)
[17] Sohn, J.; Robertazzi, T.G., Optimal divisible load sharing for bus networks, IEEE transactions on aerospace and electronic systems, 32, 34-40, (1996)
[18] Cheng, Y.C.; Robertazzi, T.G., Distributed computation for a tree network with communication delays, IEEE transactions on aerospace and electronic systems, 26, 511-516, (1990)
[19] Bataineh, S.; Robertazzi, T.G., Bus oriented load sharing for a network of sensor driven processors, IEEE transactions on systems, man and cybernetics, 21, 1202-1205, (1991)
[20] Blazewicz, J.; Drozdowski, M., Scheduling divisible jobs on hypercubes, Parallel computing, 21, 1945-1956, (1996)
[21] Blazewicz, J.; Drozdowski, M., The performance limits of a two dimensional network of load sharing processors, Foundations of computing and decision sciences, 21, 3-15, (1996) · Zbl 0860.68006
[22] Robertazzi, T.G., Processor equivalence for a linear daisy chain of load sharing processors, IEEE transactions on aerospace and electronic systems, 29, 1216-1221, (1993)
[23] Bharadwaj, V.; Ghose, D.; Mani, V., Multi-installment load distribution in tree networks with delays, IEEE transactions on aerospace and electronic systems, 31, 555-567, (1995)
[24] Y. Yang, H. Casanova, UMR: A multi-round algorithm for scheduling divisible workloads. Proceedings of the International Parallel and Distributed Processing Symposium (IPDPS’03), Nice, France, 2003
[25] O. Beaumont, A. Legrand, Y. Robert, Optimal algorithms for scheduling divisible workloads on heterogeneous systems, 12th Heterogeneous Computing Workshops HCW’2003, 2003
[26] Blazewicz, J.; Drozdowski, M., Distributed processing of distributed jobs with communication startup costs, Discrete applied mathematics, 76, 21-41, (1997) · Zbl 0879.68022
[27] Rosenberg, A.L., Sharing partitionable workloads in heterogeneous NOWs: greedier is not better, (), 124-131
[28] P.F. Dutot, Divisible load on heterogeneous linear array, Proceeding of the International Parallel and Distributed Processing Symposium (IPDPS’03), Nice, France, 2003
[29] M. Moges, T. Robertazzi, Optimal divisible load scheduling and Markov chain models, Proceedings of the 2003 Conference on Information Sciences and Systems, Baltimore, MD, 2003 · Zbl 1172.90414
[30] Ko, K.; Robertazzi, T., Scheduling in an environment of multiple job submissions, ()
[31] H. Wong, B. Veeravalli, D. Yu, T. Robertazzi, Data intensive grid scheduling: Multiple sources with capacity constraint, IASTED International Conference on Parallel and Distributed Computing and Systems (PDCS 2003), Marina del Rey, CA, 2003
[32] L. Marchal, Y. Yang, H. Casanova, Y. Robert, A realistic network/application model for scheduling loads on large-scale platforms, Proceedings of the International Parallel and Distributed Processing Symposium, Denver, Colorado, 48b, 2005
[33] T. Lammie, T. Robertazzi, A linear daisy chain with two divisible load sources, Proceedings of 2005 Conference on Information Sciences and Systems, Baltimore, MD, 2005
[34] Yu, D.; Robertazzi, T., Multi-source grid scheduling for divisible loads, () · Zbl 1189.68028
[35] Piriyakumar, D.; Murthy, C., Distributed computation for a hypercube network of sensor-driven processors with communication delays including setup time, IEEE transactions on systems, man and cybernetics, 28, 245-251, (1998)
[36] Hung, J.; Robertazzi, T., Scalable scheduling for clusters and grids using cut through switching, International journal of computers and applications, 26, 147-156, (2004)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.