On Computing Exact WCRT for DAG Tasks | IEEE Conference Publication | IEEE Xplore

On Computing Exact WCRT for DAG Tasks


Abstract:

Most current real-time parallel applications can be modeled as a directed acyclic graph (DAG) task. Existing worst-case response time (WCRT) bounds (e.g., Graham's bound)...Show More

Abstract:

Most current real-time parallel applications can be modeled as a directed acyclic graph (DAG) task. Existing worst-case response time (WCRT) bounds (e.g., Graham's bound) derived for DAGs may be very pessimistic. No one precisely knows the gap between the WCRT bound and the actual WCRT. In this paper, we aim to derive the exact WCRT of a DAG task under the list scheduling upon multi-core platforms. We encode the WCRT analysis problem into a satisfaction modular theoretical (SMT) formulation based on insights into the list scheduling algorithm, and prove that our SMT program can solve the WCRT precisely, providing an accurate baseline to measure the tightness of the existing WCRT bounds. Experiments show that our method significantly improves the tightness of the WCRT bound, and is practically quite efficient, e.g., it can analyze DAGs with more than 40 vertices in a few seconds.
Date of Conference: 20-24 July 2020
Date Added to IEEE Xplore: 09 October 2020
ISBN Information:
Print on Demand(PoD) ISSN: 0738-100X
Conference Location: San Francisco, CA, USA

I. Introduction

Nowadays multi-cores are becoming mainstream hardware platforms for embedded and real-time systems. To fully utilize the processing capacity of multi-cores, software should be fully parallelized, i.e., not only inter-task parallelism, but also intra-task parallelism needs to be explored, such that an individual task (abstraction of a parallel program) is able to potentially utilize more than one core at the same time during its execution. Parallel tasks are commonly supported by almost all modern parallel programming languages, e.g., Cilk family, OpenMP and Intel's Thread Building Blocks. The primitives in these languages and libraries, such as parallel for, omp task and spawn/sync, result in intra-task parallelism structures that can be well represented via Directed Acyclic Graph (DAG) task models, which have gained much attention in the past few years [1]-[27].

References

References is not available for this document.