Mapping cyclo-dynamic dataflow into pipelined datapath

Authors

DOI:

https://doi.org/10.18372/2073-4751.84.20899

Keywords:

data flow graph, FPGA, VHDL, datapath, pipeline, dynamic schedule

Abstract

The paper discusses the relevance of high-level synthesis (HLS) systems in designing pipelined datapaths. The goal of the research is to explore methods for mapping algorithms into a pipelined datapath that implements cyclic data flow graphs with dynamic schedules. The proposed method involves creating and optimizing cyclo-dynamic data flow graphs (CDDFG) and describing them in VHDL. A set of rules for arranging the correct CDDFG and respective finite state machine is proposed. The derived CDDFG is mapped into the pipelined datapath, as well as the synchronous dataflow. The method demonstrates its effectiveness through examples of run-length encoding decompression and LZW file decompression devices, which are implemented in field programmable gate arrays. The proposed method can be used manually or be implemented in HLS tools.

References

Gajski D. D., Abdi S., Gerstlauer A., Schirner G. Embedded System Design. Modeling, Synthesis and Verification. Springer. —2009.

Schaumont P. A Practical Introduc­tion to Hardware/Software Codesign. Springer. —2011.

Lee E. A., Messerschmitt D. G. Synchronous data flow. Proceedings of the IEEE, vol. 75, no. 9, 1987, pp. 1235–1245, Sept. https://doi.org/10.1109/PROC. 1987.13876

Lee E. A., Neuendorffer S. Concur­rent models of computation for embedded software. IEE-INST ELEC ENG. IEE Proceedings  Computers and Digital Techniques, vol. 152. No. 2, —2005, —pp. 239–250. https://doi.org/10.1049/ip-cdt:20045065

Khan S. A. Digital Design of Signal Processing Systems. A Practical Approach”. UK: Wiley. —2011.

Sergiyenko A., Serhienko A., Simo­nenko A. A method for synchronous dataflow retiming. 2017 IEEE First Ukraine Conference on Electrical and Computer Engineering (UKRCON), Kyiv, Ukraine, april 2017, 2017. pp. 1015–1018, https://doi.org/10.1109/UKRCON.2017.8100404

Parks T. M., Pino J. L., Lee E. A. A comparison of synchronous and cycle-static dataflow. 29th Asilomar Conference on Signals, Systems and Computers, Pacific Grove, CA, USA, vol. 1, —1995. —pp. 204–210 https://doi.org/10.1109/ACSSC.1995. 540541

Bhattacharyya B., Bhattacharyya S. Parameterized dataflow modeling for DSP systems. IEEE Transactions on Signal Processing, vol. 49, no. 10, 2001, pp. 2408–2421. https://doi.org/10.1109/ 78.950795

Wauters P., Engels M., Lauwereins R., Peperstraete J. A. Cyclo-dynamic data­flow. Proc. of 4th Euromicro Workshop on Parallel and Distributed Processing, Braga, Portugal, —1996, —pp. 319–326, https:// doi.org/ 10.1109/EMPDP.1996.500603

Fradet P., Girault A., Poplavko P. SPDF: A schedulable parametric data-flow MoC. Design, Automation & Test in Europe Conference & Exhibition (DATE), Dresden, Germany, 2012, pp. 769–774, https://doi.org/10.1109/DATE.2012.6176572

Keating M., Brikaud P. Reuse Methodology Manual for System-on-a-Chip Designs, 3d Ed. Kluwer. —2007.

Sergiyenko A. M. HDL dlya projectirovanija vychislitelnych ustroystv. Kyiv: Diasoft. 2004. (In Russian).

Woods R., McAllister J., Lightbody G., Yi Y. FPGA-based Implementation of Signal Processing Systems. Wiley, 2d Ed. —2017, —447 p.

Romankevych V. O., Mozghovyi I. V., Serhiienko P. A. Zacharioudakis L. Decompressor for hardware applications. Applied Aspects of Information Technology. Vol.6, No.1. —2023, —pp. 74–83. https://doi.org/10.15276/aait.06.2023.6

Zhou X., Ito Y., Nakano K. An Efficient Implementation of LZW Decom­pression in the FPGA. IEEE International Parallel and Distributed Processing Sympo­sium Workshops (IPDPSW). Chicago, IL, USA, 2016. pp. 599607, https://doi.org/10.1109/IPDPSW.2016.33.

Kagawa H., Ito Y., Nakano K. Throughput-Optimal Hardware Implementa­tion of LZW Decompression on the FPGA. 2019 Seventh International Symposium on Computing and Networking Workshops (CANDARW), Nagasaki, Japan, —2019. —pp. 7883. https://doi.org/10.1109/ CANDARW.2019.00022.

Downloads

Published

2025-12-30

How to Cite

Molchanov O. А., Sergiyenko, A. M., & Vinokurov, A. I. (2025). Mapping cyclo-dynamic dataflow into pipelined datapath. Problems of Informatization and Management, 4(84), 82–89. https://doi.org/10.18372/2073-4751.84.20899

Issue

Vol. 4 No. 84 (2025)

Section

Статті

License

The scientific journal adheres to the principles of Open Access and provides free, immediate, and permanent access to all published materials without financial, technical, or legal barriers for readers.

All articles are published in Open Access under the Creative Commons Attribution 4.0 International (CC BY 4.0) license.

Copyright

Authors who publish their works in the journal:

  • retain the copyright to their publications;

  • grant the journal the right of first publication of the article;

  • agree to the distribution of their materials under the CC BY 4.0 license;

  • have the right to reuse, archive, and distribute their works (including in institutional and subject repositories), provided that proper reference is made to the original publication in the journal.