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

Eunsung KIM; Hyeonsang EOM; Heon Y. YEOM

doi:10.1631/jzus.C1100198

Your Location：

Home >

Browse articles >

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

计算机与自动化 | Updated：2022-12-09

- Asymmetry-aware load balancing for parallel applications in single-ISA multi-core systems
- Asymmetry-aware load balancing for parallel applications in single-ISA multi-core systems
- 信息与电子工程前沿（英文） 2012年13卷第6期页码：413-427
- Affiliations：
  
  School of Computer Science and Engineering, Seoul National University, Seoul 151-744, Korea
- Author bio：
  
  [ "Eunsung KIM, E-mail: eskim@dcslab.snu.ac.kr" ]
  Hyeonsang EOM, E-mail: hseom@cse.snu.ac.kr
  [ "Heon Y. YEOM, E-mail: yeom@snu.ac.kr" ]
- Funds：
  
  Project 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) and the Korea Communications Commission, under the Communications Policy Research Center Support Program supervised by the Korea Communications Agency (No. KCA-2011-1194100004-110010100)
- DOI：10.1631/jzus.C1100198
  中图分类号： TP316
- 收稿：2011-07-04，
  
  修回：2012-;5-;4，
  
  纸质出版：2012-06
- Accepted：
Scan QR Code
Asymmetry-aware load balancing for parallel applications in single-ISA multi-core systems[J]. 信息与电子工程前沿（英文）, 2012,13(6):413-427.

Eunsung KIM, Hyeonsang EOM, Heon Y. YEOM. Asymmetry-aware load balancing for parallel applications in single-ISA multi-core systems[J]. Frontiers of Information Technology & Electronic Engineering, 2012, 13(6): 413-427.
Asymmetry-aware load balancing for parallel applications in single-ISA multi-core systems[J]. 信息与电子工程前沿（英文）, 2012,13(6):413-427. DOI： 10.1631/jzus.C1100198.

Eunsung KIM, Hyeonsang EOM, Heon Y. YEOM. Asymmetry-aware load balancing for parallel applications in single-ISA multi-core systems[J]. Frontiers of Information Technology & Electronic Engineering, 2012, 13(6): 413-427. DOI： 10.1631/jzus.C1100198.

摘要

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.

关键词

Keywords

references

K. Asanovic , , , R. Bodik , , , J. Demmel , , , T. Keaveny , , , K. Keutzer , , , J. Kubiatowicz , , , N. Morgan , , , D. Patterson , , , K. Sen , , , J. Wawrzynek , , , 等 . . A view of the parallel computing landscape . . Commun. ACM , , 2009 . . 52 ( ( 10 ): ): 56 - - 67 . . DOI: 10.1145/1562764.1562783 http://doi.org/10.1145/1562764.1562783 . .

D.H. Bailey , , , E. Barszcz , , , J.T. Barton , , , D.S. Browning , , , R.L. Carter , , , L. Dagum , , , R.A. Fatoohi , , , P.O. Frederickson , , , T.A. Lsinski , , , R.S. Schreiber , , , 等 . . The NAS Parallel Benchmarks . . Int. J. Supercomput. Appl. , , 1991 . . 5 ( ( 3 ): ): 63 - - 73 . . . .

P. Beckman , , , K. Iskra , , , K. Yoshii , , , S. Coghlan . . Operating system issues for petascale systems . . ACM SIGOPS Oper. Syst. Rev. , , 2006 . . 40 ( ( 2 ): ): 29 - - 33 . . DOI: 10.1145/1131322.1131332 http://doi.org/10.1145/1131322.1131332 . .

P. Beckman , , , K. Iskra , , , K. Yoshii , , , S. Coghlan , , , A. Nataraj . . Benchmarking the effects of operating system interference on extreme-scale parallel machines . . Cluster Comput. , , 2008 . . 11 ( ( 1 ): ): 3 - - 16 . . DOI: 10.1007/s10586-007-0047-2 http://doi.org/10.1007/s10586-007-0047-2 . .

C. Boneti , , , R. Gioiosa , , , F.J. Cazorla , , , M. Valero . . A Dynamic Scheduler for Balancing HPC Applications . . Proc. ACM/IEEE Conf. on Supercomputing, Article No.41 , , 2008 . . p.1 - - 12 . . . .

D.P. Bovet , , , M. Cesati . . Understanding the Linux Kernel (3rd Ed.) . . O'Reilly , , 2005 . . p.258 - - 293 . . . .

D. Brodowski . . Current Trend in Linux Kernel Power Management, linuxtag 2005 . . Available from , , http://www.free-it.de/archiv/talks_2005/paper-11017/paper-11017.pdf http://www.free-it.de/archiv/talks_2005/paper-11017/paper-11017.pdf , , [Accessed on Apr. 15, 2012] 2005 . . 2012 . .

P. De , , , R. Kothari , , , V. Mann . . Identifying Sources of Operating System Jitter Through Fine-Grained Kernel Instrumentation . . Proc. IEEE Int. Conf. on Cluster Computing , , 2007 . . p.331 - - 340 . . DOI: 10.1109/CLUSTR.2007.4629247 http://doi.org/10.1109/CLUSTR.2007.4629247 . .

A. Demers , , , S. Keshav , , , S. Shenker . . Analysis and simulation of a fair queueing algorithm . . ACM SIGCOMM Comput. Commun. Rev. , , 1989 . . 19 ( ( 4 ): ): 1 - - 12 . . DOI: 10.1145/75247.75248 http://doi.org/10.1145/75247.75248 . .

K. Ferreira , , , R. Brightwell , , , P. Bridges . . Characterizing Application Sensitivity to OS Interference Using Kernel-Level Noise Injection . . Proc. ACM/IEEE Conf. on Supercomputing, Article No. 19 , , 2008 . . p.1 - - 12 . . . .

R. Gioiosa , , , F. Petrini , , , K. Davis , , , F. Lebaillif-Delamare . . Analysis of System Overhead on Parallel Computers . . 4th IEEE Int. Symp. on Signal Processing and Information Technology , , 2004 . . p.387 - - 390 . . . .

R. Gioiosa , , , S.A. McKee , , , M. Valero . . Designing OS for HPC Applications: Scheduling . . Proc. IEEE Int. Conf. on Cluster Computing , , 2010 . . p.78 - - 87 . . DOI: 10.1109/CLUSTER.2010.16 http://doi.org/10.1109/CLUSTER.2010.16 . .

M.D. Hill , , , M.R. Marty . . Amdahl's law in the multicore era . . IEEE Comput. , , 2008 . . 41 ( ( 7 ): ): 33 - - 38 . . DOI: 10.1109/MC.2008.209 http://doi.org/10.1109/MC.2008.209 . .

T. Hoefler , , , T. Mehlan , , , A. Lumsdaine , , , W. Rehm . . Netgauge: a Network Performance Measurement Framework . . Proc. High Performance Computing and Communications , , 2007 . . p.659 - - 671 . . . .

S. Hofmeyr , , , C. Iancu , , , F. Blagojevíc . . Load Balancing on Speed . . Proc. 15th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming , , 2010 . . 147 - - 158 . . DOI: 10.1145/1693453.1693475 http://doi.org/10.1145/1693453.1693475 . .

X. Jiang , , , A. Mishra , , , L. Zhao , , , R. Iyer , , , Z. Fang , , , S. Srinivasan , , , S. Makineni , , , P. Brett , , , C.R. Das . . ACCESS: Smart Scheduling for Asymmetric Cache CMPs . . Proc. IEEE 17th Int. Symp. on High Performance Computer Architecture , , 2011 . . p.527 - - 538 . . DOI: 10.1109/HPCA.2011.5749757 http://doi.org/10.1109/HPCA.2011.5749757 . .

D. Koufaty , , , D. Reddy , , , S. Hahn . . Bias Scheduling in Heterogeneous Multi-core Architectures . . Proc. 5th European Conf. on Computer Systems , , 2010 . . p.125 - - 138 . . DOI: 10.1145/1755913.1755928 http://doi.org/10.1145/1755913.1755928 . .

R. Kumar , , , K.I. Farkas , , , N.P. Jouppi , , , P. Ranganathan , , , D.M. Tullsen . . Single-ISA Heterogeneous Multi-core Architectures: the Potential for Processor Power Reduction . . Proc. 36th Annual IEEE/ACM Int. Symp. on Micro-architecture , , 2003 . . p.81 - - 92 . . . .

R. Kumar , , , D.M. Tullsen , , , P. Ranganathan , , , N.P. Jouppi , , , K.I. Farkas . . Single-ISA Heterogeneous Multi-core Architectures for Multithreaded Workload Performance . . Proc. 31st Annual Int. Symp. on Computer Architecture , , 2004 . . p.64 - - 75 . . . .

N. Lakshminarayana , , , S. Rao , , , H. Kim . . Asymmetry Aware Scheduling Algorithms for Asymmetric Multiprocessors. Proc . . 4th Annual Workshop on the Interaction Between Operating Systems and Computer Architecture , , 2008 . . .

T. Li , , , D. Baumberger , , , S. Hahn . . Efficient and Scalable Multiprocessor Fair Scheduling Using Distributed Weighted Round-Robin . . Proc. 14th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming , , 2009 . . p.65 - - 74 . . DOI: 10.1145/1504176.1504188 http://doi.org/10.1145/1504176.1504188 . .

R. Olsson . . pktgen the Linux Packet Generator . . Proc. Linux Symp. , , 2005 . . p.11 - - 24 . . . .

V. Pallipadi , , , A. Starikovskiy . . The Ondemand Governor . . Proc. Linux Symp. , , 2006 . . p.223 - - 238 . . . .

F. Petrini , , , D.J. Kerbyson , , , S. Pakin . . The Case of the Missing Supercomputer Performance: Achieving Optimal Performance on the 8192 Processors of ASCI Q . . Proc. ACM/IEEE Conf. on Supercomputing , , 2003 . . p.55 - - 71 . . DOI: 10.1145/1048935.1050204 http://doi.org/10.1145/1048935.1050204 . .

P. Radojkovic , , , V. Cakarevic , , , J. Verdu , , , A. Pajuelo , , , R. Gioiosa , , , F.J. Cazorla , , , M. Nemirovsky , , , M. Valero . . Measuring Operating System Overhead on CMT Processors. Proc. 20th Int. Symp . . on Computer Architecture and High Performance Computing , , 2008 . . p.133 - - 140 . . DOI: 10.1109/SBAC-PAD.2008.19 http://doi.org/10.1109/SBAC-PAD.2008.19 . .

J.C. Saez , , , M. Prieto , , , A. Fedorova , , , S. Blagodurov . . A Comprehensive Scheduler for Asymmetric Multicore Systems . . Proc. 5th European Conf. on Computer Systems , , 2010 . . p.139 - - 152 . . DOI: 10.1145/1755913.1755929 http://doi.org/10.1145/1755913.1755929 . .

J.H. Salim . . Beyond Softnet. Proc . . 5th Annual Linux Showcase and Conf. , , 2001 . . p.165 - - 172 . . . .

T. Scogland , , , P. Balaji , , , W. Feng , , , G. Narayanaswamy . . Asymmetric Interactions in Symmetric Multi-core Systems: Analysis, Enhancements and Evaluation . . Proc. ACM/IEEE Conf. on Supercomputing, Article No. 17 , , 2008 . . p.1 - - 12 . . . .

D. Tsafrir , , , Y. Etsion , , , D.G. Feitelson , , , S. Kirkpatrick . . System Noise, OS Clock Ticks, and Fine-Grained Parallel Applications . . Proc. 19th Annual Int. Conf. on Supercomputing , , 2005 . . p.303 - - 312 . . DOI: 10.1145/1088149.1088190 http://doi.org/10.1145/1088149.1088190 . .

浏览量

Downloads

CSCD

文章被引用时，请邮件提醒。

Submit

工具集

关联资源

A self-routing load balancing algorithm in parallel computing: comparison to the central algorithm