TRANSFORMATION METHODS OF COMPUTING STRUCTURE WITH FEEDBACKS FOR EFFECTIVE IMPLEMENTATION ON RECONFIGURABLE COMPUTING SYSTEMS
Abstract
At present, various computer-aided (CAD) systems are used for solving tasks on reconfigurable computing systems (RCS). In most cases, they consist of two main parts: a compiler (translator), which translates the source code of a program into a graph-like information and computing structure, and a synthesizer, which maps it on an FPGA architecture. As a rule, existing synthesizers process computing structures without any complex optimization. Therefore, the solution, generated by the synthesizer, may contain inefficient fragments, which decrease a task solution speed. The most common examples of inefficient computing structures are fragments which implement recursive expressions. The paper proposes transformation methods for recursive expressions (fragments with feedbacks), which allow automatically reduce the data supply interval when solving tasks on reconfigurable computing systems. The methods are based on information-equivalent transformations of the computing structure of the original task. For each transformation defined a set of rules that must be satisfied by the vertices of the computing structure. Applying rules allows to perform equivalent transformations not only on simple data structures such as numbers, but also on more complex structures (matrices, vectors, tensors, etc.). On the base of the simulation results, the developed transformation methods of computing structures with feedbacks allow to reduce the task solving time about 2–5 times by reducing the data supply interval. The proposed methods are implemented in a prototype of optimizing synthesizer.
References
posobie [Reconfigurable computing systems: a textbook], ed. by I.A. Kalyaeva. Rostov-on-
Don: Izd-vo YuFU, 2016, 472 p.
2. Compton K. Reconfigurable Computing: A Survey of Systems and Software, ACM Computing
Surveys, June 2002, Vol. 34, No. 2, pp. 171-210.
3. Levin I.I., Dordopulo A.I., Kalyaev I.A., Doronchenko Yu.I., Raskladkin M.K. Sovremennye i
perspektivnye vysokoproizvoditel'nye vychislitel'nye sistemy s rekonfiguriruemoy
arkhitekturoy [Modern and promising high-performance computing systems with reconfigurable
architecture], Vestnik Yuzhno-Ural'skogo gosudarstvennogo universiteta. Seriya:
Vychislitel'naya matematika i informatika [Bulletin of the South Ural State University. Series:
Computational Mathematics and Computer Science], 2015, Vol. 4, No. 3, pp. 24-39.
4. Muslim F.B., Ma L., Roozmeh M. and Lavagno L. Efficient FPGA Implementation of OpenCL
High-Performance Computing Applications via High-Level Synthesis, In IEEE Access, 2017,
Vol. 5, pp. 2747-2762. DOI: 10.1109/ACCESS.2017.2671881.
5. Bibilo P.N., Romanov V.I. Integratsiya SAPR dlya sinteza logicheskikh skhem s
ispol'zovaniem global'noy optimizatsii [Integration of CAD for synthesis of logic circuits using
global optimization], Programmnye produkty i sistemy [Software products and systems], 2019,
No. 1, pp. 26-33.
6. Intel® Quartus® Prime Standard Edition User Guide 18.1. Getting Started. UG-20173 |
2019.12.16.
7. Xilinx Vivado Design Suite. User Guide. Synthesis. UG901 (v2019.1) June 12, 2019.
8. Synopsys Synplify Pro for Microsemi Edition User Guide November 2016.
9. Rene Mueller, Jens Teubner, and Gustavo Alonso. Data processing on FPGAs. PVLDB, 2(1),
August 2009.
10. Vereshchagin N.K., Shen' A. Lektsii po matematicheskoy logike i teorii algoritmov. Ch. 1.
Nachala teorii mnozhestv [Lectures on mathematical logic and the theory of algorithms. Part 1.
The beginnings of set theory]. 4th ed. Moscow: MTSNMO, 2012, 112 p.
11. Kolyada V.I., Korenovskiy A.A. Kurs lektsiy po matematicheskomu analizu [A course of lectures
on mathematical analysis]: In 2 part. Part 1. Odessa: Astroprint, 2009, XXVII, 369 p.
12. Novikov F.A. Diskretnaya matematika dlya programmistov: uchebnik dlya vuzov [Discrete mathematics
for programmers: textbook for universities]. 3rd ed. Saint Petersburg: Piter, 2009, 384 p.
13. Voevodin V.V. Lineynaya algebra [Linear algebra]. 2nd ed. Moscow: Glavnaya redaktsiya
fiziko-matematicheskoy literatury, 1980.
14. Kuck D. The structure of computers and computations. John Wiley and Sons. Inc., New York,
NY, 1978.
15. Samofalov K.G., Lutskiy G.M. Osnovy teorii mnogourovnevykh konveyernykh vychislitel'nykh
system [Fundamentals of the theory of multilevel conveyor computing systems].
Moscow: Radio i svyaz', 1989, 272 p.
16. Vasil'ev A.V., Mazurov V.D. Vysshaya algebra: Konspekt lektsiy. V 2 ch. [Higher Algebra:
Lecture Notes. In 2 part]. Novosibirsk: Novosib. gos. un-t, 2010, Part 1, 143 p.
17. Ricky Aditya, Muhammad Taufiq Zulfikar, Ngarap Imanuel Manik. Testing Division Rings and
Fields Using a Computer Program, Procedia Computer Science, 2015, Vol. 59, pp. 540-549.
18. Doronchenko Yu.I. Metod operatsionno-grafovogo opisaniya odnovremennykh vychisleniy
dlya mnogoprotsessornykh sistem [Method of operational graph description of simultaneous
computations for multiprocessor systems], Mater. Mezhdunar. nauch.-tekhn. konf.
“Mnogoprotsessornye vychisl. i upravlyayushchie sistemy – 2007” [Materials of the International
Scientific and Technical Conference "Multiprocessor computing and Control systems -
2007"]. Taganrog: TTI YuFU, 2007, Vol. 1, pp. 11-17.
19. Stanishevskiy O.B. Effektivnost' arifmeticheskoy obrabotki pri konveyernykh i
neyrokonveyernykh vychisleniyakh [The efficiency of arithmetic processing in conveyor and
neuroconveyor calculations], Konveyernye vychislitel'nye sistemy: Tezisy dokladov [Conveyor
computing systems: Abstracts]. Kishinev, 1988.
20. Dudko S.A. Ekvivalentnye preobrazovaniya rekurrentnykh vyrazheniy v rekonfiguriruemykh
vychislitel'nykh sistemakh [Equivalent transformations of recurrent expressions in reconfigurable
computing systems], Superkomp'yuternye tekhnologii (SKT-2020): Mater. 6-y
Vserossiyskoy nauchno-tekhnicheskoy konferentsii [Supercomputer Technologies (SKT-2020):
Materials of the 6th All-Russian Scientific and Technical Conference]. Rostov-on-Don, Taganrog:
Izd-vo YuFU, 2020, Vol. 1, pp. 181-183.
