Mathematical Model and Hardware-Oriented Algorithm for Programs Placement Planning in Systems on a Chip
DOI: 10.34759/trd-2021-119-13
Аuthors
1*, 1**, 1***, 2****1. South-Western State University, 94, 50-let Oktyabrya str., Kursk, 305040, Russia
2. Lavochkin Research and Production Association, NPO Lavochkin, 24, Leningradskay str., Khimki, Moscow region, 141400, Russia
*e-mail: ilmas46ru@gmail.com
**e-mail: bоrzоvdb@kursknеt.ru
***e-mail: amazing2004@inbox.ru
****e-mail: jv.sokolova@mail.ru
Abstract
A reconfigurable computing system () is a system that can be reconfigured after its manufacturing. A promising basis for such system constructing is an RCS-FPGA. One of the tasks of building an RCS in real time mode consists in changing the internal FPGA modules organization. However, this leads to the increase in the switching delay time. This time reduction is achieved by the internal modules redistributing, which allows increasing the RCS speed.
The article presents a mathematical model and a hardware-oriented algorithm for program scheduling in systems on a chip, which will allow reducing the time delay in computing the new topology of a reconfigurable computing system and increase its fault tolerance.
To achieve the smallest total length of interconnections, the article proposes to employ two criteria:
1) The programs with a maximum number of related programs must have a minimum distance to their adjacent programs;
2) Adjacent programs with maximum loading among themselves must have a minimum distance;
Thus, to achieve the minimum total interconnection length of the program configuration in the system-on-chip, it is necessary to find such a mapping that would satisfy the above presented conditions 1 and 2.
Based on the proposed criteria and method, a hardware-oriented algorithm was developed, which main advantages consist in the simultaneous selection and location search in the configuration of the selected programs. It reduces the total length of the obtained interconnects in the configuration being computed and the number of enumeration operations.
The software modeling of the developed hardware-oriented algorithm and its results comparison with the algorithm program model, based on the ideas of the branches and boundaries method was performed. Comparison was performed for the following types of graphs: ring, fully connected, planar, Cayley direct product, star using the Halin construction, bipartite. It revealed that the hardware-oriented algorithm works more efficiently for a configuration search for the most of the presented graphs types: in configurations computing for all presented types of graphs (on average, the total length of interconnections is 8.4% less), and in operation speed in four out of six (6.6% faster on average).
The presented method and the hardware-based system-on-chip configuration-planning algorithm developed on its basis are applicable in high-availability systems such as onboard aviation, tracking, surveillance, radar, recognition systems, etc. This approach application will reduce both the time spent on planning or design (compilation) of a new configuration plan, and reduce the switching delays of the system.
Keywords:
system-on-a-chip, reconfiguration, architecture, placement, FPGA, configuration, mathematical model, algorithmReferences
Kalyaev I.A., Levin I.I., Semernikov E.A., Shmoilov V.I. Rekonfiguriruemye mul’tikonveiernye vychislitel’nye struktury (Reconfigurable multiconveyor computing structures), Rostov na Donu, YuNTs RAN, 2008, 320 p.
- Voevodin V.V., Voevodin Vl.V. Parallel’nye vychisleniya (Parallel computing), Sankt Petersburg, BKhV-Petersburg, 2004, 608 p.
- Suvorova E.A., Sheinin Yu.E. Proektirovanie tsifrovykh sistem na VHDL (Digital systems design with VHDL), Sankt Petersburg, BKhV-Petersburg, 2003, 576 p.
- Gubanov D.A., Steshenko V.B., Khrapov V.Yu., Shipulin S.N. Chip News, 1997, no. 9, pp. 26 — 33.
- Steshenko V.B. Komponenty i tekhnologii, 2000, no. 3, pp. 43 — 46.
- Nabatov A.N., Vedenyapin I.E., Mukhtarov A.R. Trudy MAI, 2018, no. 102. URL: http://trudymai.ru/eng/published.php?ID=99177
- Kondrashin M.A., Arsenov O.Yu., Kozlov I.V. Trudy MAI, 2016, no. 89. URL http://trudymai.ru/eng/published.php?ID=73411
- Kudryavtsev V.B., Podkolzin, A.S., Bolotov A.A. Osnovy teorii odnorodnykh struktur (Fundamentals of the homogeneous structures theory), Moscow, Nauka, 1990, 296 p.
- Dobryakov V.A., Engalychev A.N., Nazarov A.V. Trudy MAI, 2014, no. 72. URL: http://trudymai.ru/eng/published.php?ID=47562
- 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
- Zhang L., Wong T.N. Solving integrated process planning and scheduling problem with constructive metaheuristics, Information Science, 2016, vol. 340 — 341, pp. 1 — 16. DOI: 10.1016/j.ins.2016.01.001
- Zhang S., Wong, T.N. Integrated process planning and scheduling: An enhanced ant colony optimization heuristic with parameter tuning, Journal of Intelligent Manufacturing, 2018, vol. 29, pp. 585 — 601. URL: https://doi.org/10.1007/s10845-014-1023-3
- Bobyntsev D.O., Borzov D.B. Izvestiya Yugo-Zapadnogo gosudarstvennogo un iversiteta. Seriya: Upravlenie, vychislitel’naya tekhnika, informatika. Meditsinskoe priborostroenie, 2012, no. 2-1, pp. 27 — 31.
- Ore O. Teoriya grafov (Theory of graphs), Moscow, Nauka, 1968, 352 p.
- Masyukov I.I. Byulleten’ nauki i praktiki, 2016, no. 5, pp. 40 — 44. DOI: 10.5281/zenodo.54825
- Moiseev D.V., Chin’ 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
- Struchenkov V.I. Diskretnaya optimizatsiya. Modeli, metody, algoritmy resheniya prikladnykh zadach (Discrete optimization. Models, methods, and algorithms for solving applied problems), Moscow, Slon-Press, 2016, p.
- Golovitsyna M.V., Litvinov V.P. Metody, modeli i algoritmy v avtomatizirovannom proektirovanii promyshlennykh izdelii (Methods, models and algorithms in the computer-aided design of industrial products), Moscow, Infra-M, 2016, 284 p.
- Sigal I.Kh., Ivanova A.P. Vvedenie v prikladnoe diskretnoe programmirovanie: modeli i vychislitel’nye algoritmy (Introduction to Applied Discrete Programming: Models and Computational Algorithms), Moscow, FIZMATLIT, 2003, 240 p