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.