Bibliographic Details
| Title: |
Optimal Greedy Algorithm for Many-Core Scheduling. |
| Authors: |
Pathania, Anuj1, Venkatramani, Vanchinathan2, Shafique, Muhammad3, Mitra, Tulika2, Henkel, Jorg1 |
| Source: |
IEEE Transactions on Computer-Aided Design of Integrated Circuits & Systems. Jun2017, Vol. 36 Issue 6, p1054-1058. 5p. |
| Subjects: |
Greedy algorithms, Dynamic programming, Integrated circuits, Computer scheduling, Resource management |
| 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. [ABSTRACT FROM PUBLISHER] |
|
Copyright of IEEE Transactions on Computer-Aided Design of Integrated Circuits & Systems is the property of IEEE and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) |
| Database: |
Engineering Source |
