Bruno Bodin
Youen Lesparre
ABSTRACT
Dataflow modeling is a highly regarded method for the design of embedded systems. Measuring the performance of the associated analysis and compilation tools requires an efficient dataflow graph generator. This paper presents a new graph generator for Phased Computation Graphs (PCG), which augment Cyclo-Static Dataflow Graphs with both initial phases and thresholds.
A sufficient condition of liveness is first extended to the PCG model. The determination of initial conditions minimizing the total amount of initial data in the channels and ensuring liveness can then be expressed using Integer Linear Programming. This contribution and other improvements of previous works are incorporated in Turbine, a new dataflow graph generator. Its effectiveness is demonstrated experimentally by comparing it to two existing generators, DFTools and SDF3.
- www.tilera.com.Google Scholar
- M. A. Bamakhrama, J. T. Zhai, H. Nikolov, and T. Stefanov. A methodology for automated design of hard-real-time embedded streaming systems. In Design, Automation & Test in Europe (DATE'12), pages 941--946, Mar. 2012. Google ScholarDigital Library
- M. Benazouz, O. Marchetti, A. Munier-Kordon, and T. Michel. A new method for minimizing buffer sizes for cyclo-static dataflow graphs. In 8th IEEE Workshop on Embedded Systems for Real-Time Multimedia (ESTIMedia'10), pages 11--20, 2010.Google ScholarCross Ref
- M. Benazouz, A. Munier-Kordon, T. Hujsa, and B. Bodin. Liveness Evaluation of a Cyclo-Static DataFlow Graph. In Design Automation Conference (DAC'13), pages 3--7, 2013. Google ScholarDigital Library
- G. Bilsen, M. Engels, R. Lauwereins, and J. A. Peperstraete. Cyclo-static data flow. IEEE Transactions on Signal Processing, pages 3255--3258, 1995. Google ScholarDigital Library
- B. Bodin, A. Munier-Kordon, and B. Dupont de Dinechin. Periodic Schedules for Cyclo-Static Dataflow. In 11th IEEE Workshop on Embedded Systems for Real-Time Multimedia (ESTIMedia'13), pages 105--114, 2013.Google Scholar
- T. Goubier, R. Sirdey, S. Louise, and V. David. ∑C: A programming model and language for embedded manycores. 11th International Conference on Algorithms and Architectures for Parallel Processing (ICA3PP'11), pages 385--394, 2011. Google ScholarDigital Library
- Kalray. Manycore processors for embedded computing. www.kalray.eu.Google Scholar
- R. M. Karp and R. E. Miller. Properties of a model for parallel computations: Determinacy, termination, queueing. SIAM Journal on Applied Mathematics, 14(6):1390--1411, 1966.Google ScholarDigital Library
- E. A. Lee and D. G. Messerschmitt. Synchronous dataflow. Proceedings of the IEEE, 75(9):1235--1245, 1987.Google ScholarCross Ref
- O. Marchetti and A. Munier-Kordon. A sufficient condition for the liveness of weighted event graphs. European Journal of Operational Research, 197(2):532--540, Sept. 2009.Google ScholarCross Ref
- H. Oh and S. Ha. Efficient code synthesis from extended dataflow graphs for multimedia applications. In Design Automation Conference (DAC '02), pages 275--280, 2002. Google ScholarDigital Library
- M. Pelcat, J. Piat, M. Wipliez, S. Aridhi, and J.-F. Nezan. An Open Framework for Rapid Prototyping of Signal Processing Applications. EURASIP Journal on Embedded Systems, pages 1--13, 2009. Google ScholarDigital Library
- R. Read. A survey of graph generation techniques. Combinatorial Mathematics VIII, pages 77--89, 1981.Google ScholarCross Ref
- F. Siyoum, M. Geilen, O. Moreira, and H. Corporaal. Worst-case throughput analysis of real-time dynamic streaming applications. 8th International Conference on Hardware/Software Codesign and System Synthesis (CODES+ISSS'12), pages 463--472, 2012. Google ScholarDigital Library
- S. Sriram and S. S. Bhattacharyya. Embedded multiprocessors: Scheduling and synchronization. CRC, second edition, 2009. Google ScholarDigital Library
- S. Stuijk, M. Geilen, and T. Basten. SDF3: SDF For Free. In 6th International Conference on Application of Concurrency to System Design (ACSD'06), pages 276--278, 2006. Google ScholarDigital Library
- W. Thies, M. Karczmarek, and S. Amarasinghe. StreamIt: A language for streaming applications. Compiler Construction, pages 179--196, 2002. Google ScholarDigital Library
- W. Thies, J. Lin, and S. Amarasinghe. Phased computation graphs in the polyhedral model. Technical Report LCS-TM-630, MIT Laboratory for Computer Science, 2002.Google Scholar
- M. H. Wiggers, M. J. Bekooij, P. G. Jansen, and G. J. Smit. Efficient Computation of Buffer Capacities for Cyclo-Static Real-Time Systems with Back-Pressure. 13th IEEE Real Time and Embedded Technology and Applications Symposium (RTAS'07), pages 281--292, Apr. 2007. Google ScholarDigital Library
- Y. Yang, M. Geilen, T. Basten, S. Stuijk, and H. Corporaal. Exploring Trade-offs between Performance and Resource Requirements for Synchronous Dataflow Graphs. In 7th IEEE Workshop on Embedded Systems for Real-Time Multimedia (ESTIMedia'09), pages 96--105, 2009.Google ScholarCross Ref
Index Terms
- Fast and efficient dataflow graph generation
Recommendations
Exhaustive Generation of k-Critical $${\mathcal H}$$-Free Graphs
WG 2016: Revised Selected Papers of the 42nd International Workshop on Graph-Theoretic Concepts in Computer Science - Volume 9941We describe an algorithm for generating all k-critical $${\mathcal H}$$-free graphs, based on a method of Hoíng et al. Using this algorithm, we prove that there are only finitely many 4-critical $$P_7,C_k$$-free graphs, for both $$k=4$$ and $$k=5$$. We ...
Exhaustive generation of k‐critical H‐free graphs
AbstractWe describe an algorithm for generating all k‐critical H‐free graphs, based on a method of Hoàng et al. A graph G is k‐critical H‐free if G is H‐free, k‐chromatic, and every H‐free proper subgraph of G is k−1‐colorable. Using this algorithm, we ...
Single-rate approximations of cyclo-static synchronous dataflow graphs
SCOPES '14: Proceedings of the 17th International Workshop on Software and Compilers for Embedded SystemsExact analysis of synchronous dataflow (sdf) graphs is often considered too costly, because of the expensive transformation of the graph into a single-rate equivalent. As an alternative, several authors have proposed approximate analyses. Existing ...
Comments