FPGA-based Minimal Latency HEFT Scheduler for Heterogeneous Computing

Ilkin Aliyev, Joshua Mack, Nirmal Kumbhare, Ali Akoglu, H. Fatih Ugurdag

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

This paper proposes a new hardware scheduler. As heterogeneous computing becomes prevalent, mapping applications on to multiple processing elements (PEs) proves to be nontrivial. Heterogeneous Earliest Finish Time (HEFT) algorithm is an already existing scheduler that aims to minimize the total execution time of an application. The paradigm of HEFT is such that it accepts an acyclic task graph as input at run-time and assigns/schedules the precompiled atomic tasks to PEs. HEFT stands out among many such schedulers not only in terms of producing shorter schedules but also in terms of its own short execution time. However, in real-time applications, the lower the latency, the better it is. To the best of our knowledge, this work is the only work that implements HEFT in hardware (on FPGA) further lowering its latency from milliseconds to as much as less than a microsecond. Porting HEFT to hardware has been challenging as data dependencies limit the amount of parallelism. Design of an efficient memory access pattern as well as an “incremental sorter” were key enablers in reducing the latency of the hardware implementation. We also integrated our FPGA-HEFT into an ARM-based SoC and validated its functionality using a realistic workload.

Original languageEnglish (US)
Title of host publicationProceedings - 6th International Conference on Computer Science and Engineering, UBMK 2021
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages244-248
Number of pages5
ISBN (Electronic)9781665429085
DOIs
StatePublished - 2021
Event6th International Conference on Computer Science and Engineering, UBMK 2021 - Ankara, Turkey
Duration: Sep 15 2021Sep 17 2021

Publication series

NameProceedings - 6th International Conference on Computer Science and Engineering, UBMK 2021

Conference

Conference6th International Conference on Computer Science and Engineering, UBMK 2021
Country/TerritoryTurkey
CityAnkara
Period9/15/219/17/21

Keywords

  • DSSoC
  • Hardware scheduler
  • Heterogeneous computing
  • Task scheduling

ASJC Scopus subject areas

  • Artificial Intelligence
  • Computer Networks and Communications
  • Hardware and Architecture
  • Information Systems
  • Information Systems and Management
  • Safety, Risk, Reliability and Quality
  • Health Informatics

Fingerprint

Dive into the research topics of 'FPGA-based Minimal Latency HEFT Scheduler for Heterogeneous Computing'. Together they form a unique fingerprint.

Cite this