Title
Scalable analysis for multi-scale dataflow models
Author
Ara, H.A.
Behrouzian, A.
Hendriks, M.
Geilen, M.
Goswami, D.
Basten, T.
Publication year
2018
Abstract
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. © 2018 ACM.
Subject
(MAX +)
Dataflow
Latency
Scalable analysis
Scenarios
Throughput
Iterative methods
Matrix algebra
Throughput
Video signal processing
(MAX Dataflow
Latency
Scalable analysis
Scenarios
Data flow analysis
To reference this document use:
http://resolver.tudelft.nl/uuid:ec419425-407e-4205-9ffe-11219f3a660f
TNO identifier
842628
Publisher
Association for Computing Machinery
ISSN
1539-9087
Source
ACM Transactions on Embedded Computing Systems, 17 (4)
Article number
80
Document type
article