A.I. Makarov – Student, Smolensk State University
E-mail: al.makarov8@gmail.com
A.I. Mironov – Student, Smolensk State University
E-mail: konsylckat@gmail.com
V.I. Munerman – Ph.D.(Eng.), Associate Professor, Department of Informatics, Smolensk State University E-mail: vimoon@gmail.com
The article considers one way to ensure timely processing of data in high availability systems (HAS), which should provide the user with the opportunity to make timely decisions. The proposed method allows you to determine the number of computational resources in the HAS, which is sufficient to ensure parallelism at the task level. The solution to this problem is based on the problem of graph coloring. A method is proposed for constructing a graph of problems taking into account their interaction. The vertices of the graph are numbered from 1 to N, according to the number of tasks that the HAS decides. An edge between vertices means that these two tasks can be executed in parallel, since none of them should wait for the results of the other. It is proved that in order to determine the minimum number of computational means, it is sufficient to determine the minimum possible number of colors for the coloring of the graph of problems. Additional requirements may be imposed on tasks. For example, tasks i, j, k can only be performed on one dedicated computing facility. It is shown that in order to take into account additional conditions in the original graph, we need to add a complete subgraph of k vertices, where k is the size of the largest complete subgraph of the original graph. It is proved that for distribution of tasks between computing facilities in the system it is enough to get a coloring of the corresponding graph. The minimum number of computers is equal to the minimum possible number of colors for coloring. An estimate of this number χ(G) ≤ ω(G) + 1 (ω(G) is the clique number of the graph). An example of the solution of the problem is given. It is concluded that the proposed method allows to determine the number of computational means sufficient to effectively implement parallelism at the task level with a load close to the maximum.
- Budzko V.I. Ot redaktora // Sistemy vysokoy dostupnosti. 2013. № 1. S. 4−5.
- Karpov D.V. Teoriya grafov. 2009. 467 s. URL = https://logic.pdmi.ras.ru/~dvk/graphs_dk.pdf.