ПРИМЕНЕНИЕ УСТРОЙСТВ ПЛАНИРОВАНИЯ И ОЦЕНКИ КАЧЕСТВА РАЗМЕЩЕНИЯ В МАТРИЧНЫХ МУЛЬТИПРОЦЕССОРНЫХ СИСТЕМАХ ВЫСОКОЙ ГОТОВНОСТИ
Аннотация
Рассматривается тема мультипроцессорных систем высокой готовности, применяю-
щихся в таких задачах, как геолокация, прицеливание, атомные системы, прогнозирование на-
блюдение, слежение и другие. При возникновении таких внештатных ситуаций, как неисправ-
ность или отказ отдельных процессорных модулей системы, а также ситуаций, связанных с
оперативным воздействием на мультипроцессорную систему, возникает необходимость срочного реагирования. Мультипроцессорная система может реагировать на внештатные ситуа-
ции определенным способом, который заключается в планировании размещения или переразме-
щения параллельных задач. Задача планирования размещения формально определяется как про-
цесс отображения вершин и дуг взвешенного орграфа, описывающего выполняемые задачи, на
нерегулярный граф, который в свою очередь представляет физическую структуру мультипро-
цессорной системы. При выборе оптимального преобразования особое внимание направлено на
минимизацию общего веса дуг, которые отражают связи между завершенными задачами.
Этот процесс, по сути, представляет собой более сложную версию задачи поиска на графе.
Важно подчеркнуть, что такой вид поиска является классической NP-полной задачей в теории
графов. Алгоритмы пчелиного улья, генетическая эволюция, муравьиные колонии и метод гиль-
отинного разреза – все эти популярные методы поиска оптимального размещения не подходят
для данной задачи, так как основном выполняют поиск на уровне программного обеспечения.
Для того чтобы система оперативно реагировала на внештатные ситуации, она должна бы-
стро выполнять вычисления, чего данные методы позволить не могут. Следовательно, акту-
альной задачей является разработка метода и алгоритма планирования размещения задач в
матричных гиперкубических мультипроцессорных системах высокой готовности. Эта работа
продолжает идеи, представленные в ранее опубликованных работах по данному направлению в
части совмещения поисковых и расчетных шагов для проверки промежуточных вариантов.
Дополнительная информация в виде отношений расстояний между элементами графа позволя-
ет сократить перебор, что подтверждается проверкой на типовых графах.
Литература
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.
