hDAGs: A Directed Acyclic Graph Representation for Scheduling Tasks on Heterogeneous Hardware

Abstract

The past decade has seen a variety of novel computational accelerators and disruptive memory systems, providing, e.g., in-memory or tensor processing capabilities. Executing tasks and placing data on these can drastically improve application performance, but only when done right - otherwise, performance may also degrade. Even when leaving the algorithmic part aside, this is challenging: data layout and task structure affect optimal placement, but placement decisions also affect the required data layout and task structure. Crucially, today's de facto standard of expressing high-performance computing workloads as directed acyclic graphs (DAGs) assumes a static application structure, and is therefore unsuitable for such devices. This paper proposes hDAGs, a workload definition method that is capable of expressing accelerator-specific, placement-dependent sub-structures within applications, thus addressing the aforementioned challenge. We show that hDAG-based placement can reduce application latency by up to 38 % compared to existing approaches, while also improving simulation-based latency prediction by up 61%. The performance of real-world applications can be improved by a factor of 1.20x even with simple scheduler adjustments. At the same time, hDAGs are backwards-compatible with existing scheduling strategies, and thus do not require placement algorithms to be re-designed from scratch.