More Web Proxy on the site http://driver.im/

research-article

Bias scheduling in heterogeneous multi-core architectures

Authors:

Scott HahnAuthors Info & Claims

EuroSys '10: Proceedings of the 5th European conference on Computer systems

Pages 125 - 138

https://doi.org/10.1145/1755913.1755928

Published: 13 April 2010 Publication History

Abstract

Heterogeneous architectures that integrate a mix of big and small cores are very attractive because they can achieve high single-threaded performance while enabling high performance thread-level parallelism with lower energy costs. Despite their benefits, they pose significant challenges to the operating system software. Thread scheduling is one of the most critical challenges.

In this paper we propose bias scheduling for heterogeneous systems with cores that have different microarchitectures and performance.We identify key metrics that characterize an application bias, namely the core type that best suits its resource needs. By dynamically monitoring application bias, the operating system is able to match threads to the core type that can maximize system throughput. Bias scheduling takes advantage of this by influencing the existing scheduler to select the core type that bests suits the application when performing load balancing operations.

Bias scheduling can be implemented on top of most existing schedulers since its impact is limited to changes in the load balancing code. In particular, we implemented it over the Linux scheduler on a real system that models microarchitectural differences accurately and found that it can improve system performance significantly, and in proportion to the application bias diversity present in the workload. Unlike previous work, bias scheduling does not require sampling of CPI on all core types or offline profiling. We also expose the limits of dynamic voltage/frequency scaling as an evaluation vehicle for heterogeneous systems.

References

[1]

M. Annavaram, E. Grochowski, and J. Shen. Mitigating Amdahl's law through EPI throttling. In Proc. of the 32nd Annual International Symposium on Computer Architecture, pages 298--309, June 2005.

Digital Library

[2]

S. Balakrishnan, R. Rajwar, M. Upton, and K. Lai. The impact of performance asymmetry in emerging multicore architectures. In Proc. of the 32nd Annual International Symposium on Computer Architecture, pages 506--517, June 2005.

Digital Library

[3]

M. Becchi and P. Crowley. Dynamic thread assignment on heterogeneous multiprocessor architectures. In CF '06: Proceedings of the 3rd conference on Computing frontiers, pages 29--40, 2006.

Digital Library

[4]

F. A. Bower, D. J. Sorin, and L. P. Cox. The impact of dynamically heterogeneous multicore processors on thread scheduling. IEEE Micro, 28 (3): 17--25, 2008.

Digital Library

[5]

M. DeVuyst, R. Kumar, and D. M. Tullsen. Exploiting unbalanced thread scheduling for energy and performance on a CMP of SMT processors. In Proc. of the 20th International Parallel and Distributed Processing Symposium, Apr. 2006.

Digital Library

[6]

S. Eyerman, L. Eeckhout, T. Karkhanis, and J. E. Smith. A top-down approach to architecting CPI component performance counters. IEEE Micro, 27 (1): 84--93, 2007.

Digital Library

[7]

S. Ghiasi, T. Keller, and F. Rawson. Scheduling for heterogeneous processors in server systems. In Proceedings of the 2nd Conference on Computing Frontiers, pages 199--210, May 2005.

Digital Library

[8]

M. Gschwind. The Cell broadband engine: Exploiting multiple levels of parallelism in a chip multiprocessor. International Journal of Parallel Programming, 35 (3): 233--262, June 2007.

Digital Library

[9]

R. A. Hankins, G. N. Chinya, J. D. Collins, P. H. Wang, R. Rakvic, H. Wang, and J. P. Shen. Multiple instruction stream processor. In Proc. of the 33rd Annual International Symposium on Computer Architecture, pages 114--127, June 2006.

Digital Library

[10]

Intel® 64 and IA-32 Architectures Software Developer's Manual, Volume 3B: System Programming Guide, Part 2. Intel Corporation, 2009.

[11]

R. Knauerhase, P. Brett, B. Hohlt, T. Li, and S. Hahn. Using OS observations to improve performance in multi-core systems. IEEE Micro, 28 (3): 54--66, 2008.

Digital Library

[12]

R. Kumar, K. I. Farkas, N. P. Jouppi, P. Ranganathan, and D. M. Tullsen. Single-ISA heterogeneous multi-core architectures: The potential for processor power reduction. In Proc. of the 36th Annual IEEE/ACM International Symposium on Microarchitecture, pages 81--92, Dec. 2003.

Digital Library

[13]

R. Kumar, D. M. Tullsen, P. Ranganathan, N. P. Jouppi, and K. I. Farkas. Single-ISA heterogeneous multi-core architectures for multithreaded workload performance. In Proc. of the 31st Annual International Symposium on Computer Architecture, pages 64--75, June 2004.

Digital Library

[14]

T. Li, D. Baumberger, D. Koufaty, and S. Hahn. Efficient operating system scheduling for performance-asymmetric multi-core architectures. In Proc. of the 2007 ACM/IEEE Conference on Supercomputing, Nov. 2007.

Digital Library

[15]

D. Shelepov, J. C. S. Alcaide, S. Jeffery, A. Fedorova, N. Perez, Z. F. Huang, S. Blagodurov, and V. Kumar. HASS: A scheduler for heterogeneous multicore systems. Operating Systems Review, 43 (2): 66--75, Apr. 2009.

Digital Library

[16]

T. Sondag, V. Krishnamurthy, and H. Rajan. Predictive thread-to-core assignment on a heterogeneous multi-core processor. In Proceedings of the 4th workshop on Programming Languages and Operating Systems, pages 1--5, 2007.

Digital Library

[17]

Standard Performance Evaluation Corporation. The SPEC CPU2006 benchmark. http://www.spec.org/cpu2006.

[18]

R. Stets, L. A. Barroso, K. Gharachorloo, and B. Verghese. A detailed comparison of TPC-C versus TPC-B. In Third Workshop on Computer Architecture Evaluation Using Commercial Workloads, 2000.

[19]

D. Tam, R. Azimi, and M. Stumm. Thread clustering: sharing-aware scheduling on SMP-CMP-SMT multiprocessors. In EuroSys '07: Proceedings of the 2nd ACM SIGOPS/EuroSys European Conference on Computer Systems 2007, pages 47--58, 2007.

Digital Library

[20]

P. H. Wang, J. D. Collins, G. N. Chinya, H. Jiang, X. Tian, M. Girkar, N. Y. Yang, G.-Y. Lueh, and H. Wang. EXOCHI: Architecture and programming environment for a heterogeneous multi-core multithreaded system. In Proc. of the ACM SIGPLAN 2007 Conference on Programming Language Design and Implementation, pages 156--166, June 2007.

Digital Library

[21]

O. Weschler. Inside Intel Core Microarchitecture. White Paper, Intel Corporation, 2006.

Cited By

Heerekar BPhilippidis CChuang HOlivier PBarbalace ARavindran B(2024)Offloading Datacenter Jobs to RISC-V Hardware for Improved Performance and Power EfficiencyProceedings of the 17th ACM International Systems and Storage Conference10.1145/3688351.3689152(39-52)Online publication date: 16-Sep-2024
https://dl.acm.org/doi/10.1145/3688351.3689152
Hada RSrivastava A(2024)A Novel Priority Based Scheduler for Asymmetric Multi-core Edge ComputingCurrent Trends in Web Engineering10.1007/978-3-031-50385-6_1(7-18)Online publication date: 4-Jan-2024
https://doi.org/10.1007/978-3-031-50385-6_1
Ma TChen SWu YDeng ESong ZChen QGuo MAamodt TJerger NSwift M(2023)Efficient Scheduler Live Update for Linux Kernel with ModularizationProceedings of the 28th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 310.1145/3582016.3582054(194-207)Online publication date: 25-Mar-2023
https://dl.acm.org/doi/10.1145/3582016.3582054
Show More Cited By

Index Terms

Bias scheduling in heterogeneous multi-core architectures
1. Computer systems organization
  1. Architectures
    1. Other architectures
      1. Heterogeneous (hybrid) systems
2. Software and its engineering
  1. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Process management
        Scheduling

Recommendations

Efficient operating system scheduling for performance-asymmetric multi-core architectures
SC '07: Proceedings of the 2007 ACM/IEEE conference on Supercomputing

Recent research advocates asymmetric multi-core architectures, where cores in the same processor can have different performance. These architectures support single-threaded performance and multithreaded throughput at lower costs (e.g., die size and ...
Energy-efficient scheduling on heterogeneous multi-core architectures
ISLPED '12: Proceedings of the 2012 ACM/IEEE international symposium on Low power electronics and design

The use of heterogeneous multi-core architectures has increased because of their potential energy efficiency compared to the homogeneous multi-core architectures. The shift from homogeneous multi-core to heterogeneous multi-core architectures creates ...
Asymmetry-Aware Scheduling in Heterogeneous Multi-core Architectures
NPC 2013: Proceedings of the 10th IFIP International Conference on Network and Parallel Computing - Volume 8147

As threads of execution in a multi-programmed computing environment have different characteristics and hardware resource requirements, heterogeneous multi-core processors can achieve higher performance as well as power efficiency than homogeneous multi-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

EuroSys '10: Proceedings of the 5th European conference on Computer systems

April 2010

388 pages

ISBN:9781605585772

DOI:10.1145/1755913

General Chair:
Christine Morin
INRIA Rennes, France
,
Program Chair:
Gilles Muller
INRIA/LIP6, France

Copyright © 2010 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGOPS: ACM Special Interest Group on Operating Systems

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 April 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

EuroSys '10

Sponsor:

SIGOPS

EuroSys '10: Fifth EuroSys Conference 2010

April 13 - 16, 2010

Paris, France

Acceptance Rates

Overall Acceptance Rate 241 of 1,308 submissions, 18%

Upcoming Conference

EuroSys '25

Sponsor:
sigops

Twentieth European Conference on Computer Systems

March 30 - April 3, 2025

Rotterdam , Netherlands

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

190
Total Citations
View Citations
2,551
Total Downloads

Downloads (Last 12 months)68
Downloads (Last 6 weeks)9

Reflects downloads up to 15 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Heerekar BPhilippidis CChuang HOlivier PBarbalace ARavindran B(2024)Offloading Datacenter Jobs to RISC-V Hardware for Improved Performance and Power EfficiencyProceedings of the 17th ACM International Systems and Storage Conference10.1145/3688351.3689152(39-52)Online publication date: 16-Sep-2024
https://dl.acm.org/doi/10.1145/3688351.3689152
Hada RSrivastava A(2024)A Novel Priority Based Scheduler for Asymmetric Multi-core Edge ComputingCurrent Trends in Web Engineering10.1007/978-3-031-50385-6_1(7-18)Online publication date: 4-Jan-2024
https://doi.org/10.1007/978-3-031-50385-6_1
Ma TChen SWu YDeng ESong ZChen QGuo MAamodt TJerger NSwift M(2023)Efficient Scheduler Live Update for Linux Kernel with ModularizationProceedings of the 28th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 310.1145/3582016.3582054(194-207)Online publication date: 25-Mar-2023
https://dl.acm.org/doi/10.1145/3582016.3582054
Mummidi CKundu S(2023)A Neural Network-Based Approach to Dynamic Core Morphing for AMPs2023 IEEE International Symposium on Smart Electronic Systems (iSES)10.1109/iSES58672.2023.00013(4-9)Online publication date: 18-Dec-2023
https://doi.org/10.1109/iSES58672.2023.00013
Bilbao CSaez JPrieto-Matias M(2023)Rapid Development of OS Support with PMCSched for Scheduling on Asymmetric Multicore SystemsEuro-Par 2022: Parallel Processing Workshops10.1007/978-3-031-31209-0_14(184-196)Online publication date: 2-May-2023
https://doi.org/10.1007/978-3-031-31209-0_14
Bilbao CSaez JPrieto‐Matias M(2023)Flexible system software scheduling for asymmetric multicore systems with PMCSched: A case for Intel Alder LakeConcurrency and Computation: Practice and Experience10.1002/cpe.781435:25Online publication date: 6-Jun-2023
https://doi.org/10.1002/cpe.7814
Liu NGu JTang DLi KZang BChen HLee JAgrawal KSpear M(2022)Asymmetry-aware scalable lockingProceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming10.1145/3503221.3508420(294-308)Online publication date: 2-Apr-2022
https://dl.acm.org/doi/10.1145/3503221.3508420
Sheikh SPasha M(2022)Energy-Efficient Cache-Aware Scheduling on Heterogeneous Multicore SystemsIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2021.309058733:1(206-217)Online publication date: 1-Jan-2022
https://doi.org/10.1109/TPDS.2021.3090587
Kim IHwang JWang WHumphrey M(2022)Guaranteeing Performance SLAs of Cloud Applications Under Resource StormsIEEE Transactions on Cloud Computing10.1109/TCC.2020.298537210:2(1329-1343)Online publication date: 1-Apr-2022
https://doi.org/10.1109/TCC.2020.2985372
Iskandar VSalama CTaher M(2022)Dynamic thread mapping for power-efficient many-core systems under performance constraintsMicroprocessors & Microsystems10.1016/j.micpro.2022.10461493:COnline publication date: 1-Sep-2022
https://dl.acm.org/doi/10.1016/j.micpro.2022.104614
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents