APPLICATION OF DEVICES FOR PLANNING AND ASSESSMENT OF PLACEMENT QUALITY IN MATRIX MULTIPROCESSOR SYSTEMS OF HIGH AVAILABILITY
Abstract
The article discusses the topic of high-availability multiprocessor systems used in tasks such as
geolocation, targeting, atomic systems, forecasting, surveillance, tracking and others. When emergency
situations arise, such as a malfunction or failure of individual processor modules of the system, as well
as situations associated with operational impact on a multiprocessor system, there is a need for an urgent
response. A multiprocessor system can respond to emergency situations in a certain way, which
consists of scheduling the placement or relocation of parallel tasks. The placement planning problem is
formally defined as the process of mapping the vertices and arcs of a weighted digraph describing the
tasks being performed onto an irregular graph, which in turn represents the physical structure of a multiprocessor
system. When choosing the optimal transformation, special attention is paid to minimizing
the total weight of the arcs that reflect the relationships between completed tasks. This process is essentially
a more complex version of the graph search problem. It is important to emphasize that this type of
search is a classical NP-complete problem in graph theory. Beehive algorithms, genetic evolution, ant
colonies, and guillotine cutting are all popular methods for finding optimal placements that are not
suitable for this task because they mostly perform the search at the software level. In order for the system
to quickly respond to emergency situations, it must quickly perform calculations, which these methods
cannot allow. Therefore, an urgent task is to develop a method and algorithm for planning the
placement of tasks in matrix hypercubic multiprocessor systems of high availability. This work continues
the ideas presented in previously published works in this area in terms of combining search and calculation
steps to test intermediate options. Additional information in the form of relations of distances between
graph elements allows us to reduce the search, which is confirmed by testing on typical graphs.
References
BKhV–Peterburg. 2002, 608 p.
2. Korneev V.V. Parallel'nye vychislitel'nye sistemy [Parallel computing systems]. Moscow:
Nolidzh, 1999, 340 p.
3. Ore O. Teoriya grafov [Graph Theory]. Moscow: Nauka, 1968, 352 p.
4. Borzov D.B., Zotov I.V., Titov V.S. Patent RF №2193796. Ustroystvo dlya formirovaniya
suboptimal'nogo razmeshcheniya i ego otsenki [Patent RF No. 2193796. Device for the formation of
suboptimal placement and its evaluation]; Appl. 01/29/2001; publ. 11/27/2002, BI No. 33, 14 p.
5. Borzov D.B., Tiov V.S. Parallel'nye vychislitel'nye sistemy (arkhitektura, printsipy
razmeshcheniya zadach): monografiya [Parallel computing systems (architecture, principles of
task placement): monograph]. Kursk: Kurs. gos. tekh. un-t., 2009, 159 p.
6. Borzov D.B., Tiov V.S. Voprosy proektirovaniya i dinamicheskoy rekonfiguratsii topologii
sistem logicheskogo upravleniya v sistemakh vysokoy gotovnosti: monografiya [Issues of design
and dynamic reconfiguration of the topology of logical control systems in high readiness
systems: monograph]. Kursk: Yugo-Zapad.. gos. un-t., 2015, 282 p.
7. Borzov D.B. Apparatnye sredstva planirovaniya razmeshcheniya zadach v
mul'tiprotsessornykh sistemakh kriticheskogo naznacheniya (teoreticheskie osnovy):
monografiya [Hardware tools for scheduling tasks placement in critical multiprocessor systems
(theoretical foundations): monograph]. Kursk: Yugo-Zapad.. gos. un-t., 2018, 179 p.
8. Morozov K.K., Odinokov V.G., Kureychik V.M. Avtomatizirovannoe proektirovanie konstruktsiy
radioelektronnoy apparatury: ucheb. posobie dlya vuzov [Computer-aided design of electronic
equipment structures: Textbook for universities]. Moscow: Radio i svyaz', 1983, 280 p.
9. Kureychik V.M., Glushan' V.M. Shcherbakov L.I. Kombinatornye apparatnye modeli i
algoritmy v SAPR [Combinatorial hardware models and algorithms in CAD]. Moscow: Radio
i svyaz', 1990, 216 p.
10. Borzov D.B. Patent RF №2275681. Ustroystvo poiska nizhney otsenki razmeshcheniya v
matrichnykh sistemakh [Device for searching for a lower placement estimate in matrix systems];
Appl. October 6, 2004; publ. 04/27/2006, BI No. 12, 16 s.
11. Borzov D.B., Al'-Marayat B.I., Tipikin A.P. Akselerator planirovaniya razmeshcheniya zadach
v klasternykh vychislitel'nykh sistemakh vysokoy gotovnosti [Accelerator for task placement
scheduling in high-availability cluster computing systems], Izvestiya vuzov. Priborostroenie
[Izvestiya vuzov. Instrumentation], 2008, No. 2, pp. 29-33.
12. Borozov D.B. Babaskina A.Yu., Klyuchnikova O.E.Patent RF №2356085. Ustroystvo
podscheta znacheniya intensivnosti razmeshcheniya v polnosvyaznykh matrichnykh sistemakh
pri napravlennoy peredache informatsii [Patent RF No. 2356085. A device for calculating the
value of the placement intensity in fully connected matrix systems during directed information
transfer]; Appl. 1.10.2007; publ. 05/20/2009, BI No. 14, 17 p.
13. Borozov D.B. Patent RF №2398270. Ustroystvo poiska nizhney otsenki razmeshcheniya v
polnosvyaznykh matrichnykh sistemakh pri odnonapravlennoy peredache informatsii [Patent RF
No. 2398270. A search device for a lower location estimate in fully connected matrix systems
with unidirectional information transfer]; Appl. 02/11/2009; publ. 27.08.2010, BI 24, 21 p.
14. Borzov D.B., Chesnokova E.O. Patent RF №2398270. Ustroystvo poiska nizhney otsenki
razmeshcheniya v polnosvyaznykh matrichnykh sistemakh pri odnonapravlennoy peredache
informatsii [Patent RF No. 2398270. Device for searching for a lower location estimate in fully
connected matrix systems with unidirectional information transfer]; Appl. 02/11/2009; publ.
27.08.2010, BI 24, 21 p.
15. Borzov D.B., Bobyntsev D.O. Patent RF №2406135. Ustroystvo poiska nizhney otsenki
razmeshcheniya v sistemakh s matrichnoy organizatsiey pri napravlennoy peredache
informatsii [Patent RF No. 2406135. Device for searching for a lower estimate of placement in
systems with a matrix organization in the case of directed transmission of information]; Appl.
February 9, 2009, publ. 12/10/2010, BI No. 34, 12 p.
16. Borzov D.B., Chesnokova E.O., Marukhlenko A.L, A-A Mudzhib Mokhammed YAkh"ya. Patent
RF №2421805, Ustroystvo poiska nizhney otsenki razmeshcheniya v polnosvyaznykh
matrichnykh sistemakh pri dvunapravleno peredachi informatsii [Patent RF No. 2421805.
Search device for a lower location estimate in fully connected matrix systems for bidirectional
information transfer]; Appl. 11/24/2008, publ. 06/27/2011, 17 p.
17. Borzov D.B., Masyukov I.I., Titenko E.A. Patent na izobretenie RU 2688236, Ustroystvo dlya
podscheta minimal'nogo znacheniya intensivnosti razmeshcheniya v mnogoprotsessornykh
kubicheskikh tsiklicheskikh sistemakh pri odnonapravlennoy peredache informatsii [Patent for
invention RU 2688236. A device for calculating the minimum value of the placement intensity
in multiprocessor cubic cyclic systems with unidirectional information transfer]. 05/21/2019.
Appl. No. 2018120597 dated 06/05/2018.
18. Borzov D.B., Dyubryuks S.A. Patent RF №2628329. Ustroystvo dlya poiska minimal'nogo
znacheniya intensivnosti razmeshcheniya v toroidal'nykh sistemakh pri napravlennoy
peredache informatsii [Patent RF No. 2628329. Device for finding the minimum value of the
placement intensity in toroidal systems with directional information transfer]; Appl.
07/27/2016; publ. 08/15/2017, BI No. 23.
19. Borzov D.B., Zaikina T.A., B.I. Al'-Marayat, Khasan N.M. Patent RF №2323467. Ustroystvo
otsenki kachestva razmeshcheniya v sistemakh s matrichnoy organizatsiey [Patent RF No.
2323467. A device for assessing the quality of placement in systems with a matrix organization.];
Appl. January 9, 2007; publ. 04/27/2008, BI No. 12, 16 p.
20. Borzov D.B., Zholobov A.A. Patent RF №2279709. Ustroystvo dlya otsenki kachestva
razmeshcheniya v matrichnykh sistemakh [Device for assessing the quality of placement in matrix
systems / RF Patent No. 2279709]; Appl. 03/28/2005; publ. 07/10/2008, BI No. 19, 12 p.
