Conservative Dynamic Load Balancer for Performance Enhancement of NUMA Multiprocessor Systems

Conservative Dynamic Load Balancer for Performance Enhancement of NUMA Multiprocessor Systems
  IJETT-book-cover           
  
© 2022 by IJETT Journal
Volume-70 Issue-3
Year of Publication : 2022
Authors : D. A. Mehta, Priyesh Kanungo
https://doi.org/10.14445/22315381/IJETT-V70I3P207

How to Cite?

D. A. Mehta, Priyesh Kanungo, "Conservative Dynamic Load Balancer for Performance Enhancement of NUMA Multiprocessor Systems," International Journal of Engineering Trends and Technology, vol. 70, no. 3, pp. 54-65, 2022. Crossref, https://doi.org/10.14445/22315381/IJETT-V70I3P207

Abstract
In pursuit of enhancing the performance of NUMA multiprocessor systems in terms of throughput, CPU utilization and Turn Around Time of processes, Linux load balancer performs load balancing periodically, which in turn causes storms of load balancing attempts and process migrations involving large overheads of time. Many of these attempts are futile and impose performance penalties. We, therefore, propose a Conservative Dynamic Load Balancer which avoids the aggressive load balancing as done by existing load balancers and adheres to the restrictive policies of balancing the load under certain conditions. Reducing the overheads of load balancing attempts, process migration, and memory & cache access improves the Turn Around Time of processes significantly as compared to the Linux load balancer. The results of experimentation exhibit the performance gain in the range of 7-12 % for different NUMA systems.

Keywords
Dynamic Load Balancing, DLB, Load Balancer, NUMA, Sched domain.

Reference
[1] Martin J. Bligh, M. Dobson, D. Hart, and G. Hu Lzenga, Linux on NUMA Systems, Linux Symposium, (2004).
[2] Christoph Lameter, Process Scheduling on 1024 Processors, in Proc. Gelato ICE 2007: Itanium Conference & Expo, San Jose, California, (2007).
[3] Mei-Ling Chiang, Shu-Wei Tu, Wei-Lun Su, and Chen-Wei Lin, Enhancing Inter-Node Process Migration for Load Balancing on Linux-Based NUMA Multicore Systems, in Proc. IEEE 42nd Annual Computer Software and Applications Conference (COMPSAC), (2018).
[4] Priyesh Kanungo, Contributions in Dynamic Load Balancing Techniques for Distributed Computing Environment, Ph.D. Thesis, IET-DAVV, (2007).
[5] M. Correa, R. Chanin, A. Sales, R. Scheer, and A. Zorzo, Multilevel Load Balancing in NUMA Computers, Technical Report No. 49, PPGCC-FACIN-PUCRS, Brazil, (2005).
[6] Dejan S. Milojicic, F. Douglis, Y. Paindaveine, R. Wheeler, S. Zhou, Process Migration, ACM Computing Survey, 32(3) (2000) 241-299.
[7] Erich Focht, Mathew Dobson, Patricia Gaughen, and Michael Hohnbaum, Linux Support for NUMA Hardware, Linux Symposium, (2003).
[8] S. Hofmeyr, C. Iancu, and F. Blagojevi, Load Balancing on Speed, in Proc. 15th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP `10), New York, USA, (2010) 147-158.
[9] Weiwei Jia, How does load balancing work inside of operating systems, Linux as an example, Available:https://www.systutorials.com/load-balancing-work-internal-operating-systems (accessed June 9, 2020).
[10] M. Tim Jones, Inside the Linux Scheduler, Available: http://www.ibm.com, (accessed Jan. 27, 2015).
[11] Sandeep Sharma, Sarabjit Singh, and Meenakshi Sharma, Performance Analysis of Load Balancing Algorithms, in Proc. World Academy of Science, Engineering and Technology, 28 (2008).
[12] Linux Kernel Documentation [Online]. Available: https://www.kernel.org/doc/html/latest/ (accessed Jan. 2021).
[13] Adam Wynne, Load Balancing in Distributed Operating Systems, Technical Report, Western Washington Univ., (2005).
[14] Geunsik Lim, Changwoo Min, and Younglk Eom, Load-Balancing for Improving User Responsiveness on Multicore Embedded Systems, Linux Symposium, (2012).
[15] Ye Liu, Shinpei Kato, and Masato Edahiro, Optimization of the Load Balancing Policy for Tiled Many-Core Processors, IEEE Access Journal, (2018).
[16] Robert Love, Linux Kernel Development, Novell Press, 2nd edition, (2005).
[17] Jean-Pierre Lozi, Baptiste Lepers, Justin Funston, Fabien Gaud, Vivien Qu´ema, and Alexandra Fedorova, The Linux Scheduler: a Decade of Wasted Cores, in Proc. EuroSys ’16, London, UK, (2016).
[18] N. Padhy, A. Panda, and S.P. Patro, A Cyclic Scheduling for Load Balancing on Linux in Multi-core Architecture, in Proc. Third International Conference on Smart Computing and Informatics, (2019) 369-378.
[19] Shreelekha Pandey, Simulator for Linux Scheduler and Load Balancer for NUMA Multiprocessor Architectures, M.E. Dissertation, S.G.S.I.T.S., (2009).
[20] Shreelekha Pandey, D.A. Mehta, Simulator of NUMA Multiprocessor Environment & Linux Load Balancing Scheduler, IJCEE, (2013).
[21] L. L. Pilla et al., A Hierarchical Approach for Load Balancing on Parallel Multi-Core Systems, in Proc. 41st Int. Conf. Parallel Processing (ICPP), (2012) 118–127.
[22] Kishore Kumar Pusukuri, Rajiv Gupta, and Laxmi N. Bhuyan, Tumbler: An Effective Load Balancing Technique for MultiCPU Multicore Systems, ACM Transactions on Architecture and Code Optimization, Springer, Singapore, 160 (2015).
[23] Suresh Siddha, sched: new sched domain for representing multicore, Available: http://lwn.net/Articles/169277/ (accessed Feb. 2014).
[24] Ian K. T. Tan, Ian Chai, and Poo Kuan Hoong, An Adaptive Task-Core Ratio Load Balancing Strategy for Multi-core Processors, International Journal of Computer and Electrical Engineering, 3(5) (2011).
[25] Saleh A. Khawatreh, An Efficient Algorithm for Load Balancing in Multiprocessor Systems, International Journal of Advanced Computer Science and Applications (IJACSA), 9(3) (2018).
[26] Automatic NUMA Balancing, Available: https://documentation.suse.com/sles/15- SP1/html/SLES-all/cha-tuning-numactl.html, (accessed April 1, 2020).
[27] B. Mallikarjuna, D. Arun Kumar Reddy, and N Venkata Vinod Kumar, Green Computing: Efficient Energy Load balancing Technique in Cloud computing, International Journal of Computing Communications and Data Engineering, (2018).
[28] M.L. Chiang, W.L. Su, S.W. Tu, and Z.W. Lin, Memory-Aware Kernel Mechanism and Policies for Improving Inter-Node Load Balancing on NUMA Systems, in Software: Practice and Experience, John Wiley, NJ, USA, 49 (2019) 1485–1508.
[29] J. Chen, S. S. Banerjee, Z.T. Kalbarczyk, and R.K. Iyer, Machine Learning for Load Balancing in the Linux Kernel, in Proc. The 11th ACM SIGOPS Asia-Pacific Workshop on Systems, Tsukuba, Japan, (2020).
[30] Mei-Ling Chiang and Wei-Lun Su, Thread-Aware Mechanism to Enhance Inter-Node Load Balancing for Multithreaded Applications on NUMA Systems, Applied Sciences, Available: https://doi.org/10.3390/app11146486, (accessed Nov. 2021).