Distributed fair scheduling for many-cores

Anuj Pathania; Vanchinathan Venkataramani; Muhammad Shafique; Tulika Mitra; Jörg Henkel

doi:10.3850/9783981537079_0286

Distributed fair scheduling for many-cores

Anuj Pathania, Vanchinathan Venkataramani, Muhammad Shafique, Tulika Mitra, Jörg Henkel

Electrical Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

Transition of embedded processors from multi-cores to many-cores continues unabated. Many-cores execute tens of tasks in parallel and in some contexts, it is crucial that the processing cores are distributed fairly amongst the tasks. Traditional queue-based centralized fair schedulers designed for multi-cores will have excessive overhead on many-cores due to the enlarged optimization search-space. Further, the processing requirements of executing tasks may vary under different phases of their execution necessitating lightweight dynamic fair schedulers to regularly perform partial reallocation of the cores. We introduce a distributed dynamic fair scheduler that can scale up with the increase in number of cores because it disburses the processing overhead of scheduling amongst all the cores. Based on observations made for task executions on many-cores, we propose an optimal solution under certain constraints for the fair scheduling problem, which in general is NP-Hard.

Original language	English (US)
Title of host publication	Proceedings of the 2016 Design, Automation and Test in Europe Conference and Exhibition, DATE 2016
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	379-384
Number of pages	6
ISBN (Electronic)	9783981537062
DOIs	https://doi.org/10.3850/9783981537079_0286
State	Published - Apr 25 2016
Event	19th Design, Automation and Test in Europe Conference and Exhibition, DATE 2016 - Dresden, Germany Duration: Mar 14 2016 → Mar 18 2016

Publication series

Name	Proceedings of the 2016 Design, Automation and Test in Europe Conference and Exhibition, DATE 2016

Other

Other	19th Design, Automation and Test in Europe Conference and Exhibition, DATE 2016
Country/Territory	Germany
City	Dresden
Period	3/14/16 → 3/18/16

ASJC Scopus subject areas

Hardware and Architecture
Safety, Risk, Reliability and Quality

Access to Document

10.3850/9783981537079_0286

Cite this

Pathania, A., Venkataramani, V., Shafique, M., Mitra, T., & Henkel, J. (2016). Distributed fair scheduling for many-cores. In Proceedings of the 2016 Design, Automation and Test in Europe Conference and Exhibition, DATE 2016 (pp. 379-384). Article 7459340 (Proceedings of the 2016 Design, Automation and Test in Europe Conference and Exhibition, DATE 2016). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.3850/9783981537079_0286

Distributed fair scheduling for many-cores. / Pathania, Anuj; Venkataramani, Vanchinathan; Shafique, Muhammad et al.
Proceedings of the 2016 Design, Automation and Test in Europe Conference and Exhibition, DATE 2016. Institute of Electrical and Electronics Engineers Inc., 2016. p. 379-384 7459340 (Proceedings of the 2016 Design, Automation and Test in Europe Conference and Exhibition, DATE 2016).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Pathania, A, Venkataramani, V, Shafique, M, Mitra, T & Henkel, J 2016, Distributed fair scheduling for many-cores. in Proceedings of the 2016 Design, Automation and Test in Europe Conference and Exhibition, DATE 2016., 7459340, Proceedings of the 2016 Design, Automation and Test in Europe Conference and Exhibition, DATE 2016, Institute of Electrical and Electronics Engineers Inc., pp. 379-384, 19th Design, Automation and Test in Europe Conference and Exhibition, DATE 2016, Dresden, Germany, 3/14/16. https://doi.org/10.3850/9783981537079_0286

Pathania A, Venkataramani V, Shafique M, Mitra T, Henkel J. Distributed fair scheduling for many-cores. In Proceedings of the 2016 Design, Automation and Test in Europe Conference and Exhibition, DATE 2016. Institute of Electrical and Electronics Engineers Inc. 2016. p. 379-384. 7459340. (Proceedings of the 2016 Design, Automation and Test in Europe Conference and Exhibition, DATE 2016). doi: 10.3850/9783981537079_0286

Pathania, Anuj ; Venkataramani, Vanchinathan ; Shafique, Muhammad et al. / Distributed fair scheduling for many-cores. Proceedings of the 2016 Design, Automation and Test in Europe Conference and Exhibition, DATE 2016. Institute of Electrical and Electronics Engineers Inc., 2016. pp. 379-384 (Proceedings of the 2016 Design, Automation and Test in Europe Conference and Exhibition, DATE 2016).

@inproceedings{dcb92b76ef494318a01e3453ed39d9d3,

title = "Distributed fair scheduling for many-cores",

abstract = "Transition of embedded processors from multi-cores to many-cores continues unabated. Many-cores execute tens of tasks in parallel and in some contexts, it is crucial that the processing cores are distributed fairly amongst the tasks. Traditional queue-based centralized fair schedulers designed for multi-cores will have excessive overhead on many-cores due to the enlarged optimization search-space. Further, the processing requirements of executing tasks may vary under different phases of their execution necessitating lightweight dynamic fair schedulers to regularly perform partial reallocation of the cores. We introduce a distributed dynamic fair scheduler that can scale up with the increase in number of cores because it disburses the processing overhead of scheduling amongst all the cores. Based on observations made for task executions on many-cores, we propose an optimal solution under certain constraints for the fair scheduling problem, which in general is NP-Hard.",

author = "Anuj Pathania and Vanchinathan Venkataramani and Muhammad Shafique and Tulika Mitra and J{\"o}rg Henkel",

note = "Publisher Copyright: {\textcopyright} 2016 EDAA. Copyright: Copyright 2020 Elsevier B.V., All rights reserved.; 19th Design, Automation and Test in Europe Conference and Exhibition, DATE 2016 ; Conference date: 14-03-2016 Through 18-03-2016",

year = "2016",

month = apr,

day = "25",

doi = "10.3850/9783981537079_0286",

language = "English (US)",

series = "Proceedings of the 2016 Design, Automation and Test in Europe Conference and Exhibition, DATE 2016",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "379--384",

booktitle = "Proceedings of the 2016 Design, Automation and Test in Europe Conference and Exhibition, DATE 2016",

}

TY - GEN

T1 - Distributed fair scheduling for many-cores

AU - Pathania, Anuj

AU - Venkataramani, Vanchinathan

AU - Shafique, Muhammad

AU - Mitra, Tulika

AU - Henkel, Jörg

PY - 2016/4/25

Y1 - 2016/4/25

N2 - Transition of embedded processors from multi-cores to many-cores continues unabated. Many-cores execute tens of tasks in parallel and in some contexts, it is crucial that the processing cores are distributed fairly amongst the tasks. Traditional queue-based centralized fair schedulers designed for multi-cores will have excessive overhead on many-cores due to the enlarged optimization search-space. Further, the processing requirements of executing tasks may vary under different phases of their execution necessitating lightweight dynamic fair schedulers to regularly perform partial reallocation of the cores. We introduce a distributed dynamic fair scheduler that can scale up with the increase in number of cores because it disburses the processing overhead of scheduling amongst all the cores. Based on observations made for task executions on many-cores, we propose an optimal solution under certain constraints for the fair scheduling problem, which in general is NP-Hard.

AB - Transition of embedded processors from multi-cores to many-cores continues unabated. Many-cores execute tens of tasks in parallel and in some contexts, it is crucial that the processing cores are distributed fairly amongst the tasks. Traditional queue-based centralized fair schedulers designed for multi-cores will have excessive overhead on many-cores due to the enlarged optimization search-space. Further, the processing requirements of executing tasks may vary under different phases of their execution necessitating lightweight dynamic fair schedulers to regularly perform partial reallocation of the cores. We introduce a distributed dynamic fair scheduler that can scale up with the increase in number of cores because it disburses the processing overhead of scheduling amongst all the cores. Based on observations made for task executions on many-cores, we propose an optimal solution under certain constraints for the fair scheduling problem, which in general is NP-Hard.

UR - http://www.scopus.com/inward/record.url?scp=84973665106&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84973665106&partnerID=8YFLogxK

U2 - 10.3850/9783981537079_0286

DO - 10.3850/9783981537079_0286

M3 - Conference contribution

AN - SCOPUS:84973665106

T3 - Proceedings of the 2016 Design, Automation and Test in Europe Conference and Exhibition, DATE 2016

SP - 379

EP - 384

BT - Proceedings of the 2016 Design, Automation and Test in Europe Conference and Exhibition, DATE 2016

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 19th Design, Automation and Test in Europe Conference and Exhibition, DATE 2016

Y2 - 14 March 2016 through 18 March 2016

ER -

Distributed fair scheduling for many-cores

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this