EQUIVALENT TRANSFORMATIONS FOR SOME KINDS OF RECURSIVE NON-LINEAR COMPUTING STRUCTURES FOR EFFICIENT IMPLEMENTATION ON RECONFIGURABLE COMPUTER SYSTEMS
Abstract
In the paper, we consider data-equivalent transformations of some kinds of non-linear computing structures, such as quadratic, fractional and conditional. All computing structures contain feedbacks. If a pipeline computing structure of a task, implemented on a reconfigurable computer system, contains feedbacks, the data processing rate slows down, because it is necessary to wait for feedback results to calculate the next value. The processing rate slows down not only in the chain with feedback, but in the whole computing structure. As a result, the task solution time increases. Previous fragments have to delay their data to supply it into a chain with feedback, and subsequent ones have to remain idle waiting for the feedback result data. At pr esent, there are no software development tools for reconfigurable computer systems with automatic optimization of such computing structures. So, the user has to analyze the source code to find expressions with feedbacks, and to optimize them. As a result, the development time of eff icient applications considerably increases. We suggest methods decreasing the data processing time interval (down to unity in the best case) for applied tasks solved on reconfigurable computer systems. Besides, the task solution time also decreases. Owing to the suggested methods, implemented in the optimizing synthesizer of circuit solutions, transformations are performed automatically. As a result, the development time for efficient applied tasks with feedbacks decreases from several days to several minutes.
References
[Reconfigurable computer systems: a tutorial], under the general ed. I.A. Kalyaeva, Rostov-on-
Don: Izd-vo YuFU, 2016, 472 p. ISBN 978-5-9275-1980-7.
2. Compton K. Reconfigurable Computing: A Survey of Systems and Software, ACM Computing
Surveys, 2002, Vol. 34, No. 2, pp. 171-210.
3. Popov A.Yu. Proektirovanie tsifrovykh ustroystv s ispol'zovaniem PLIS: ucheb. posobie [Designing
digital devices using FPGAs: a tutorial]. Moscow: Izd-vo MGTU im. N.E. Baumana,
2009, 80 p.
4. Krishna G, Sahadev R. Fundamentals of FPGA Architecture, Advanced Engineering Technical
and Scientific Publisher, 2017, Part 2, pp. 12-30.
5. Kalyaev A.V. Modul'no-narashchivaemye mnogoprotsessornye sistemy so strukturnoprotsedurnoy
organizatsiey vychisleniy [Modular-scalable multiprocessor systems with structural
and procedural organization of calculations]. Moscow: Yanus-K, 2003, 380 p.
6. Intel® Quartus® Prime Standard Edition User Guide 18.1. Getting Started. UG-20173
2018.09.24, pp. 44-47. Available at: https://www.intel.com/content/dam/www/programmable/
us/ en/pdfs/literature/ug/archives/ug-qps-getting-started-18-1.pdf (accessed 01 October 2020).
7. Xilinx Vivado Design Suite. User Guide. Synthesis. UG901 (v2017.1) April 19, 2017. – P. 7-
38. Available at: https://www.xilinx.com/support/documentation/sw_manuals/xilinx2017_1/
ug901-vivado-synthesis.pdf (accessed 25 September 2020).
8. Synopsys Identify Microsemi Edition Instrumentor User Guide, January 2018. – P. 50-51. Available
at: https://www.microsemi.com/document-portal/doc_download/136672-synopsys-identifyrtl-
l2016-09m-2-debugger-instrumentor-for-libero-soc-v11-8 (accessed 28 September 2020).
9. Dudko S.A. Metod preobrazovaniya rekurrentnykh vyrazheniy v informatsionnom grafe
[Transforming method of recursive expressions in an information graph], XVI Ezhegodnaya
molodezhnaya nauchnaya konferentsiya «Yug Rossii: vyzovy vremeni, otkrytiya, perspektivy»:
materialy konferentsii (g. Rostov-na-Donu, 13–28 aprelya 2020 g.) [XVI Annual Youth Scientific
Conference "South of Russia: Challenges of Time, Discoveries, Prospects": conference
proceedings (Rostov-on-Don, April 13-28, 2020)]. Rostov-on-Don: Izd-vo YuNTS RAN,
2020, 168 p.
10. Agapova E.G. Vychislitel'naya matematika: ucheb. posobie [Computational mathematics: a
tutorial], ed. by T.M. Popova. 2017. Khabarovsk: Izd-vo Tikhookean. gos. un-ta, 2017, 92 p.
11. Lindenhovius B., Mislove M., Zamdzhiev V. Mixed linear and non-linear recursive types, Proceedings
of the ACM on Programming Languages, 2019, Vol. 3, Article 111.
12. Vasil'ev A.V., Mazurov V.D. Vysshaya algebra: V 2 ch. [Abstract Algebra: In 2 parts],
Konspekt lektsiy [Lecture notes]. Novosibirsk: Izd-vo Novosib. gos. un-t., 2010, Part 1, 143 p.
13. Aditya R., Zulfikar M.T., Manik N.I. Testing Division Rings and Fields Using a Computer
Program, Procedia Computer Science, 2015, Vol. 59, pp. 540-549.
14. Tyugashev A.A. Osnovy programmirovaniya [Basics of programming]. Part I. Saint Petersburg:
Universitet ITMO, 2016, 160 p.
15. Nielsen F. A Concise and Practical Introduction to Programming Algorithms in Java, Undergraduate
Topics in Computer Science. Springer-Verlag London Limited, 2009.
16. Akchurin A.D., Yusupov K.M. Programmirovanie na yazyke Verilog: ucheb. posobie [Verilog
Programming: a tutorial]. Kazan', 2016, 90 p.
17. Nabulsi M., Al-Husainy M. Using Combinational Circuits for Control Purposes, Journal of
Computer Science, 2009, No. 5 (7), pp. 507-510.
18. Wang X. Estimation of Number of Bits in Binary Representation of an Integer, International
Journal of Research Studies in Computer Science and Engineering, 2015, Vol. 2, pp. 28-31.
19. Kharris D.M., Kharris S.L. Tsifrovaya skhemotekhnika i arkhitektura komp'yutera [Digital
Design and Computer Architecture]. 2nd ed., DMK-Press, 2018, 792 p.
20. Voevodin V.V. Lineynaya algebra [Linear Algebra]. 2nd ed. Moscow: Glavnaya redaktsiya
fiziko-matematicheskoy literatury, 1980.
