Performant, Multi-Objective Scheduling of Highly Interleaved Task Graphs on Heterogeneous System on Chip Devices

Joshua Mack, Samet E. Arda, Umit Y. Ogras, Ali Akoglu

Research output: Contribution to journalArticlepeer-review


Performance-, power-, and energy-aware scheduling techniques play an essential role in optimally utilizing processing elements (PEs) of heterogeneous systems. List schedulers, a class of low-complexity static schedulers, have commonly been used in static execution scenarios. However, list schedulers are not suitable for runtime decision making, particularly when multiple concurrent applications are interleaved dynamically. For such cases, the static task execution times and expectation of idle PEs assumed by list schedulers lead to inefficient system utilization and poor performance. To address this problem, we present techniques for optimizing execution of list scheduling algorithms in dynamic runtime scenarios via a family of algorithms inspired by the well-known heterogeneous earliest finish time (HEFT) list scheduler. Through dynamically arriving, realistic workload scenarios that are simulated in an open-source discrete event heterogeneous SoC simulator, we exhaustively evaluate each of the proposed algorithms across two SoCs modeled after the Xilinx Zynq Ultrascale+ ZCU102 and O-Droid XU3 development boards. Altogether, depending on the chosen variant in this family of algorithms, we are able to achieve an up to 39% execution time improvement, up to 7.24x algorithmic speedup, or up to 30% energy consumption improvement compared to the baseline HEFT implementation.

Original languageEnglish (US)
Pages (from-to)2148-2162
Number of pages15
JournalIEEE Transactions on Parallel and Distributed Systems
Issue number9
StatePublished - Sep 1 2022
Externally publishedYes


  • HEFT
  • Scheduling and task partitioning
  • energy-aware systems
  • hardware simulation
  • heterogeneous (hybrid) systems

ASJC Scopus subject areas

  • Signal Processing
  • Hardware and Architecture
  • Computational Theory and Mathematics


Dive into the research topics of 'Performant, Multi-Objective Scheduling of Highly Interleaved Task Graphs on Heterogeneous System on Chip Devices'. Together they form a unique fingerprint.

Cite this