A Dynamic Approach For Scheduling Dependent Tasks On The Xavantes Grid Middleware

A scheduler must consider the heterogeneity and communication delays when scheduling dependent tasks on a grid. The task scheduling problem is NP-Complete in general, what led us to the development of a heuristic for the associated optimization problem. In this work we present a dynamic approach to schedule dependent tasks onto a grid based on the Xavantes grid middleware. The developed dynamic approach is applied to the Path Clustering Heuristic (PCH), and introduces the concept of rounds, which take turns sending tasks to execution and evaluating the performance of the resources. The experiments show that the round-based dynamic schedule can minimize the effects of performance losses while executing processes on the grid. © 2006 ACM.1941186686Bajaj, R., Agrawal, D.P., Improving scheduling of tasks in a heterogeneous environment (2004) IEEE Trans. Parallel and Distributed Systems, 15 (2), pp. 107-118L. F. Bittencourt, E. R. M. Madeira, F. R. L. Cicerre, and L. E. Buzato. A path clustering heuristic for scheduling taks graphs onto a grid (short paper). In 3rd ACM International Workshop on Middleware for Grid Computing, Grenoble, France, nov 2005Cicerre, F.R.L., Madeira, E.R.M., Buzato, L.E., A hierarchical process execution support for grid computing (2006) Concurrency and Computation: Practice and Experience, 18 (6), pp. 581-594Cooper, K., Dasgupta, A., Kennedy, K., New grid scheduling and rescheduling methods in the grads project (2004) 18th International Parallel and Distributed Processing Symposium, , IEEE Computer SocietyFrey, J., DAGMan, C., (2002) Handling inter-job dependencies, , http://www.cs.wisc.edu/condor/dagmanFujimoto, N., Hagihara, K., Near-optimal dynamic task scheduling of precedence constrained coarse-grained tasks onto a computational grid (2003) 2nd Intl. Symp. on Parallel and Distributed Computing, Slovenia, pp. 80-87. , IEEE, octHagras, T., Janeček, J., An approach to compile-time task scheduling in heterogeneous computing systems (2004) 33rd International Conference on Parallel Processing Workshops, pp. 182-189. , IEEE Computer SocietyKwok, Y.-K., Ahmad, I., Dynamic critical-path scheduling: An effective technique for allocating task graphs to multiprocessors (1996) IEEE Trans. on Parallel and Distributed Systems, 7 (5), pp. 506-521Prodan, R., Fahringer, T., Dynamic scheduling of scientific workflow applications on the grid: A case study (2005) SAC '05: Proceedings of the 2005 ACM symposium on Applied computing, pp. 687-694. , New York, NY, USA, ACM PressTopcuoglu, H., Hariri, S., Wu, M.-Y., Performance-effective and low-complexity task scheduling for heterogeneous computing (2002) IEEE Trans. Parallel and Distributed Systems, 13 (3), pp. 260-274Wolski, R., Spring, N.T., Hayes, J., The network weather service: A distributed resource performance forecasting service for metacomputing (1999) Future Generation Computer Systems, 15 (5-6), pp. 757-76