research-article

Fairness-oriented OS Scheduling Support for Multicore Systems

Authors:

Jaehyuk HuhAuthors Info & Claims

ICS '16: Proceedings of the 2016 International Conference on Supercomputing

Article No.: 29, Pages 1 - 12

https://doi.org/10.1145/2925426.2926262

Published: 01 June 2016 Publication History

Abstract

Although traditional CPU scheduling efficiently utilizes multiple cores with equal computing capacity, the advent of multicores with diverse capabilities pose challenges to CPU scheduling. For the multi-cores with uneven computing capability, scheduling is essential to exploit the efficiency of core asymmetry, by matching each application with the best core type. However, in addition to the efficiency, an important aspect of CPU scheduling is fairness in CPU provisioning. Such uneven core capability is inherently unfair to threads and causes performance variance, as applications running on fast cores receive higher capability than applications on slow cores. Depending on co-running applications and scheduling decisions, the performance of an application may vary significantly. This study investigates the fairness problem in multi-cores with uneven capability, and explores the design space of OS schedulers supporting multiple fairness constraints. In this paper, we consider two fairness-oriented constraints, minimum fairness for the minimum guaranteed performance and uniformity for performance variation reduction. This study proposes three scheduling policies which guarantee a minimum performance bound while improving the overall throughput and reducing performance variation too. The three proposed fairness-oriented schedulers are implemented for the Linux kernel with an online application monitoring technique. Using an emulated asymmetric multi-core with frequency scaling and a real asymmetric multi-core with the big.LITTLE architecture, the paper shows that the proposed schedulers can effectively support the specified fairness while improving overall system throughput.

References

[1]

N. Binkert, B. Beckmann, G. Black, S. K. Reinhardt, A. Saidi, A. Basu, J. Hestness, D. R. Hower, T. Krishna, S. Sardashti, R. Sen, K. Sewell, M. Shoaib, N. Vaish, M. D. Hill, and D. A. Wood. The gem5 simulator. SIGARCH Comput. Archit. News, 39(2):1--7, August 2011.

Digital Library

[2]

N. K. Choudhary, S. V. Wadhavkar, T. A. Shah, H. Mayukh, J. Gandhi, B. H. Dwiel, S. Navada, H. H. Najaf-abadi, and E. Rotenberg. Fabscalar: composing synthesizable RTL designs of arbitrary cores within a canonical superscalar template. In Proceedings of the 38th annual International Symposium on Computer Architecture (ISCA), 2011.

Digital Library

[3]

J. Demme and S. Sethumadhavan. Rapid identification of architectural bottlenecks via precise event counting. In Proceedings of the 38th annual International Symposium on Computer architecture (ISCA), 2011.

Digital Library

[4]

P. Greenhalgh. Big.LITTLE processing with ARM Cortex-A15 & Cortex-A7. ARM whitepaper, 2011.

[5]

S. Herbert and D. Marculescu. Variation-aware dynamic voltage/frequency scaling. In Proceedings of the 15th IEEE international symposium on High Performance Computer Architecture (HPCA), 2009.

[6]

J. A. Joao, M. A. Suleman, O. Mutlu, and Y. N. Patt. Bottleneck identification and scheduling in multithreaded applications. In Proceedings of the 17th international conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), 2012.

Digital Library

[7]

J. A. Joao, M. A. Suleman, O. Mutlu, and Y. N. Patt. Utility-based acceleration of multithreaded applications on asymmetric CMPs. In Proceedings of the 40th Annual International Symposium on Computer Architecture (ISCA), 2013.

Digital Library

[8]

D. Koufaty, D. Reddy, and S. Hahn. Bias scheduling in heterogeneous multi-core architectures. In Proceedings of the 5th European conference on Computer systems (EuroSys), 2010.

Digital Library

[9]

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 Proceedings of the 36th annual IEEE/ACM International Symposium on Microarchitecture (MICRO), 2003.

Digital Library

[10]

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 Proceedings of the 31st annual International Symposium on Computer architecture (ISCA), 2004.

Digital Library

[11]

Y. Kwon, C. Kim, S. Maeng, and J. Huh. Virtualizing performance asymmetric multi-core systems. In Proceedings of the 38th annual International Symposium on Computer Architecture (ISCA), 2011.

Digital Library

[12]

N. B. Lakshminarayana, J. Lee, and H. Kim. Age based scheduling for asymmetric multiprocessors. In Proceedings of the 2009 Conference on High Performance Computing Networking, Storage and Analysis (SC), 2009.

Digital Library

[13]

T. Li, D. Baumberger, and S. Hahn. Efficient and scalable multiprocessor fair scheduling using distributed weighted round-robin. In Proceedings of the 14th ACM SIGPLAN symposium on Principles and Practice of Parallel Programming (PPoPP), 2009.

Digital Library

[14]

T. Li, D. Baumberger, D. A. Koufaty, and S. Hahn. Efficient operating system scheduling for performance-asymmetric multi-core architectures. In Proceedings of the 2007 Conference on High Performance Computing Networking, Storage and Analysis (SC), 2007.

Digital Library

[15]

T. Li, P. Brett, R. Knauerhase, D. Koufaty, D. Reddy, and S. Hahn. Operating system support for overlapping-ISA heterogeneous multi-core architectures. In Proceedings of the 16th IEEE international symposium on High Performance Computer Architecture (HPCA), 2010.

[16]

J. C. Saez, A. Fedorova, M. Prieto, and H. Vegas. Operating system support for mitigating software scalability bottlenecks on asymmetric multicore processors. In Proceedings of the 7th ACM international conference on Computing Frontiers (CF), 2010.

Digital Library

[17]

J. C. Saez, M. Prieto, A. Fedorova, and S. Blagodurov. A comprehensive scheduler for asymmetric multicore systems. In Proceedings of the 5th European conference on Computer systems (EuroSys), 2010.

Digital Library

[18]

D. Shelepov, J. C. Saez Alcaide, S. Jeffery, A. Fedorova, N. Perez, Z. F. Huang, S. Blagodurov, and V. Kumar. HASS: a scheduler for heterogeneous multicore systems. SIGOPS Oper. Syst. Rev., 43:66--75, 2009.

Digital Library

[19]

M. A. Suleman, O. Mutlu, M. K. Qureshi, and Y. N. Patt. Accelerating critical section execution with asymmetric multi-core architectures. In Proceedings of the 14th international conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), 2009.

Digital Library

[20]

R. Teodorescu and J. Torrellas. Variation-aware application scheduling and power management for chip multiprocessors. In Proceedings of the 35th annual International Symposium on Computer Architecture (ISCA), 2008.

Digital Library

[21]

K. Van Craeynest, S. Akram, W. Heirman, A. Jaleel, and L. Eeckhout. Fairness-aware scheduling on single-ISA heterogeneous multi-cores. In Proceedings of the 22nd international conference on Parallel Architectures and Compilation Techniques (PACT), 2013.

Digital Library

[22]

K. Van Craeynest, A. Jaleel, L. Eeckhout, P. Narvaez, and J. Emer. Scheduling heterogeneous multi-cores through performance impact estimation (PIE). In Proceedings of the 39th annual International Symposium on Computer Architecture (ISCA), 2012.

Digital Library

Cited By

Du HQin YChen SKang Y(2024)FASA-DRAM: Reducing DRAM Latency with Destructive Activation and Delayed RestorationACM Transactions on Architecture and Code Optimization10.1145/364945521:2(1-27)Online publication date: 21-May-2024
https://dl.acm.org/doi/10.1145/3649455
Sang QYan JXie RHu CSuo KCheng D(2024)QoS-Aware Power Management via Scheduling and Governing Co-Optimization on Mobile DevicesIEEE Transactions on Mobile Computing10.1109/TMC.2024.343826723:12(13654-13669)Online publication date: Dec-2024
https://doi.org/10.1109/TMC.2024.3438267
Guo XCharles JNarendra NKlimeck GKubis T(2024)General resource manager for computationally demanding scientific software (MARE)Engineering with Computers10.1007/s00366-023-01890-z40:3(1927-1942)Online publication date: 1-Jun-2024
https://dl.acm.org/doi/10.1007/s00366-023-01890-z
Show More Cited By

Fairness-oriented OS Scheduling Support for Multicore Systems
1. Software and its engineering
  1. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Process management

Recommendations

Leveraging Core Specialization via OS Scheduling to Improve Performance on Asymmetric Multicore Systems

Asymmetric multicore processors (AMPs) consist of cores with the same ISA (instruction-set architecture), but different microarchitectural features, speed, and power consumption. Because cores with more complex features and higher speed typically use ...
Towards completely fair scheduling on asymmetric single-ISA multicore processors

Single-ISA asymmetric multicore processors (AMPs), which combine high-performance big cores with low-power small cores, were shown to deliver higher performance per watt than symmetric CMPs (Chip Multi-Processors). Previous work has highlighted that ...
A comprehensive scheduler for asymmetric multicore systems
EuroSys '10: Proceedings of the 5th European conference on Computer systems

Symmetric-ISA (instruction set architecture) asymmetric-performance multicore processors were shown to deliver higher performance per watt and area for applications with diverse architectural requirements, and so it is likely that future multicore ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

ICS '16: Proceedings of the 2016 International Conference on Supercomputing

June 2016

547 pages

ISBN:9781450343619

DOI:10.1145/2925426

Copyright © 2016 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

SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 2016

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed limited

Conference

ICS '16

Sponsor:

SIGARCH

ICS '16: 2016 International Conference on Supercomputing

June 1 - 3, 2016

Istanbul, Turkey

Acceptance Rates

Overall Acceptance Rate 629 of 2,180 submissions, 29%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
214
Total Downloads

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

Reflects downloads up to 09 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Du HQin YChen SKang Y(2024)FASA-DRAM: Reducing DRAM Latency with Destructive Activation and Delayed RestorationACM Transactions on Architecture and Code Optimization10.1145/364945521:2(1-27)Online publication date: 21-May-2024
https://dl.acm.org/doi/10.1145/3649455
Sang QYan JXie RHu CSuo KCheng D(2024)QoS-Aware Power Management via Scheduling and Governing Co-Optimization on Mobile DevicesIEEE Transactions on Mobile Computing10.1109/TMC.2024.343826723:12(13654-13669)Online publication date: Dec-2024
https://doi.org/10.1109/TMC.2024.3438267
Guo XCharles JNarendra NKlimeck GKubis T(2024)General resource manager for computationally demanding scientific software (MARE)Engineering with Computers10.1007/s00366-023-01890-z40:3(1927-1942)Online publication date: 1-Jun-2024
https://dl.acm.org/doi/10.1007/s00366-023-01890-z
Fang JKong HYang HXu YCai M(2022)A Heterogeneity-Aware Replacement Policy for the Partitioned Cache on Asymmetric Multi-Core ArchitecturesMicromachines10.3390/mi1311201413:11(2014)Online publication date: 18-Nov-2022
https://doi.org/10.3390/mi13112014
Yu TZhong RJanjic VPetoumenos PZhai JLeather HThomson J(2021)Collaborative Heterogeneity-Aware OS Scheduler for Asymmetric Multicore ProcessorsIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2020.304527932:5(1224-1237)Online publication date: 1-May-2021
https://doi.org/10.1109/TPDS.2020.3045279
Yu TPetoumenos PJanjic VLeather HThomson JMars JTang LXue JWu P(2020)COLAB: a collaborative multi-factor scheduler for asymmetric multicore processorsProceedings of the 18th ACM/IEEE International Symposium on Code Generation and Optimization10.1145/3368826.3377915(268-279)Online publication date: 22-Feb-2020
https://dl.acm.org/doi/10.1145/3368826.3377915
Salami BNoori HNaghibzadeh M(2020)Fairness-Aware Energy Efficient Scheduling on Heterogeneous Multi-Core ProcessorsIEEE Transactions on Computers10.1109/TC.2020.2984607(1-1)Online publication date: 2020
https://doi.org/10.1109/TC.2020.2984607
Durbhakula M(2019)OS Scheduling Algorithms for Memory Intensive Workloads in Multi-socket Multi-core ServersIntelligent Computing10.1007/978-3-030-22871-2_18(243-253)Online publication date: 23-Jun-2019
https://doi.org/10.1007/978-3-030-22871-2_18
Durbhakula M(2019)OS Scheduling Algorithms for Improving the Performance of Multithreaded WorkloadsIntelligent Computing10.1007/978-3-030-22871-2_15(194-208)Online publication date: 23-Jun-2019
https://doi.org/10.1007/978-3-030-22871-2_15
Garcia-Garcia ASaez JPrieto-Matias M(2018)Contention-Aware Fair Scheduling for Asymmetric Single-ISA Multicore SystemsIEEE Transactions on Computers10.1109/TC.2018.283641867:12(1703-1719)Online publication date: 1-Dec-2018
https://doi.org/10.1109/TC.2018.2836418

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.

Figures

Tables

Media

View Table of Conten