SDF3: Synchronous Data Flow For Free – Computational Modeling

SDF³ is a C++ library that implements a large collection of algorithms for timed dataflow graphs, including Scenario-Aware Dataflow, max-plus algebra, including switching max-plus-linear systems, and multiprocessor mapping. For example, throughput analysis [1, 2], latency analysis [3], buffer sizing [4, 5, 6], parametric analysis [7, 8], and many more.

An somewhat older version of SDF³ is GPL Licensed and available on https://www.es.ele.tue.nl/sdf3/ We plan to make a more recent version available on github.

In case you prefer a graphical user interface, you may consider using the SDF³ Wizard, which supports most of the SDF³ tools. The Dataflow Modeller is a graphical user interface for editing and debugging dataflow graphs. Provided that relevant extensions supported by the Dataflow Modeller are not used, such dataflow graphs can also be exported to SDF³.

Selected Related Publications

M. Damavandpeyma, S. Stuijk, T. Basten, M. Geilen, and H. Corporaal, “Modeling static-order schedules in synchronous dataflow graphs,” in Design, automation test in europe conference exhibition (date), 2012, 2012, pp. 775-780.
[Bibtex]

@InProceedings{DSBGC12,
Title = {Modeling static-order schedules in synchronous dataflow graphs},
Author = {M. Damavandpeyma and S. Stuijk and T. Basten and M. Geilen and H. Corporaal},
Booktitle = {Design, Automation Test in Europe Conference Exhibition (DATE), 2012},
Year = {2012},
Month = {March},
Pages = {775-780},
Doi = {10.1109/DATE.2012.6176588},
ISSN = {1530-1591},
Keywords = {data flow graphs;media streaming;processor scheduling;HSDFG;homogeneous SDFG;model periodic static-order scheduling;model streaming;scheduled graphs;synchronous dataflow graph;Algorithm design and analysis;Decoding;Optimization;Schedules;System recovery;Throughput;Vectors},
Owner = {reinier},
Timestamp = {2016.04.11}
}

S. Stuijk, T. Basten, M. C. W. Geilen, and H. Corporaal, “Multiprocessor resource allocation for throughput-constrained synchronous dataflow graphs,” in Proceedings of the 44th annual design automation conference, New York, NY, USA, 2007, p. 777–782.
[Bibtex]

@InProceedings{SBGC07,
Title = {Multiprocessor Resource Allocation for Throughput-constrained Synchronous Dataflow Graphs},
Author = {Stuijk, S. and Basten, T. and Geilen, M. C. W. and Corporaal, H.},
Booktitle = {Proceedings of the 44th Annual Design Automation Conference},
Year = {2007},
Address = {New York, NY, USA},
Pages = {777--782},
Publisher = {ACM},
Series = {DAC '07},
Acmid = {1278674},
Doi = {10.1145/1278480.1278674},
ISBN = {978-1-59593-627-1},
Keywords = {mapping, multi-processor, synchronous dataflow, throughput},
Location = {San Diego, California},
Numpages = {6},
Owner = {reinier},
Timestamp = {2016.08.25},
Url = {http://doi.acm.org/10.1145/1278480.1278674}
}

S. Stuijk, M. C. W. Geilen, and T. Basten, “SDF$^3$: SDF For Free,” in Application of concurrency to system design, 6th international conference, acsd 2006, proceedings, 2006, p. 276–278.
[Bibtex]

@InProceedings{SGB06,
Title = {{SDF}$^3$: {SDF For Free}},
Author = {S. Stuijk and M.C.W. Geilen and T. Basten},
Booktitle = {Application of Concurrency to System Design, 6th International Conference, ACSD 2006, Proceedings},
Year = {2006},
Month = {June},
Pages = {276--278},
Publisher = {IEEE Computer Society Press, Los Alamitos, CA, USA},
Doi = {10.1109/ACSD.2006.23},
Location = {Turku, Finland},
Owner = {reinier},
Timestamp = {2014.10.23},
Url = {http://www.es.ele.tue.nl/sdf3}
}

S. Stuijk, M. Geilen, and T. Basten, “A predictable multiprocessor design flow for streaming applications with dynamic behaviour,” in 2010 13th euromicro conference on digital system design: architectures, methods and tools, 2010, pp. 548-555.
[Bibtex]

@INPROCEEDINGS{SGB10,
author={S. Stuijk and M. Geilen and T. Basten},
booktitle={2010 13th Euromicro Conference on Digital System Design: Architectures, Methods and Tools},
title={A Predictable Multiprocessor Design Flow for Streaming Applications with Dynamic Behaviour},
year={2010},
volume={},
number={},
pages={548-555},
keywords={data flow graphs;embedded systems;multimedia systems;multiprocessing systems;dynamic application behaviour;embedded systems;predictable multiprocessor design flow;synchronous dataflow graphs;time-constrained streaming applications;Bandwidth;Decoding;Schedules;Throughput;Tiles;Timing;Transform coding;dataflow;mapping;multi-processor;throughput},
doi={10.1109/DSD.2010.31},
ISSN={},
month={Sept},}

M. Damavandpeyma, S. Stuijk, M. Geilen, T. Basten, and H. Corporaal, “Parametric throughput analysis of scenario-aware dataflow graphs,” in 2012 ieee 30th international conference on computer design (iccd), 2012, pp. 219-226.
[Bibtex]

@INPROCEEDINGS{DSGBC12,
author={M. Damavandpeyma and S. Stuijk and M. Geilen and T. Basten and H. Corporaal},
booktitle={2012 IEEE 30th International Conference on Computer Design (ICCD)},
title={Parametric throughput analysis of scenario-aware dataflow graphs},
year={2012},
volume={},
number={},
pages={219-226},
keywords={automata theory;data flow graphs;design-space exploration;max-plus automata;parametric throughput analysis;run-time management;scenario-aware dataflow graphs;synchronous dataflow graphs;throughput calculations;video decoder;Algorithm design and analysis;Analytical models;Automata;Concrete;Throughput;Timing;Vectors},
doi={10.1109/ICCD.2012.6378644},
ISSN={1063-6404},
month={Sept},}

A. H. Ghamarian, M. C. W. Geilen, T. Basten, and S. Stuijk, “Parametric throughput analysis of synchronous data flow graphs,” in 2008 design, automation and test in europe, 2008, pp. 116-121.
[Bibtex]

@INPROCEEDINGS{GGBS08,
author={A. H. Ghamarian and M. C. W. Geilen and T. Basten and S. Stuijk},
booktitle={2008 Design, Automation and Test in Europe},
title={Parametric Throughput Analysis of Synchronous Data Flow Graphs},
year={2008},
volume={},
number={},
pages={116-121},
keywords={data flow graphs;divide and conquer methods;SDFG models;actor execution times;divide and conquer algorithm;parametric throughput analysis;synchronous data flow graphs;Algorithm design and analysis;Data analysis;Digital signal processing;Flow graphs;Performance analysis;Runtime;Space exploration;State-space methods;Throughput;Timing},
doi={10.1109/DATE.2008.4484672},
ISSN={1530-1591},
month={March},}

S. Stuijk, M. Geilen, and T. Basten, “Throughput-buffering trade-off exploration for cyclo-static and synchronous dataflow graphs,” Ieee trans. comput., vol. 57, iss. 10, p. 1331–1345, 2008.
[Bibtex]

@Article{SGB08,
author = {Sander Stuijk and Marc Geilen and Twan Basten},
title = {Throughput-Buffering Trade-Off Exploration for Cyclo-Static and Synchronous Dataflow Graphs},
journal = {IEEE Trans. Comput.},
year = {2008},
volume = {57},
number = {10},
pages = {1331--1345},
issn = {0018-9340},
address = {Washington, DC, USA},
doi = {http://dx.doi.org/10.1109/TC.2008.58},
owner = {mgeilen},
publisher = {IEEE Computer Society},
timestamp = {2008.12.19},
}

M. Geilen and S. Stuijk, “Worst-case performance analysis of synchronous dataflow scenarios,” in Proceedings of the eighth ieee/acm/ifip international conference on hardware/software codesign and system synthesis, New York, NY, USA, 2010, p. 125–134.
[Bibtex]

@InProceedings{GS10,
author = {Geilen, Marc and Stuijk, Sander},
title = {Worst-Case Performance Analysis of Synchronous Dataflow Scenarios},
year = {2010},
isbn = {9781605589053},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1878961.1878985},
doi = {10.1145/1878961.1878985},
booktitle = {Proceedings of the Eighth IEEE/ACM/IFIP International Conference on Hardware/Software Codesign and System Synthesis},
pages = {125–134},
numpages = {10},
location = {Scottsdale, Arizona, USA},
series = {CODES/ISSS '10}
}

S. Stuijk, T. Basten, M. Geilen, A. H. Ghamarian, and B. Theelen, “Resource-efficient routing and scheduling of time-constrained streaming communication on networks-on-chip,” Journal of systems architecture, vol. 54, iss. 3, pp. 411-426, 2008.
[Bibtex]

@article{SBGGT07,
title = {Resource-efficient routing and scheduling of time-constrained streaming communication on networks-on-chip},
journal = {Journal of Systems Architecture},
volume = {54},
number = {3},
pages = {411-426},
year = {2008},
note = {System and Network on Chip},
issn = {1383-7621},
doi = {https://doi.org/10.1016/j.sysarc.2007.07.004},
url = {https://www.sciencedirect.com/science/article/pii/S1383762107001154},
author = {Sander Stuijk and Twan Basten and Marc Geilen and Amir Hossein Ghamarian and Bart Theelen},
keywords = {Networks-on-chip, Time-constrained scheduling, Resource-minimization, Predictable design, Synchronous dataflow},
abstract = {Network-on-chip-based multiprocessor systems-on-chip are considered as future embedded systems platforms. One of the steps in mapping an application onto such a parallel platform involves scheduling the communication on the network-on-chip. This paper presents different scheduling strategies that minimize resource usage by exploiting all scheduling freedom offered by networks-on-chip. It also introduces a technique to take the dynamism in applications into account when scheduling the communication of an application on the network-on-chip while minimizing the resource usage. Our experiments show that resource-utilization is improved when compared to existing techniques.}
}

S. Stuijk, “Predictable mapping of streaming applications on multiprocessors,” PhD Thesis, 2007.
[Bibtex]

@phdthesis{Stuijk07,
title = "Predictable mapping of streaming applications on multiprocessors",
author = "S. Stuijk",
note = "Proefschrift.",
year = "2007",
doi = "10.6100/IR630223",
language = "English",
isbn = "978-90-386-1624-7",
publisher = "Technische Universiteit Eindhoven",
school = "Electrical Engineering",
}

S. Stuijk, T. Basten, M. Geilen, A. H. Ghamarian, and B. Theelen, “Resource-efficient routing and scheduling of time-constrained network-on-chip communication,” in 9th euromicro conference on digital system design (dsd’06), 2006, pp. 45-52.
[Bibtex]

@INPROCEEDINGS{SBGGT06,
author={Stuijk, S. and Basten, T. and Geilen, M. and Ghamarian, A.H. and Theelen, B.},
booktitle={9th EUROMICRO Conference on Digital System Design (DSD'06)},
title={Resource-Efficient Routing and Scheduling of Time-Constrained Network-on-Chip Communication},
year={2006},
volume={},
number={},
pages={45-52},
doi={10.1109/DSD.2006.81}}

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 design automation conference, New York, NY, USA, 2006, p. 899–904.
[Bibtex]

@inproceedings{SGB06b,
author = {Stuijk, Sander and Geilen, Marc and Basten, Twan},
title = {Exploring Trade-Offs in Buffer Requirements and Throughput Constraints for Synchronous Dataflow Graphs},
year = {2006},
isbn = {1595933816},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1146909.1147138},
doi = {10.1145/1146909.1147138},
booktitle = {Proceedings of the 43rd Annual Design Automation Conference},
pages = {899–904},
numpages = {6},
keywords = {synchronous dataflow, optimization, buffering, throughput},
location = {San Francisco, CA, USA},
series = {DAC '06}
}

A. H. Ghamarian, M. C. W. Geilen, S. Stuijk, T. Basten, B. D. Theelen, M. R. Mousavi, A. J. M. Moonen, and M. J. G. Bekooij, “Throughput analysis of synchronous data flow graphs,” in Sixth international conference on application of concurrency to system design (acsd’06), 2006, pp. 25-36.
[Bibtex]

@INPROCEEDINGS{GGSea06,
author={Ghamarian, A.H. and Geilen, M.C.W. and Stuijk, S. and Basten, T. and Theelen, B.D. and Mousavi, M.R. and Moonen, A.J.M. and Bekooij, M.J.G.},
booktitle={Sixth International Conference on Application of Concurrency to System Design (ACSD'06)},
title={Throughput Analysis of Synchronous Data Flow Graphs},
year={2006},
volume={},
number={},
pages={25-36},
doi={10.1109/ACSD.2006.33}
}

M. Geilen, T. Basten, and S. Stuijk, “Minimising buffer requirements of synchronous dataflow graphs with model checking,” in Proceedings of the 42nd annual design automation conference, New York, NY, USA, 2005, p. 819–824.
[Bibtex]

@inproceedings{GBS05,
author = {Geilen, Marc and Basten, Twan and Stuijk, Sander},
title = {Minimising Buffer Requirements of Synchronous Dataflow Graphs with Model Checking},
year = {2005},
isbn = {1595930582},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1065579.1065796},
doi = {10.1145/1065579.1065796},
booktitle = {Proceedings of the 42nd Annual Design Automation Conference},
pages = {819–824},
numpages = {6},
keywords = {synchronous dataflow, buffering, optimization, model-checking},
location = {Anaheim, California, USA},
series = {DAC '05}
}

S. Stuijk, M. Geilen, B. Theelen, and T. Basten, “Scenario-aware dataflow: modeling, analysis and implementation of dynamic applications,” in 2011 international conference on embedded computer systems: architectures, modeling and simulation, 2011, pp. 404-411.
[Bibtex]

@INPROCEEDINGS{SGTB11,
author={Stuijk, Sander and Geilen, Marc and Theelen, Bart and Basten, Twan},
booktitle={2011 International Conference on Embedded Computer Systems: Architectures, Modeling and Simulation},
title={Scenario-aware dataflow: Modeling, analysis and implementation of dynamic applications},
year={2011},
volume={},
number={},
pages={404-411},
doi={10.1109/SAMOS.2011.6045491}
}

M. Geilen, S. Stuijk, and T. Basten, “Predictable dynamic embedded data processing,” in 2012 international conference on embedded computer systems (samos), 2012, pp. 320-327.
[Bibtex]

@INPROCEEDINGS{GSB12,
author={Geilen, Marc and Stuijk, Sander and Basten, Twan},
booktitle={2012 International Conference on Embedded Computer Systems (SAMOS)},
title={Predictable dynamic embedded data processing},
year={2012},
volume={},
number={},
pages={320-327},
doi={10.1109/SAMOS.2012.6404194}
}

Link to the tool page

References

[1]

@INPROCEEDINGS{GGSea06,
author={Ghamarian, A.H. and Geilen, M.C.W. and Stuijk, S. and Basten, T. and Theelen, B.D. and Mousavi, M.R. and Moonen, A.J.M. and Bekooij, M.J.G.},
booktitle={Sixth International Conference on Application of Concurrency to System Design (ACSD'06)},
title={Throughput Analysis of Synchronous Data Flow Graphs},
year={2006},
volume={},
number={},
pages={25-36},
doi={10.1109/ACSD.2006.33}
}

[2]

@InProceedings{GS10,
author = {Geilen, Marc and Stuijk, Sander},
title = {Worst-Case Performance Analysis of Synchronous Dataflow Scenarios},
year = {2010},
isbn = {9781605589053},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1878961.1878985},
doi = {10.1145/1878961.1878985},
booktitle = {Proceedings of the Eighth IEEE/ACM/IFIP International Conference on Hardware/Software Codesign and System Synthesis},
pages = {125–134},
numpages = {10},
location = {Scottsdale, Arizona, USA},
series = {CODES/ISSS '10}
}

[3]

@article{SBGGT07,
title = {Resource-efficient routing and scheduling of time-constrained streaming communication on networks-on-chip},
journal = {Journal of Systems Architecture},
volume = {54},
number = {3},
pages = {411-426},
year = {2008},
note = {System and Network on Chip},
issn = {1383-7621},
doi = {https://doi.org/10.1016/j.sysarc.2007.07.004},
url = {https://www.sciencedirect.com/science/article/pii/S1383762107001154},
author = {Sander Stuijk and Twan Basten and Marc Geilen and Amir Hossein Ghamarian and Bart Theelen},
keywords = {Networks-on-chip, Time-constrained scheduling, Resource-minimization, Predictable design, Synchronous dataflow},
abstract = {Network-on-chip-based multiprocessor systems-on-chip are considered as future embedded systems platforms. One of the steps in mapping an application onto such a parallel platform involves scheduling the communication on the network-on-chip. This paper presents different scheduling strategies that minimize resource usage by exploiting all scheduling freedom offered by networks-on-chip. It also introduces a technique to take the dynamism in applications into account when scheduling the communication of an application on the network-on-chip while minimizing the resource usage. Our experiments show that resource-utilization is improved when compared to existing techniques.}
}

[4]

@inproceedings{GBS05,
author = {Geilen, Marc and Basten, Twan and Stuijk, Sander},
title = {Minimising Buffer Requirements of Synchronous Dataflow Graphs with Model Checking},
year = {2005},
isbn = {1595930582},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1065579.1065796},
doi = {10.1145/1065579.1065796},
booktitle = {Proceedings of the 42nd Annual Design Automation Conference},
pages = {819–824},
numpages = {6},
keywords = {synchronous dataflow, buffering, optimization, model-checking},
location = {Anaheim, California, USA},
series = {DAC '05}
}

[5]

@inproceedings{SGB06b,
author = {Stuijk, Sander and Geilen, Marc and Basten, Twan},
title = {Exploring Trade-Offs in Buffer Requirements and Throughput Constraints for Synchronous Dataflow Graphs},
year = {2006},
isbn = {1595933816},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1146909.1147138},
doi = {10.1145/1146909.1147138},
booktitle = {Proceedings of the 43rd Annual Design Automation Conference},
pages = {899–904},
numpages = {6},
keywords = {synchronous dataflow, optimization, buffering, throughput},
location = {San Francisco, CA, USA},
series = {DAC '06}
}

[6]

M. Hendriks, H. A. Ara, M. Geilen, T. Basten, R. G. Marin, R. de Jong, and S. van der Vlugt, “Monotonic optimization of dataflow buffer sizes,” Journal of signal processing systems, vol. 91, p. 21–32, 2019.
[Bibtex]

@article{HAGea19,
title={Monotonic optimization of dataflow buffer sizes},
author={Hendriks, Martijn and Ara, Hadi Alizadeh and Geilen, Marc and Basten, Twan and Marin, Ruben Guerra and de Jong, Rob and van der Vlugt, Steven},
journal={Journal of signal processing systems},
volume={91},
pages={21--32},
year={2019},
publisher={Springer},
doi={10.1007/s11265-018-1415-2}
}

[7]

@INPROCEEDINGS{GGBS08,
author={A. H. Ghamarian and M. C. W. Geilen and T. Basten and S. Stuijk},
booktitle={2008 Design, Automation and Test in Europe},
title={Parametric Throughput Analysis of Synchronous Data Flow Graphs},
year={2008},
volume={},
number={},
pages={116-121},
keywords={data flow graphs;divide and conquer methods;SDFG models;actor execution times;divide and conquer algorithm;parametric throughput analysis;synchronous data flow graphs;Algorithm design and analysis;Data analysis;Digital signal processing;Flow graphs;Performance analysis;Runtime;Space exploration;State-space methods;Throughput;Timing},
doi={10.1109/DATE.2008.4484672},
ISSN={1530-1591},
month={March},}

[8]

@INPROCEEDINGS{DSGBC12,
author={M. Damavandpeyma and S. Stuijk and M. Geilen and T. Basten and H. Corporaal},
booktitle={2012 IEEE 30th International Conference on Computer Design (ICCD)},
title={Parametric throughput analysis of scenario-aware dataflow graphs},
year={2012},
volume={},
number={},
pages={219-226},
keywords={automata theory;data flow graphs;design-space exploration;max-plus automata;parametric throughput analysis;run-time management;scenario-aware dataflow graphs;synchronous dataflow graphs;throughput calculations;video decoder;Algorithm design and analysis;Analytical models;Automata;Concrete;Throughput;Timing;Vectors},
doi={10.1109/ICCD.2012.6378644},
ISSN={1063-6404},
month={Sept},}