CN105389448B - A kind of graph model building method for protecting the assessment of energy degree for computer cluster - Google Patents

Abstract

The present invention relates to a kind of graph model building method for protecting the assessment of energy degree for computer cluster, its step with the following method: step 1: it is configured to computer cluster and protects the tree-model that energy degree is assessed；Step 2: graph model conversion is carried out using the method for merge node；Step 3: graph model conversion is carried out using the method for useless knot removal；Step 4: graph model conversion is carried out using the method that redundant node is deleted；It is insufficient that it solves system mode enumeration methodology performance, it is difficult to carry out the problem of large-scale computer cluster protects the assessment of energy degree, it has many advantages, such as that making to protect the assessment of energy degree faster more saves resource.

Description

A Graph Model Construction Method for Computer Cluster Resilience Evaluation

technical field

The present invention relates to a method for constructing a graph model used for evaluating the survivability of computer clusters.

Background technique

A computer cluster is a collection of independent computers. The computers are connected through a high-performance interconnection network. Each computer can work together and provide services to network users as a single, centralized computing resource. Computer cluster is a parallel machine architecture with low cost, easy construction and good scalability. The computers in the cluster are independent of each other and have different performance values. For example, the specific performance values of different IBM computers, HP computers, and Lenovo computers in a computer cluster tend to vary widely. The performance of the entire computer cluster is the accumulation (aggregation) of the performance values of all the computers that make up the cluster. During operation, each computer in the computer cluster will have random failures. When a computer fails, the computer contributes 0 to the performance value of the entire cluster. When a computer does not fail and works normally, the computer contributes to the performance of the entire cluster. The performance value contribution is the performance value of that computer.

Evaluating the survivability of a computer cluster is to evaluate the probability that the performance value of the computer cluster is in a specified interval under the condition that the computer will fail randomly. This interval is also known as the sturdiness evaluation interval. It has the following problems: the existing computer cluster sufficiency evaluation is usually based on the method of system state enumeration. When the number N of computers included in the cluster increases, the number of system states ^2N in the cluster increases sharply. Therefore, the enumeration method is only suitable for small computer clusters, and it is difficult to evaluate large-scale computer clusters, and it is difficult to obtain accurate evaluation values.

SUMMARY OF THE INVENTION

The purpose of the present invention is to aim at the defects and deficiencies of the prior art, to provide a simple structure, reasonable design, and convenient use of a graph model construction method for computer cluster survivability evaluation, which solves the performance of the system state enumeration method. Insufficient, it is difficult to evaluate the energy retention of large-scale computer clusters. It has the advantages of making energy retention evaluation faster and saving resources.

For achieving the above object, the technical scheme adopted in the present invention is:

A method for constructing a graph model for evaluating computer cluster tenacity according to the present invention adopts the following method steps:

Step 1: Construct a tree model for the evaluation of computer cluster energy retention; among them, the energy retention of computer cluster is to evaluate the probability that the performance value of the computer cluster is in a specified interval under the condition that the computer will randomly fail. The interval also becomes the energy retention evaluation interval;

Step 2: For the tree model obtained in step 1, the method of merging nodes is used to convert the graph model;

Step 3: For the graph model obtained in step 2, use the method of deleting useless nodes to convert the graph model;

Step 4: For the graph model obtained in step 3, the method of deleting redundant nodes is used to convert the graph model.

Further, in the first step, according to the 'normal' and 'fault' states of each computer in the computer cluster, and the performance values of each computer in the 'normal' state, a corresponding state space tree is established. model, and set the leaf nodes of the tree model according to the definition of the evaluation interval of energy retention.

Further, in the second step, for each layer of nodes in the tree model obtained in the first step, isomorphism is judged according to the aggregated performance value of the node, and when there are two nodes in one layer with the same aggregated performance value. , then merge the two nodes

Further, in the third step, each node in the graph model obtained in the second step is judged according to the aggregated performance value of the node. If the current aggregated performance value has exceeded the upper limit of the evaluation interval of the energy preservation degree, the If the node is a useless node, you can directly replace the node with the leaf node '0'; if the current aggregated performance value plus the remaining maximum aggregated performance value still cannot be greater than the lower limit of the evaluation interval of the energy preservation degree, the node is a useless node and can directly use the leaf Node '0' replaces the section.

Further, in the fourth step, for each node in the graph model obtained in the third step, if the two branches of the node point to the same child node, the node is a redundant node and the child node can be used to replace the node.

After the above structure is adopted, the beneficial effects of the present invention are as follows: the method for constructing a graph model for evaluating the energy retention of computer clusters according to the present invention solves the problem of insufficient performance of the system state enumeration method and is difficult to maintain energy in large-scale computer clusters. It has the advantages of faster and more resource-saving evaluation of energy conservation.

Description of drawings

Fig. 1 is the state enumeration model of computer cluster instance survivability evaluation;

Fig. 2 is the tree model of the evaluation tree model of the computer cluster instance;

Fig. 3 is a graph model of the energy retention evaluation graph after being processed by the method of merging nodes;

Fig. 4 is the graph model of energy retention evaluation after the method of deleting useless nodes;

Fig. 5 is a graph model for evaluating the retention degree after the method of deleting redundant nodes;

Detailed ways

The present invention will be further described below in conjunction with the accompanying drawings.

As shown in Fig. 1, a graph model construction method for computer cluster sufficiency evaluation according to the present invention adopts the following method steps:

Step 1: Construct a tree model for the evaluation of computer cluster energy retention; among them, the energy retention of computer cluster is to evaluate the probability that the performance value of the computer cluster is in a specified interval under the condition that the computer will randomly fail. The interval also becomes the energy retention evaluation interval;

Step 2: For the tree model obtained in step 1, the method of merging nodes is used to convert the graph model;

Step 3: For the graph model obtained in step 2, use the method of deleting useless nodes to convert the graph model;

Step 4: For the graph model obtained in step 3, the method of deleting redundant nodes is used to convert the graph model.

As a preference of the present invention, in the first step, according to the two states of 'normal' and 'failure' of each computer in the computer cluster, and the performance value of each computer in the 'normal' state, establish The corresponding state space tree model, and according to the definition of the evaluation interval of energy retention, set the leaf nodes of the tree model.

As a preference of the present invention, in the second step, for each layer of nodes in the tree model obtained in step the same aggregated performance value, then merge the two nodes

As a preferred aspect of the present invention, in the third step, each node in the graph model obtained in the second step is judged according to the aggregated performance value of the node. If the current aggregated performance value has exceeded the evaluation of the energy preservation degree The upper limit of the interval, the node is a useless node, and the node can be directly replaced with the leaf node '0'; if the current aggregated performance value plus the remaining maximum aggregated performance value still cannot be greater than the lower limit of the evaluation interval of the energy preservation degree, the node is useless A node can directly replace the section with a leaf node '0'.

As a preference of the present invention, in the fourth step, for each node in the graph model obtained in the third step, if the two branches of the node point to the same child node, the node is a redundant node and the child node can be used. Replace the node.

The working principle of the present invention is as follows:

Step 1: Construct a tree model for the evaluation of computer cluster energy retention;

According to the two states of 'normal' and 'fault' of each computer in the computer cluster, and the performance value of each computer in the 'normal' state, a corresponding tree model is established, and defined according to the evaluation interval of energy retention. , set the leaf node of the tree model.

Take computer cluster A as an example.

Computer cluster A contains 4 computers. Computer 1 has a performance value of 1, computer 2 has a performance value of 1, computer 3 has a performance value of 0.5, and computer 4 has a performance value of 0.5. The evaluation interval of energy retention is [1, 1.5], that is, the lower limit of the cluster performance value is 1 and the upper limit is 1.5.

For this computer cluster, the state enumeration model shown in Figure 1 can be directly constructed. Each non-bottom node in the tree model corresponds to a computer, for example, the top-level node corresponds to computer 1, and the second-level node corresponds to computer 2. Each node in the tree model has 2 branches, and branch 1 indicates that the computer is in a normal state , branch 0 indicates that the computer is in a failed state. Each node in the tree model has a current aggregated performance value. The calculation method of the current summary performance value is described below with an example. For example, a node belonging to computer 4 in the fourth layer marked in Figure 1, the conditions that need to be met from the top node to this node are: computer 1 is faulty, computer 2 and computer 3 are normal, so this marked The current aggregate performance value of the computer 4 node is the performance value of computer 2 plus the performance value of computer 3, that is, 1+0.5=1.5. For another example, a bottom node of the fifth layer marked in Figure 1, from the top node to the node The conditions that need to be met are: Computer 2 and Computer 3 are faulty, and Computer 1 and Computer 4 are normal, so the current aggregate performance value of the bottom node marked with the performance value of Computer 1 plus the performance value of Computer 4, that is, 1+ 0.5=1.5.

For the state enumeration model in Figure 1, the bottom node can be converted into a leaf node according to the definition of the evaluation interval of energy retention. The conversion rule is: if the current aggregated performance value of the underlying node is in the evaluation interval of energy preservation, then the underlying node is converted to leaf node 1; if the current aggregated performance value of the underlying node is not in the evaluation interval of energy preservation, then The underlying node is converted to leaf node 0. Finally, the tree model of the computer cluster instance retention evaluation shown in Figure 2 is obtained.

Step 2, using the method of merging nodes to convert the graph model;

For each layer of nodes in the tree model obtained in step 1, the isomorphism is judged according to the current aggregated performance value of the node. When there are two nodes in one layer with the same current aggregated performance value, the two nodes are merged. .

Take computer cluster A as an example.

The two nodes belonging to computer 3 in the third layer in Fig. 2 have the same current aggregated performance value (both are 1), then these two nodes can be merged to obtain the guaranteed performance value processed by the method of merging nodes shown in Fig. 3. Capability assessment graph model.

Step 3: Use the method of deleting useless nodes to convert the graph model;

For each node in the graph model obtained in step 2, judge according to the current aggregated performance value of the node. If the current aggregated performance value has exceeded the upper limit of the evaluation interval of the energy preservation degree, the node is a useless node and the leaf can be used directly. The node '0' replaces the node; if the current aggregated performance value plus the remaining maximum aggregated performance value still cannot be greater than the lower limit of the evaluation interval of the energy preservation degree, the node is a useless node and the leaf node '0' can directly replace the node.

Take computer cluster A as an example.

A node belonging to computer 3 in the third layer in Figure 3, its current aggregated performance value has exceeded the upper limit of the evaluation interval of the energy preservation degree, so the node is a useless node and can directly replace the node with the leaf node '0'. A node belonging to computer 4 in the fourth layer, its current aggregated performance value of 0 plus the remaining maximum aggregated performance value of 0.5 still cannot be greater than the lower limit of the evaluation interval of energy preservation degree 1, so this node is a useless node and can be directly used as a leaf node' 0' to replace the node. Finally, the graph model for evaluating the energy preservation degree after being processed by the useless node method as shown in Fig. 4 is obtained.

Step 4: Use the method of deleting redundant nodes to convert the graph model.

For each node in the graph model obtained in step 3, if the two branches of the node point to the same child node, the node is a redundant node and the child node can be used to replace the node.

Take computer cluster A as an example.

A node in the fourth layer in Figure 3 belongs to computer 4. The two branches of the node point to the same child node, that is, leaf node 1, so this node is a redundant node and can be replaced by a child node (leaf node 1). . Obtain the graph model for evaluating the energy preservation degree after processing the useless node method shown in Fig. 5 .

Implementation effect of the present invention: It can be seen from the comparison between Fig. 1 and Fig. 5 that Fig. 1 is the model processed by the traditional state enumeration method, and Fig. 5 is the model processed by the graph model construction method provided by the present invention. The model of the present invention is much smaller than the model of the traditional enumeration method, so that the evaluation of energies can be made faster and resources are saved.

The method for constructing a graph model for the evaluation of the energy retention of computer clusters according to the present invention solves the problem that the system state enumeration method has insufficient performance and is difficult to evaluate the energy retention of large-scale computer clusters. Evaluate the advantages of faster and less resource-intensive

The above descriptions are only the preferred embodiments of the present invention, so all equivalent changes or modifications made according to the structures, features and principles described in the scope of the patent application of the present invention are included in the scope of the patent application of the present invention.

Claims (4)

1. a kind of graph model building method for protecting the assessment of energy degree for computer cluster, it is characterised in that: it is with the following method Step:

Step 1: it is configured to the tree-model that computer cluster protects the assessment of energy degree；Wherein, guarantor's energy degree of computer cluster is exactly to comment The performance number for estimating computer cluster under conditions of random fault can occur for computer is in the probability in section as defined in some, this A section, which also becomes, protects energy degree assessment section；

Step 2: being directed to step 1 tree-model obtained, carries out graph model conversion using the method for merge node；To step 1 Each node layer in tree-model obtained summarizes performance number according to possessed by node and carries out isomorphism judgement, deposits when in one layer Summarize performance number two nodes are having the same, then merges the two nodes；

Step 3: being directed to step 2 graph model obtained, carries out graph model conversion using the method for useless knot removal；

Step 4: being directed to step 3 graph model obtained, carries out graph model conversion using the method that redundant node is deleted.

2. a kind of graph model building method for protecting the assessment of energy degree for computer cluster according to claim 1, feature It is: in the step 1, for ' normal ' and ' failure ' two states possessed by computer each in computer cluster, with And each computer possessed performance number under ' normal ' state, corresponding state space tree-model is established, and according to guarantor's energy The evaluation interval of degree defines, and the leaf node of tree-model is arranged.

3. a kind of graph model building method for protecting the assessment of energy degree for computer cluster according to claim 1, feature It is: in the step 3, to each node in step 2 graph model obtained, performance number is summarized according to possessed by node Judged, if currently summarizing performance number has exceeded the evaluation interval upper limit for protecting energy degree, which is that useless node can Directly to replace the node with leaf node ' 0 '；Summarize performance number still not if currently summarizing performance number and adding remaining maximum The evaluation interval lower limit for protecting energy degree can be greater than, then the node is that useless node directly can replace the section with leaf node ' 0 '.

4. a kind of graph model building method for protecting the assessment of energy degree for computer cluster according to claim 1, feature It is: in the step 4, to each node in step 3 graph model obtained, if the Liang Ge branch direction of node is identical Child node, then the node is that redundant node can use child node and replace the node.