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

Robert de Groote, P.K.F. Holzenspies, Jan Kuper, Haitze J. Broersma

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

12 Citations (Scopus)
65 Downloads (Pure)

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.
Original languageUndefined
Title of host publicationProceedings of the 11th ACM/IEEE International Conference on Formal Methods and Models for Codesign, MEMOCODE 2013
Place of PublicationUSA
PublisherIEEE Computer Society
Pages35-46
Number of pages12
ISBN (Print)978-1-4799-0903-2
Publication statusPublished - Oct 2013

Publication series

Name
PublisherIEEE Computer Society

Keywords

  • Performance analysis
  • Synchronous Data Flow
  • METIS-300052
  • IR-87981
  • Approximation
  • EWI-23789

Cite this

de Groote, R., Holzenspies, P. K. F., Kuper, J., & Broersma, H. J. (2013). Back to basics: homogeneous representations of multi-rate synchronous dataflow graphs. In Proceedings of the 11th ACM/IEEE International Conference on Formal Methods and Models for Codesign, MEMOCODE 2013 (pp. 35-46). USA: IEEE Computer Society.
de Groote, Robert ; Holzenspies, P.K.F. ; Kuper, Jan ; Broersma, Haitze J. / Back to basics: homogeneous representations of multi-rate synchronous dataflow graphs. Proceedings of the 11th ACM/IEEE International Conference on Formal Methods and Models for Codesign, MEMOCODE 2013. USA : IEEE Computer Society, 2013. pp. 35-46
@inproceedings{6f5e206bea6f401298280ea5b9bd3e17,
title = "Back to basics: homogeneous representations of multi-rate synchronous dataflow graphs",
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.",
keywords = "Performance analysis, Synchronous Data Flow, METIS-300052, IR-87981, Approximation, EWI-23789",
author = "{de Groote}, Robert and P.K.F. Holzenspies and Jan Kuper and Broersma, {Haitze J.}",
year = "2013",
month = "10",
language = "Undefined",
isbn = "978-1-4799-0903-2",
publisher = "IEEE Computer Society",
pages = "35--46",
booktitle = "Proceedings of the 11th ACM/IEEE International Conference on Formal Methods and Models for Codesign, MEMOCODE 2013",
address = "United States",

}

de Groote, R, Holzenspies, PKF, Kuper, J & Broersma, HJ 2013, Back to basics: homogeneous representations of multi-rate synchronous dataflow graphs. in Proceedings of the 11th ACM/IEEE International Conference on Formal Methods and Models for Codesign, MEMOCODE 2013. IEEE Computer Society, USA, pp. 35-46.

Back to basics: homogeneous representations of multi-rate synchronous dataflow graphs. / de Groote, Robert; Holzenspies, P.K.F.; Kuper, Jan; Broersma, Haitze J.

Proceedings of the 11th ACM/IEEE International Conference on Formal Methods and Models for Codesign, MEMOCODE 2013. USA : IEEE Computer Society, 2013. p. 35-46.

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

TY - GEN

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

AU - de Groote, Robert

AU - Holzenspies, P.K.F.

AU - Kuper, Jan

AU - Broersma, Haitze J.

PY - 2013/10

Y1 - 2013/10

N2 - 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.

AB - 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.

KW - Performance analysis

KW - Synchronous Data Flow

KW - METIS-300052

KW - IR-87981

KW - Approximation

KW - EWI-23789

M3 - Conference contribution

SN - 978-1-4799-0903-2

SP - 35

EP - 46

BT - Proceedings of the 11th ACM/IEEE International Conference on Formal Methods and Models for Codesign, MEMOCODE 2013

PB - IEEE Computer Society

CY - USA

ER -

de Groote R, Holzenspies PKF, Kuper J, Broersma HJ. Back to basics: homogeneous representations of multi-rate synchronous dataflow graphs. In Proceedings of the 11th ACM/IEEE International Conference on Formal Methods and Models for Codesign, MEMOCODE 2013. USA: IEEE Computer Society. 2013. p. 35-46