Please wait a minute...
Front. Inform. Technol. Electron. Eng.  2012, Vol. 13 Issue (6): 413-427    DOI: 10.1631/jzus.C1100198
    
Asymmetry-aware load balancing for parallel applications in single-ISA multi-core systems
Eunsung Kim, Hyeonsang Eom, Heon Y. Yeom
School of Computer Science and Engineering, Seoul National University, Seoul 151-744, Korea
Download:   PDF(0KB)
Export: BibTeX | EndNote (RIS)      

Abstract  Contemporary operating systems for single-ISA (instruction set architecture) multi-core systems attempt to distribute tasks equally among all the CPUs. This approach works relatively well when there is no difference in CPU capability. However, there are cases in which CPU capability differs from one another. For instance, static capability asymmetry results from the advent of new asymmetric hardware, and dynamic capability asymmetry comes from the operating system (OS) outside noise caused from networking or I/O handling. These asymmetries can make it hard for the OS scheduler to evenly distribute the tasks, resulting in less efficient load balancing. In this paper, we propose a user-level load balancer for parallel applications, called the ‘capability balancer’, which recognizes the difference of CPU capability and makes subtasks share the entire CPU capability fairly. The balancer can coexist with the existing kernel-level load balancer without detrimenting the behavior of the kernel balancer. The capability balancer can fairly distribute CPU capability to tasks with very little overhead. For real workloads like the NAS Parallel Benchmark (NPB), we have accomplished speedups of up to 9.8% and 8.5% in dynamic and static asymmetries, respectively. We have also experienced speedups of 13.3% for dynamic asymmetry and 24.1% for static asymmetry in a competitive environment. The impacts of our task selection policies, FIFO (first in, first out) and cache, were compared. The use of the cache policy led to a speedup of 5.3% in overall execution time and a decrease of 4.7% in the overall cache miss count, compared with the FIFO policy, which is used by default.

Key wordsScheduler      Load balancing      Capability asymmetry      OS noise      Multi-core     
Received: 04 July 2011      Published: 05 June 2012
CLC:  TP316  
Cite this article:

Eunsung Kim, Hyeonsang Eom, Heon Y. Yeom. Asymmetry-aware load balancing for parallel applications in single-ISA multi-core systems. Front. Inform. Technol. Electron. Eng., 2012, 13(6): 413-427.

URL:

http://www.zjujournals.com/xueshu/fitee/10.1631/jzus.C1100198     OR     http://www.zjujournals.com/xueshu/fitee/Y2012/V13/I6/413


Asymmetry-aware load balancing for parallel applications in single-ISA multi-core systems

Contemporary operating systems for single-ISA (instruction set architecture) multi-core systems attempt to distribute tasks equally among all the CPUs. This approach works relatively well when there is no difference in CPU capability. However, there are cases in which CPU capability differs from one another. For instance, static capability asymmetry results from the advent of new asymmetric hardware, and dynamic capability asymmetry comes from the operating system (OS) outside noise caused from networking or I/O handling. These asymmetries can make it hard for the OS scheduler to evenly distribute the tasks, resulting in less efficient load balancing. In this paper, we propose a user-level load balancer for parallel applications, called the ‘capability balancer’, which recognizes the difference of CPU capability and makes subtasks share the entire CPU capability fairly. The balancer can coexist with the existing kernel-level load balancer without detrimenting the behavior of the kernel balancer. The capability balancer can fairly distribute CPU capability to tasks with very little overhead. For real workloads like the NAS Parallel Benchmark (NPB), we have accomplished speedups of up to 9.8% and 8.5% in dynamic and static asymmetries, respectively. We have also experienced speedups of 13.3% for dynamic asymmetry and 24.1% for static asymmetry in a competitive environment. The impacts of our task selection policies, FIFO (first in, first out) and cache, were compared. The use of the cache policy led to a speedup of 5.3% in overall execution time and a decrease of 4.7% in the overall cache miss count, compared with the FIFO policy, which is used by default.

关键词: Scheduler,  Load balancing,  Capability asymmetry,  OS noise,  Multi-core 
[1] Yun-xiang Zhao, Wan-xin Zhang, Dong-sheng LI, Zhen Huang, Min-ne Li, Xi-cheng Lu. Pegasus: a distributed and load-balancing fingerprint identification system[J]. Front. Inform. Technol. Electron. Eng., 2016, 17(8): 766-780.
[2] Zhi-xiang Chen, Zhao-lin Li, Shan Cao, Fang Wang, Jie Zhou. Schedule refinement for homogeneous multi-core processors in the presence of manufacturing-caused heterogeneity[J]. Front. Inform. Technol. Electron. Eng., 2015, 16(12): 1018-1033.
[3] Mei Wen, Da-fei Huang, Chang-qing Xun, Dong Chen. Improving performance portability for GPU-specific OpenCL kernels on multi-core/many-core CPUs by analysis-based transformations[J]. Front. Inform. Technol. Electron. Eng., 2015, 16(11): 899-916.
[4] Hui Sun, Xiao Qin, Chang-sheng Xie. Exploring optimal combination of a file system and an I/O scheduler for underlying solid state disks[J]. Front. Inform. Technol. Electron. Eng., 2014, 15(8): 607-621.
[5] Hong-yan Li, Nai-xue Xiong, Ping Huang, Chao Gui. PASS: a simple, efficient parallelism-aware solid state drive I/O scheduler[J]. Front. Inform. Technol. Electron. Eng., 2014, 15(5): 321-336.
[6] Razieh Sadat Sadjady, Kamran Zamanifar. A self-routing load balancing algorithm in parallel computing: comparison to the central algorithm[J]. Front. Inform. Technol. Electron. Eng., 2011, 12(6): 455-463.
[7] Dan Wu, Xue-cheng Zou, Kui Dai, Jin-li Rao, Pan Chen, Zhao-xia Zheng. Implementation and evaluation of parallel FFT on Engineering and Scientific Computation Accelerator (ESCA) architecture[J]. Front. Inform. Technol. Electron. Eng., 2011, 12(12): 976-989.