Title

A Runtime Job Scheduling Algorithm for Cluster Architectures with Dataflow Accelerators

Abstract

This article discusses specialized computer cluster architectures for high performance computing that include both control-flow and DataFlow components, as well as their runtime scheduling algorithms. A novel optimal scheduling algorithm for such architectures is proposed. The proposed algorithm is general, but is limited in some cases due to its time complexity. From the base optimal algorithm, two additional heuristic algorithms are derived, and then compared to other schedulers. These heuristic algorithms produce near-optimal schedules for both DataFlow hardware jobs and control-flow jobs at large job counts, with negligible scheduling penalty. Compared to an optimal scheduler, the performance gain decreases slightly as job count increases. This research illustrates that the performance of existing cluster structures can be considerably improved by adding appropriate DataFlow accelerators and a proper scheduling algorithm, while at the same time decreasing the system transistor count and power consumption.

Department(s)

Electrical and Computer Engineering

Publication Status

In Press, Corrected Proof

Comments

Available online 23 February 2022

National Science Foundation, Grant III44006

Keywords and Phrases

Accelerating Execution; Computing Cluster; DataFlow Hardware; High Performance Computing; Job Scheduling

International Standard Serial Number (ISSN)

0065-2458

Document Type

Article - Journal

Document Version

Citation

File Type

text

Language(s)

English

Rights

© 2022 Elsevier, All rights reserved.

Publication Date

23 Feb 2022

Share

 
COinS