Current approaches in parallel processing of requests used in modern distributed information systems are considered. The multilevel scheme of balancing the resources of the infrastructure of the distributed information system based on the graph of tasks is constructed. Methods for estimating the optimization of the graph of problems based on the indicators of the length of the normalized graph and the normalized energy distribution are determined. Mathematical modeling is performed for calculation methods by hierarchical structure, algorithms for graph partitioning, methods based on algebraic graph theory, and structuring of the type "Diamond Dags" with uniform, binomial, and geometric distributions. A comparison of the results of mathematical modeling with statistical data showed the level of adequacy of the developed mathematical model. Distributed information networks, task graphs, normalized energy consumption, normalized schedule length, partitioning algorithms, linear algebra task graphs, diamond dags structuring Number of working stations (servers) ∈ [1; ] at the border of the DIN infrastructure (server Number of CPU cores ∈ [1; ] i CPU clock frequency for all і . Number of central processing units (CPU) servers in the complex ∈ [1; ] for all ; Increase in productivity of DIN fields , , CMiGIN 2022: 2nd International Conference on Conflict Management in Global Information Networks, November 30, 2022, Kyiv, Ukraine
complex);
Today, the methodology of organization, optimization, and scaling of distributed information network systems (DIN) includes both analysis of the components of the hardware platform and the definition of methods for organizing multithreaded architecture, virtualization of hardware resources, and implementation of energy-saving measures. The components of the hardware platform can be considered at the level of the following four-level hierarchy, which allows you to determine the computing resources of DIN: і , so in the implementation of parallel processing procedures through the implementation of methods of flexible processing robots with input power supplies. On the basis of a basic model, the procedure of parallel processing can be formalized through the introduction of offensive functions and indicators (Fig. 1):
A complete set of tasks and a set of tasks with limited priority; Size of tasks, maximum requirements and work to perform the task; A graph of tasks for which the tasks act as edges.Consider a complete set of tasks { }, where ∈ [1; ], and a set of tasks with sequencing { }, where ∈ [1; ], moreover precedes , that is ≺ ; accordingly, the function of the task graph is defined as ( , ). For each task with ∀ you can determine the number of processor cores , used and the average frequency of the respective processors , as well as the size of the task and an indicator of the maximum level of requirements , which corresponds to the total number of commands to be executed (Fig. 1). Based on these indicators, the work of the task can be defined as a product = ∙ .
Analysis of current research in this area [
The results of practical research on the application of algorithms for splitting graphs in order to
balance the load DIN [
Fundamental aspects of working with graph models used in distributed networks were also identified
[
Thus, the task of the study is to build a model for calculating the length of the normalized graph of tasks and normalized energy distribution for the actual types of structure of the graph of tasks and distribution methods, as well as determining the accuracy of the corresponding mathematical modelling.
Let us present the basic model of the DIN hardware platform as an average set of CPUs, the cores of which are identical and are characterized by the same clock frequency. coefficient. The advantage of this approach is the ability to build a relatively simple mathematical apparatus that can be further improved for a specific practical problem. A set of incoming requests { }, processed by the specified hardware and software complex can be divided according to a set of graphs and the same multicore { } where ∈ [1; ] and >
. The procedure for optimizing graphs of problems is that for i restrictions on the size of the graph of tasks . parallel size problems , characterized by requirements , determine the minimum size of the graph of tasks T by calculating the set of robot tasks { } subject to restrictions on the full value of the system energy . Similarly, it is necessary to determine the minimum energy function , subject to 2.1.
The task graph as a directed acyclic graph can be decomposed on ∈ [1; ] lists. When building a turn, includes three-tier hierarchical system, each of levels is divided into ∈ [1; ] groups, each of which, in ∈ [1; ] subgroups. In this case, all tasks that are on the same level are performed independently of each other. The size of the task of the group and subgroup is determined by the number of cores used to perform it: (1) [ ∈ [
+ 1 ; ] ∈ [
+ 1 ; 1 ≥ ⋯ ≥ ≥ ⋯ ≥ (LRF: Largest Requirement First); following algorithms for organizing the planning list: where — the number of cores to perform tasks in the list , — the number of cores to perform tasks in a group , — the number of cores to perform tasks in a subgroup . Thus, scheduling the process of performing parallel group tasks, each of which is characterized by a set of task sizes and a set of maximum requirements can be represented as building a list of consecutive tasks on the appropriate number of processors, where each task is characterized by maximum processor requirements. The calculation of optimal values і is performed after clustering of CPU cores in relation to the specified hierarchical structure on the basis of values , та . Thus, we can offer the Planning the size of the task: 1 ≤ ⋯ … ≤ (SRF: Smallest Requirement First) and Planning according to the level of maximum requirements: 1 ≤ ⋯ ≤ ≤ ⋯ ≤ (SSF: Smallest Size First) and 1 ≥ ⋯ ≥ ≥ ⋯ ≥ (LSF: Largest Size First);
Planning for the amount of work to be done: 1 ≤ ⋯ ≤ ≤ ⋯ ≤ (SWF: Smallest Work First) and 1 ≥ ⋯ ≥ ≥ ⋯ ≥ (LWF: Largest Work First).
According to the selected algorithm, a single task is distributed to the cluster of the virtualized DIN system until the cluster overflows, after which there is a transition to the next cluster. 2.2.
The presented three-level scheme of task clustering forces to optimize DIN by searching for the minimum values of the graph length and the level of total power consumption for lists, groups and subgroups of the task graph. This corresponds to four levels of DIN hardware resource optimization: Optimization of the allocation of hardware resources DIN within one subgroup of tasks ; Optimization of the allocation of hardware resources DIN at the level of interaction between task groups { }; task lists { };
Optimization of the allocation of hardware resources DIN at the level of interaction between Optimization of the allocation of hardware resources DIN at the level of interaction between = ∙ =
( = ∙
( = −1 ∙ 1 1 −1 , , 1 ) 1 1 )
−1 , (2) (3) (4) (5)
The simplest step is the first level of optimization, the execution of tasks within the subgroup is carried out sequentially, and the length of the list of tasks of the subgroup is minimized at the appropriate values і . The second level considers the interaction between subgroups of tasks. The set of cores is divided into clusters, and the share of power of each cluster is determined by their total number. Each cluster is considered as a separate element designed to handle a single task, respectively, the full set of tasks is divided into
subgroups. Similarly, at the third level, task optimization is target values are minimized і for to-do lists { }: performed for everyone groups of a separate list . Finally, for the fourth level of optimization, the where is the multicore coefficient, which is the same for all CPUs of the server complex, or its average value. Based on this, the target functions of the normalized graph of tasks (NSL: Normalized Schedule Length) and the normalized energy distribution (NEC: Normalized Energy Consumption) can be determined:
∑ =1 (∑ =1 ((∑ =1
( , , ∙ ( , , ) )) )) ∑ =1 ((∑ =1
( , , ∙ ( , , ) )) ) ∑ =1 (∑ =1 (∑ =1
( , , ∙ ( , , ) ))) ∑ =1 (∑ =1 ((∑ =1
( , , ∙ ( , , ) )) )) ∑ =1 (∑ =1 (∑ =1
( , , ))) (∑ =1 (∑ =1 ((∑ =1
( , , ∙ ( , , ) )) ))) ∑ =1 (∑ =1 (∑ =1 ( , , ))) Thus, the optimization procedure can be performed by calculating the extremes (minima) of the objective functions, the arguments of which are the parameters of the DIN hardware platform and a set of input queries.
In order to verify the presented approach to DIN load balancing, mathematical modeling was
performed for such typical methods of working with graphs of tasks as methods of calculation by
hierarchical structure, algorithms for partitioning graphs (Partitioning Algorithms), methods based on
algebraic graph theory (Linear Algebra Task Graphs) structuring type "Diamond Dags". The obtained
results of mathematical modeling were further compared with statistical data [
Mathematical modeling of objective functions is carried out і from the expected size of the problem for methods of calculation by hierarchical structure, which is the simplest approach to optimize load balancing, is presented in Fig. 2 (for normal distribution), fig. 3 (for binomial distribution) and fig. 4 (for geometric distribution).
The maximum relative error between the experimental values and the results of mathematical modeling for is = 4,1%, and for — = 7,1%, therefore, the maximum relative error in calculating the graph in accordance with the hierarchical structure of a uniform distribution is = 7,1%.
Similarly, modeling for a binomial distribution should be considered.
The maximum relative error between the experimental values and the results of mathematical modeling for is = 16,8%, and for — = 4%, therefore, the maximum relative error in calculating the graph in accordance with the hierarchical structure of the binomial distribution is = 16,8%. Accordingly, the accuracy of the simulation in this case is unacceptable.
Finally, the simulation results for the geometric distribution should be considered:
The maximum relative error between the experimental values and the results of mathematical modeling for is = 3,7%, and for — = 0,6%, and therefore the maximum relative error in calculating the graph in accordance with the hierarchical structure of the geometric distribution is = 3,7%. 3.2. Calculation of the graph of tasks according to the algorithms of graph partitioning
Mathematical modeling of objective functions is more complicated і from the expected task size for graph partitioning algorithms, which is presented in Fig. 5 (for normal distribution), fig. 6 (for binomial distribution) and fig. 7 (for geometric distribution).
The maximum relative error between the experimental values and the results of mathematical modeling for is = 3,4%, and for — = 8,6%, therefore, the maximum relative error of the graph calculation in accordance with the algorithms for dividing the graph by a uniform distribution is = 8,6%.
For the binomial distribution of dependence і from are also similar.
The maximum relative error between the experimental values and the results of mathematical modeling for is = 9%, and for — = 2,3%, and therefore the maximum relative error in calculating the graph in accordance with the algorithms for dividing the graph by the binomial distribution is = 9%.
Similarly, for the geometric distribution there is a similarity of dependencies і from . Also in this case, the values of relative errors are close.
The maximum relative error between the experimental values and the results of mathematical modeling for is = 6,1%, and for — = 4%, therefore, the maximum relative error in calculating the graph in accordance with the algorithms for dividing the graph by geometric distribution is = 6,1%. 3.3.
Application of algebraic graph theory as a direction within which algebraic methods are used in theoretical-graph problems, which provides an opportunity to conduct accurate mathematical modeling of objective functions і from the expected size of the task. The results of modeling, which was carried out in this study, are presented in Fig. 8 (for normal distribution), fig. 9 (for binomial distribution) and fig. 10 (for geometric distribution). from when calculating a graph based on the algebraic
from when calculating a graph based on algebraic
The maximum relative error between the experimental values and the results of mathematical modeling for is = 4,1%, and for — = 9,5%, and therefore the maximum relative error of the calculation of the graph in accordance with the algorithms for dividing the graph by a uniform distribution is = 9,5%.
The lowest value of the maximum relative error in this case is characterized by the binomial distribution.
(a)
The maximum relative error between the experimental values and the results of mathematical modeling for is = 3%, and for — = 1,8%, therefore, the maximum relative error in calculating the graph in accordance with the algorithms for dividing the graph by the binomial distribution is = 3%.
On the other hand, for the geometric distribution, the value of the maximum relative error is unacceptably large. from when calculating a graph based on the
The maximum relative error between the experimental values and the results of mathematical modeling for is = 6,8%, and for — = 12,7%, therefore, the maximum relative error in calculating the graph in accordance with the algorithms for dividing the graph by geometric distribution is = 12,7%. 3.4.
Finally, consider the results of modeling the objective functions і from the expected size of the task when structuring by the method of "Diamond Dags", which today is considered as an extremely relevant approach for most practical tasks. The results of modeling, which was carried out in this study, are presented in Fig. 11 (for normal distribution), fig. 12 (for binomial distribution) and fig. 13 (for geometric distribution).
(a) (b)
The maximum relative error between the experimental values and the results of mathematical modeling for is = 5%, and for — = 19%, therefore, the maximum relative error of the graph calculation in accordance with the algorithms for dividing the graph by a uniform distribution is = 19%, which is unacceptable.
The smaller value of the maximum relative error is characterized by the binomial distribution.
The maximum relative error between the experimental values and the results of mathematical modeling for is = 3,8%, and for — = 2,6%, and therefore the maximum relative error in calculating the graph in accordance with the algorithms for dividing the graph by the binomial distribution is = 3,8%.
In this case, for the geometric distribution, the value of the maximum relative error, again, is unacceptably large.
The maximum relative error between the experimental values and the results of mathematical modeling for is = 6,8%, and for — = 15,6%, therefore, the maximum relative error in calculating the graph in accordance with the algorithms for dividing the graph by geometric distribution is = 15,6%.
As a result of the study, the current approaches in the field of parallel processing of requests for distributed information systems were identified. To summarize the problems typical for this area and methods for their solution, a multilevel scheme of balancing the resources of the infrastructure of a distributed information system based on the graph of tasks was built. Thus, the methods of estimating the optimization of the task graph in accordance with the indicators of the length of the normalized graph and the normalized energy distribution were determined. The stage of mathematical modeling was carried out for methods of calculation by hierarchical structure, algorithms for graph partitioning, methods based on algebraic graph theory and structuring of the type "Diamond Dags" with uniform, binomial and geometric distributions. Comparison of the results of mathematical modeling with the statistical data of the relevant studies showed a fairly high level of adequacy of mathematical model.