Abstract
This chapter proposes a novel Grid-based scheduling algorithm that optimizes both computation and communications costs of workflow applications. Based on a hierarchical two-steps optimization process, a super scheduler first applies a Recursive Convex Clustering Algorithm (RCCA) that efficiently clusters tasks while minimizing communication costs. In the second step, a resource-broker assigns the generated convex sets to resources clusters. Local schedulers then optimize the makespan for the group of tasks assigned to their cluster, using a graphic processing unit (GPU)-based parallel cellular Genetic Algorithm(cGA). The performance improvement brought by this novel two-step scheduling algorithm compared to a hierarchical list-scheduling approach is empirically demonstrated on different real-world workflow applications.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alba, E., Dorronsoro, B.: Cellular Genetic Algorithms. In: Operations Research/Compuer Science Interfaces. Springer, Heidelberg (2008)
Alba, E., Tomassini, M.: Parallelism and Evolutionary Algorithms. IEEE Transactions on Evolutionary Computation 6, 443–462 (2002)
Bampis, E., Giroudeau, R., König, J.C.: An approximation algorithm for the precedence constrained scheduling problem with hierarchical communications. Theor. Comput. Sci. 290(3), 1883–1895 (2003)
Blachot, F., Huard, G., Pecero, J.E., Saule, E., Trystram, D.: Scheduling instructions on hierarchical machines. In: IEEE IPDPS-PDSEC 2010, USA (2010), doi:10.1109/IPDPSW.2010.5470711
Bolze, R., Cappello, F., Caron, E., Daydé, M., Desprez, F., Jeannot, E., Jégou, Y., Lanteri, S., Leduc, J., Melab, N., Mornet, G., Namyst, R., Primet, P., Quetier, B., Richard, O., Talbi, E.-G., Irena, T.: Scheduling on large scale distributed platforms: from models to implementations. Int. J. Found. Comput. Sci. 16(2), 217–237 (2005)
Deelman, E., Singh, G., Su, M.-H., Blythe, J., Gil, Y., Kesselman, C., Mehta, G., Vahi, K., Berriman, G.B., Good, J., Laity, A., Jacob, J.C., Katz, D.S.: Pegasus: a Framework for Mapping Complex Scientific Workflows onto Distributed Systems. Scientific Programming Journal 13(3), 219–237 (2005)
Dong, F., Akl, S.: An Adaptive Double-layer Workflow Scheduling Approach for Grid Computing. In: Proc. of the High Performance Computing Symposium (HPCS) 2007, Canada (2007)
Dorronsoro, B., Bouvry, P., Cañero, J.A., Maciejewski, A.A., Siegel, H.J.: Multi-objective robust static mapping of independent tasks on grids. In: International Conference on Evolutionary Computation (CEC), part of the IEEE World Congress on Computational Intelligence (WCCI), pp. 3389–3396 (2010)
Dutot, P.-F., Eyraud, L., Mounié, G., Trystram, D.: Scheduling on large scale distributed platforms: from models to implementations. Int. J. Found. Comput. Sci. 16(2), 217–237 (2005)
Dutot, P.-F., N’Takpé, T., Suter, F., Casanova, H.: Scheduling Parallel Task Graphs on (Almost) Homogeneous Multi-cluster Platforms. IEEE Trans on Parallel and Distributed Systems 20(7), 940–952 (2009)
El-Rewini, H., Ali, H., Lewis, T.: Task Scheduling in Parallel and Distributed Systems. PTR Prentice Hall, Englewood Cliffs (1994)
Garg, S., Buyya, R., Siegel, H.J.: Time and cost trade-off management for scheduling parallel applications on utility grids. Future Generation Computer Systems 26(8), 1344–1355 (2010)
Gauja, B., Huard, G., Pecero, J., Thierry, E., Trystram, D.: Convex Scheduling for Grid Computing. In: WASC 2004 - 1st Workshop on Algorithms for Scheduling and Communication, Bertinoro, Italy (2004)
Grid5000 (2009), http://www.grid5000.org
Guzek, M., Pecero, J., Dorronsoro, B., Bouvry, P.: A cellular genetic algorithm for scheduling applications and energy-aware communication optimization. In: Workshop on Optimization Issues in Energy Efficient Distributed Systems (OPTIM), part of the International Conference on High Performance Computing & Simulation (HPCS), Caen, France, pp. 241–248 (2010)
He, L., Jarvis, S.A., Spooner, D.P., Bacigalupo, D., Tan, G., Nudd, G.R.: Mapping DAG-based applications to multiclusters with background workload. In: IEEE International Symposium on Cluster Computing and the Grid, vol. 2, pp. 855–862 (2005), doi:10.1109/CCGRID.2005.1558651
Hwang, J.J., Chow, Y.C., Angers, F.D., Lee, C.Y.: Scheduling precedence graphs in systems with interprocessor communication times. SIAM Journal on Computing 18(2), 244–257 (1989)
Krauter, K., Buyya, R., Maheswaran, M.: A taxonomy and survey of Grid resource management systems for distributed computing. Int. J. of Software: Practice and Experience 32(2), 135–164 (2002)
Lee, Y.C., Subrata, R., Zomaya, A.Y.: On the performance of a dual-objective optimization model for workflow applications on Grid platforms. IEEE Trans on Parallel and Distributed Systems 20(9), 1273–1284 (2009)
Lepére, R., Trystram, D.: A new clustering algorithm for scheduling with large communication delays. In: 16th IEEE-ACM annual International Symposium on Parallel and Distributed Processing (IPDPS 2002), USA (2002)
Mahjoub, A., Pecero, J.E., Trystram, D.: Scheduling with uncertainties on new computing platforms. Journal Comput Optim Appl. (2010)
Manderick, B., Spiessens, P.R.: Fine-grained parallel genetic algorithm. In: Schaffer, J. (ed.) Third International Conference on Genetic Algorithms (ICGA), pp. 428–433. Morgan Kaufmann, San Francisco (1989)
Martino, B.D., Dongarra, J., Hoisie, A., Yang, L.T., Zima, H.: Engineering the Grid: Status and Perspective. American Scientific Publishers (2006)
Nasri, W., Steffenel, L.A., Trystram, D.: Adaptive approaches for efficient parallel algorithms on cluster-based systems. International Journal of Grid and Utility Computing (IJGUC) 1(2), 98–108 (2009)
Pecero, J.E., Bouvry, P.: An improved genetic algorithm for efficient scheduling on distributed memory parallel systems. In: IEEE/ACS International Conference on Computer Systems and Applications, AICCSA 2010 (2010), doi:10.1109/AICCSA.2010.5587030
Pecero, J.E., Trystram, D., Zomaya, A.Y.: A new genetic algorithm for scheduling for large communication delays. In: Sips, H., Epema, D., Lin, H.-X. (eds.) Euro-Par 2009. LNCS, vol. 5704, pp. 241–252. Springer, Heidelberg (2009)
Radulescu, A., van Gemund, A.J.C.: Flb: Fast load balancing for distributed-memory machines. In: Proc. Int. Conf. on Parallel Processing (1999)
Radulescu, A., van Gemund, A.J.C.: Fast and effective task scheduling in heterogeneous systems. In: Proc. 9th Heterogeneous Computing Workshop, HCW (2000)
Sánchez, J.E.P., Trystram, D.: A new genetic convex clustering algorithm for parallel time minimization with large communication delays. In: Joubert, G.R., Nagel, W.E., Peters, F.J., Plata, O., Tirado, P., Zapata, E. (eds.) Parallel Computing: Current & Future Issues of High-End Computing, vol. 33, pp. 709–716. John von Newmann (2006)
Shivle, S., Siegel, H.J., Maciejewski, A.A., Sugavanam, P., Banka, T., Castain, R., Chindam, K., Dussinger, S., Pichumani, P., Satyasekaran, P., Saylor, W., Sendek, D., Sousa, J., Sridharan, J., Velazco, J.: Static allocation of resources to communicating subtasks in a heterogeneous ad hoc grid environment. Journal of Parallel and Distributed Computing, Special Issue on Algorithms for Wireless and Ad-hoc Networks 66(4), 600–611 (2006)
Tchernykh, A., Schwiegelson, U., Yahyapour, R., Kuzjurin, N.: On-line hierarchical job scheduling on grids with admisible allocation. J. Sched. 13(5), 545–552 (2010)
Topcuoglu, H., Hariri, S., Wu, M.: Performance-Effective and Low- Complexity Task Scheduling for Heterogeneous Computing. IEEE Trans. Parallel and Distributed Systems 13(3), 260–274 (2002)
Wilcoxon, F.: Individual comparisons by ranking methods. Biometrics Bulletin 1(6), 80–83 (1945)
Whitley, D.: Cellular genetic algorithms. In: Forrest, S. (ed.) Fifth International Conference on Genetic Algorithms (ICGA), p. 658. Morgan Kaufmann, California (1993)
Yu, J., Buyya, R.: A taxonomy of workflow management systems for grid computing. Journal of Grid Computing 3(3-4), 171–200 (2006), doi:10.1007/s10723-005-9010-8
Yu, J., Buyya, R., Ramamohanarao, K.: Workflow scheduling algorithms for Grid computing. In: Xhafa, F., Abraham, A. (eds.) Metaheuristics for Scheduling in Distributed Computing Environments. Studies in Computational Intelligence, vol. 146, pp. 173–214. Springer, Heidelberg (2008)
Zomaya, A.Y., Chan, G.: Efficient clustering for parallel tasks execution in distributed systems. In: Proc. of Workshop NIDISC 2004, New Mexico, USA, pp. 167–177 (2004)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Pecero, J.E., Pinel, F., Dorronsoro, B., Danoy, G., Bouvry, P., Zomaya, A.Y. (2011). Efficient Hierarchical Task Scheduling on GRIDS Accounting for Computation and Communications. In: Bouvry, P., González-Vélez, H., Kołodziej, J. (eds) Intelligent Decision Systems in Large-Scale Distributed Environments. Studies in Computational Intelligence, vol 362. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-21271-0_2
Download citation
DOI: https://doi.org/10.1007/978-3-642-21271-0_2
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-21270-3
Online ISBN: 978-3-642-21271-0
eBook Packages: EngineeringEngineering (R0)