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

Автори, які публікуються у цьому журналі, погоджуються з наступними умовами:

  1. Автори залишають за собою право на авторство своєї роботи та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons Attribution License, котра дозволяє іншим особам вільно розповсюджувати опубліковану роботу з обов'язковим посиланням на авторів оригінальної роботи та першу публікацію роботи у цьому журналі.

  2. Автори мають право укладати самостійні додаткові угоди щодо неексклюзивного розповсюдження роботи у тому вигляді, в якому вона була опублікована цим журналом (наприклад, розміщувати роботу в електронному сховищі установи або публікувати у складі монографії), за умови збереження посилання на першу публікацію роботи у цьому журналі.

  3. Політика журналу дозволяє і заохочує розміщення авторами в мережі Інтернет (наприклад, у сховищах установ або на особистих веб-сайтах) рукопису роботи, як до подання цього рукопису до редакції, так і під час його редакційного опрацювання, оскільки це сприяє виникненню продуктивної наукової дискусії та позитивно позначається на оперативності та динаміці цитування опублікованої роботи (див. The Effect of Open Access).