Abstract
The need for better energy efficiency in grid computing is significant given the massive amount of energy dissipated by large grids. We approximate the optimal allocation of compute nodes to a job stream, with each job consisting of multiple tasks, and while considering both the computing requirements and a desired balance of shorter makespans and lower energy consumption. The approach is widely applicable to many grid scenarios and does not require the scheduler to have administrative rights to change the workers’ DVFS or hibernation state. A discrete particle swarm optimisation (PSO) determines the worker assignments based on estimations of the tasks’ service times and energy consumption using an online learning process, and taking into account pending task executions from prior jobs. The performance of the proposed system is then evaluated through extensive Monte Carlo simulations using traces of real multi-threaded program executions on representative computer hardware. The results demonstrate the latent energy savings that are possible in grid computing through an energy-aware task scheduling.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Great Internet Mersenne Prime Search. http://www.mersenne.org Accessed 2014 12 28
Anderson, D.P.: Boinc: A system for public-resource computing and storage. In: 5th IEEE/ACM International Workshop on Grid Computing, pp 4–10 (2004)
Anderson, D.P., Christensen, C., Allen, B.: Designing a runtime system for volunteer computing. IEEE Computer (2006)
Attiya, G., Hamam, Y.: Task allocation for maximizing reliability of distributed systems: A simulated annealing approach. J. Parallel Distrib. Comput 66(10), 1259–1266 (2006). doi:10.1016/j.jpdc.2006.06.006. http://www.sciencedirect.com/science/article/pii/S0743731506001432
Barrios Hernandez, C., Sierra, D., Varrette, S., Pacheco, D.: Energy efficiency on scalable computing architectures. In: Computer and Information Technology (CIT), 2011 IEEE 11th International Conference on, pp. 635–640 (2011). doi:10.1109/CIT.2011.108
Basmadjian, R., Meer, H.D., Lent, R., Giuliani, G.: Cloud computing and its interest in saving energy: the use case of a private cloud. Journal of Cloud Computing (2012)
Benedict, S.: Energy-aware performance analysis methodologies for hpc architecturesan exploratory study. J. Netw. Comput. Appl. 35(6), 1709–1719 (2012)
Bienia, C., Kumar, S., Singh, J.P., Li, K.: The PARSEC benchmark suite: Characterization and architectural implications. In: Proceedings of the 17th International Conference on Parallel Architectures and Compilation Techniques (2008)
Chang, R.S., Chang, J.S., Lin, P.S.: An ant algorithm for balanced job scheduling in grids. Futur. Gener. Comput. Syst. 25(1), 20–27 (2009). doi:10.1016/j.future.2008.06.004. http://www.sciencedirect.com/science/article/pii/S0167739X08000848
Chen, T., Zhang, B., Hao, X., Dai, Y.: Task scheduling in grid based on particle swarm optimization. In: Parallel and Distributed Computing, 2006. ISPDC ’06. The Fifth International Symposium on, pp. 238–245 (2006). doi:10.1109/ISPDC.2006.46
Coutinho, F., de Carvalho, L., Santana, R.: A workflow scheduling algorithm for optimizing energy-efficient grid resources usage. In: Dependable, Autonomic and Secure Computing (DASC), IEEE Ninth International Conference on, pp. 642–649 (2011). doi:10.1109/DASC.2011.115
Dorronsoro, B., Nesmachnow, S., Taheri, J., Zomaya, A.Y., Talbi, E.G., Bouvry, P.: A hierarchical approach for energy-efficient scheduling of large workloads in multicore distributed systems. Sustainable Computing: Informatics and Systems 4(4), 252–261 (2014). doi:10.1016/j.suscom.2014.08.003. http://www.sciencedirect.com/science/article/pii/S2210537914000444. Special Issue on Energy Aware Resource Management and Scheduling(EARMS)
Elbeltagi, E., Hegazy, T., Grierson, D.: Comparison among five evolutionary-based optimization algorithms. Adv. Eng. Inform. 19(1), 43–53 (2005). doi:10.1016/j.aei.2005.01.004
Fernández-Montes, A., Gonzalez-Abril, L., Ortega, J.A., Lefèvre, L.: Smart scheduling for saving energy in grid computing. Expert Syst. Appl. 39(10), 9443–9450 (2012). doi:10.1016/j.eswa.2012.02.115
Foster, I.T., Zhao, Y., Raicu, I., Lu, S.: Cloud computing and grid computing 360-degree compared (2009). arXiv:CoRR/0901.0131
Franken, N., Engelbrecht, A.: Particle swarm optimization approaches to coevolve strategies for the iterated prisoner’s dilemma. IEEE Trans. Evol. Comput. 9 (6), 562–579 (2005). doi:10.1109/TEVC.2005.856202
Garey, M.R., Johnson, D.S., Sethi, R.: The complexity of flowshop and jobshop scheduling. Math. of Op. Res 2(2), 117–129 (1976)
Gelenbe, E., Lent, R.: Trade-offs between energy and quality of service. In: The Second IFIP Conference on Sustainable Internet and ICT for Sustainability. Pisa, Italy (2012)
Gelenbe, E., Lent, R.: Optimising server energy consumption and response time. Theoretical and Applied Informatics 24(4), 257–270 (2013). doi:10.2478/v10179-012-0016-1
He, X., Sun, X.H., von Laszewski, G.: Qos guided min-min heuristic for grid task scheduling. J. Comput. Sci. Technol 18(4), 442–451 (2003). http://dblp.uni-trier.de/db/journals/jcst/jcst18.htmlHeSL03
Hu, X., Shi, Y., Eberhart, R.: Recent advances in particle swarm. In: Evolutionary Computation, 2004. CEC2004. Congress on, vol. 1, pp. 90–97 Vol.1 (2004). doi:10.1109/CEC.2004.1330842
Hussin, M., Lee, Y.C., Zomaya, A.: Priority-based scheduling for large-scale distribute systems with energy awareness. In: Dependable, Autonomic and Secure Computing (DASC), 2011 IEEE Ninth International Conference on, pp. 503–509 (2011). doi:10.1109/DASC.2011.96
Kang, Q., He, H., Wang, H., Jiang, C.: A novel discrete particle swarm optimization algorithm for job scheduling in grids. In: Natural Computation, 2008. ICNC ’08. Fourth International Conference on, vol. 1, pp. 401–405 (2008). doi:10.1109/ICNC.2008.63
Kennedy, J., Eberhart, R.: Particle swarm optimization. In: Neural Networks, 1995. Proceedings., IEEE International Conference on, vol. 4, pp. 1942–1948 vol.4 (1995). doi:10.1109/ICNN.1995.488968
Kolodziej, J., Szmajduch, M., Maqsood, T., Madani, S., Min-Allah, N., Khan, S.: Energy-aware grid scheduling of independent tasks and highly distributed data. In: Frontiers of Information Technology (FIT), 2013 11th International Conference on, pp. 211– 216 (2013). doi:10.1109/FIT.2013.46
Korpela, E., Werthimer, D., Anderson, D., Cobb, J., Leboisky, M.: Seti@home-massively distributed computing for seti. Computing in Science Engineering 3(1), 78–83 (2001). doi:10.1109/5992.895191
Lent, R.: A sensor network to profile the electrical power consumption of computer networks. In: GLOBECOM Workshops (GC Wkshps), 2010 IEEE, pp. 1433 –1437 (2010). doi:10.1109/GLOCOMW.2010.5700175
Lent, R.: Analysis of an energy proportional data center. Ad Hoc Networks 25 Part B(0), 554–564 (2015). doi:10.1016/j.adhoc.2014.11.001. http://www.sciencedirect.com/science/article/pii/S1570870514002352. New Research Challenges in Mobile, Opportunistic and Delay-Tolerant Networks Energy-Aware Data Centers: Architecture, Infrastructure, and Communication
Li, C., Li, L.: Utility-based scheduling for grid computing under constraints of energy budget and deadline. Comput. Stand. Interfaces 31(6), 1131–1142 (2009). doi:10.1016/j.csi.2008.12.004
Mezmaz, M., Melab, N., Kessaci, Y., Lee, Y., Talbi, E.G., Zomaya, A., Tuyttens, D.: A parallel bi-objective hybrid metaheuristic for energy-aware scheduling for cloud computing systems. Journal of Parallel and Distributed Computing 71(11), 1497–1508 (2011). doi:10.1016/j.jpdc.2011.04.007. http://www.sciencedirect.com/science/article/pii/S0743731511000827
Morelli, D., Cisternino, A.: A compositional model to characterize software and hardware from their resource usage. In: A.V. Jones (ed.) ICCSW, OASICS, vol. 28, pp. 95–101.Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany (2012)
Najjarzadeh, M., Ayatollahi, A.: A comparison between genetic algorithm and PSO for linear phase FIR digital filter design. In: Signal Processing, 2008. ICSP 2008. 9th International Conference on, pp. 2134–2137 (2008). doi:10.1109/ICOSP.2008.4697568
Nesmachnow, S., Dorronsoro, B., Pecero, J., Bouvry, P.: Energy-aware scheduling on multicore heterogeneous grid computing systems. Journal of Grid Computing 11(4), 653–680 (2013). doi:10.1007/s10723-013-9258-3
Nesmachnow, S., Dorronsoro, B., Pecero, J.E., Bouvry, P.: Energy-aware scheduling on multicore heterogeneous grid computing systems. J. Grid Comput 11(4), 653–680 (2013). doi:10.1007/s10723-013-9258-3
Pinel, F., Dorronsoro, B., Pecero, J.E., Bouvry, P., Khan, S.U.: A two-phase heuristic for the energy-efficient scheduling of independent tasks on computational grids. Cluster Computing 16(3), 421–433 (2013). http://dblp.uni-trier.de/db/journals/cluster/cluster16.htmlPinelDPBK13
Ponciano, L., Brasileiro, F.: On the impact of energy-saving strategies in opportunistic grids. In: Grid Computing (GRID), 2010 11th IEEE/ACM International Conference on, pp. 282–289 (2010). doi:10.1109/GRID.2010.5698003
Ponciano, L., Brasileiro, F.: Assessing green strategies in peer-to-peer opportunistic grids. Journal of Grid Computing 11(1), 129–148 (2013). doi:10.1007/s10723-012-9218-3
Qureshi, M., Dehnavi, M., Min-Allah, N., Qureshi, M., Hussain, H., Rentifis, I., Tziritas, N., Loukopoulos, T., Khan, S., Xu, C.Z., Zomaya, A.: Survey on grid resource allocation mechanisms. Journal of Grid Computing 12(2), 399–441 (2014). doi:10.1007/s10723-014-9292-9
Reda, S., Nowroz, A.N.: Power modeling and characterization of computing devices: A survey. Foundations and Trends in Electronic Design Automation 6(2), 121–216 (2012)
Rivoire, S., Shah, M.A., Ranganathan, P., Kozyrakis, C., Meza, J.: Models and metrics to enable energy-efficiency optimizations. Computer 40(12), 39–48 (2007). doi:10.1109/MC.2007.436
Schubert, S., Kostic, D., Zwaenepoel, W., Shin, K.G.: Profiling software for energy consumption, vol. 0 (2012)
Subrata, R., Zomaya, A.Y., Landfeldt, B.: Artificial life techniques for load balancing in computational grids. J. Comput. Syst. Sci. 73(8), 1176–1190 (2007). doi:10.1016/j.jcss.2007.02.006. Network-Based Computing http://www.sciencedirect.com/science/article/pii/S0022000007000116
Tang, Z., Qi, L., Cheng, Z., Li, K., Khan, S., Li, K.: An energy-efficient task scheduling algorithm in dvfs-enabled cloud environment. Journal of Grid Computing, 1–20 (2015). doi:10.1007/s10723-015-9334-y
Tiwari, V., Malik, S., Wolfe, A.: Power analysis of embedded software: A first step towards software power minimization. IEEE Transactions on VLSI Systems 2, 437–445 (1994)
Towns, J., Cockerill, T., Dahan, M., Foster, I., Gaither, K., Grimshaw, A., Hazlewood, V., Lathrop, S., Lifka, D., Peterson, G., Roskies, R., Scott, J., Wilkens-Diehr, N.: Xsede: Accelerating scientific discovery. Comput. Sci. Eng 16(5), 62–74 (2014). doi:10.1109/MCSE.2014.80
Uchechukwu, A., Li, K., Shen, Y.: Improving cloud computing energy efficiency. In: Cloud Computing Congress (APCloudCC), 2012 IEEE Asia Pacific, pp. 53–58 (2012). doi:10.1109/APCloudCC.2012.6486511
Zomaya, A.Y., Lee, Y.C.: Energy Efficient Distributed Computing Systems, 1st. Wiley (2012)
How much electricity does an American home use? U.S. Energy Information Administration (EIA) http://www.eia.gov/tools/faqs/ Accessed 25 Aug 2015
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Lent, R. Grid Scheduling with Makespan and Energy-Based Goals. J Grid Computing 13, 527–546 (2015). https://doi.org/10.1007/s10723-015-9349-4
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10723-015-9349-4