Method and system for controlling computer communications in multilevel composite computer cluster

The invention relates to the field of computer technology, in particular, to methods and technical means for organizing the interaction of computers in computer clusters.

A multilevel composite computer cluster performing distributed computing by network means is understood as a cluster consisting of groups of simple computer clusters. At the same time, in a simple cluster, its computers exchange messages using tools that belong only to this cluster. In a composite cluster, computers belonging to different simple clusters for messaging must use means external to these clusters. The multilevel structure of a composite cluster means the ability to combine simple clusters into a hierarchical structure so that the higher in the hierarchy clusters can control the actions of the lower ones, and for any two simple clusters there is a hierarchy of clusters, with the help of which the messages of the specified clusters will be exchanged.

In modern supercomputers and computer clusters, groups of computers are used that, on their own initiative, transmit messages and tasks to perform distributed computing to other computers in the system. The execution of such calculations is used directly by network means (In-Network Computing), which for this purpose contain computing means - network computers. It is also possible to carry out a number of calculations using network tools that do not have network computers (see. Computer network with fast distributed restructuring of its structure and data processing in the process of their transmission, Control problems №1. 2017.S. 47-56; Networked information and computational support for the interaction of mobile robots, Control problems No. 5. 2018.S. 56-65.)

The second publication is taken as a prototype for the method of the present invention. The prototype is focused on the systems of mobile robots with computers, in which computers are connected by wireless non-directional optical or radio channels and communication modules.

The solutions proposed in the patent are focused on providing the capabilities of the prototype, but for systems with a different structure. Therefore, we will describe in more detail the main features of the prototype.

In the prototype, each computer contains a network controller for managing the exchange of messages with other computers in the system; contains a communication module and directional wireless optical or radio communication channels of computers with a communication module. Each network controller contains a source and a receiver for optical or radio signals. The network controller also contains a device for controlling the interaction of the computer with the sources and receivers of messages in the system.

The aim of the present invention is to develop a method and system for managing communications between computers in a multilevel composite computer cluster performing distributed computing by network means.

The following components of the prototype cluster structure and the main operations in which they are involved are important for the management of computers in a multilevel composite computer cluster proposed in the patent. These components are a simple cluster structure, network nodes, a communication module. Operations - the procedure for starting a cluster, synchronization, resolving access conflicts, asynchronous barrier synchronization, computing in the network tools of the cluster.

In what follows, the following notation will be used. The communication module is designated MS. Computer hardware - a controller that interacts computers via MS, we will call object O_i.

A. Network structure of a simple cluster, network nodes - communication module, objects. Each computer in the proposed cluster contains a network controller, which is the first of the host types for the network — an object that represents that computer in the computer cluster.

FIG. 1 objects O_i, denoted as 1. The object initiates and ensures the execution of all the necessary distributed operations in the cluster.

The second type of node is the MS communication module, referred to here as 2. There is only one communication module in the network. Objects transmit signals to the communication module via channels 3 and receive signals from the communication module via channels 4. Both types of channels can be directional and non-directional, wired and wireless, transmitting optical or radio signals. Interaction between objects via MS is carried out as follows.

Objects must send frequency signals ƒ₁ to transmit binary unit and frequency ƒ_0. to transfer binary zero to MS. The MS module converts these signals accordingly to signals^*ƒ₁ and ^*ƒ₀ other frequencies and sends them to all objects. These signals have the same duration for the entire network.

Objects use signals to control asynchronous processes ƒ₂ and ^*ƒ₂... Signals ƒ₂ send objects. Everyone ƒ₂ has the duration required by a particular process. MS module sends signals^*ƒ₂ objects if it receives at least one signal ƒ₂.

Cluster computers are stationary. Therefore, it is possible to determine once the transit time of the signal between each object of the cluster and the MS. This time is required to obtain high performance for all distributed computing. It can be omitted if fast distributed operations are not required.

B. Synchronization. The task of synchronization is delivery to MS of a group of object messages in the form of one general message containing messages of objects following one after another without time pauses between them, as well as in the form of one message with the coincidence of identical bits of object messages. There are three types of synchronization: special command synchronization, MS access conflict resolution, and barrier synchronization.

In the first variant, one of the objects sends a synchronization command via MS to all objects. After receiving it, the objects send messages to the MS with a delay, taking into account the distance of the object from the MS. The object knows the time interval T_max - the interval is not less than the propagation time of the signal between the most distant object and the MS. After receiving the command, the object sends a message with a delay D_i= T_max-T_iwhere T_i - signal propagation time between O_i and MS.

In this case, message bits with the same names arrive at the MS simultaneously from all objects, and all objects receive a common message from the MS - the result of overlapping signals from message objects.

In the second variant, in the absence of signals from the MS, the objects begin to transmit messages, detect a conflict in the MS, and send a binary scale to the MS. The scale has the number of bits equal to the number of objects, and has a digit one in the bits corresponding to the objects that must send the message. Having received this scale from the MS, the sequencing objects send messages. This removes the conflict for all conflicting objects.

With asynchronous barrier synchronization, the objects participating in it send signals to the MS at a frequency ƒ₂... The MS module returns a signal to the object with a frequency^*ƒ₂... When finished, the object removes the signal ƒ₂... Signal disappearance^*ƒ₂ in objects is the moment of synchronization.

C. Presentation of data in a cluster. The distributed data is processed either entirely in the communication module, or with a significant part of such calculations being performed in it.

For this, paraphase coding of binary digits and the representation of the digits of numbers in the form of logical scales are used.

In paraphase coding, the digit "one" is represented by a sequence of signals ƒ₁ƒ₀, digit "zero" - with the sequence ƒ₀ƒ₁.

When using a logical scale, each digit of a number given in the base p number system is represented by a binary scale, the number of bits in which is equal to p. In the scale, only one bit, corresponding to the value of the digit, is equal to 1, and the rest are equal to 0. For example, for p = 10 and the digit 7, the scale is 001000000.

Examples of calculations.

D. Logical operations AND, OR. Objects synchronously transmit data bits to the MS using the paraphase representation of the binary digits 1 and 0. If an AND operation is performed, the signal combination ƒ₁ƒ₀, which occurs as a result of overlapping signals in MS, gives the result of the operation equal to 1, otherwise the result is equal to 0. For the OR operation, the combination ƒ₀ƒ₁ gives the result of the operation 0, otherwise 1.

These operations are performed in the MS without signal delay; The settlement time does not depend on the number of participants in the operation. Logic gates are not used for calculations in MS.

E. Search for MAX and MIN. To calculate MAX, objects transmit to the MS the largest digit of their number, represented as a logical scale, and upon receipt of a scale with several units from the MS, the largest value of this digit is determined for all objects simultaneously. The next digit is transmitted by the entities that passed the largest leading digit. MAX will be received after all digits of the numbers have been transmitted. To calculate MIN, objects determine the minimum values ​​of the digits. Increasing the base p speeds up the operation because the number of message exchanges decreases.

F. Analog-to-digital operations. The prototype shows how, if there is an analog-to-digital converter of signal levels in the communication module, fast network summing operations are performed directly in the network module. The summation time does not depend on the number of objects participating in the operation.

The disadvantage of the method in the prototype is that it does not provide for the ability to divide all the computers in the system into hierarchically organized groups - clusters so that independent (autonomous) data processing is simultaneously performed in each cluster, with the exchange of messages within the cluster. This reduces the performance of such a system.

As a prototype of the system, the system given in the above article is taken - Network information and computational support for the interaction of mobile robots, Control problems No. 5. 2018.S. 56-65.

The disadvantage of the system in the prototype is that it does not allow the simultaneous use of several hierarchically linked cluster communication modules for simultaneous autonomous execution of work in several clusters with independent messaging in the cluster. This slows down the processing of data.

The objective of the present invention for the method is to eliminate the disadvantage of the prototype - the impossibility of processing data simultaneously by several groups of computers interacting within the group and to develop for this a method for managing hierarchical connections of computers in a multi-level composite computer cluster using a group of communication modules to perform distributed computing by network means.

The technical result for the method is the inclusion of methods for interaction of computers with a group of communication modules and methods for managing hierarchical connections of computers in a multi-level composite computer cluster using a group of communication modules to perform distributed computing by network means.

The technical result of the method is achieved by the fact that at each level of the hierarchy, equal to k = 0 and more, the leader is one of the objects ^kO_idirectly related to the communication module ^kMS of hierarchy level k, sends command via ^kMS to the communication modules of the next hierarchy level specified in the command ^{k + 1}MS and directly related objects ^{k + 1}O_i, while the modules ^{k + 1}MS send to ^kMS signal starts barrier synchronization and interrupts signal transmission from ^kMS objects ^{k + 1}O_irelated to these ^{k + 1}MS, which is subsequently recovered by a command from ^kO_i, and these ^{k + 1}O_icontinue to work autonomously, interacting only with their own ^{k + 1}MS running one of the facilities ^{k + 1}O_i - the leader of the hierarchy level k + 1, who, after completing the actions specified by the command, stops the transmission from ^{k + 1}MS to ^kMS signal barrier synchronization and reestablishes communication between ^kMS and ^{k + 1}O_i resulting in ^kMS, ^{k + 1}MS, ^kO_i and ^{k + 1}O_i begin to send signals to and receive signals from directly connected communication modules and objects.

The objective of the present invention for a system of devices is to eliminate the indicated drawback of the system of devices of the prototype - the impossibility to use several communication modules simultaneously and to create an organized multi-level composite computer cluster using this group of communication modules to perform distributed computing by network means.

The technical result for the system of devices is that it solves the specified problem of creating a hierarchically organized multi-level composite computer cluster using a group of communication modules to perform distributed computing by network means.

The technical result for the system is achieved by the fact that at each level of the hierarchy k≥0, it contains communication modules ^kMS and Controllers in Computers - Objects ^kO_i, and wireless or wired communication lines made connections, respectively, between ^kMS and ^{k + 1}MS, between ^kMS and ^kO_i, between ^{k + 1}MS and ^{k + 1}O_i, and in each of these devices there are receivers of signals sent to it and sources of signals sent by them to receivers of these devices, and in communication modules ^{k + 1}MS contains blocks that break and restore communication between devices of hierarchy levels k and k + 1, and a control unit for them, and ^kO_i also contain a control unit for the exchange of commands and signals with a computer.

The technical essence and principle of operation of the proposed system of devices are illustrated by drawings.

FIG. 1. Simple cluster.

FIG. 2. Composite cluster.

FIG. 3. The structure of the communication module.

FIG. 4. Block of isolation of objects of neighboring levels of the hierarchy.

FIG. 5. The structure of the object.

The devices shown in the drawings should be considered as examples of the implementation of the devices proposed in the patent.

Brief description of the proposed method.

The main feature of the method of managing computer connections in a multilevel composite computer cluster is as follows. At each level k of the hierarchy of a composite cluster, other than the top zero level, one of the objects of level k through the module^kThe MS sends a command to the communication modules of levels greater than k, which for the duration of its action isolates all directly connected objects in the modules indicated by the command from the signals of the previous levels. This allows dedicated computers to act interconnected and isolated from other devices, increasing the overall performance of the composite cluster.

Brief description of the proposed system of devices.

The main feature of the computer communication control system in a multi-level composite computer cluster is that at each level of the hierarchy k≥0, it contains communication modules ^kMS, and in computers contains controllers - objects ^kO_i... Connections between^kMS and ^{k + 1}MS, between ^kMS and ^kO_i, between ^{k + 1}MS and ^{k + 1}O_i made by wireless or wired communication lines. Each of these devices has receivers of signals sent to it and sources of signals sent to them. Communication modules^{k + 1}MS contain blocks that break and restore communication between devices of hierarchy levels k and k + 1, and a control block for them. Objects^kO_i contain a control unit for exchanging commands and signals with a computer.

Detailed description of the proposed method.

The method is applied to a multilevel composite cluster containing a central cluster and subordinate clusters. It is oriented towards the development of the structure of FIG. 1. In a composite cluster, a method is considered that consists of two interacting methods - synchronous and asynchronous (autonomous).

Synchronous way of functioning of a composite cluster.

The organization of the interaction of the nodes of a composite cluster consisting of a central and subordinate clusters is shown in Fig. 2. The following components of the composite cluster in FIG. 2 are assigned the numbers indicated in the text below in parentheses.

Here ⁰MS (5) is the main zero-level communication module belonging to the central cluster. Objects⁰ABOUT₁,…,⁰O_i (6) directly related to ⁰MS. Level 1 slave clusters¹O_i (8) with numbers i = 1, ..., k are also connected to ⁰MS through its first level communication modules ¹MS₁,…, ¹MS_k (7). Fiber optic channels (9) connect objects to the first level modules: to the module¹MS₁- objects <img file="RU2744591C2_D0001.tif" />, to the module ¹MS_k-objects ¹O_kl,…, ¹O_km... Modules¹MS connected to ⁰MS also channels (9).

For all objects of the composite cluster, their distance from ⁰MS and the greatest distance of all objects from ⁰MS.

Module ⁰MS works like the simple cluster MS module described above. Modules¹MS₁ receive signals ƒ₀, ƒ₁ and ƒ₂ objects connected to them and, without changing the frequency of signals, transmit them to ⁰MS. therefore⁰MS perceives modules ¹MS as objects connected to channels (9).

Module ⁰MS sends signals ^*ƒ₁, ^*ƒ₀ and ^*ƒ₂ not only objects, but also modules ¹MS. The latter, like⁰MSs send these signals to their objects.

So the modules ¹MS perform only the functions of repeaters (repeaters) of signals received in ⁰MS from objects. System with modules¹MS acts as a system containing only ⁰MS. The only difference is that signals from objects of any cluster do not directly go to objects of other clusters.

The synchronization process in a composite cluster needs to be refined. For simplicity, let the clusters use synchronization scales of the same number of binary digits for synchronization. The number of subordinate clusters is known. The synchronization process includes all clusters that transmit their scales in a common message. From⁰MS general scale will return to all objects. This will allow the cluster objects to synchronously send their messages of the same duration.

In this process, an additional condition must be met. Object messages must arrive without conflicts, not only to⁰MS, but also on ¹MS. Since all distances between objects⁰MS and ¹MS are known, for this each object must send any of its messages with an additional delay, taking into account the distance between ⁰MS and his ¹MS, as well as the order of transmission of messages in ⁰MS from others ¹MS preceding in sync scale ¹MS of this object.

In such a cluster, all data exchange methods and digital operations are similar to the actions of a cluster that does not have subordinate clusters. It is also easy to organize work with scales and messages of different, but known in advance. You can work with dynamically changing message lengths, but for this you need to specify these lengths in the synchronization scale. Instead, a normal sync timeline can be sent, followed by a shorter timeline sent only by entities that transmit messages. The second scale reports the length of the messages.

The synchronous method can be applied independently, but it is also included in the next stand-alone method.

An autonomous way of functioning of a composite cluster.

Unlike the previous section, objects connected to modules ¹MS, work in this cluster autonomously, without delaying the operation of objects in other clusters. Let's go back to a simple cluster first. Let one of the U objects in the cluster send the job to other objects. Each of these objects starts an asynchronous operation, sends a signal ƒ₂ barrier synchronization in ⁰MS and completes the transfer ƒ₂ after completion of task U. Module ⁰MS in response to ƒ₂ sends a signal ^*ƒ₂ objects and completes the transfer ^*ƒ₂ when the signal arrives at it ƒ₂... With absence^*ƒ₂ object U can submit a new job.

To simplify the presentation of the operation of the module ¹MS further for simplicity of presentation are presented in the form of interaction of its two parts ¹MS_a and ¹MS_b... Although these parts can be physically implemented on fully or partially overlapping technical means, their logical functioning is different. Translation by the central cluster of the module¹MS offline consists of the following steps.

Stage 1. Arbitrary central cluster object - U sends command C1. Module¹MS, having received the command C1, informs the objects connected to it about the upcoming autonomous work. Modules¹MS and their objects, which receive the C1 command, wait for the C2 command from the U object. C2 lists the names of the objects - recipients of C2. For each object, an action or sequence of actions (program) that the object must perform is indicated. Module¹MS performs stage 2.

Stage 2. After receiving the C2 module ¹MS prohibits the passage of signals from ⁰MS to the objects of this module ¹MS and signals of these objects to ⁰MS. Part¹MS_a sends a signal ƒ₂ is a sign of barrier synchronization in ⁰MS. From the module⁰MS signal arrives ^*ƒ₂... Module objects¹The MSs will asynchronously execute the tasks specified in the C2 command, completing step 3.

Stage 3. The task received from ⁰MS, allocates an arbitrary object ^*U among objects ¹MS. An object^*U should control the actions of the rest of the module objects ¹MS. An object^*U acts like the object U of the central cluster. An object^*U can also be selected by joint action of objects ¹MS.

Each object that received a command from ^*U, send parts ¹MS_b signal ƒ₂, but ¹MS_b converts the signal ƒ₂ into signal ^*ƒ₂sent to module objects ¹MS.

After finishing work, the object turns off its signal ƒ₂... In the absence of signals ƒ₂ module ¹MS_b turns off the signal ^*ƒ₂... In response, the object^*U either continues to work with objects ¹MS, either exits and sends the command to the part ¹MS_a to complete sending the signal ƒ₂ to the module ⁰MS. An object^*U also removes the isolation of its objects from the central cluster.

Stage 4. When the module ⁰MS stops receiving signals ƒ₂, it will stop transmitting the signal ^*ƒ₂ objects and modules ¹MS. After completing stages 1-4, the results of calculations in modules¹MS remain in objects connected to these modules and are not available in objects connected to ⁰MS. To access them, step 5 is performed.

Stage 5. It is assumed that in the C2 command the object ^*U got task to collect data from objects connected to ¹MS, and generate from them the data necessary for objects connected to ⁰MS. An object^*U performs these actions. Similarly, the U object collects through the module⁰MS all data from objects.

So splitting the module ¹MS apart ¹MS_a and ¹MS_b allows two asynchronous processes to communicate. Part¹MS_a provides module connection ¹MS as an object to ⁰MS. Part¹MS_b allows objects connected to the module ¹MS, work autonomously from all objects connected to ⁰MS.

Slave modules ¹MS versus ⁰MSs must have additional equipment to perform the above steps.

Stages 1-5 can be changed to include the number of levels of the hierarchy k exceeding the above considered k = 0, 1. Introduce the modules ^kMS with k&gt; 1 and connect them to the system like connecting modules ¹MS to module ⁰MS. If any communication module^{k + 1}MS receives a command that breaks its connection with the communication module higher in the hierarchy ^kMS, then this ^{k + 1}MS acts similarly to subordinate communication modules and objects ¹MS in relation to ⁰MS. This creates a layered structure.

If modules and objects do not use an autonomous way of interaction at the current time, their actions do not differ from those in the case of a synchronous way of functioning of a composite cluster.

In a composite cluster, any computer can be replaced by a composite cluster.

A detailed description of the proposed system for managing communications of computers in a multilevel composite computer cluster.

The proposed system is presented for simplicity only at the zero and first levels of the hierarchy. It is shown in FIG. 2 and contains a zero-level communication module⁰MS (5), communication modules of the first level ¹MS₁ … ¹MS_k (7), objects of the zero level O₁ - O_i (6), objects of the first level ¹ABOUT₁ - O_m (8). The listed devices are connected by communication channels (9).

FIG. 3 shows the device of the modules^kMS 7, the first and higher levels of the hierarchy.

Communication modules design ⁰MS and MS are not considered, since it directly follows from the design of the modules 7. FIG. 3 on the left, the common channel 9 is represented by channels 3 and 4, connecting the communication module 7 with the previous hierarchy level, similarly on the right, channels 3 and 4 connect the communication module with the next hierarchy level.

Communication module 7 contains blocks 13 and 11 of signal receivers ƒ₀, ƒ₁, ƒ₂ and ^*ƒ₀, ^*ƒ₁, ^*ƒ₂ respectively, converting them into electrical signals; blocks 12 and 14 of signal sources ƒ₀, ƒ₁, ƒ₂ and ^*ƒ₀, ^*ƒ₁, ^*ƒ₂ accordingly, forming them in response to the arrival of electrical signals; contains a block 10 for isolating objects of neighboring levels of the hierarchy, the organization of which is shown in FIG. four; contains control unit 15.

In block 15, its inputs 16, 20 are connected to the outputs of blocks 11, 13, respectively, outputs 17, 19 are connected to the inputs of blocks 12, 14, output 18 is connected to the control input of block 10, which is shown in FIG. 4 is designated as 21. Here, block 21 contains keys 22, 23, 25. To perform the method steps for isolating objects of neighboring levels of the hierarchy, block 15 controls the keys 22, 23. To break the connections, the signal sent to the input 24 (Fig. 4) opens 22, 23 and closes 25.

The prototype uses analog-to-digital operations using an ADC. To have such a possibility in the proposed system, a node 26 is introduced, which includes an ADC. If an analog-to-digital operation is requested from the output 13 to the node 26, then during the execution of this operation and the transmission of its result to the system, the node opens the key 25.

The construction of the object is shown in FIG. 5. Here 27 is an object, i.e. network controller of a computer included in one of the clusters; 28 - control unit; 29 - block of signal sources ƒ₀, ƒ₁, ƒ₂sent to the communication module via channel 3; 30 - block of signal receivers^*ƒ₀, ^*ƒ₁, ^*ƒ₂received from the communication module via channel 4. The control unit 28 is connected to 29 and 30, and is also connected to the cluster computer by channels 31 and 32, through which commands and signals are transmitted that ensure the actions of the proposed method.