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

Computer & Automation | 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
- Frontiers of Information Technology & Electronic Engineering Vol. 13, Issue 6, Pages: 413-427(2012)
- 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：
- DOI：10.1631/jzus.C1100198
  CLC： TP316
- Received：04 July 2011，
  
  Revised：2012-;5-;4，
  
  Published：2012-06
- Accepted：
Scan QR Code
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：

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 . .

Views

Downloads

CSCD

Alert me when the article has been cited

Submit

Tools

Publicity Resources

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

Related Author

Dan WU

Xue-cheng ZOU

Kui DAI

Jin-li RAO

Pan CHEN

Zhao-xia ZHENG

Sadat SADJADY

Kamran ZAMANIFAR

Related Institution

Department of Electronic Science & Technology, Huazhong University of Science and Technology

Department of Computer Engineering, Islamic Azad University, Najafabad Branch, Isfahan

Faculty of Information Technology, Beijing University of Technology

Chat

Address：Zhejiang University Press, 148 Tianmushan Road, Hangzhou, China Postal code：310028
Tel：+86-571-88273162 Email：fitee@zju.edu.cn
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.

⁰