Article

Back to basics: Homogeneous representations of multi-rate synchronous dataflow graphs

MEMOCODE '13: Proceedings of the Eleventh ACM/IEEE International Conference on Formal Methods and Models for Codesign

Pages 35 - 46

Published: 01 October 2013 Publication History

Abstract

Exact temporal analyses of multi-rate synchronous dataflow (MRSDF) graphs, such as computing the maximum achievable throughput, or sufficient buffer sizes required to reach a minimum throughput, require a homogeneous representation called a homogeneous synchronous dataflow (HSDF) graph. The size of such an HSDF graph may, in the worst case, be exponential in the size of the MRSDF graph. In this paper, we revisit the transformation from MRSDF to HSDF, and show how this transformation may be done either exactly or approximately. The approximate transformation gives both an optimistic and a pessimistic HSDF graph, each of which has the same size as the MRSDF graph. We furthermore show how strict lower and upper bounds on throughput, or on the buffer sizes required to reach a minimum throughput, may be obtained from these approximating graphs.

References

[1]

E. Lee and D. Messerschmitt, "Synchronous data flow," Proceedings of the IEEE, vol. 75, no. 9, pp. 1235-1245, 1987.

[2]

S. Sriram and S. S. Bhattacharyya, Embedded multiprocessors: Scheduling and synchronization. CRC press, 2009.

Digital Library

[3]

A. H. Ghamarian, M. C. W. Geilen, S. Stuijk, T. Basten, A. J. M. Moonen, M. Bekooij, B. Theelen, and M. Mousavi, "Throughput analysis of synchronous data flow graphs," in Proceedings of the 6th International Conference on Application of Concurrency to System Design (ACSD). IEEE Computer Society Press, Los Alamitos, CA, USA, Jun. 2006, pp. 25-36.

Digital Library

[4]

J. P. Hausmans, S. J. Geuns, M. H. Wiggers, and M. J. Bekooij, "Compositional temporal analysis model for incremental hard real-time system design," in Proceedings of the tenth ACM international conference on Embedded software - EMSOFT '12. New York, New York, USA: ACM Press, Oct. 2012, p. 185.

Digital Library

[5]

M. H. Wiggers, "Aperiodic Multiprocessor Scheduling for Real-Time Stream Processing Applications," Ph.D. dissertation, University of Twente, Enschede, The Netherlands, Jun. 2009.

[6]

S. Stuijk, M. C. W. Geilen, and T. Basten, "SDF³: SDF For Free," in Proceedings on the 6th International Conference on Application of Concurrency to System Design (ACSD). IEEE Computer Society Press, Los Alamitos, CA, USA, Jun. 2006, pp. 276-278.

Digital Library

[7]

O. Marchetti and A. Munier-Kordon, "Complexity results for Weighted Timed Event Graphs," Discrete Optimization, vol. 7, no. 3, pp. 166-180, Aug. 2010.

Digital Library

[8]

G. Cohen, S. Gaubert, and J. Quadrat, "Timed-event graphs with multipliers and homogeneous min-plus systems," IEEE Transactions on Automatic Control, vol. 43, no. 9, pp. 1296-1302, 1998.

[9]

E. Teruel, P. Chrzastowski-Wachtel, J. M. Colom, and M. Silva, "On Weighted T-Systems," Lecture Notes In Computer Science; Vol. 616, p. 348, 1992.

Digital Library

[10]

G. Cohen, G. J. Olsder, and J.-p. Quadrat, Synchronization and linearity. Wiley New York, 1992.

[11]

M. Geilen, "Reduction techniques for synchronous dataflow graphs," Annual ACM IEEE Design Automation Conference, pp. 911-916, 2009.

Digital Library

[12]

R. de Groote, J. Kuper, H. Broersma, and G. J. Smit, "Max-Plus Algebraic Throughput Analysis of Synchronous Dataflow Graphs," in 2012 38th Euromicro Conference on Software Engineering and Advanced Applications. IEEE, Sep. 2012, pp. 29-38.

Digital Library

[13]

K. Ito and K. K. Parhi, "Determining the minimum iteration period of an algorithm," Journal of VLSI Signal Processing, vol. 11, no. 3, pp. 229-244, Dec. 1995.

Digital Library

[14]

M. Nakamura and M. Silva, "Cycle time computation in deterministically timed weighted marked graphs," in 1999 7th IEEE International Conference on Emerging Technologies and Factory Automation. Proceedings ETFA '99 (Cat. No. 99TH8467), vol. 2. IEEE, pp. 1037-1046.

[15]

A. Dasdan, "Experimental analysis of the fastest optimum cycle ratio and mean algorithms," ACM Transactions on Design Automation of Electronic Systems (TODAES), vol. 9, no. 4, p. 385, 2004.

Digital Library

[16]

J. Cochet-terrasson, G. Cohen, S. Gaubert, M. M. Gettrick, and J.-P. Quadrat, "Numerical Computation of Spectral Elements in Max-Plus Algebra," in Proceedings of the IFAC Conference on System Structure and Control, Jul. 1998.

[17]

B. Heidergott, G. J. Olsder, and J. van der Woude, Max Plus at Work: modeling and analysis of synchronized systems. Princeton University Press, 2006.

[18]

N. Young, R. Tarjan, and J. Orlin, "Faster Parametric Shortest Path and Minimum Balance Algorithms," ArXiv Computer Science e-prints, May 2002.

[19]

R. Karp, "Parametric shortest path algorithms with an application to cyclic staffing," Discrete Applied Mathematics, vol. 3, no. 1, pp. 37-45, Feb. 1981.

[20]

M. Geilen, "Synchronous dataflow scenarios," ACM Transactions on Embedded Computing Systems, vol. 10, no. 2, pp. 1-31, Dec. 2010.

Digital Library

[21]

M. Geilen, S. Tripakis, and M. Wiggers, "The earlier the better," in Proceedings of the 14th international conference on Hybrid systems: computation and control - HSCC '11. New York, New York, USA: ACM Press, Apr. 2011, p. 23.

Digital Library

[22]

A. Ghamarian, M. Geilen, T. Basten, B. Theelen, M. Mousavi, and S. Stuijk, "Liveness and boundedness of synchronous data flow graphs," FMCAD06, no. August, pp. 68-75, 2006.

Digital Library

[23]

G. Cohen, S. Gaubert, and J.-P. Quadrat, "Max-plus algebra and system theory: Where we are and where to go now," Annual Reviews in Control, vol. 23, pp. 207-219, Jan. 1999.

[24]

J. Pino, S. Bhattacharyya, and E. Lee, "A hierarchical multiprocessor scheduling system for DSP applications," in Conference Record of The Twenty-Ninth Asilomar Conference on Signals, Systems and Computers, vol. 1. IEEE Comput. Soc. Press, pp. 122-126.

Digital Library

[25]

S. Tripakis, D. Bui, B. Rodiers, and E. A. Lee, "Compositionality in Synchronous Data Flow," in Proceedings of the 1st ACM/IEEE International Conference on Cyber-Physical Systems - ICCPS '10. New York, New York, USA: ACM Press, Apr. 2010, p. 199.

Digital Library

[26]

S. Stuijk, M. Geilen, and T. Basten, "Exploring trade-offs in buffer requirements and throughput constraints for synchronous dataflow graphs," in Proceedings of the 43rd annual conference on Design automation - DAC '06. New York, New York, USA: ACM Press, Jul. 2006, p. 899.

Digital Library

[27]

G. Bilsen, M. Engels, R. Lauwereins, and J. Peperstraete, "Cyclo-static data flow," in Acoustics, Speech, and Signal Processing, 1995. ICASSP-95., 1995 International Conference on, vol. 5, 1995, pp. 3255-3258 vol. 5.

Cited By

Kuiper GKurtin PBekooij M(2017)Hybrid Latency Minimization Approach using Model Checking and Dataflow AnalysisProceedings of the 20th International Workshop on Software and Compilers for Embedded Systems10.1145/3078659.3078665(41-50)Online publication date: 12-Jun-2017
https://dl.acm.org/doi/10.1145/3078659.3078665
Rosvall KKhalilzad NUngureanu GSander I(2017)Throughput Propagation in Constraint-Based Design Space Exploration for Mixed-Criticality SystemsProceedings of the 9th Workshop on Rapid Simulation and Performance Evaluation: Methods and Tools10.1145/3023973.3023977(1-8)Online publication date: 23-Jan-2017
https://dl.acm.org/doi/10.1145/3023973.3023977
(2014)Unified dataflow model for the analysis of data and pipeline parallelism, and buffer sizingProceedings of the Twelfth ACM/IEEE Conference on Formal Methods and Models for Codesign10.1109/MEMCOD.2014.6961839(12-21)Online publication date: 1-Oct-2014
https://dl.acm.org/doi/10.1109/MEMCOD.2014.6961839

Recommendations

From Graph Theory to Graph Algorithms, and Back
On the Multichromatic Number of s-Stable Kneser Graphs

For positive integers n and s, a subset Sï [n] is s-stable if sï |i-j|ï n-s for distinct i,j∈S . The s-stable r-uniform Kneser hypergraph KGrn,ks-stable is the r-uniform hypergraph that has the collection of all s-stable k-element subsets of [n] as ...
Bipartite subgraphs of triangle-free subcubic graphs

Suppose G is a graph with n vertices and m edges. Let n^' be the maximum number of vertices in an induced bipartite subgraph of G and let m^' be the maximum number of edges in a spanning bipartite subgraph of G. Then b(G)=m^'/m is called the bipartite ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

MEMOCODE '13: Proceedings of the Eleventh ACM/IEEE International Conference on Formal Methods and Models for Codesign

October 2013

194 pages

ISBN:9781479909056

Copyright © 2013.

Sponsors

Publisher

IEEE Computer Society

United States

Publication History

Published: 01 October 2013

Check for updates

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 34 of 82 submissions, 41%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
27
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Kuiper GKurtin PBekooij M(2017)Hybrid Latency Minimization Approach using Model Checking and Dataflow AnalysisProceedings of the 20th International Workshop on Software and Compilers for Embedded Systems10.1145/3078659.3078665(41-50)Online publication date: 12-Jun-2017
https://dl.acm.org/doi/10.1145/3078659.3078665
Rosvall KKhalilzad NUngureanu GSander I(2017)Throughput Propagation in Constraint-Based Design Space Exploration for Mixed-Criticality SystemsProceedings of the 9th Workshop on Rapid Simulation and Performance Evaluation: Methods and Tools10.1145/3023973.3023977(1-8)Online publication date: 23-Jan-2017
https://dl.acm.org/doi/10.1145/3023973.3023977
(2014)Unified dataflow model for the analysis of data and pipeline parallelism, and buffer sizingProceedings of the Twelfth ACM/IEEE Conference on Formal Methods and Models for Codesign10.1109/MEMCOD.2014.6961839(12-21)Online publication date: 1-Oct-2014
https://dl.acm.org/doi/10.1109/MEMCOD.2014.6961839

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents