Scalable analysis for multi-scale dataflow models

H. Alizadeh Ara, A. Behrouzian, M. Hendriks, M. Geilen, D. Goswami, T. Basten

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

5 Citaten (Scopus)
33 Downloads (Pure)

Samenvatting

Multi-scale dataflow models have actors acting at multiple granularity levels, e.g., a dataflow model of a video processing application with operations on frame, line, and pixel level. The state of the art timing analysis methods for both static and dynamic dataflow types aggregate the behaviours across all granularity levels into one, often large iteration, which is repeated without exploiting the structure within such an iteration. This poses scalability issues to dataflow analysis, because behaviour of the large iteration is analysed by some form of simulation that involves a large number of actor firings. We take a fresh perspective of what is happening inside the large iteration. We take advantage of the fact that the iteration is a sequence of smaller behaviours, each captured in a scenario, that are typically repeated many times. We use the (max ,+) linear model of dataflow to represent each of the scenarios with a matrix. This allows a compositional worst-case throughput analysis of the repeated scenarios by raising the matrices to the power of the number of repetitions, which scales logarithmically with the number of repetitions, whereas the existing throughput analysis scales linearly. We moreover provide the first exact worst-case latency analysis for scenario-aware dataflow. This compositional latency analysis also scales logarithmically when applied to multi-scale dataflow models. We apply our new throughput and latency analysis to several realistic applications. The results confirm that our approach provides a fast and accurate analysis.
Originele taal-2Engels
Artikelnummer80
Aantal pagina's26
TijdschriftACM Transactions on Embedded Computing Systems
Volume17
Nummer van het tijdschrift4
DOI's
StatusGepubliceerd - aug 2018

Vingerafdruk Duik in de onderzoeksthema's van 'Scalable analysis for multi-scale dataflow models'. Samen vormen ze een unieke vingerafdruk.

  • Citeer dit