Record link: 
http://hdl.handle.net/20.500.12708/147506
-
Title: 
Optimal Greedy Algorithm for Many-Core Scheduling
-
Citation: 
Pathania, A., Venkataramani, V., Shafique, M., Mitra, T., & Henkel, J. (2017). Optimal Greedy Algorithm for Many-Core Scheduling. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 36(6), 1054–1058. https://doi.org/10.1109/tcad.2016.2618880
-
Publisher DOI: 
10.1109/tcad.2016.2618880
-
Publication Type: 
Article - Original Research Article
en
Language: 
English
-
Authors: 
Pathania, Anuj 
Venkataramani, Vanchinathan 
Shafique, Muhammad 
Mitra, Tulika 
Henkel, Jörg 
-
Organisational Unit: 
E191-02 - Forschungsbereich Embedded Computing Systems 
-
Journal: 
IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 
-
ISSN: 
0278-0070
-
Date (published): 
Jun-2017
-
Number of Pages: 
5
-
Publisher: 
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
-
Peer reviewed: 
Yes
-
Keywords: 
Electrical and Electronic Engineering; Software; Computer Graphics and Computer-Aided Design; scheduling; Greedy algorithm; many-cores; throughput maximization
-
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 10000× to provide near-optimal solutions.
en
Research Areas: 
Computer Engineering and Software-Intensive Systems: 100%
-
Science Branch: 
Informatik
-
Appears in Collections:
Article

Show full item record

Page view(s)

119
checked on Nov 23, 2023

Google ScholarTM

Check