Energy-Aware Online Non-Clairvoyant Scheduling Using Speed Scaling with Arbitrary Power Function
Source abstract
Abstract
Efficient job scheduling reduces energy consumption and enhances the performance of machines in data centers and battery-based computing devices. Practically important online non-clairvoyant job scheduling is studied less extensively than other algorithms. In this paper, an online non-clairvoyant scheduling algorithm Highest Scaled Importance First (HSIF) is proposed, where HSIF selects an active job with the highest scaled importance. The objective considered is to minimize the scaled importance based flow time plus energy. The processor’s speed is proportional to the total scaled importance of all active jobs. The performance of HSIF is evaluated by using the potential analysis against an optimal offline adversary and simulating the execution of a set of jobs by using traditional power function. HSIF is 2-competitive under the arbitrary power function and dynamic speed scaling. The competitive ratio obtained by HSIF is the least to date among non-clairvoyant scheduling. The simulation analysis reflects that the performance of HSIF is best among the online non-clairvoyant job scheduling algorithms.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Cloud Computing and Resource Management · Distributed and Parallel Computing Systems · Parallel Computing and Optimization Techniques
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
Department of Computer Science Engineering, Amity School of Engineering and Technology, Noida 226010, India
Department of Electrical and Computer Engineering, Hawassa University, Awasa P.O. Box 05, Ethiopia
Department of CSE, Jaypee Institute of Information Technology Noida, Noida 201309, India
Department of Electrical Power Engineering, Tishreen University, Lattakia 2230, Syria
Department of Management & Innovation Systems, University of Salerno, 84084 Salerno, Italy
References (34)
Show source-provided references
1. Prashast Release Round Robin: R3 an energy-aware non-clairvoyant scheduling on speed bounded processors10.1016/j.kijoms.2015.11.008 ↗
2. Executed-time Round Robin: EtRR an online non-clairvoyant scheduling on speed bounded processor with energy management
3. U.S. Environmental Protection Agency (2015, June 10). EPA Report on server and data centre energy efficiency, Available online: https://www.energystar.gov/index.cfm?c=prod_development.server_efficiency_study.
4. Data center growth in the United States: Decoupling the demand for services from electricity use10.1088/1748-9326/aaec9c ↗
5. Security supportive energy-aware scheduling and energy policies for cloud environments10.1016/j.jpdc.2018.04.015 ↗
6. A multi-objective co-evolutionary algorithm for energy-efficient scheduling on a green data center10.1016/j.cor.2016.05.014 ↗
7. Speed Scaling of Processes with Arbitrary Speedup Curves on a Multiprocessor10.1007/s00224-011-9349-0 ↗
8. Dynamic speed scaling to manage energy and temperature10.1145/1206035.1206038 ↗
9. Getting the best response for your erg10.1145/1367064.1367078 ↗
10. Bansal, N., Chan, H.L., and Pruhs, K. (2009, January 4–6). Speed scaling with an arbitrary power function. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, New York, NY, USA.10.1137/1.9781611973068.76 ↗
11. Azar, Y., Devanur, N.R., Huang, Z., and Panigrahi, D. (2015, January 13–15). Speed Scaling in the Non-clairvoyant Model. Proceedings of the Annual ACM Symposium on Parallelism in Algorithms and Architectures, Portland, OR, USA.10.1145/2755573.2755582 ↗
12. Speed Scaling for Weighted Flow Time10.1137/08072125X ↗
13. Nonclairvoyant scheduling10.1016/0304-3975(94)90151-1 ↗
14. Non-clairvoyant Scheduling for Minimizing Mean Slowdown10.1007/s00453-004-1115-0 ↗
15. Yao, F., Demers, A., and Shenker, S. (1995, January 23–25). A scheduling model for reduced CPU energy. Proceedings of the Annual Symposium on Foundations of Computer Science, Berkeley, CA, USA.
16. Leonardi, S., and Raz, D. (1997, January 4–6). Approximating total flow time on parallel machines. Proceedings of the ACM Symposium on Theory of Computing, El Paso, TX, USA.10.1145/258533.258562 ↗
17. Chekuri, C., Khanna, S., and Zhu, A. (2001, January 6–8). Algorithms for minimizing weighted flow time. Proceedings of the ACM Symposium on Theory of Computing, Crete, Greece.10.1145/380752.380778 ↗
18. Minimizing the Flow Time Without Migration10.1137/S009753970037446X ↗
19. Avrahami, N., and Azar, Y. (2003, January 7–9). Minimizing total flow time and total completion time with immediate dispatching. Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures, San Diego, CA, USA.10.1145/777412.777415 ↗
20. Chekuri, C., Goel, A., Khanna, S., and Kumar, A. (2004, January 13–15). Multiprocessor scheduling to minimize flow time with epsilon resource augmentation. Proceedings of the ACM Symposium on Theory of Computing, Chicago, IL, USA.10.1145/1007352.1007411 ↗
21. Leung, J.Y.-T. (2004). Online Scheduling. Handbook of Scheduling: Algorithms, Models, and Performance Analysis, CRC Press. [1st ed.].10.1201/9780203489802 ↗
22. Online weighted flow time and deadline scheduling10.1016/j.jda.2005.12.001 ↗
23. Chadha, J., Garg, N., Kumar, A., and Muralidhara, V. (June, January 31). A competitive algorithm for minimizing weighted flow time on unrelated processors with speed augmentation. Proceedings of the Annual ACM Symposium on Theory of Computing, Bethesda, MD, USA.
24. Anand, S., Garg, N., and Kumar, A. (2012, January 17–19). Resource Augmentation for Weighted Flow-time explained by Dual Fitting. Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, Kyoto, Japan.10.1137/1.9781611973099.97 ↗
25. Energy-efficient algorithms for flow time minimization10.1145/1290672.1290686 ↗
26. Chan, S.-H., Lam, T.-W., and Lee, L.-K. (2010, January 6–8). Non-clairvoyant Speed Scaling for Weighted Flow Time. Proceedings of the Annual European Symposium, Liverpool, UK.10.1007/978-3-642-15775-2_3 ↗
27. Im, S., Kulkarni, J., Munagala, K., and Pruhs, K. (2014, January 18–21). SelfishMigrate: A Scalable Algorithm for Non-clairvoyantly Scheduling Heterogeneous Processors. Proceedings of the 2014 IEEE 55th Annual Symposium on Foundations of Computer Science (FOCS), Philadelphia, PA, USA.10.1109/FOCS.2014.63 ↗
28. Energy policies for data-center monolithic schedulers10.1016/j.eswa.2018.06.007 ↗
29. Duy, T.V.T., Sato, Y., and Inoguchi, Y. (2010, January 19–23). Performance evaluation of a Green Scheduling Algorithm for energy savings in Cloud computing. Proceedings of the IEEE international Symposium on Parallel & Distributed Processing, Workshops and Phd Forum (IPDPSW), Atlanta, GA, USA.10.1109/IPDPSW.2010.5470908 ↗
30. Energy-aware resource allocation heuristics for efficient management of data centers for Cloud computing10.1016/j.future.2011.04.017 ↗
31. Sohrabi, S., Tang, A., Moser, I., and Aleti, A. (2016, January 16). Adaptive virtual machine migration mechanism for energy efficiency. Proceedings of the 2016 IEEE/ACM 5th International Workshop on Green and Sustainable Software (GREENS), Austin, TX, USA.10.1145/2896967.2896969 ↗
32. Dynamic energy-aware scheduling for parallel task-based application in cloud computing10.1016/j.future.2016.06.029 ↗
33. Gupta, A., Krishnaswamy, R., and Pruhs, K. (2010, January 6–10). Scalably Scheduling Power-Heterogeneous Processors. Proceedings of the 37th International Colloquium Conference on Automata, Languages and Programming, Bordeaux, France.10.1007/978-3-642-14165-2_27 ↗
34. Energy-efficient multiprocessor scheduling for flow time and makespan10.1016/j.tcs.2014.07.007 ↗