Method for Mapping Cyclo-Dynamic Dataflow Into Pipelined Datapath
DOI:
https://doi.org/10.20535/2786-8729.4.2024.304965Keywords:
data flow graph, FPGA, VHDL, datapath, pipeline, dynamic scheduleAbstract
An overview of high-level synthesis (HLS) systems for designing pipelined datapaths is presented in the paper. The goal is to explore methods of mapping algorithms to the pipelined datapaths implementing the cyclic data flow graphs with dynamic schedules. The cyclo-dynamic dataflow (CDDF) is selected as the very expressive model for describing a wide domain of the dataflow algorithms. CDDF is distinguished in that, the algorithm period depends on the calculated data and has a dynamic schedule. A set of mapping conditions is formulated that provide the deadlock-free schedule of CDDF when it is mapped into the pipelined datapath. Due to the proposed method, the algorithm is represented by a set of CDDF and finite state machines (FSMs). The latter are subgraphs of CDDF. CDDF is optimized using retiming and pipelining methods. After that CDDF and its FSMs are described by the hardware description language like VHDL as well as the synchronous dataflow is described. The proposed method involves describing cyclo-dynamic data flow graphs in VHDL and optimizing them for implementation in the field programable gate arrays (FPGAs). The example of the sequence detector design shows the method implementation in detail. More sophisticated LZW decompression algorithm mapping demonstrates that the proposed method is rather effective and can give the pipelined datapath which effectivenes is comparable with that of the best hardware solution. The method can be implemented in modern HLS systems.
References
Calypto's Catapult 8 HLS: C-Based Hardware Design Matures. BDTI Resources for Engineers. December 17, 2014. https://www.bdti.com/InsideDSP/2014/11/18/Calypto.
Intel oneAPI DPC++/C++ Compiler Handbook for Intel FPGAs. Intel Corporation. 05.08.2024. https://cdrdv2.intel.com/v1/dl/getContent/805578?fileName=oneapi-fpga-add-on_developer-guide_2024.1-785441-805578.pdf
Vitis High-Level Synthesis User Guide (UG1399). AMD Adaptive Computing. 18.12.2023. https://docs.xilinx.com/r/en-US/ug1399-vitis-hls
C-to-Silicon Compiler High-Level Synthesis Automated high-level synthesis for design and verification. Cadence. 2008. 4 p. http://pdf2.solecsy.com/564/5c0644f6-808c-4d18-9b31-0eec054873e5.pdf
K. Kintali, Y. Gu, “Model-Based Design with Simulink, HDL Coder, and Xilinx System Generator for DSP,” MathWorks. White paper. 2017. pp. 1–15. https://de.mathworks.com/content/ dam/mathworks/tag-team/Objects/x/86457_92077_v01_ Xilinx_WhitePaper.pdf
S. S. Bhattacharyya, P. K. Murthy, E. A. Lee, Software Synthesis from Dataflow Graphs, Springer US. 2012.
K. Lee, Y. Lee, A. Raina, et al. “Software synthesis from dataflow schedule graphs.” SN Appl. Sci. No. 3, Vol. 142. 2021. https://doi.org/10.1007/s42452-020-04135-6
D. D. Gajski, S. Abdi, A. Gerstlauer, G. Schirner, Embedded System Design. Modeling, Synthesis and Verification. Springer. 2009.
P. Schaumont, A Practical Introduction to Hardware/Software Codesign. Springer. 2011.
E. A. Lee, D. G. Messerschmitt, “Synchronous data flow.” Proceedings of the IEEE, vol. 75, no. 9, pp. 1235–1245, Sept. 1987, DOI: https://doi.org/10.1109/PROC.1987.13876
E. A. Lee, S. Neuendorffer, “Concurrent 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
S. A. Khan, Digital Design of Signal Processing Systems. A Practical Approach. UK: Wiley. 2011.
A. Sergiyenko, A. Serhienko, A. Simonenko, “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
T. M. Parks, J. L. Pino, E. A. Lee, “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
B. Bhattacharyya, S. Bhattacharyya, “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
W. Plishker, N. Sane, M. Kiemb, S.S. Bhattacharyya, (2008). “Heterogeneous Design in Functional DIF”. In: Bereković, M., Dimopoulos, N., Wong, S. (eds) Embedded Computer Systems: Architectures, Modeling, and Simulation. SAMOS 2008. Lecture Notes in Computer Science, vol. 5114. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-70550-5_18.
H. -H. Wu, C. -C. Shen, N. Sane, W. Plishker and S. S. Bhattacharyya, "A Model-Based Schedule Representation for Heterogeneous Mapping of Dataflow Graphs," 2011 IEEE International Symposium on Parallel and Distributed Processing Workshops and Phd Forum, Anchorage, AK, USA, 2011, pp. 70-81, doi: 10.1109/IPDPS.2011.128.
P. Wauters, M. Engels, R. Lauwereins, J. A. Peperstraete, “Cyclo-dynamic dataflow”. Proc. of 4th Euromicro Workshop on Parallel and Distributed Processing, Braga, Portugal, 1996, pp. 319–326, https://doi.org/10.1109/EMPDP.1996.500603
P. Fradet, A. Girault, P. Poplavko, “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.
M. Keating, P. Brikaud, Reuse Methodology Manual for System-on-a-Chip Designs, 3d Ed. Kluwer. 2007.
A. M. Sergiyenko, VHDL dlya projectirovanija vychislitelnych ustroystv. Kyiv: Diasoft. 2004. (In Russian).
R. Woods, J. McAllister, G. Lightbody, Y. Yi, FPGA-based Implementation of Signal Processing Systems. Wiley, 2d Ed. 2017, 447 p.
V. O. Romankevych, I. V. Mozghovyi, P. A. Serhiienko L. Zacharioudakis, “Decompressor for hardware applications”. Applied Aspects of Information Technology. 2023. Vol.6, no.1. P. 74–83. https://doi.org/10.15276/aait.06.2023.6
A.М. Sergiyenko, I.V. Mozghovyi: “Hardware decompressor design”. Electron. Model. 2023, vol. 45. no. 5, pp.113-128. https://doi.org/10.15407/emodel.45.05.113
H. Kagawa, Y. Ito, K. Nakano, “Throughput-Optimal Hardware Implementation of LZW Decompression on the FPGA”. 2019 Seventh International Symposium on Computing and Networking Workshops (CANDARW), Nagasaki, Japan, 2019. pp. 7883. https://doi.org/10.1109/CANDARW.2019.00022.
