Load balancing in multicore systems using heuristics based approach

Load balancing in multicore systems using heuristics based approach

Автор: Shruti Jadon, Rama Shankar Yadav

Журнал: International Journal of Intelligent Systems and Applications @ijisa

Статья в выпуске: 12 vol.10, 2018 года.

Бесплатный доступ

Multicore processing is advantageous over single core processors in the present highly advanced time critical applications. The tasks in real time applications need to be completed within the prescribed deadlines. Based on this philosophy, the proposed paper discusses the concept of load balancing algorithms in such a way that the work load is equally distributed amongst all cores in the processor. The equal distribution of work load amongst all the cores will result in enhanced utilization and increase in computing speed of application with all the deadlines met. In the heuristic based load balanced algorithm (HBLB), the best task from the set of tasks is selected using the feasibility check window and is assigned to the core. The application of HBLB reduces imbalance among the cores and results in lesser migration leading to low migration overhead. By utilizing all the cores of the multicore system, the computing speed of the application increases tremendously which results in the increase in efficiency of the system. The present paper also discusses the improved version of HBLB, known as Improved_Heuristic Based Load Balancing (Improved_HBLB), which focuses on further reducing the imbalance and the number of backtracks as compared to HBLB algorithm. It was observed that Improved_HBLB gives approximately 10% better results over the HBLB algorithm.

Еще

Load balancing, imbalance, heuristic, backtracking, feasibility check window, real time system

Короткий адрес: https://sciup.org/15016554

IDR: 15016554   |   DOI: 10.5815/ijisa.2018.12.06

Список литературы Load balancing in multicore systems using heuristics based approach

  • A. Vajda, “Programming many-core chips”, Springer Science and Business Media, 2011. DOI: 10.1007/978-1-4419-9739-5.
  • J. W. Langston and X. He, “Multi-core processors and caching-a-survey”, Tennessee Technological University, 2007.
  • S. Jadon and R. S. Yadav, “Multicore processor: Internal structure, architecture, issues, challenges, scheduling strategies and performance”, IEEE International Conference on Industrial and Information Systems, pp. 381-386, 2016. DOI: 10.1109/ICIINFS.2016.8262970.
  • R. Mohan and N. P. Gopalan, "Dynamic Load Balancing using Graphics Processors", International Journal of Intelligent Systems and Applications (IJISA), Vol.6, No.5, pp.70-75, 2014. DOI: 10.5815/ijisa.2014.05.07.
  • M. Verma, N. Bhardwaj, and A. K. Yadav, "Real Time Efficient Scheduling Algorithm for Load Balancing in Fog Computing Environment", International Journal of Information Technology and Computer Science (IJITCS), Vol.8, No.4, pp.1-10, 2016. DOI: 10.5815/ijitcs.2016. 04.01.
  • M. Mesbahi and A. M. Rahmani, "Load Balancing in Cloud Computing: A State of the Art Survey", International Journal of Modern Education and Computer Science (IJMECS), Vol.8, No.3, pp.64-78, 2016. DOI: 10.5815/ ijmecs.2016.03.08.
  • P. S. Kshirsagar and A. M. Pujar, "Resource Allocation Strategy with Lease Policy and Dynamic Load Balancing", International Journal of Modern Education and Computer Science (IJMECS), Vol.9, No.2, pp.27-33, 2017. DOI: 10.5815/ijmecs.2017.02.03.
  • X. Zhang, J. Li, and X. Feng, "A Dynamic Feedback-based Load Balancing Methodology", International Journal of Modern Education and Computer Science (IJMECS), Vol.9, No.12, pp. 57-65, 2017. DOI: 10.5815/ijmecs. 2017.12.07.
  • L. L. Pilla , C. P. Ribeiro, P. Coucheneyb, F. Broquedis, B. Gaujal, P. O. A. Navauxa, and J-F Méhaut, “A topology-aware load balancing algorithm for clustered hierarchical multi-core machines”, Future Generation Computer Systems, Vol. 30, pp. 191-201, 2014. DOI: 10.1016/ j.future.2013.06.023.
  • V. Thakur and S. Kumar, “Load Balancing Approaches: Recent Computing Trends”, International Journal of Computer Applications, Vol. 131, No.14, 2015.
  • K. M. Katre, H. Ramaprasad, A. Sarkar, and F. Mueller, “Policies for migration of real-time tasks in embedded multi-core systems”, Real Time System Symposium, pp. 17–20, 2009.
  • J. Luo and N. Jha, “Power-efficient scheduling for heterogeneous distributed real time embedded systems”, IEEE Transaction Computer-Aided Design of Integrated Circuits and Systems, pp. 1161–1171, 2007. DOI: 10.1109/TCAD.2006.885736.
  • A. Srinivasan and J. Anderson, “Optimal rate-based scheduling on multiprocessors”, ACM Symposium on Theory of Computing, pp. 189–198, 2002. DOI: 10.1145/509907.509938.
  • J. Anderson and A. Srinivasan, “Early-release fair scheduling”, Euromicro Conference on Real-Time Systems, pp. 35–43, 2000. DOI: 10.1109/EMRTS. 2000.853990.
  • H. Anderson and A. Srinivasan, “Mixed pfair/erfair scheduling of asynchronous periodic tasks”, Euromicro Conference on Real-Time Systems, pp. 76–85, 2001. DOI: 10.1109/EMRTS.2001.934004
  • M. Moir and S. Ramamurthy, “Pfair scheduling of fixed and migrating periodic tasks on multiple resources”, IEEE Real-Time Systems Symposium, pp. 294–303, 1999. DOI: 10.1109/REAL.1999.818857.
  • S. K. Baruah, N. K. Cohen, C. G. Plaxton, and D. Varvel, “Proportionate progress: A notion of fairness in resource allocation”, Algorithmica, Vol. 15, pp. 600–625, 1996. DOI: 10.1007/BF01940883.
  • S. Baruah, “Techniques for multiprocessor global schedulability analysis”, IEEE Real-Time Systems Symposium, pp. 119–128, 2007. DOI: 10.1109/RTSS. 2007.35.
  • J. Kang and D. G.Waddington, “Load balancing aware real-time task partitioning in multicore systems”, Embedded and Real-Time Computing Systems and Applications (RTCSA), pp. 404-407, 2004. DOI: 10.1109/RTCSA.2012.71.
  • S. Park, E. Seo, J. Jeong, and J. Lee. “Energy efficient scheduling of real time tasks on multicore processors”, IEEE Transaction on Parallel and Distributed Systems, Vol. 19, pp. 1540-1552, 2008. DOI: 10.1109/TPDS. 2008.104.
  • J. L. March, J. Sahuquillo, S. Petit, H. Hassan, and J. Duato, “A dynamic power-aware partitioner with task migration for multicore embedded systems”, Parallel Processing, Springer, 2011, pp. 218-229. DOI: 10.1007/978-3-642-23400-2_21.
  • K.-M. Cho, C.-W. Tsai, Y.-S.Chiu, and C.-S. Yang, “A high performance load balance strategy for real-time multicore systems”, The Scientific World Journal, Vol. 14, 2014. DOI: 10.1155/2014/101529.
  • J. A. Stankovic, M. Spuri, K. Ramamritham, and G. Buttazzo, “Deadline scheduling for Real-Time Systems”, The Springer International Series in Engineering and Computer Science, Vol. 460, 1998. DOI: 10.1007/978-1-4615-5535-3.
  • I. Chai, Ian K. T. Tan, and P. K. Hoong, “Dynamic threshold for imbalance assessment on load balancing for multicore systems”, Computers & Electrical Engineering, Vol. 39, pp. 338-348, 2013. DOI: 10.1016/j.compeleceng. 2012.10.013
Еще
Статья научная
QR-код для установки приложения SciUp Наведите камеру и скачайте бесплатное приложение SciUp