Optimal Greedy Algorithm for Many-Core Scheduling

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

Research output: Contribution to journalArticlepeer-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 languageEnglish (US)
Article number7593220
Pages (from-to)1054-1058
Number of pages5
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Volume36
Issue number6
DOIs
StatePublished - 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

Fingerprint Dive into the research topics of 'Optimal Greedy Algorithm for Many-Core Scheduling'. Together they form a unique fingerprint.

Cite this