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 

出 版 物：《Journal of Zhejiang University-Science C(Computers and Electronics)》 (浙江大学学报C辑（计算机与电子（英文版）)

年 卷 期：2012年第13卷第6期

页      面：413-427页

核心收录：

学科分类：08[工学] 081201[工学-计算机系统结构] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：supported by the Next-Generation Information Computing Development Program through the National Research Foundation of Korea funded by the Ministry of Education, Science and Technology(No. 2011-0020521) the Korea Communications Commission,under the Communications Policy Research Center Support Program supervised by the Korea Communications Agency (No. KCA-2011-1194100004-110010100) 

主　　题：Scheduler Load balancing Capability asymmetry OS noise Multi-core 

摘      要：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 balaneer 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 kemel-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.