Please wait a minute...
FITEE
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
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
 全文: PDF 
摘要： 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    
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 words: Scheduler    Load balancing    Capability asymmetry    OS noise    Multi-core
收稿日期: 2011-07-04 出版日期: 2012-06-05
CLC:  TP316  
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章　　
Eunsung Kim
Hyeonsang Eom
Heon Y. Yeom

引用本文:

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.

链接本文:

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

[1] 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.
[2] 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.