RU2749336C1 - Method for forming federation of computers - Google Patents

Abstract

FIELD: computer technology.SUBSTANCE: invention relates to the field of computer technology. The technical result is achieved by the fact that the method of forming a federation of calculators includes the following stages: 1) providing a set of calculators that are candidates for federations, 2) forming a set of benchmarks intended for execution on each computer from a set of calculators formed at stage 1), 3) serial execution of a set of benchmarks on each computer with the definition and fixation of the execution time of each benchmark from the set, 4) determination of the average execution time in a series of each benchmark separately and of the entire set of benchmarks as a whole on each computer from a set of computers, 5) determination of the Pearson correlation coefficient for all pairs calculators that make up the set at step 1), 6) the formation of groups of calculators, including all pairs of calculators having a Pearson correlation coefficient (PCC) greater than a predetermined value, 7) determination in each group of calculators formed in step 6), a calculator characterized by a minimum the average time for the execution of a set of benchmarks, determined in step 4), 8) the formation of a federation from the computers defined in step 7) with the exception of their duplication.EFFECT: possibility of maximum coverage of the classes of problems to be solved with a minimum number of calculators included in the complex.6 cl, 3 tbl, 1 dwg

Description

The technical field to which the invention relates

The claimed invention relates to the field of computer technology, namely to networked computer technologies that allow combining and using computing resources of various types for interdisciplinary research, for example, in the field of bioinformatics, bioengineering, space research, medicine, physics, etc. Different areas of research often require the use of computers of various types, as a result of which the task of combining computing resources into a single system working on solving one problem becomes extremely urgent. The choice of computers for the formation of such a system (federation) is a non-trivial process that requires the use of specialized hardware and software solutions.

State of the art

At this stage, the development of many high-tech branches of science and technology implies the use of high-performance data processing systems. For such tasks, modular computing systems (federations) are used, consisting of separate servers, the computing resources of which are combined into a single whole by means of special software. The following federations of calculators are known in the art:

1) GENI [Hwang, T. (2017, March). NSF GENI cloud enabled architecture for distributed scientific computing. In 2017 IEEE Aerospace Conference (pp. 1-8). IEEE.] - is an open infrastructure for large-scale networked and distributed systems of research and education that spans the United States. The project allows computing resources to be sourced from locations throughout the United States;

2) Federation of Cloud Computing EGI (EU, Holland) - an infrastructure for conducting scientific interdisciplinary research based on the principles of federation by combining computing power, ICT resources;

Known federations do not provide the ability to group their constituent federates (calculators) according to the classes of executable programs, as a result of which there is no possibility of priority execution of this or that program by the calculator of the corresponding class, that is, all federates have equal priority for tasks of any class. Thus, on each computer of the federation it is possible to launch a program of any class. In this case, the programs executed by this or that federation are not associated with certain classes, since after the results of the program execution are received, information about the program class becomes redundant, its repeated starts are unlikely. However, in the absence of such a grouping of federates according to the classes of executable programs, the completeness of the federation may decrease, as a result of which the federation will be less efficient.

There is a known method for determining the composition of the federation, which ensures optimal power consumption of a set of computers (US8225119, Energy-aware server management, Microsoft Technology Licensing LLC, https://patents.google.com/patent/US8225119). This approach manages power consumption in a server farm by switching individual servers between active and inactive states, while maintaining response times for the server farm at a predetermined level. For this, when implementing the method, depending on the expected load, it was determined which computers should be turned on (the rest of the computers were turned off). Thus, we made a choice of a subset of computers that determine the composition of the computing complex for the state of the system at a certain point in time. To determine the composition of the federation, the future workload is predicted for the set of servers that will be included in the federation.

The closest in technical essence to the claimed method is a method for determining the optimal composition of a federation of calculators, based on information about the current workload and power of calculators. With this approach, the programs are classified according to their expected duration of execution, after which the programs that require a longer duration of time for implementation are sent for execution to the most powerful of the least loaded computers of the federation. With this approach, the calculators are grouped by power, and the program classes correspond to the levels of program execution duration.

However, the disadvantage of this method is the fact that this approach does not ensure the achievement of the completeness of the federation, that is, the ratio of the number of groups of calculators designed to solve certain classes of problems and having a size greater than a given one to the total number of calculators that make up the federation, since for each program separately the optimal is to direct it for execution on the most powerful of the least loaded computers of its class, as a result of which the composition of the federation is formed from the most powerful computers, which can lead to duplication of classes of calculators, and, as a result, to a decrease in the completeness of the federation, as well as the efficiency of its functioning in further. Thus, the programs of some classes cannot be executed in such a federation, in the case when these classes correspond to less powerful computers that will not be included in the federation. As a result, the known method of forming a federation of calculators does not ensure the optimality of its composition and, accordingly, does not cover the possibility of executing programs from the maximum possible number of classes.

The technical problem solved by the claimed invention consists in the need to overcome the disadvantages inherent in the known methods of forming federations of calculators by creating a method for determining such a composition of a federation of calculators, which will ensure the representation of as many program classes as possible with the least number of computers, taking into account that one calculator can belong to several classes.

Brief disclosure of the essence of the invention

The technical result achieved when using the claimed invention is to provide the possibility of maximum coverage of the classes of tasks to be solved (the maximum possible number of executable programs of different classes) with a minimum number of computers included in the complex, which corresponds to an increase in the completeness of the federation by eliminating duplication of computers intended for solving problems from various classes, when creating a federation, and adding new calculators that provide the ability to solve problems from new classes (additional coverage of classes). The inventive method ensures the selection of a subset of calculators from a plurality of computers in such a way that the composition of the federation of calculators is selected that is optimal in terms of the ratio of the number of federation participants to the number of different classes, i.e. maximum coverage of software classes is ensured with a minimum number of calculators. The increase in completeness is achieved by the fact that calculators that duplicate existing classes are not included in the federation, and calculators that define new classes are included.

The claimed technical result is achieved by the method of forming a federation of calculators of the optimal composition includes the following stages:

1) providing a set of calculators who are candidates for federations,

2) the formation of a set of benchmarks intended for execution on each computer from the set of computers formed at stage 1),

3) serial execution of a set of benchmarks on each calculator with the definition and fixation of the execution time of each benchmark from the set,

4) determination of the average execution time in a series of each benchmark separately and the entire set of benchmarks as a whole on each computer from a set of computers,

5) determination of the Pearson correlation coefficient for all pairs of calculators that make up the set at step 1),

6) the formation of groups of calculators, including all pairs of calculators having a Pearson correlation coefficient (KKP) greater than a predetermined value,

7) determination in each group of calculators formed at step 6) a calculator characterized by the minimum average execution time of a set of benchmarks determined at step 4),

8) formation of a federation from the calculators defined in step 7) with the exception of their duplication. When forming a set of benchmarks at stage 2), benchmarks belonging to different classes of programs are selected. A benchmark run involves at least three runs of a set of benchmarks on each cleaner tested. At stage 6), the cliques formation algorithm is used to form groups of calculators. The Bron-Kerbosch algorithm can be used as an algorithm for generating clicks. The threshold value of the Pearson correlation coefficient is in the range from 0.5 to 0.99.

Brief Description of Drawings

The claimed invention is illustrated by the following drawings, where

FIG. 1 shows a graph, the vertices of which are the calculators that are candidates for the federation being created, and the edges are connected to the calculators, the PCC between which exceeds a predetermined threshold value (in the example, equal to 0.75).

Terminology used

For a better understanding of the claimed essence of the invention, below are the main terms and definitions used in the following description.

Federation is a computing environment in which all members can share and / or use each other's computing resources.

Federates are members of the federation.

A candidate for federation is a potential member of the federation.

Benchmark is a benchmark test of the performance of a computer system (program).

Pearson's correlation coefficient [http://www.machinelearning.ru/wiki/index.php?title=%D0%9A%D0%BE%D1%8D%D1%84%D1%84%D0%B8%D1%86 % D0% B8% D0% B5% D0% BD% D1% 82_% D0% BA% D0% BE% D1% 80% D1% 80% D0% B5% D0% BB% D1% 8F% D1% 86% D0 % B8% D0% B8_% D0% 9F% D0% B8% D1% 80% D1% 81% D0% BE% D0% BD% D0% B0] characterizes the existence of a linear relationship between two quantities.

,Let two samples of size m be given:

,

Pearson's correlation coefficient is calculated by the formula:

- выборочные средние

и

,

.Where

- the sample mean is,

and

,

...

Pearson's correlation coefficient is also called the closeness of the linear relationship:

линейно зависимы,

linearly dependent,

линейно независимы.

linearly independent.

Algorithm for the formation of cliques - an algorithm that determines in an undirected graph all complete subgraphs, maximum by inclusion.

There are several known such algorithms, you can choose any of them, this does not affect the essence of the invention. One of the most efficient algorithms for generating clicks is the Bron-Kerbosch algorithm (https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8% D1% 82% D0% BC_% D0% 91% D1% 80% D0% BE% D0% BD% D0% B0_% E2% 80% 94_% D0% 9A% D0% B5% D1% 80% D0% B1% D0% BE% D1% 88% D0% B0).

The algorithm operates on three sets of graph vertices:

• The set compsub is a set containing at each step of the recursion the complete subgraph for this step. It is built recursively.

• Candidate set - set of vertices that can increase compsub.

• Set not - the set of vertices that were already used to expand compsub in the previous steps of the algorithm.

The algorithm is a recursive procedure applied to these three sets.

PROCEDURE extend ( candidates , not ):

UNTIL candidates is not empty and does not contain the vertex not connected to all the vertices of candidates,

PERFORM :

1 Select vertex v from candidates and add it to compsub

2 Form new_candidates and new_not , removing from candidates and not vertices that are not CONNECTED with v

3 IF new_candidates and new_not are empty

4 TO compsub - click

5 AKA recursively call extend (new_candidates, new_not)

6 Remove v from compsub and candidates , and place it in not .

The completeness of the federation is the ratio of the number of clicks with a size greater than the specified one to the number of calculators that make up the federation.

Class - a sequence of time intervals of a given width that defines a measuring scale in which the size of the interval is a unit of measurement.

In essence, the claimed method is reduced to the selection of federates from a plurality of candidates for federations in order to maximize the completeness of the federation or to obtain an estimate of the completeness for the existing federation.

Implementation of the invention

1. To implement the claimed invention at the first stage of the method, a plurality of calculators are formed, which are candidates for federations. As calculators united in such federations, one can use, for example, clusters, which are distributed systems of computers, supercomputers or cloud IT resources. Each calculator is assigned an identification number, as well as its main characteristics (processor speed, memory size, etc.) are recorded.

2. Then, from a certain known set of benchmarks, a set of benchmarks is determined, which they plan to run on each of the calculators of the set formed above. Typically, a set of benchmarks includes up to 15 testing programs. Popular benchmarks are considered, consisting of programs of various subject areas [https://www.spec.org/auto/accel/Docs/#Benchmark%20Documentation]. For example, commonly used and specific to their areas are:

• 503.postencil - Thermodynamics (https://www.spec.org/auto/accel/Docs/503.postencil.html)

• 504.polbm - Computational Fluid Dynamics, lattice Boltzmann method (https://www.spec.org/auto/accel/Docs/504.polbm.html)

• 514.pomriq - Medicine (https://www.spec.org/auto/accel/Docs/514.pomriq.html)

• 550.pmd - Molecular Dynamics (https://www.spec.org/auto/accel/Docs/550.pmd.html)

• 551.ppalm - Large Eddy Simulation, Atmospheric Turbulence (https://www.spec.org/auto/accel/Docs/551.ppalm.html)

• 552.pep - Extreme Concurrency (https://www.spec.org/auto/accel/Docs/552.pep.html)

• 553.pclvrleaf - Accurate Fluid Dynamics (https://www.spec.org/auto/accel/Docs/553.pclvrleaf.html)

• 554.pcg - Conjugate Gradient (https://www.spec.org/auto/accel/Docs/554.pcg.html)

• 555.pseismic - Seismic Wave Modeling (https://www.spec.org/auto/accel/Docs/555.pseismic.html)

• 556.psp - Scalar Penta-Diagonal Solver (https://www.spec.org/auto/accel/Docs/556.psp.html)

• 557.pcsp - Scalar Penta-Diagonal Solver (https://www.spec.org/auto/accel/Docs/557.pcsp.html)

• 559.pmniGhost - Finite Differences (https://www.spec.org/auto/accel/Docs/559.pmniGhost.html)

• 560.pilbdc - Fluid Mechanics (https://www.spec.org/auto/accel/Docs/560.pilbdc.html)

• 563.pswim - Weather (https://www.spec.org/auto/accel/Docs/563.pswim.html)

• 570.pbt - Block-Three-Diagonal Solver for 3D PDE (https://www.spec.org/auto/accel/Docs/570.pbt.html).

3. As a result of running each benchmark from the set on each calculator, the time of its execution is recorded and correlated with the identification number of the calculator. On each calculator, a series of at least three runs of the generated set of benchmarks is performed from a plurality of calculators.

4. The results of the benchmark execution are sent to the federation architect, who forms a table of the results of benchmark runs on the computers, which is a matrix with averaged run results, in the columns of which are the identification numbers of the computers, in the rows - the ordinal numbers of the benchmarks. Each cell of the results matrix contains the average execution time of the benchmark on the calculator (sec.) (See Table 1).

Table 1

0 one 2 3 four five 6 7 eight nine 10 eleven 12 13 fourteen fifteen sixteen 17 eighteen nineteen twenty 21 22 23 24 0 288.9 15.4 14.5 72.0 2333.8 27.3 520.8 106.8 154.4 64.2 73.0 41.9 53.7 48.2 43.9 114.6 29.8 47.6 15.4 44.7 243.0 107.3 63.9 48.6 35.1 one 197.8 25.9 25.6 52.7 459.7 19.0 268.4 83.2 157.4 60.2 53.1 24.2 36.6 39.7 22.6 83.6 30.3 31.1 25.8 40.3 169.5 122.6 65.8 39.8 36.5 2 1376.2 128.5 112.9 309.6 3382.0 259.0 19732.3 509.3 226.1 505.7 364.7 2147.0 229.0 288.0 292.9 733.5 97.7 214.3 122.3 181.6 659.3 621.1 359.8 213.5 109.2 3 378.7 30.5 30.2 92.8 1182.6 61.6 1328.6 214.5 57.1 131.0 109.1 611.6 57.6 83.5 77.5 245.6 26.2 44.7 29.7 51.0 168.9 240.9 115.8 58.3 32.4 four 463.4 149.7 139.7 230.3 2105.3 537.2 689.2 184.2 5223.6 199.0 269.6 223.4 5182.0 180.6 4654.3 342.1 191.4 194.5 152.8 209.8 282.1 553.6 259.8 4961.5 194.3 five 374.5 56.3 57.5 94.3 434.0 76.4 510.0 215.5 96.2 167.5 112.3 151.5 64.7 85.2 97.4 253.2 46.6 74.6 56.2 70.0 160.2 230.1 100.2 58.4 50.9 6 806.7 202.5 199.6 256.7 4320.0 90.0 1314.6 338.9 578.8 280.0 258.8 132.8 165.7 170.7 102.9 379.6 138.5 164.8 202.1 166.3 672.7 1170.0 266.7 107.0 163.4 7 154.5 60.8 50.5 61.9 1325.1 135.3 255.6 87.0 211.6 73.1 73.1 49.1 213.5 54.0 210.9 101.6 56.7 53.0 57.4 53.0 101.1 329.0 59.0 195.5 60.3 eight 434.8 107.9 105.7 130.8 967.0 48.1 760.8 189.7 271.0 158.9 132.3 78.9 101.1 94.1 51.2 236.8 74.3 91.0 107.6 91.1 286.8 282.3 135.8 216.9 86.7 nine 251.9 54.2 52.6 81.5 2360.5 34.7 486.6 109.6 185.0 86.4 82.7 52.2 64.7 56.6 42.5 139.3 44.8 55.3 53.9 52.7 143.4 815.7 84.3 49.9 52.8 10 262.8 54.9 53.5 83.0 2248.6 45.6 491.6 116.3 239.1 80.2 84.4 44.8 65.6 62.0 55.9 126.4 46.7 60.8 54.5 53.9 136.7 875.9 87.0 64.7 54.8 eleven 469.9 90.6 87.3 126.3 12351.9 57.7 1468.0 187.0 402.1 118.6 126.6 67.0 210.1 94.1 68.0 221.3 70.0 94.1 90.1 93.4 304.7 398.5 127.3 98.0 79.5 12 879.0 165.5 162.6 265.5 1722.9 64.9 1818.3 547.8 344.4 182.8 266.2 120.4 80.0 183.5 76.8 441.7 119.8 157.7 165.1 154.7 585.2 663.4 287.4 79.8 140.3 13 244.6 42.4 41.8 75.2 5674.1 29.5 552.9 106.6 170.6 99.4 74.8 31.8 58.1 48.8 32.8 99.2 37.7 46.0 42.5 47.3 122.0 173.3 80.2 64.1 46.9 fourteen 177.7 28.7 28.0 51.1 4054.0 26.2 555.7 67.1 79.0 42.0 52.6 55.0 51.4 35.4 30.8 101.7 25.3 32.7 28.7 32.2 77.4 781.8 47.7 55.5 29.7

Thus, as a result of the execution of this stage, data is obtained on the average execution time of a particular test on each calculator from the selected set, as well as the average execution time of each testing program on each calculator.

5. The calculators are grouped in accordance with the following criterion:

All calculators that make up the set formed in step 1) are combined in pairs, and for each pair of calculators, the Pearson correlation coefficient (CPC) is determined by columns with the corresponding benchmark execution times (see Table 2). If the PCC exceeds a predetermined threshold value, this means that there is a linear dependence between the calculators in terms of the execution time of a given set of benchmarks on them. In Table 2, the columns and rows represent the identification numbers of the federated candidate calculators. Accordingly, the cells contain the value of the KKP, defined for each pair of calculators.

table 2

0 one 2 3 four five 6 7 eight nine 10 eleven 12 13 fourteen fifteen sixteen 17 eighteen nineteen twenty 21 22 23 24 0 1.00 0.72 0.70 0.92 0.11 0.35 0.82 0.93 0.06 0.94 0.93 0.78 0.04 0.95 0.05 0.98 0.56 0.86 0.70 0.79 0.92 0.35 0.93 0.03 0.60 one 0.72 1.00 1.00 0.90 0.12 0.48 0.28 0.73 0.41 0.66 0.85 0.23 0.36 0.80 0.35 0.72 0.90 0.89 1.00 0.91 0.84 0.57 0.86 0.35 0.94 2 0.70 1.00 1.00 0.88 0.12 0.44 0.23 0.73 0.39 0.63 0.83 0.18 0.33 0.77 0.33 0.69 0.89 0.86 1.00 0.88 0.84 0.58 0.84 0.33 0.93 3 0.92 0.90 0.88 1.00 0.08 0.56 0.61 0.89 0.37 0.87 0.99 0.58 0.34 0.97 0.34 0.93 0.83 0.97 0.89 0.95 0.93 0.46 1.00 0.33 0.86 four 0.11 0.12 0.12 0.08 1.00 -0.08 0.07 -0.00 -0.04 0.03 0.04 -0.02 -0.06 0.04 -0.09 0.02 0.05 0.09 0.12 0.08 0.14 0.13 0.04 -0.08 0.07 five 0.35 0.48 0.44 0.56 -0.08 1.00 0.32 0.24 0.90 0.48 0.63 0.37 0.91 0.61 0.92 0.49 0.78 0.71 0.49 0.75 0.26 0.13 0.58 0.91 0.71 6 0.82 0.28 0.23 0.61 0.07 0.32 1.00 0.63 -0.07 0.86 0.68 0.97 -0.05 0.76 -0.03 0.82 0.20 0.60 0.26 0.48 0.59 0.14 0.65 -0.05 0.21 7 0.93 0.73 0.73 0.89 -0.00 0.24 0.63 1.00 0.01 0.80 0.87 0.60 -0.02 0.88 -0.00 0.91 0.55 0.79 0.72 0.74 0.89 0.32 0.89 -0.02 0.60 eight 0.06 0.41 0.39 0.37 -0.04 0.90 -0.07 0.01 1.00 0.15 0.41 -0.02 1.00 0.35 0.99 0.19 0.76 0.52 0.43 0.62 0.08 0.11 0.38 0.99 0.69 nine 0.94 0.66 0.63 0.87 0.03 0.48 0.86 0.80 0.15 1.00 0.90 0.85 0.14 0.94 0.16 0.96 0.56 0.85 0.64 0.78 0.82 0.30 0.89 0.14 0.58 10 0.93 0.85 0.83 0.99 0.04 0.63 0.68 0.87 0.41 0.90 1.00 0.66 0.39 0.99 0.40 0.95 0.82 0.98 0.84 0.95 0.89 0.41 1.00 0.38 0.84 eleven 0.78 0.23 0.18 0.58 -0.02 0.37 0.97 0.60 -0.02 0.85 0.66 1.00 0.01 0.74 0.03 0.81 0.18 0.56 0.20 0.46 0.52 0.08 0.63 0.01 0.18 12 0.04 0.36 0.33 0.34 -0.06 0.91 -0.05 -0.02 1.00 0.14 0.39 0.01 1.00 0.33 1.00 0.18 0.72 0.49 0.37 0.59 0.04 0.06 0.35 1.00 0.65 13 0.95 0.80 0.77 0.97 0.04 0.61 0.76 0.88 0.35 0.94 0.99 0.74 0.33 1.00 0.34 0.98 0.75 0.96 0.78 0.92 0.87 0.37 0.98 0.33 0.77 fourteen 0.05 0.35 0.33 0.34 -0.09 0.92 -0.03 -0.00 0.99 0.16 0.40 0.03 1.00 0.34 1.00 0.20 0.72 0.50 0.37 0.59 0.04 0.06 0.36 1.00 0.64 fifteen 0.98 0.72 0.69 0.93 0.02 0.49 0.82 0.91 0.19 0.96 0.95 0.81 0.18 0.98 0.20 1.00 0.62 0.90 0.70 0.83 0.86 0.32 0.95 0.18 0.64 sixteen 0.56 0.90 0.89 0.83 0.05 0.78 0.20 0.55 0.76 0.56 0.82 0.18 0.72 0.75 0.72 0.62 1.00 0.89 0.91 0.95 0.66 0.44 0.81 0.72 0.99 17 0.86 0.89 0.86 0.97 0.09 0.71 0.60 0.79 0.52 0.85 0.98 0.56 0.49 0.96 0.50 0.90 0.89 1.00 0.88 0.99 0.85 0.43 0.97 0.49 0.90 eighteen 0.70 1.00 1.00 0.89 0.12 0.49 0.26 0.72 0.43 0.64 0.84 0.20 0.37 0.78 0.37 0.70 0.91 0.88 1.00 0.91 0.83 0.57 0.86 0.37 0.95 nineteen 0.79 0.91 0.88 0.95 0.08 0.75 0.48 0.74 0.62 0.78 0.95 0.46 0.59 0.92 0.59 0.83 0.95 0.99 0.91 1.00 0.81 0.41 0.95 0.59 0.95 twenty 0.92 0.84 0.84 0.93 0.14 0.26 0.59 0.89 0.08 0.82 0.89 0.52 0.04 0.87 0.04 0.86 0.66 0.85 0.83 0.81 1.00 0.44 0.91 0.03 0.72 21 0.35 0.57 0.58 0.46 0.13 0.13 0.14 0.32 0.11 0.30 0.41 0.08 0.06 0.37 0.06 0.32 0.44 0.43 0.57 0.41 0.44 1.00 0.42 0.06 0.48 22 0.93 0.86 0.84 1.00 0.04 0.58 0.65 0.89 0.38 0.89 1.00 0.63 0.35 0.98 0.36 0.95 0.81 0.97 0.86 0.95 0.91 0.42 1.00 0.35 0.83 23 0.03 0.35 0.33 0.33 -0.08 0.91 -0.05 -0.02 0.99 0.14 0.38 0.01 1.00 0.33 1.00 0.18 0.72 0.49 0.37 0.59 0.03 0.06 0.35 1.00 0.64 24 0.60 0.94 0.93 0.86 0.07 0.71 0.21 0.60 0.69 0.58 0.84 0.18 0.65 0.77 0.64 0.64 0.99 0.90 0.95 0.95 0.72 0.48 0.83 0.64 1.00

6. Then a graph is formed, the vertices of which are using computers (their identification numbers), while the edges connect pairs of calculators with a PCC exceeding a predetermined threshold value (see Fig. 1).

7. An algorithm for the formation of cliques is applied to the graph constructed in this way (for example, the Bron-Kerbosch algorithm), as a result of which complete subgraphs (cliques) are selected, which are groups of calculators, the pairwise modulus of the value of the ccp within which is greater than a predetermined threshold value, for example, 0.75. By changing the value of the threshold value of the CCP when forming the graph of calculators, it is possible to influence the number of allocated groups of calculators, and, consequently, the size of the federation. Thus, if the threshold value is small, for example, 0.2, the number of groups in the federation will also be small, for example, 6, which in turn means insignificant coverage of program classes. If the threshold is large, for example, 0.99, then the number of groups in the federation will also be large, for example, 17, which in turn means a significant coverage of the program classes, but also leads to a significant size of the federation. Therefore, in order to obtain the optimal ratio of the number of participants / coverage of the classes of the federation programs of calculators, it is necessary to select such a threshold value of the CCP, at which the maximum value is equal to the ratio of the number of groups over a given size to the size of the federation - the completeness of the federation. The minimum group size is significant because, for example, a group of one node may be an anomaly and not define the class of programs.

8. After grouping the calculators in the manner described above, the most efficient calculator in terms of benchmark execution time is selected from each group. The level of efficiency in this case is set by the value of the average execution time of a set of benchmarks. The lowest average time is the most effective. The calculators selected in this way from each group are united into a federation that has the optimal composition.

The concept of class is important. Since, in fact, a comparison of programs and calculators is being built, this concept should be universal and applicable both for calculators and for programs. With this in mind, a class is a unit of measurement. Each calculator has a certain scale in which the step is determined. And each program has the result of its measurement in each such scale (meaningfully, this is the execution time). If a program fits into a close to an integer number of steps, it is considered that it belongs to the class of the corresponding scale. Since all calculators belonging to one group have a linear dependence of the execution times, it is possible to choose a scale that includes all steps (meaningfully, this is the least common multiple, LCM). Thus, each group has its own scale, which determines the class of programs that can be measured by close to an integer number of steps of such a scale. This means that the more groups there are in the federation, the higher the coverage of the program classes.

An example of a specific implementation

As an example of a specific implementation, the claimed method is implemented in a trial operation mode.

1. To implement the proposed method formed a set of candidates for federates, consisting of 25 computers (identification numbers 0..24).

2. To assess the possibility of including these calculators in the federation, a set of benchmarks described above was formed.

3. On each calculator from the generated set, each of the selected benchmarks was run three times, and after each run, the time of its execution was recorded, and the average execution time of each test for three runs (a series of runs) was also determined.

4. The results obtained were recorded on the server that controls the formation of the federation. Table 1 shows an example of a matrix of results of executing programs on computers presented in https://www.spec.org/accel/results/accel_omp.html and benchmarks described earlier.

5. For the obtained measurement results, the Pearson correlation coefficient was determined - in pairs, in relation to all pairs of calculators. Table 2 provides an example of a pairwise correlation matrix. For further grouping of calculators, various threshold values of CCP were set, equal from 0.20 to 0.99, and the federation of calculators was determined depending on a predetermined threshold value.

6. In FIG. 1 shows a graph of calculators, in which computers are connected by edges, the CCP between which exceeds 0.75 (this value is chosen for illustrative purposes only). Table 3 shows the results of the implementation of the proposed method for various threshold values of the CCP. As a result of grouping with different PFCs (see column 1 of Table 3), the groups of calculators (see column 2 of Table 3) have been identified, the pairwise PSCs of which are greater than the corresponding predetermined threshold value. So, for a value of ccp 0.2, 6 clicks are selected in the graph, and for ccp value equal to 0.99, 17 clicks are selected.

7. In each group (click) of calculators, according to the smallest average execution time of a set of benchmarks, the most powerful calculator is selected (see column 3 of Table 3).

8. From the selected most powerful calculators form a federation of optimal composition, while taking into account (excluding) the duplication of calculators included as selected most powerful representatives from various groups (see column 4 of Table 3). So, in line 3 of Table 3, it can be seen that the duplication of calculators 0, 6, 8 was eliminated during the formation of the federation.

Table 3

Threshold value KKP Clicks Selected click representatives Federation composition Completeness of the federation one 0.20 [1, 3, 10, 13, 17, 18, 19, 22, 2, 16, 24, 21, 0, 9, 20, 15, 7],
[1, 3, 10, 13, 17, 18, 19, 22, 2, 16, 24, 5, 8, 12, 14, 23],
[1, 3, 10, 13, 17, 18, 19, 22, 2, 16, 24, 5, 15, 0, 9, 20, 6, 7],
[1, 3, 10, 13, 17, 18, 19, 22, 2, 16, 24, 5, 15, 14],
[1, 3, 10, 13, 17, 18, 19, 22, 11, 0, 5, 6, 9, 20, 15, 7],
[four] 21
eight
6
fourteen
6
four {4, 6, 8, 14, 21} 5/5 = 1. 2 0.50 [four],
[6, 0, 3, 7, 9, 10, 11, 13, 17, 20, 22, 15],
[16, 19, 24, 17, 8, 5, 14],
[16, 19, 24, 17, 3, 10, 13, 22, 0, 1, 2, 7, 9, 18, 20, 15],
[16, 19, 24, 17, 3, 10, 13, 22, 5],
[16, 19, 24, 12, 8, 5, 14, 23],
[21, 1, 2, 18] four
6
eight
0
22
eight
21 {0, 4, 6, 8, 21, 22} 6/6 = 1. 3 0.75 [four],
[5, 8, 16],
[5, 8, 12, 14, 23],
[5, 19, 16],
[11, 0, 9, 6, 15],
[13, 3, 10, 17, 22, 19, 16, 24, 1, 2, 18],
[13, 3, 10, 17, 22, 19, 20, 0, 9, 15],
[13, 3, 10, 17, 22, 19, 20, 1, 2, 18],
[13, 3, 10, 17, 22, 7, 0, 9, 20, 15],
[13, 6, 0, 9, 15],
[21] four
eight
eight
five
6
22
0
twenty
0
6
21 {0, 4, 5, 6, 8, 20, 21, 22} 9/8 = 1.125 four 0.80 [3, 10, 22, 17, 0, 9, 20, 13, 15],
[3, 10, 22, 17, 19, 1, 2, 18, 16, 24],
[3, 10, 22, 17, 19, 1, 2, 18, 20],
[3, 10, 22, 17, 19, 13, 20, 15],
[3, 10, 22, 7, 0, 9, 20, 13, 15],
[four],
[5, 8, 12, 14, 23],
[6, 9, 15, 0],
[6, 9, 15, 11],
[21] 0
22
twenty
twenty
0
four
eight
6
6
21 {0, 4, 6, 8, 20, 21, 22} 8/7 = 1.142 five 0.85 [3, 17, 24, 19, 1, 2, 18],
[3, 17, 22, 10, 1, 19],
[3, 17, 22, 10, 13, 0, 9, 15],
[3, 17, 22, 10, 13, 19],
[3, 17, 22, 18, 1, 19],
[3, 20, 0, 7, 10, 13, 22, 15],
[four],
[5, 8, 12, 14, 23],
[6, 9, 11],
[16, 1, 2, 24, 17, 18, 19],
[21] 3
22
0
22
22
0
four
eight
6
17
21 {0, 3, 4, 6, 8, 17, 21, 22} 9/8 = 1.125 6 0.90 [0, 20, 3, 22],
[0, 15, 10, 13, 9],
[0, 15, 10, 13, 3, 22],
[0, 15, 7],
[2, 24, 1, 18],
[four],
[5, 12, 14, 23],
[6, 11],
[8, 12, 14, 23],
[19, 16, 24, 1, 18],
[19, 17, 24],
[19, 17, 3, 10, 13, 22],
[21] 0
0
0
0
one
four
12
6
eight
nineteen
17
22
21 {0, 1, 4, 6, 8, 12, 17, 19, 21, 22} 10/10 = 1 7 0.95 [0, 13, 15],
[1, 2, 18],
[four],
[five],
[6, 11],
[7],
[8, 12, 14, 23],
[9, 15],
[10, 3, 17, 19],
[10, 3, 17, 13, 22],
[10, 15, 13],
[16, 24],
[twenty],
[21],
[24, 19] 0
one
four
five
6
7
eight
fifteen
10
22
fifteen
24
twenty
21
nineteen {0, 1, 4, 5, 6, 7, 8, 10, 15, 19, 20, 21, 22, 24} 6/14 = 0.428 eight 0.99 [0],
[1, 2, 18],
[3, 10, 22],
[four],
[five],
[6],
[7],
[8, 12, 14, 23],
[nine],
[10, 13],
[eleven],
[fifteen],
[16, 24],
[17],
[nineteen],
[twenty],
[21]] 0
one
22
four
five
6
7
eight
nine
10
eleven
fifteen
24
17
nineteen
twenty
21 {0, 1, 4, 5, 6, 7, 8, 9, 10, 11, 15, 17, 19, 20, 21, 22, 24} 3/17 = 0.176

With the minimum size of the group 3, the optimal threshold of the QCP among the considered examples is the threshold QCP of 0.8, since at this threshold the maximum completeness estimate is reached - 1.142.

Thus, by adjusting the threshold value of the CCP, it is possible for a multitude of candidates to a federation to form a federation of optimal composition with maximum completeness, that is, a federation that provides maximum coverage of the classes of problems to be solved.

Claims (14)

1. A method of forming a federation of calculators, including the following steps: 1) providing a set of calculators who are candidates for federations, 2) the formation of a set of benchmarks intended for execution on each computer from the set of computers formed at stage 1), 3) serial execution of a set of benchmarks on each calculator with the definition and fixation of the execution time of each benchmark from the set, 4) determination of the average execution time in a series of each benchmark separately and the entire set of benchmarks as a whole on each computer from a set of computers, 5) determination of the Pearson correlation coefficient for all pairs of calculators that make up the set at step 1), 6) the formation of groups of calculators, including all pairs of calculators having a Pearson correlation coefficient (KKP) greater than a predetermined value, 7) determination in each group of calculators formed at step 6) a calculator characterized by the minimum average execution time of a set of benchmarks determined at step 4), 8) formation of a federation from the calculators defined in step 7) with the exception of their duplication. 2. The method according to claim 1, characterized in that when forming a set of benchmarks at step 2), benchmarks belonging to different classes of programs are selected. 3. The method of claim 1, wherein the series of benchmark runs is at least three runs of each benchmark. 4. The method according to claim 1, characterized in that in step 6) the algorithm for generating clicks is used to form groups of calculators. 5. The method according to claim 4, characterized in that the Bron-Kerbosch algorithm is used as the clicks generation algorithm. 6. The method according to claim 1, characterized in that the threshold value of the Pearson correlation coefficient is in the range from 0.5 to 0.99.

Images