Article

Efficient computation of buffer capacities for cyclo-static dataflow graphs

Authors:

Maarten H. Wiggers,

Marco J. G. Bekooij,

Gerard J. M. SmitAuthors Info & Claims

DAC '07: Proceedings of the 44th annual Design Automation Conference

Pages 658 - 663

https://doi.org/10.1145/1278480.1278647

Published: 04 June 2007 Publication History

Get Access

Abstract

A key step in the design of cyclo-static real-time systems is the determination of buffer capacities. In our multi-processor system, we apply back-pressure, which means that tasks wait for space in output buffers. Consequently buffer capacities affect the throughput. This requires the derivation of buffer capacities that both result in a satisfaction of the throughput constraint, and also satisfy the constraints on the maximum buffer capacities. Existing exact solutions suffer from the computational complexity that is associated with the required conversion from a cyclo-static dataflow graph to a single-rate dataflow graph. In this paper we present an algorithm, with polynomial computational complexity, that does not require this conversion and that obtains close to minimal buffer capacities. The algorithm is applied to an MP3 play-back application that is mapped on our multi-processor system. For this application, we see that a cyclo-static dataflow model can reduce the buffer capacities by 50% compared to a multi-rate dataflow model.

References

[1]

M. J. G. Bekooij et al. Dataflow Analysis for Real-Time Embedded Multiprocessor System Design, chapter 15. Dynamic and Robust Streaming Between Connected CE Devices. Kluwer Academic Publishers, 2005.

Google Scholar

[2]

D. Bertsimas and J. N. Tsitsiklis. Introduction to Linear Optimization. Athena Scientific, 1997.

Digital Library

Google Scholar

[3]

G. Bilsen et al. Cyclo-Static Dataflow. IEEE Transactions on Signal Processing, 44(2):397--408, February 1996.

Digital Library

Google Scholar

[4]

A. Dasdan. Experimental Analysis of the Fastest Optimum Cycle Ratio and Mean Algorithms. ACM Transactions on Design Automation of Embedded Systems, 9(4):385--418, October 2004.

Digital Library

Google Scholar

[5]

R. Govindarajan et al. Minimizing Buffer Requirement under Rate-Optimal Schedules in Regular Dataflow Networks. Journal of VLSI Signal Processing, 31(3), 2002.

Digital Library

Google Scholar

[6]

E. A. Lee and D. G. Messerschmitt. Synchronous Dataflow. Proceedings of the IEEE, 75(9):1235--1245, September 1987.

Crossref

Google Scholar

[7]

C. W. Mercer et al. Processor Capacity Reserves: Operating System Support for Multimedia Applications. In Proc. IEEE Int'l Conference on Multimedia Computing and Systems, pages 90--99, 1994.

Crossref

Google Scholar

[8]

T. M. Parks et al. A Comparison of Synchronous and Cyclo-Static Dataflow. In Proc. IEEE Asilomar Conference on Signals, Systems and Computers, pages 204--210, October 1995.

Digital Library

Google Scholar

[9]

J. L. Pino and E. A. Lee. Hierarchical Static Scheduling of Dataflow Graphs onto Multiple Processors. In Proc. IEEE Int'l Conference on Acoustics, Speech, and Signal Processing, May 1995.

Crossref

Google Scholar

[10]

S. Sriram and S. S. Bhattacharyya. Embedded Multiprocessors: Scheduling and Synchronization. Marcel Dekker Inc., 2000.

Digital Library

Google Scholar

[11]

S. Stuijk et al. Exploring Trade-Offs in Buffer Requirements and Throughput Constraints for Synchronous Dataflow Graphs. In Proc. Design Automation Conference (DAC), pages 889--904, July 2006.

Digital Library

Google Scholar

[12]

M. H. Wiggers et al. Efficient Computation of Buffer Capacities for Multi-Rate Real-Time Systems with Back-Pressure. In Proc. Int'l Conference on Hardware/Software Codesign and System Synthesis (CODES+ISSS), October 2006.

Digital Library

Google Scholar

Cited By

View all

Honorat ADardaillon MMiomandre HNezan J(2024)Automated Buffer Sizing of Dataflow Applications in a High-level Synthesis WorkflowACM Transactions on Reconfigurable Technology and Systems10.1145/362610317:1(1-26)Online publication date: 27-Jan-2024
https://dl.acm.org/doi/10.1145/3626103
Koh JBodin B(2022)K-Periodic Scheduling for Throughput-Buffering Trade-Off Exploration of CSDFACM Transactions on Embedded Computing Systems10.1145/355976022:1(1-28)Online publication date: 29-Oct-2022
https://dl.acm.org/doi/10.1145/3559760
Hendriks MAra HGeilen MBasten TMarin RJong RVlugt S(2019)Monotonic Optimization of Dataflow Buffer SizesJournal of Signal Processing Systems10.1007/s11265-018-1415-291:1(21-32)Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.1007/s11265-018-1415-2
Show More Cited By

Index Terms

Efficient computation of buffer capacities for cyclo-static dataflow graphs
1. Computer systems organization
  1. Embedded and cyber-physical systems
  2. Real-time systems

Recommendations

Cyclo-static DataFlow phases scheduling optimization for buffer sizes minimization
M-SCOPES '13: Proceedings of the 16th International Workshop on Software and Compilers for Embedded Systems

Cyclo-Static DataFlow (CSDF) is a powerful model for the specification of DSP applications. However, as in any asynchronous model, the synchronization of the different communicating tasks (processes) is made through buffers that have to be sized such ...
Efficient computation of buffer capacities for multi-rate real-time systems with back-pressure
CODES+ISSS '06: Proceedings of the 4th international conference on Hardware/software codesign and system synthesis

A key step in the design of multi-rate real-time systems is the determination of buffer capacities. In our multi-processor system, we apply back-pressure as caused by bounded buffers in order to control jitter. This requires the derivation of buffer ...
Efficient Computation of Buffer Capacities for Cyclo-Static Real-Time Systems with Back-Pressure
RTAS '07: Proceedings of the 13th IEEE Real Time and Embedded Technology and Applications Symposium

This paper describes a conservative approximation algorithm that derives close to minimal buffer capacities for an application described as a cyclo-static dataflow graph. The resulting buffer capacities satisfy constraints on the maximum buffer ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

DAC '07: Proceedings of the 44th annual Design Automation Conference

June 2007

1016 pages

ISBN:9781595936271

DOI:10.1145/1278480

General Chair:
Steven P. Levitan
Univ. of Pittsburgh, Pittsburgh, PA

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 June 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

DAC07

Sponsor:

SIGDA

DAC07: The 44th Annual Design Automation Conference 2007

June 4 - 8, 2007

California, San Diego

Acceptance Rates

DAC '07 Paper Acceptance Rate 152 of 659 submissions, 23%;

Overall Acceptance Rate 1,770 of 5,499 submissions, 32%

Upcoming Conference

DAC '25

Sponsor:
sigda

62nd ACM/IEEE Design Automation Conference

June 22 - 26, 2025

San Francisco , CA , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

51
Total Citations
View Citations
300
Total Downloads

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

Reflects downloads up to 14 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Honorat ADardaillon MMiomandre HNezan J(2024)Automated Buffer Sizing of Dataflow Applications in a High-level Synthesis WorkflowACM Transactions on Reconfigurable Technology and Systems10.1145/362610317:1(1-26)Online publication date: 27-Jan-2024
https://dl.acm.org/doi/10.1145/3626103
Koh JBodin B(2022)K-Periodic Scheduling for Throughput-Buffering Trade-Off Exploration of CSDFACM Transactions on Embedded Computing Systems10.1145/355976022:1(1-28)Online publication date: 29-Oct-2022
https://dl.acm.org/doi/10.1145/3559760
Hendriks MAra HGeilen MBasten TMarin RJong RVlugt S(2019)Monotonic Optimization of Dataflow Buffer SizesJournal of Signal Processing Systems10.1007/s11265-018-1415-291:1(21-32)Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.1007/s11265-018-1415-2
Ara HGeilen MBehrouzian ABasten TOuhammou YRidouard FGrolleau EJan MBehnam M(2018)Throughput-Buffering Trade-Off Analysis for Scenario-Aware Dataflow ModelsProceedings of the 26th International Conference on Real-Time Networks and Systems10.1145/3273905.3273921(265-275)Online publication date: 10-Oct-2018
https://dl.acm.org/doi/10.1145/3273905.3273921
Honorat ATran HBesnard LGautier TTalpin JBouakaz ABini EPagetti C(2017)ADFGProceedings of the 25th International Conference on Real-Time Networks and Systems10.1145/3139258.3139267(158-167)Online publication date: 4-Oct-2017
https://dl.acm.org/doi/10.1145/3139258.3139267
Geilen MFalk JHaubelt CBasten TTheelen BStuijk S(2017)Performance Analysis of Weakly-Consistent Scenario-Aware Dataflow GraphsJournal of Signal Processing Systems10.1007/s11265-016-1193-787:1(157-175)Online publication date: 1-Apr-2017
https://dl.acm.org/doi/10.1007/s11265-016-1193-7
Pöppl ABader MSchwarzer TGlaß M(2016)SWE-X10Proceedings of the Second Internationsl Workshop on Extreme Scale Programming Models and Middleware10.5555/3018814.3018820(32-39)Online publication date: 13-Nov-2016
https://dl.acm.org/doi/10.5555/3018814.3018820
Tripakis SLimaye RRavindran KWang GAndrade HGhosal A(2016)Tokens vs. SignalsJournal of Signal Processing Systems10.1007/s11265-015-0971-y85:1(23-43)Online publication date: 1-Oct-2016
https://dl.acm.org/doi/10.1007/s11265-015-0971-y
Groote RHölzenspies PKuper JSmit G(2015)Incremental Analysis of Cyclo-Static Synchronous Dataflow GraphsACM Transactions on Embedded Computing Systems10.1145/279298114:4(1-26)Online publication date: 8-Dec-2015
https://dl.acm.org/doi/10.1145/2792981
Mirzoyan DAkesson BStuijk SGoossens K(2015)Maximizing the Number of Good Dies for Streaming Applications in NoC-Based MPSoCs Under Process VariationACM Transactions on Embedded Computing Systems10.1145/278596814:4(1-26)Online publication date: 24-Sep-2015
https://dl.acm.org/doi/10.1145/2785968
Show More Cited By

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.

PDF

eReader

View online with eReader.

eReader

Abstract

References

Cited By

Index Terms

Recommendations

Cyclo-static DataFlow phases scheduling optimization for buffer sizes minimization

Efficient computation of buffer capacities for multi-rate real-time systems with back-pressure

Efficient Computation of Buffer Capacities for Cyclo-Static Real-Time Systems with Back-Pressure

Comments

Information

Published In

Sponsors

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Conference

Acceptance Rates

Upcoming Conference

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

Login options

Full Access

View options

PDF

eReader

Share

Share this Publication link

Share on social media

Affiliations