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.