Optimal Greedy Algorithm for Many-Core Scheduling

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

doi:10.1109/TCAD.2016.2618880

Optimal Greedy Algorithm for Many-Core Scheduling

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

Electrical Engineering

Research output: Contribution to journal › Article › peer-review

Abstract

In this paper, we propose an optimal greedy algorithm for the problem of run-time many-core scheduling. The previously best known centralized optimal algorithm proposed for the problem is based on dynamic programming. A dynamic programming-based scheduler has high overheads which grow fast with increase in both the number of cores in the many-cores as well as number of tasks independently executing on them. We show in this paper that the inherent concavity of extractable instructions per cycle in tasks with increase in number of allocated cores allows for an alternative greedy algorithm. The proposed algorithm significantly reduces the run-time scheduling overheads, while maintaining theoretical optimality. In practice, it reduces the problem solving time 10 000x to provide near-optimal solutions.

Original language	English (US)
Article number	7593220
Pages (from-to)	1054-1058
Number of pages	5
Journal	IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Volume	36
Issue number	6
DOIs	https://doi.org/10.1109/TCAD.2016.2618880
State	Published - Jun 2017

Keywords

Greedy algorithm
many-cores
scheduling
throughput maximization

ASJC Scopus subject areas

Software
Computer Graphics and Computer-Aided Design
Electrical and Electronic Engineering

Access to Document

10.1109/TCAD.2016.2618880

Cite this

@article{e24526d6a2174ead94f44967522a1d6b,

title = "Optimal Greedy Algorithm for Many-Core Scheduling",

abstract = "In this paper, we propose an optimal greedy algorithm for the problem of run-time many-core scheduling. The previously best known centralized optimal algorithm proposed for the problem is based on dynamic programming. A dynamic programming-based scheduler has high overheads which grow fast with increase in both the number of cores in the many-cores as well as number of tasks independently executing on them. We show in this paper that the inherent concavity of extractable instructions per cycle in tasks with increase in number of allocated cores allows for an alternative greedy algorithm. The proposed algorithm significantly reduces the run-time scheduling overheads, while maintaining theoretical optimality. In practice, it reduces the problem solving time 10 000x to provide near-optimal solutions.",

keywords = "Greedy algorithm, many-cores, scheduling, throughput maximization",

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

year = "2017",

month = jun,

doi = "10.1109/TCAD.2016.2618880",

language = "English (US)",

volume = "36",

pages = "1054--1058",

journal = "IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems",

issn = "0278-0070",

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

number = "6",

}

TY - JOUR

T1 - Optimal Greedy Algorithm for Many-Core Scheduling

AU - Pathania, Anuj

AU - Venkatramani, Vanchinathan

AU - Shafique, Muhammad

AU - Mitra, Tulika

AU - Henkel, Jörg

PY - 2017/6

Y1 - 2017/6

N2 - In this paper, we propose an optimal greedy algorithm for the problem of run-time many-core scheduling. The previously best known centralized optimal algorithm proposed for the problem is based on dynamic programming. A dynamic programming-based scheduler has high overheads which grow fast with increase in both the number of cores in the many-cores as well as number of tasks independently executing on them. We show in this paper that the inherent concavity of extractable instructions per cycle in tasks with increase in number of allocated cores allows for an alternative greedy algorithm. The proposed algorithm significantly reduces the run-time scheduling overheads, while maintaining theoretical optimality. In practice, it reduces the problem solving time 10 000x to provide near-optimal solutions.

AB - In this paper, we propose an optimal greedy algorithm for the problem of run-time many-core scheduling. The previously best known centralized optimal algorithm proposed for the problem is based on dynamic programming. A dynamic programming-based scheduler has high overheads which grow fast with increase in both the number of cores in the many-cores as well as number of tasks independently executing on them. We show in this paper that the inherent concavity of extractable instructions per cycle in tasks with increase in number of allocated cores allows for an alternative greedy algorithm. The proposed algorithm significantly reduces the run-time scheduling overheads, while maintaining theoretical optimality. In practice, it reduces the problem solving time 10 000x to provide near-optimal solutions.

KW - Greedy algorithm

KW - many-cores

KW - scheduling

KW - throughput maximization

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

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

U2 - 10.1109/TCAD.2016.2618880

DO - 10.1109/TCAD.2016.2618880

M3 - Article

AN - SCOPUS:85019973401

SN - 0278-0070

VL - 36

SP - 1054

EP - 1058

JO - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

JF - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

IS - 6

M1 - 7593220

ER -

Optimal Greedy Algorithm for Many-Core Scheduling

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this