زمانبندی کارها در محیط‌های ابری با استفاده از چارچوب نگاشت – کاهش و الگوریتم ژنتیک
محورهای موضوعی : عمومىسید نیما خضر 1 , نیما جعفری نویمی پور 2 *
1 - گروه مهندسی کامپیوتر، واحد تبریز، دانشگاه آزاد اسلامی، تبریز، ایران
2 - گروه مهندسی کامپیوتر، واحد تبریز، دانشگاه آزاد اسلامی، تبریز، ایران
کلید واژه: رایانش ابری, زمانبندی وظایف, کاهش زمان اجرا, الگوریتم ژنتیک, نگاشت-کاهش, هادوپ,
چکیده مقاله :
زمانبندی وظایف یک جزء حیاتی هر سیستم توزیع‌شده همچون گرید، ابر و شبکه های نظیر به نظیر می باشد که وظایف را برای اجرا به منابع مناسب ارجاع می دهد. روش های رایج در زمانبندی دارای معایبی از قبیل پیچیدگی زمانی بالا، هم‌زمان اجرا نشدن کارهای ورودی و افزایش زمان اجرای برنامه است. الگوریتم های زمانبندی بر پایه اکتشاف جهت اولویت‌دهی به وظایف از سیاست های متفاوتی استفاده می کنند که باعث به وجود آمدن زمان های اجرای بالا بر روی سیستم های رایانش توزیع شده ناهمگن می شود. بنابراین، روشی مناسب است که اولویت دهی آن باعث تولید زمان اجرای کل کمینه گردد. الگوریتم ژنتیک به‌عنوان یکی از روش‌های تکاملی به‌منظور بهینه کردن مسائل NP-کامل به کار گرفته می شود. در این مقاله الگوریتم ژنتیک موازی با استفاده از چارچوب نگاشت-کاهش برای زمانبندی وظایف بر روی رایانش ابری با استفاده از صف های اولویت چندگانه ارائه‌شده است. ایده اصلی این مقاله، استفاده از چارچوب نگاشت-کاهش برای کاهش زمان اجرای کل برنامه می باشد. نتایج آزمایش‌ها بر روی مجموعه ای از گراف های جهت دار بدون دور تصادفی حاکی از آن است که روش پیشنهادی زمان اجرای کل دو روش موجود را با سرعت همگرایی بالا بهبود داده است.
Task scheduling is a vital component of any distributed system such as grids, clouds, and peer-to-peer networks that refer tasks to appropriate resources for execution. Common scheduling methods have disadvantages such as high time complexity, inconsistent execution of input tasks, and increased program execution time. Exploration-based scheduling algorithms to prioritize tasks from
1. Khemka, B., et al., Utility maximizing dynamic resource management in an oversubscribed energy-constrained heterogeneous computing system. Sustainable Computing: Informatics and Systems, 2015. 5: p. 14-30.
2. Arunarani, A.R., Manjula, D. and Sugumaran, V., 2019. Task scheduling techniques in cloud computing: A literature survey. Future Generation Computer Systems, 91, pp.407-415.
3. Zang, X., Sun, J., Zhao, J. and Zeng, W., 2018, May. Research Progress of Cloud Computing Task Scheduling Technology. In 2018 3rd International Conference on Automation, Mechanical Control and Computational Engineering (AMCCE 2018). Atlantis Press.
4. Young Choon, L. and A.Y. Zomaya, A Novel State Transition Method for Metaheuristic-Based Scheduling in Heterogeneous Computing Systems. Parallel and Distributed Systems, IEEE Transactions on, 2008. 19(9): p. 1215-1223.
5. Keshanchi, B. and Navimipour, N.J., 2016. Priority-based task scheduling in the cloud systems using a memetic algorithm. Journal of Circuits, Systems and Computers, 25(10), p.1650119.
6. Dean, J. and S. Ghemawat, MapReduce: a flexible data processing tool. Communications of the ACM, 2010. 53(1): p. 72-77.
7. Khezr, S.N. and Navimipour, N.J., 2017. MapReduce and its applications, challenges, and architecture: a comprehensive review and directions for future research. Journal of Grid Computing, 15(3), pp.295-321.
8. Topcuoglu, H., S. Hariri, and W. Min-You, Performance-effective and low-complexity task scheduling for heterogeneous computing. Parallel and Distributed Systems, IEEE Transactions on, 2002. 13(3): p. 260-274.
9. Mateos, C., E. Pacini, and C.G. Garino, An ACO-inspired algorithm for minimizing weighted flowtime in cloud-based parameter sweep experiments. Advances in Engineering Software, 2013. 56: p. 38-50.
10. Ashouraie, M. and N. Jafari Navimipour, Priority-based task scheduling on heterogeneous resources in the Expert Cloud. Kybernetes, 2015. 44(10): p. 1455-1471.
11. Wang, W., et al., Cloud-DLS: Dynamic trusted scheduling for Cloud computing. Expert Systems with Applications, 2012. 39(3): p. 2321-2329.
12. Xu, Y., et al., A genetic algorithm for task scheduling on heterogeneous computing systems using multiple priority queues. Information Sciences, 2014. 270(0): p. 255-287. , 2014. 270(0): p. 255-287.
13. Abed, I., et al., Optimization of the Time of Task Scheduling for Dual Manipulators using a Modified Electromagnetism-Like Algorithm and Genetic Algorithm. Arabian Journal for Science and Engineering, 2014. 39(8): p. 6269-6285.
14. Lipowski, A. and D. Lipowska, Roulette-wheel selection via stochastic acceptance. Physica A: Statistical Mechanics and its Applications, 2012. 391(6): p. 2193-2196.
15. Ong, B. and M. Fukushima, Genetic algorithm with automatic termination and search space rotation. Memetic Computing, 2011. 3(2): p. 111-127.
16. Hashem, Ibrahim Abaker Targio, Nor Badrul Anuar, Mohsen Marjani, Ejaz Ahmed, Haruna Chiroma, Ahmad Firdaus, Muhamad Taufik Abdullah et al. "MapReduce scheduling algorithms: a review." The Journal of Supercomputing (2018): 1-31.
17. Keshanchi B, Souri A, Navimipour NJ. An improved genetic algorithm for task scheduling in the cloud environments using the priority queues: formal verification, simulation, and statistical testing. Journal of Systems and Software. 2017 Feb 1;124:1-21.
18. Shabestari, F., Rahmani, A. M., Navimipour, N. J., & Jabbehdari, S. (2019). A taxonomy of software-based and hardware-based approaches for energy efficiency management in the Hadoop. Journal of Network and Computer Applications, 126, 162-177.
19. Ashouraei, M., Khezr, S. N., Benlamri, R., & Navimipour, N. J. (2018, August). A new SLA-aware load balancing method in the cloud using an improved parallel task scheduling algorithm. In 2018 IEEE 6th International Conference on Future Internet of Things and Cloud (FiCloud) (pp. 71-76). IEEE.
20. Panahi, V., & Navimipour, N. J. (2019). Join query optimization in the distributed database system using an artificial bee colony algorithm and genetic operators. Concurrency and Computation: Practice and Experience, e5218.
21. Mirjalili, S. (2019). Genetic algorithm. In Evolutionary Algorithms and Neural Networks (pp. 43-55). Springer, Cham.
22. Malik, M., Neshatpour, K., Rafatirad, S., Joshi, R. V., Mohsenin, T., Ghasemzadeh, H., & Homayoun, H. (2019). Big vs little core for energy-efficient Hadoop computing. Journal of Parallel and Distributed Computing, 129, 110-124.