Method and device for arranging tasks in reconfigurable computing systems
DOI: 10.34759/trd-2021-120-13
Аuthors
South-Western State University, 94, 50-let Oktyabrya str., Kursk, 305040, Russia
e-mail: ilmas46ru@gmail.com
Abstract
In view of the growing complexity of the problems being solved, reconfigurable computing systems (RCS) have become widespread in various branches such as industry, aviation, instrument making, etc. The RCS distinctive aspect consists in the ability of the internal architecture changing for the task being solved, allowing productivity and energy efficiency increasing. The high degree of integration and hardware configuration allowed FPGAs application as the main computational element. When solving the information graph on the RCS, in view of the employed and available resources of the reconfigurable field, it is being divided into subgraphs, for which a configuration, describing the tasks locating among the FPGAs is being composed. Due to the complexity of the location search problem, which is NP-complex, its execution on a host computer operating in real time seems impossible. The existing approaches are either inapplicable for the DCS configuration search, or being solved programmatically. Thus, the development of the tools reducing the search time for the RCS configuration is up-to-date. An algorithm and a model, including the problem of the set covering, were created when developing a unit for the tasks location in the RCS. The model describes the unit construction, and four criteria. These criteria are being based on the ideas of tasks selecting from an adjacency matrix based on the number of links, the intensity of exchange between them and the occupied and available resources for location, allowing reduce the number of enumeration options, which made it possible to reduce the computational complexity of the algorithm. The algorithm developed on the basis of the model, in the set of selection, storage and assignment procedures, can be implemented on the current hardware. In the course of experimental studies of the tasks arrangement in the RCS, an analysis of the performance and the resulting final configuration was performed. It is shown that the developed unit is 5.17 times faster than the similar software. Thus, the inference can be drawn on the hardware implementation of the presented method and algorithm advantage. The developed unit is applicable in the RCS operating in real time, due to its productivity increase.
Keywords:
reconfigurable computing system, FPGA, configuration, algorithm, graphReferences
Voevodin V.V., Voevodin Vl.V. Parallelrsquo;nye vychisleniya (Parallel computing), Saint Peterburg, BKhV-Peterburg, 2015, 608 p.
Guzik V.F., Kalyaev I.A., Levin I.I. Rekonfiguriruemye vychislitelrsquo;nye sistemy (Reconfigurable Computing Systems), Taganrog, Yuzhnyi federalrsquo;nyi universitet, 2016, 472 p.
Kalyaev I.A., Levin I.I., Semernikov E.A., Shmoilov V.I. Rekonfiguriruemye mulrsquo;tikonveiernye vychislitelrsquo;nye struktury (Reconfigurable multicore computational structures), Rostov na Donu, YuNTs RAN, 2008, 320 p.
Masyukov I.I., Borzov D.B., Titov D.V., Sokolova Yu.V. Trudy MAI, 2021, no. 119. URL http://trudymai.ru/eng/published.php?ID=159791. DOI: 10.34759/trd-2021-119-13
Borzov D.B., Koshelev M.A., Sokolova Yu.V. Trudy MAI, 2021, no. 117. URL: http://trudymai.ru/eng/published.php?ID=156284. DOI: 10.34759/trd-2021-117-13
Konovalov I.S., Ostapenko S.S., Kobak V.G. Vestnik Donskogo gosudarstvennogo tekhnicheskogo universiteta. 2017, no. 3(90), pp. 137ndash;144.
Dobryakov V.A., Engalychev A.N., Nazarov A.V. Trudy MAI, 2014, no. 72. URL: http://trudymai.ru/eng/published.php?ID=47562
Zaozerskaya L.A., Kolokolov A.A. Problemy informatiki, 2009, no. 1(2), pp. 14ndash;23.
Lebedev B.K., Lebedev O.B. Problemy razrabotki perspektivnykh mikro- i nanoelektronnykh system, 2016, no. 1, pp. 187-194.
Pankratov A.V., Yakimov V.L., Makovskii V.N. Trudy MAI, 2015, no. 82. URL: http://trudymai.ru/eng/published.php?ID=58828
Borzov D.B., Basov R.G., Titov V.S., Sokolova Yu.V. Trudy MAI, 2020, no. 115. URL: http://trudymai.ru/eng/published.php?ID=119942. DOI: 10.34759/trd-2020-115-14
Solovrsquo;ev V.V. Osnovy yazyka proektirovaniya tsifrovoi apparatury Verilog (Fundamentals of the Verilog digital hardware design language), Moscow, Goryachaya Liniya-Telekom, 2021, 364 p.
Moiseev D.V., Chinrsquo; V.M., Mozolev L.A., Moiseeva S.G., Fam S.K. Trudy MAI, 2015, no. 79. URL http://trudymai.ru/eng/published.php?ID=55782
Zotov V.Yu. Komponenty i tekhnologii, 2010, no. 12, pp. 17-24.
Pedroni V.A. Digital Electronics and Design with VHDL, 1st edition, Burlington, Morgan Kaufmann, 2008, 717 p.
Ledin J. Architecting High-Performance Embedded Systems: Design and build high-performance real-time digital systems based on FPGAs and custom circuits, Birmingham, Packt Publishing, 2021, 376 p.
Deschamps J., Sutter D. G., Cantoacute; E. Guide to FPGA Implementation of Arithmetic Functions, Berlin, Springer, 2012, 472 p.
Ore O. Teoriya grafov (Graph theory), Moscow, Librokom, 2009, 354 p.
Uilson R. Vvedenie v teoriyu grafov (Introduction to graph theory), Moscow, Vilrsquo;yams, 2020, 240 p.
Matafonov D.E. Trudy MAI, 2018, no. 103. URL: http://trudymai.ru/eng/published.php?ID=100780
Kordover K.A., Zhdanov A.A., Danilov A.M. Trudy MAI, 2013, no. 65. URL: http://trudymai.ru/eng/published.php?ID=35985
Konovalov I.S., Fatkhi V.A., Kobak V.G. Vestnik Donskogo gosudarstvennogo tekhnicheskogo universiteta, 2016, no. 3(86), pp. 125-132.
Download