Reducing the Complexity of Dataflow Graphs using Slack-based Merging

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F17%3A00243311" target="_blank" >RIV/68407700:21230/17:00243311 - isvavai.cz</a>

Result on the web

<a href="http://dx.doi.org/10.1145/2956232" target="_blank" >http://dx.doi.org/10.1145/2956232</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1145/2956232" target="_blank" >10.1145/2956232</a>

Result language

angličtina

Original language name

Reducing the Complexity of Dataflow Graphs using Slack-based Merging

Original language description

There exist many dataflow applications with timing constraints that require real-time guarantees on safe execution without violating their deadlines. Extraction of timing parameters (offsets, deadlines, periods) from these applications enables the use of real-time scheduling and analysis techniques, and provides guarantees on satisfying timing constraints. However, existing extraction techniques require the transformation of the dataflow application from highly expressive dataflow computational models, for example, Synchronous Dataflow (SDF) and Cyclo-Static Dataflow (CSDF) to Homogeneous Synchronous Dataflow (HSDF). This transformation can lead to an exponential increase in the size of the application graph that significantly increases the runtime of the analysis. In this article, we address this problem by proposing an offline heuristic algorithm called slack-based merging. The algorithm is a novel graph reduction technique that helps in speeding up the process of timing parameter extraction and finding a feasible real-time schedule, thereby reducing the overall design time of the real-time system. It uses two main concepts: (a) the difference between the worst-case execution time of the SDF graph's firings and its timing constraints (slack) to merge firings together and generate a reducedsize HSDF graph, and (b) the novel concept of merging called safe merge, which is a merge operation that we formally prove cannot cause a live HSDF graph to deadlock.

Czech name

—

Czech description

—

Type

J_imp - Article in a specialist periodical, which is included in the Web of Science database

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

<a href="/en/project/EE2.3.30.0034" target="_blank" >EE2.3.30.0034: Support of inter-sectoral mobility and quality enhancement of research teams at Czech Technical University in Prague</a><br>

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year

2017

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Name of the periodical

ACM Transactions on Design Automation of Electronic Systems

ISSN

1084-4309

e-ISSN

1557-7309

Volume of the periodical

22

Issue of the periodical within the volume

2

Country of publishing house

US - UNITED STATES

Number of pages

22

Pages from-to

—

UT code for WoS article

000399120800005

EID of the result in the Scopus database

2-s2.0-85011411549