Paper Info
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.
Year
DOI
Venue
2017
10.1109/TCAD.2016.2618880
IEEE Trans. on CAD of Integrated Circuits and Systems
Keywords
Field
DocType
Integrated circuits,Resource management,Greedy algorithms,Scheduling,Dynamic programming,Throughput,Processor scheduling
Fixed-priority pre-emptive scheduling,Optimal substructure,Mathematical optimization,Fair-share scheduling,Computer science,Greedy algorithm,Real-time computing,Least slack time scheduling,Rate-monotonic scheduling,Greedy randomized adaptive search procedure,Dynamic priority scheduling
Journal
Volume
Issue
ISSN
36
6
0278-0070
Citations 
PageRank 
References 
3
0.36
14
Authors
5
Name
Order
Citations
PageRank
Anuj Pathania118114.97
Vanchinathan Venkataramani2765.85
Muhammad Shafique31945157.67
Tulika Mitra42714135.99
J. Henkel54471366.50