franklinqin0/multi-rate-dag

Code for the paper "Latency-Aware Generation of Single-Rate DAGs from Multi-Rate Task Sets" (RTAS 2020)

Latency-Aware Generation of Single-Rate DAGs from Multi-Rate Task Sets

This is the official repository for the paper "Latency-Aware Generation of Single-Rate DAGs from Multi-Rate Task Sets", by Micaela Verucchi, Mirco Theile, Marco Caccamo and Marko Bertogna (in proceeding RTAS 2020).
Contact: Micaela Verucchi, [email protected].

Abstract

This is an implementation of a conversion from a multi-rate DAG to a single rate DAG that meet given requirements on scheduling and end-to-end latency.

Input

The input is a task set , modeling an application composed of N periodic tasks arriving at time t=0. Each task is described by the tuple , where:

• is the Worst Case Execution Time (WCET) of the task;
• is the Best Case Execution Time (BCET);
• is the period;
• represents the relative deadline.

The exchange of data between two tasks is modeled with as data edge, a directed edge between the producer and the consumer of the data.

To constrain the latency of data propagation in task-chains, upper bounds on data age and on reaction time can be given, as well as maximum number of cores available.

Output

The output is a single-rate Directed Acyclic Graph (DAG). In this model, the full application is represented as directed acyclic graphs, with a unique source vertex and a unique sink vertex. Each vertex represents a task instance (job), while edges represent precedence constraints between jobs. In detail, the DAG is specified by a 3-tuple (V,E,HP) where:

• V represents the set of nodes, namely the jobs of the tasks of , and n = |V|;
• E is the set of edges describing job-level precedence constraints;
• HP is the period of the DAG, namely the hyper-period of the tasks involved: .

In this model, the communication between jobs utilizes buffers in shared memory, which can be accessed by all the cores. The time to write/read a shared buffer is included in the execution time of each task. We adopt the implicit communication model defined in AUTOSAR, solving mutual exclusion via double-buffering. Each task complies with a read-execute-write semantic, i.e., it reads a private copy before the execution, and it writes a private copy at the end of the execution

How to build the project

git clone https://github.com/mive93/multi-rate-DAG
cd multi-rate-DAG
mkdir build
cd build
cmake ../src
./main