CN108089918B - Graph computation load balancing method for heterogeneous server structure - Google Patents
Graph computation load balancing method for heterogeneous server structure Download PDFInfo
- Publication number
- CN108089918B CN108089918B CN201711274503.8A CN201711274503A CN108089918B CN 108089918 B CN108089918 B CN 108089918B CN 201711274503 A CN201711274503 A CN 201711274503A CN 108089918 B CN108089918 B CN 108089918B
- Authority
- CN
- China
- Prior art keywords
- node
- migration
- vertex
- graph
- nodes
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Active
Links
Images
Classifications
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F9/00—Arrangements for program control, e.g. control units
- G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
- G06F9/46—Multiprogramming arrangements
- G06F9/48—Program initiating; Program switching, e.g. by interrupt
- G06F9/4806—Task transfer initiation or dispatching
- G06F9/4843—Task transfer initiation or dispatching by program, e.g. task dispatcher, supervisor, operating system
- G06F9/485—Task life-cycle, e.g. stopping, restarting, resuming execution
- G06F9/4856—Task life-cycle, e.g. stopping, restarting, resuming execution resumption being on a different machine, e.g. task migration, virtual machine migration
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F9/00—Arrangements for program control, e.g. control units
- G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
- G06F9/46—Multiprogramming arrangements
- G06F9/50—Allocation of resources, e.g. of the central processing unit [CPU]
- G06F9/5061—Partitioning or combining of resources
- G06F9/5072—Grid computing
Landscapes
- Engineering & Computer Science (AREA)
- Software Systems (AREA)
- Theoretical Computer Science (AREA)
- Physics & Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Mathematical Physics (AREA)
- Computer And Data Communications (AREA)
- Management, Administration, Business Operations System, And Electronic Commerce (AREA)
Abstract
The invention discloses a graph computation load balancing method for a heterogeneous server structure, which comprises the following steps: and if the variation coefficient in the super steps of two consecutive times is larger than a preset threshold value, judging that the graph calculation load of each calculation node in operation is unbalanced, redistributing the graph calculation load on the calculation node after the super step of the current time is finished, otherwise, continuously executing the next super step by all the calculation nodes. The method of the invention balances the processing time among the computing nodes in each super step by using the vertex migration, thereby effectively reducing the synchronous cost of all the computing nodes in each super step, shortening the running time of the graph computing task and improving the resource utilization rate of each computing node in running.
Description
Technical Field
The invention belongs to the technical field of graph computation, and particularly relates to a graph computation load balancing method for a heterogeneous server structure.
Background
The distributed graph computing technology is widely applied to a plurality of fields such as social network analysis, natural language processing, webpage information retrieval and the like, and a composition system of the distributed graph computing technology generally comprises three parts: graph algorithms, graph datasets, and graph computation systems. Most graph computing systems employ a bsp (bulk Synchronization barrier) computing model under which the graph computation process is typically divided into a number of iterations, each iteration also referred to as a super-step. In each super step, the active vertex updates the vertex value according to the message received in the last super step, and sends the updated value to the corresponding neighbor vertex in the form of the message. And a synchronization barrier is arranged between every two adjacent super steps to ensure that all the activated vertexes finish the numerical value updating operation in the current super step before the next super step starts.
Existing graph computing systems allocate a comparable number of vertices to all compute nodes at the stage of importing a graph dataset by the compute nodes for load balancing. However, the current data center or cluster usually adopts a heterogeneous server structure, which causes the processing time of the computing nodes with different processing capacities in each super step to be different, i.e. the computing node with strong processing capacity always completes the local computation in each super step preferentially than the computing node with weak processing capacity, and waits for synchronization at the synchronization obstacle. In addition, in the process of processing the graph calculation task, the number of the active vertices distributed on each calculation node changes, and thus the load amount of each calculation node in each super also changes dynamically. Due to the above two reasons, most graph computing systems have difficulty in ensuring that the processing time of each computing node in each super step is balanced.
To address the problem of load imbalance among compute nodes when processing graph computation tasks, a few graph computation systems (e.g., Mizan and GPS) propose to use vertex migration to balance the load on each compute node in each superstep. However, these graph computing systems typically use vertex-level parameters (e.g., the number of messages that a vertex accepts in a super-step) to formulate a migration plan, resulting in undesirable migration effects and uneven load among the compute nodes after the vertex migration. In addition, these graph computing systems typically employ a more sensitive migration strategy, which performs vertex migration even if slight load imbalance is detected, resulting in the overhead (such as migration time, resource occupation, etc.) of vertex migration being far greater than the benefit of load balancing.
Disclosure of Invention
Aiming at the defects or the improvement requirements in the prior art, the invention provides a graph computation load balancing method oriented to a heterogeneous server structure, which is used for balancing the processing time of all computation nodes in each super step in a distributed graph computation system, thereby reducing the synchronization overhead of the computation nodes in each super step, shortening the running time of a graph computation task, and solving the problems of unbalanced load of the computation nodes and asynchronous processing time when the graph computation task is processed under the existing heterogeneous server structure.
The invention provides a graph computation load balancing method for a heterogeneous server structure, which comprises the following steps:
and (3) detecting unbalance: when a graph calculation task runs, the main control node monitors the processing time of each calculation node in each super step, and judges whether graph calculation loads on the calculation nodes are balanced or not according to the variation coefficient of the processing time of all the calculation nodes in the super step and a threshold preset by a user; the coefficient of variation is a parameter reflecting the degree of dispersion of a set of data values; for a graph algorithm, if the user does not know the characteristics of the graph algorithm in operation, namely the change of the number of the active vertexes of the user in operation is unknown, the threshold value is defaulted to be 0.10; for a stable graph algorithm, namely the number of the active vertexes is not changed during operation, a threshold value smaller than 0.10 is set; for unstable graph algorithms, i.e. the number of active vertices continuously changes during operation, a threshold greater than 0.10 should be set; the default threshold of the present invention may be set to 0.10, and the selection of specific thresholds for different graph algorithms is not within the scope of the present invention.
A migration planning stage is drawn: each computing node determines vertexes which need to be migrated, and the main control node determines migration nodes corresponding to the vertexes;
implementing a migration stage: all the emigration nodes transmit vertex information to corresponding emigration nodes in a delayed migration mode, and the main control node updates position information after vertex migration; the delayed migration refers to that the migration node only migrates the ID, the numerical value and the adjacent edge table of the vertex after the super step is finished, and migrates the vertex with larger size after the transmission message is locally processed on the migration node; the position information of the vertex refers to the node where the vertex is located currently, and other vertices can send messages to the vertex by knowing the position information of the vertex.
Further, the method comprises the following steps:
step 1, importing all computing nodes into a graph algorithm and a graph data set; generally, graph algorithms and graph datasets constitute the computational load;
step 2, executing one super step of the graph algorithm by all the computing nodes; (graph algorithms are typically system-provided or user-written, graph algorithms are used for information extraction from graph data sets, and the process of extracting information can be generally divided into a number of super-steps);
step 3, the main control node judges whether graph computation loads on the computation nodes are balanced;
step 4, if the judgment result in the step 3 is that the load is unbalanced, entering a stage of planning a migration plan, and turning to the step 5; otherwise, turning to step 7, and enabling all the computing nodes to enter the next super step;
step 5, each computing node determines the vertex needing to be migrated, and the main control node determines the migration nodes corresponding to the vertices;
step 6, all the computing nodes transmit the vertex information to the corresponding migration nodes in a delayed migration mode, and the main control node updates and summarizes the position information after the vertex migration;
and 7, repeating the steps 2 to 6 until the graph algorithm converges.
Further, the step 3 of detecting the unbalance phase includes the following sub-steps:
3-1, each computing node sends the processing time monitored in the super step to a main control node (each computing node can monitor the processing time in each super step in the running process);
step 3-2, the main control node calculates the coefficient of variation CV of all processing time in the super step:
wherein u is the average processing time of all the calculation nodes in the super step, N is the total number of the calculation nodes, and tiCalculating the processing time monitored by the node i in the super step;
3-3, if the coefficient of variation CV calculated in the last super step and the super step is larger than the threshold CV preset by the userthrIf so, the main control node judges that the graph calculation load on each calculation node is unbalanced; otherwise, determining the graph computation load on each computation node as balanced; if the computed CV is larger than the threshold value in the first super step, the vertex migration is not carried out; the vertex migration can be performed only if the CV in the super-steps of two consecutive times is larger than the threshold value;
and 3-4, the main control node sends the judged result to all the computing nodes.
Further, the step 5 of formulating the migration plan includes the following sub-steps:
step 5-1, the main control node sends the average processing time u in the super step to each computing node;
step 5-2, each computing node judges whether the computing node is a migration node, namely the processing time is more than the average processing time, or the migration node, namely the processing time is less than the average processing time according to the average processing time u;
if the node is migrated, calculating the number E of the edges needing to be migratedoutAnd further according to EoutDetermining a vertex needing to be migrated; the vertex that moves out is also the vertex that moves in, and the vertex is transferred from one computing node to another computing node in the process of moving;
if the node is moved in, calculating the number E of the edges needing to be moved inin；EoutAnd EinRespectively describing the number of the edges which can be migrated out at most and the number of the edges which can be migrated in at most of one computing node;
step 5-3, calculating the number of edges which the nodes need to be respectively migrated out or in, namely EoutOr EinSending the data to a master control node;
step 5-4, the main control node moves out or moves in according to the number of edges of each computing node, namely EoutOr EinDetermining migration nodes corresponding to the migration vertexes; the migration vertices on the migration nodes are already determined, that is, in the work of step 5-2, the current master control node needs to determine to which nodes the migration vertices should be transferred;
and 5-5, the main control node sends the migration node information corresponding to the migration vertex to the corresponding migration node.
Further, in step 5-2, when each migration node determines the vertex that needs to be migrated, the following operations are performed:
each computing node arranges the maintained vertexes in a descending order according to the number of edges connected with the vertexes (the computing node maintains one vertex, which means that the computing node needs to store all information of the vertex and update the numerical value of the vertex in each super step); when the computing node i receives the average position sent by the main control nodeAfter processing the time u, calculating the processing time t of the super stepiDifference Δ t from the average processing time u is ti-u; when Δ t is positive, the graph representing the computation node i has a computation load higher than the average load level, and the number of edges that the node needs to migrate is Eout＝(ti-μ)*EPSiIn which EPSiCalculating the average number of edges processed per second in the current super step for the node i; the calculation node can count the number of edges processed in each super step, and the EPS in the super step can be obtained by dividing the number of edges by the processing timei；
When Δ t is negative, the graph representing the computation node i has a computation load lower than the average load level, and the number of edges that the node needs to migrate into is Ein＝(μ-ti)*EPSi；
Number of edges E that the emigration node needs to emigrationoutAfter the determination, the vertex to be migrated can be selected from the vertices maintained by the migration node in descending order according to the number of the connected edges until the sum of the number of the edges of the selected vertex reaches Eout(ii) a (the determined migration vertices are also migration vertices because the information of the vertices is sent to the migration nodes by the migration nodes in the migration process, and the vertices needing to be migrated in the migration nodes do not need to be calculated because the migration vertices are the migration vertices of other nodes.)
Further, when the main control node determines the migration node corresponding to the migration vertex in step 5-4, the operation is as follows:
when the main control node receives the number of edges needing to be migrated or migrated from each computing node, namely EoutOr EinAccording to the corresponding EoutOr EinThe numerical values are sorted for all the computing nodes;
the master node first loads the heaviest, ieoutAssigning the migration vertex on the compute node with the largest | value to the one with the lightest load, i.e. | EinIf the heavy-load computing node still has migration vertices not assigned to the migration node, the number of edges migrated by the heavy-load computing node temporarily does not reach | EoutAssign these unassigned migration vertices to the next light loadCalculating a node; when the light load computing node has redundant space (each immigration node has an E)inValue, indicating how many edges it can accommodate at most) to accommodate more migration vertices, i.e., the number of edges the lightly loaded compute node has migrated to temporarily not reach | E |inIf yes, assigning the migration vertex on the next heavy-load computing node to the light-load computing node;
the main control node assigns corresponding migration nodes to all migration vertexes according to the method; due to each | EoutI is calculated from the corresponding emigration node, and each EinI is calculated from the corresponding entry node, so all | EoutSum of | and all | EinThe sum of | is not necessarily equal; when | EoutSum of | and | EinIf the sum of | is not equal, then there remains unmatched EoutOr EinWill be ignored by the master node.
Further, the migration phase implemented in step 6 includes the following sub-steps:
6-1, each emigration node sends migration vertex information to a corresponding emigration node;
6-2, after the vertex migration is completed, each migration node sends the ID and the position information of the migration vertex, namely the migration node of the migration vertex, to a master control node;
step 6-3, the main control node collects the ID of each migration vertex and the position information after migration in a table structure; the table structure is created at the first vertex migration and the contents of the table structure are updated at the later vertex migration; because a plurality of migration nodes migrate the vertexes maintained by the migration nodes, the position information of all the migration vertexes needs to be summarized at the main control node;
6-4, the master control node sends the aggregated position information table to each computing node; step 6-2, step 6-3 and step 6-4 update the location information of the migration vertices.
Further, in the step 6-1, the following method is used when the migration node migrates the vertex to the migration node:
after the super step is finished, the emigration node transmits the ID, the numerical value and the adjacent edge list of the migration vertex to the corresponding emigration node, and the new incoming message of the vertex, namely the message sent to the vertex by other vertices in the next super step is guided to the emigration node by changing the position information mode of the migration vertex (firstly, the emigration node of the vertex is sent to the main control node by the emigration node, and the main control node broadcasts the emigration node of the vertex to all other calculation nodes after being summarized); the incoming message received by the migration vertex in the super step of the current time is locally processed by the migration node in the super step of the next time, namely the message received in the super step of the current time is not sent immediately in the migration process, but is sent after being processed by the migration node, because the size of the message is very large, and the cost for transmitting the message through the network is huge; the new vertex value obtained after processing is sent to the immigration node by the immigration node after the next super step is finished; the vertex migration method enables incoming messages of the vertices to be locally processed by the migration nodes, and updated vertex values are sent to the migration nodes after next super-step is completed, so that the vertex migration can be completed only by two super-steps in total, and the method is called delayed migration; in the migration process, the node sending the migration vertex is called an egress node, and the node receiving the migration vertex is called an ingress node.
In general, the method of the present invention includes three main stages, namely, an unbalanced detection stage, a migration planning stage and a migration implementation stage. The technical conception of the invention is as follows: monitoring the processing time of each computing node in each super step when the graph computing task runs, and judging whether the graph computing load on each computing node is balanced or not according to the variation coefficient of the processing time of all the computing nodes in the previous super step and the current super step and a threshold preset by a user; and if the judgment result is that the graph calculation load is unbalanced, transferring the vertexes with corresponding quantity between the calculation nodes in a delayed transfer mode so as to balance the processing time of each calculation node in the next super step.
Compared with the prior art, the technical scheme of the invention has the following advantages:
the invention can balance the processing time of all the computing nodes in the distributed graph computing system in each super step, thereby reducing the synchronous cost of the computing nodes in each super step and shortening the running time of the graph computing task. In addition, in the invention, the computing nodes with strong processing capability are distributed with heavier graph computing load in each super step, so the hardware resources of each computing node are fully used to accelerate the convergence of the graph algorithm.
Drawings
FIG. 1 is a schematic structural view of the present invention;
FIG. 2 is a schematic diagram of the main steps of load calculation of the equilibrium graph according to the present invention;
FIG. 3 is a schematic diagram illustrating the determination of migration nodes during the migration planning phase of the present invention;
FIG. 4 is a schematic diagram illustrating a delayed migration in a migration phase of the present invention.
Detailed Description
In order to make the objects, technical solutions and advantages of the present invention more apparent, the present invention is described in further detail below with reference to the accompanying drawings and embodiments. It should be understood that the specific embodiments described herein are merely illustrative of the invention and are not intended to limit the invention. In addition, the technical features involved in the embodiments of the present invention described below may be combined with each other as long as they do not conflict with each other.
Some definitions will be used in the embodiments of the present invention, where the terms are to be interpreted as follows:
the heterogeneous server structure: a data center or cluster of servers with different processing capabilities or hardware configurations.
The master control node: and the nodes are responsible for resource management and task scheduling in the data center or the cluster.
The computing node: and in the data center or the cluster, except the main control node, the nodes which are responsible for processing local tasks.
Graph calculation: is a mode of computation. The method respectively abstracts objects and the relation thereof in the real world into vertexes and edges in a graph structure, and applies a corresponding graph algorithm on the graph structure to extract deep information which is interesting to a user in the graph structure.
Graph data set: a graph structure abstracted from objects and their relationships in the real world.
And (3) graph algorithm: mining algorithms written by developers or users to extract deep information in the graph.
Super step: the graph computation process is typically divided into several iterations, one iteration being referred to as a superstep.
Dyssynchrony: a synchronization barrier is arranged between two adjacent super steps to synchronize the numerical update of the activated vertex in each super step.
Standard deviation DS: weighing a group of data { x1，x2...xNThe parameter of the degree of dispersion is calculated by the formula
Where N is the total number of data items in the set of data. The magnitude of the standard deviation is affected by both the absolute value of the data item and the degree of dispersion.
Coefficient of variation CV: weighing a group of data { x1，x2...xNThe parameter of the degree of dispersion is calculated by the formula
Where u is the average of the set of data and N is the total number of data items in the set of data. The coefficient of variation is eliminated from the dimensional effect with respect to the standard deviation, and its magnitude is only affected by the degree of dispersion of the data items, not by the absolute values of the data items.
Migrating the node: in vertex migration, the compute node that migrated the vertex is sent.
And migrating the node: in vertex migration, a compute node that migrates a vertex is received.
Adjacent edge table: a vertex is typically connected to one or more edges, and the table of contiguous edges records the edges to which a vertex is connected and the weights of those edges.
Load balancing algorithm design scheme
In the running process of the graph computing task, when the graph computing load on the computing nodes is unbalanced in one super step, the most direct result is that the processing time of each computing node is different. To describe the problem of load imbalance among the compute nodes, a parameter is needed to quantify the degree of process time dispersion in a super-step. The most common parameter is the standard deviation, the size of which is affected by both the absolute value and the degree of dispersion of the data items. However, the absolute values of the processing times of the various graphical algorithms vary widely in one super-step, and the standard deviation obtained for the graphical algorithms with long processing times is also large. In order to consider the influence of the absolute magnitude of a group of time values but only the dispersion degree, the invention selects the coefficient of variation C as a key parameter for quantizing the dispersion degree of time. After one super step is finished, the larger the variation coefficient of the processing time is, the higher the discrete degree of the processing time in the super step is, that is, the more serious the imbalance of the graph calculation load among the calculation nodes is. The coefficient of variation calculation formula of the processing time in one super step is as follows:
wherein u is the average processing time in the super step, N is the total number of the computing nodes, and tiTo calculate the processing time of the node i in the super step. In order to balance the graph computation load among the computation nodes in each super step, the invention reduces the variation coefficient of the processing time in each super step in a vertex migration mode.
For some slight load imbalances, the overhead caused by the vertex migration is far greater than the benefit of load balancing. To avoid such unproductive vertex migration, the present invention provides for the user to assign a threshold CV to the algorithm prior to running the graph algorithmthr(default may be set to 0.10) for determining whether the degree of load imbalance in each super step is outside the user acceptable range; if the coefficient of variation calculated after one super step is over the threshold value (CV > CV)thr) If the graph calculation load of each calculation node is determined to be unbalanced during the operation, the graph calculation load on the calculation nodes needs to be redistributed after the super step is finished,otherwise, all the computing nodes will continue to execute the next super step. In addition, due to the characteristics of some graph algorithms (such as a single-source shortest path algorithm), the number of active vertices on each computing node changes dramatically during the operation process, so that the coefficient of variation increases sharply in one super step and recovers to a lower level in the next super step. When this occurs, it results in computing nodes migrating the same vertex back and forth in successive super-steps. In order to reduce the migration cost in the operation process of the graph algorithm, the invention provides that the vertex migration is executed for the computing node once only when the variation coefficients in the super step at the last time and the super step at the present time are both larger than the preset threshold value so as to balance the processing time in the subsequent super step.
Therefore, the graph computation load balancing algorithm oriented to the heterogeneous server structure is mainly suitable for a distributed graph computation system meeting the requirements of a master-slave structure. As shown in fig. 1, each compute node is responsible for storing information of a local vertex and performing update operation on a vertex value, sending the updated vertex value to other nodes in a message form, and concurrently migrating the vertex information to other nodes in a vertex migration phase; the main control node is responsible for collecting the state information of each computing node, including the processing time in each super step, drawing up a migration plan, informing all computing nodes of the migration plan, and updating and summarizing the position information of the vertex after migration. The subject logic of the load balancing algorithm is implemented in the master node.
As shown in fig. 2, the graph computation load distributed on the heterogeneous server structure is balanced, and the method includes the following steps:
step 1, importing all computing nodes into a graph algorithm and a graph data set;
step 2, executing one super step of the graph algorithm by all the computing nodes;
step 3, the main control node judges whether graph computation loads on the computation nodes are balanced;
step 4, if the judgment result in the step 3 is that the load is unbalanced, entering a stage of planning a migration plan, and turning to the step 5; otherwise, turning to step 7, and enabling all the computing nodes to enter the next super step;
step 5, each computing node determines the vertex needing to be migrated, and the main control node determines the migration nodes corresponding to the vertices;
step 6, all the computing nodes transmit the vertex information to the corresponding migration nodes in a delayed migration mode, and the main control node updates and summarizes the position information after the vertex migration;
and 7, repeating the steps 2 to 6 until the graph algorithm converges.
The graph computing load balancing algorithm oriented to the heterogeneous server structure provided by the invention is independent of a specific graph algorithm and a graph data set executed by a user, and can be used on any distributed graph computing system (such as Giraph and PowerGraph) meeting the requirements of a master-slave structure.
Second, drawing up the migration plan stage
When the variation coefficients calculated by the main control node in two consecutive super steps are larger than a preset threshold, it is determined that the graph calculation load on the calculation node is unbalanced, and the vertices on the calculation node need to be migrated to balance the processing time between the calculation nodes in the next super step. Therefore, the graph computing system enters a migration planning stage, and the main work of the stage is to determine the vertexes to be migrated on each computing node and migration nodes corresponding to the vertexes.
Firstly, the main control node sends the average processing time u calculated in the super step to each calculation node. When the computing node i receives the average processing time u sent by the main control node, the processing time t of the super step is computediDifference from average processing time Δ t ═ ti-u; when Δ t is positive, the graph representing the computation node i has a computation load higher than the average load level, and the number of edges that the node needs to migrate is Eout＝(ti-μ)*EPSiIn which EPSiCalculating the average number of edges processed per second in the current super step for the node i; when Δ t is negative, the graph representing the computation node i has a computation load lower than the average load level, and the number of edges that the node needs to migrate into is Ein＝(μ-ti)*EPSi. Number of edges E that the emigration node needs to emigrationoutAfter determination, then it is necessaryThe vertex to be migrated can be selected from the vertices maintained by the migration node in descending order according to the number of the connected edges until the sum of the number of the edges of the selected vertex reaches Eout. Here, the number of edges processed per second in one super-step is used to define the throughput of the compute node, rather than the number of vertices processed per second, because most graph data sets in the real world obey a power law distribution, i.e., a few vertices connect most edges in the graph. The time to process a vertex varies with the number of edges it connects, while the time to process an edge is generally stable, so the number of edges processed per second is used herein to define the throughput of the compute nodes to quantify the throughput of each compute node relatively fairly.
The number of edges that each compute node needs to migrate to or from (i.e., E)outOr Ein) Sending to the master control node according to EoutOr EinThe values of (c) are sorted for all compute nodes. As shown in FIG. 3, | E of node 1 is migratedoutThe | value is maximum, so the load of the super step is the heaviest, and the number of the top points to be migrated is the largest; similarly, | E migrating to node 1inThe value of | is the largest, so the load of the super step is the lightest, and the number of the top points to be migrated is the largest. Assigning the migration vertex on the computing node with the heaviest load (i.e. migration node 1) to the computing node with the lightest load (i.e. migration node 1), and if the migration vertex still on the computing node with the heaviest load is not assigned to the migration node, assigning the unassigned migration vertex to the next computing node with the light load (e.g. the vertex of migration node 1 is assigned to migration nodes 1 and 2); conversely, when there is excess space on a lightly loaded compute node to accommodate more migration vertices, then the migration vertices on the next heavily loaded compute node are assigned to the lightly loaded compute node (e.g., the vertices of the migrant nodes 2, 3 are assigned to the migrant node 3). The master node assigns migration nodes to all migration vertices according to the boxed method when all | E | (R)outSum of | and all | EinThe sum of | is unequal (e.g.
Then unmatched E remainsoutOr EinWill be ignored by the master node.
And finally, the master control node sends the result of assigning the migration node to the corresponding migration node, thereby completing the stage of planning the migration plan and entering the stage of implementing the migration.
Thirdly, implementing the migration phase
In the migration implementation phase, the graph computing system needs to complete two tasks, namely, migrating the vertex information to the corresponding migration node by the migration node, and updating and summarizing the position information of the migrated vertex by the main control node. Because each migration vertex has a definite migration node, the migration node can simultaneously send vertex information to one or more migration nodes. For most graph algorithms, the information of the vertices can be divided into two categories: constant size and varying size. The ID, value and adjacent edge table of the vertex are usually not changed in operation, for example, the ID of the vertex can be represented by an integer type, and the value of the vertex can be represented by a floating point type. The number of messages received by a vertex in each super-step varies due to the variation in the number of active vertices. Furthermore, the number of edges a vertex connects may be large, i.e., the number of messages that the vertex receives in a super-step may be large. Therefore, incoming messages for vertices are large in size relative to other types of vertex information, transmitting vertex messages across a network between compute nodes is time and resource intensive, and will severely impact the time for the graph algorithm to run.
In order to avoid huge cost for transmitting vertex information in vertex migration, the invention adopts a delay migration mode to migrate the vertex information. As shown in fig. 4, the compute node has a load imbalance in super step 1, and the master node detects the imbalance and develops a migration plan. At synchronization barrier 1, the migrant node sends the vertex ID, vertex message and adjacent edge table with relatively small size to the migrant node, while the incoming message with relatively large size is retained on the migrant node, and at the same time, the location information of the migration vertex becomes the migrant node (the location information is broadcasted to other computing nodes by the master node). In super-step 2, all incoming messages for the vertex are directed to the migrating node due to the change in the location information for the vertex, while incoming messages for the vertex received in super-step 1 are processed locally by the migrating node and a new vertex value is generated. In synchronization barrier 2, the emigration node sends the new vertex value obtained by calculation to the emigration node. Before super-step 3 begins, the vertex completes the migration from the migration node to the migration node. The migration is delayed, so that the incoming message of the vertex is locally processed by the emigration node and then is sent to the emigration node after the next super step is completed, and therefore, the migration of the vertex can be completed only by continuously performing two super steps in total. Meanwhile, in order to ensure the consistency of the values of the vertexes, the invention provides that only after the delay migration of one vertex is completely finished, the vertex can be arranged to carry out the next delay migration.
The post-vertex migration location information should be updated in time to ensure that incoming messages for the vertex are sent to the correct compute node after migration. In order to reduce the overhead of updating the vertex position information, the invention provides that the main control node updates and summarizes the position information of all the vertexes after the migration. And after the vertex ID, the vertex numerical value and the adjacent edge table are sent to the migration node, the migration node sends the ID of the migration vertex and the corresponding migration node to the main control node. The main control node collects the ID of each migration vertex and the position information after migration in a table structure, and sends the table structure to all the computing nodes after all the vertices are migrated, and each computing node records the latest position information of the migration vertex. At this point, each compute node completes the migration of the vertices.
Fourthly, characteristics of
The invention provides a graph computation load balancing algorithm for a heterogeneous server structure. The algorithm comprises three main stages in total: in the unbalanced detection stage, the main control node judges whether graph calculation loads on the calculation nodes are balanced or not according to the variation coefficients of the processing time of all the calculation nodes in the super step and a threshold preset by a user; in the stage of planning a migration plan, each computing node determines vertexes to be migrated, and a main control node determines migration nodes corresponding to the vertexes; and in the migration implementation stage, all the computing nodes transmit the vertex information to the corresponding migration nodes in parallel in a delayed migration mode, and the main control node updates and summarizes the position information after the vertex migration.
Compared with the existing similar invention, the algorithm takes the variation coefficient of the processing time in one super step as the key parameter for quantifying the load imbalance, and can accurately reflect the real distribution of the calculation load of the calculation node-node graph in the heterogeneous server structure; when the variation coefficient of the processing time in the super-steps of two consecutive times is larger than a preset threshold value, the vertex migration is executed, so that the migration cost when certain graph algorithms are executed can be effectively reduced; the vertex information is migrated among the computing nodes in a delayed migration mode, so that the time and the network bandwidth required by migration can be greatly reduced; the main control node is adopted to update and summarize the position information after the vertex migration, so that the cost for updating the position information can be reduced.
In general, the graph computation load balancing algorithm oriented to the heterogeneous server structure provided by the invention can adaptively balance the processing time of each computation node in each super step, and reduce various expenses in the vertex migration process as much as possible, thereby greatly reducing the running time of the graph computation task. In addition, in the graph computation load balancing algorithm provided by the invention, the computation nodes with strong processing capability are distributed with heavier graph computation loads in each super step, so that the hardware resources of each computation node are fully utilized to accelerate the convergence of the graph algorithm.
It will be understood by those skilled in the art that the foregoing is only a preferred embodiment of the present invention, and is not intended to limit the invention, and that any modification, equivalent replacement, or improvement made within the spirit and principle of the present invention should be included in the scope of the present invention.
Claims (7)
1. A graph computation load balancing method oriented to a heterogeneous server structure is characterized by comprising the following stages:
and (3) detecting unbalance: when a graph calculation task runs, the main control node monitors the processing time of each calculation node in each super step, and judges whether graph calculation loads on the calculation nodes are balanced or not according to the variation coefficient of the processing time of all the calculation nodes in the super step and a threshold preset by a user; the coefficient of variation is a parameter reflecting the degree of dispersion of a set of data values;
a migration planning stage is drawn: each computing node determines vertexes which need to be migrated, and the main control node determines migration nodes corresponding to the vertexes;
implementing a migration stage: all the emigration nodes transmit vertex information to corresponding emigration nodes in a delayed migration mode, and the main control node updates position information after vertex migration;
in the stage of detecting imbalance, judging whether graph computation loads on the computation nodes are balanced according to the variation coefficients of the processing times of all the computation nodes in the super step and a threshold preset by a user, including:
each computing node sends the processing time monitored in the super step to a main control node;
the main control node calculates the coefficient of variation CV of all processing time in the super step:
wherein u is the average processing time of all the calculation nodes in the super step, N is the total number of the calculation nodes, and tiCalculating the processing time monitored by the node i in the super step;
if the coefficient of variation CV calculated in the last super step and the super step is larger than the threshold CV preset by the userthrIf so, the main control node judges that the graph calculation load on each calculation node is unbalanced; otherwise, determining the graph computation load on each computation node as balanced;
and the master control node sends the judged result to all the computing nodes.
2. The heterogeneous server architecture oriented graph computation load balancing method of claim 1, comprising the steps of:
step 1, importing all computing nodes into a graph algorithm and a graph data set;
step 2, executing one super step of the graph algorithm by all the computing nodes;
step 3, the main control node judges whether graph computation loads on the computation nodes are balanced;
step 4, if the judgment result in the step 3 is that the load is unbalanced, entering a stage of planning a migration plan, and turning to the step 5; otherwise, turning to step 7, and enabling all the computing nodes to enter the next super step;
step 5, each computing node determines the vertex needing to be migrated, and the main control node determines the migration nodes corresponding to the vertices;
step 6, all the computing nodes transmit the vertex information to the corresponding migration nodes in a delayed migration mode, and the main control node updates and summarizes the position information after the vertex migration;
and 7, repeating the steps 2 to 6 until the graph algorithm converges.
3. The method for graph computation load balancing oriented to heterogeneous server structures as claimed in claim 2, wherein the step 5 of formulating a migration plan stage comprises the sub-steps of:
step 5-1, the main control node sends the average processing time u in the super step to each computing node;
step 5-2, each computing node judges whether the computing node is a migration node or a migration node according to the average processing time u;
if the node is migrated, calculating the number E of the edges needing to be migratedoutAnd further according to EoutDetermining a vertex needing to be migrated;
if the node is moved in, calculating the number E of the edges needing to be moved inin；
Step 5-3, the computing node sends the number of edges which need to be migrated out or migrated in to the master control node;
step 5-4, the main control node determines an immigration node corresponding to the immigration vertex according to the number of edges to be emigrated or immigrated by each calculation node;
and 5-5, the main control node sends the migration node information corresponding to the migration vertex to the corresponding migration node.
4. The graph computation load balancing method for the heterogeneous server structure according to claim 3, wherein the following operations are performed when each migration node determines the vertex to be migrated in step 5-2:
each computing node arranges the maintained vertexes in a descending order according to the number of edges connected with the vertexes; when the computing node i receives the average processing time u sent by the main control node, the processing time t of the super step is computediDifference Δ t from the average processing time u is ti-u; when Δ t is positive, the graph representing the computation node i has a computation load higher than the average load level, and the number of edges that the node needs to migrate is Eout＝(ti-μ)*EPSiIn which EPSiCalculating the average number of edges processed per second in the current super step for the node i;
when Δ t is negative, the graph representing the computation node i has a computation load lower than the average load level, and the number of edges that the node needs to migrate into is Ein＝(μ-ti)*EPSi；
Number of edges E that the emigration node needs to emigrationoutAfter the determination, the vertex to be migrated can be selected from the vertices maintained by the migration node in descending order according to the number of the connected edges until the sum of the number of the edges of the selected vertex reaches Eout。
5. The graph computation load balancing method for the heterogeneous server structure according to claim 3, wherein the operations when the main control node determines the migration node corresponding to the migration vertex in step 5-4 are as follows:
when the main control node receives the number of edges which need to be migrated or migrated and are sent by each computing node, the main control node migrates the edge number according to the corresponding EoutOr EinThe numerical values are sorted for all the computing nodes;
the main control node firstly assigns the migration vertex on the computing node with the heaviest load to the computing node with the lightest load, and if the migration vertex on the computing node with the heaviest load is not assigned to the migration node, assigns the migration vertex which is not assigned to the next computing node with the lightest load; when the light-load computing node has redundant space for containing more migration vertexes, assigning the migration vertexes on the next heavy-load computing node to the light-load computing node;
the main control node assigns corresponding migration nodes to all migration vertexes according to the method; due to each | EoutI is calculated from the corresponding emigration node, and each EinI is calculated from the corresponding entry node, so all | EoutSum of | and all | EinThe sum of | is not necessarily equal; when | EoutSum of | and | EinIf the sum of | is not equal, then there remains unmatched EoutOr EinWill be ignored by the master node.
6. The method for graph computation load balancing towards heterogeneous server structures according to claim 2, wherein the implementation of the migration phase in step 6 comprises the sub-steps of:
6-1, each emigration node sends migration vertex information to a corresponding emigration node;
6-2, after the vertex migration is completed, each migration node sends the ID and the position information of the migration vertex to a main control node;
step 6-3, the main control node collects the ID of each migration vertex and the position information after migration in a table structure;
and 6-4, the master control node sends the aggregated position information table to each computing node.
7. The graph computation load balancing method for the heterogeneous server structure according to claim 6, wherein the following method is used when migrating the vertex from the migration node to the migration node in step 6-1:
after the super step is finished, the emigration node transmits the ID, the numerical value and the adjacent edge table of the migration vertex to the corresponding emigration node, and leads new incoming messages of the vertex to be guided to the emigration node in the next super step by changing the position information of the migration vertex; and the incoming message received by the migration vertex in the super step is sent to the migration node by the migration node after the next super step is finished by the new vertex numerical value obtained after the local processing of the migration node in the next super step.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201711274503.8A CN108089918B (en) | 2017-12-06 | 2017-12-06 | Graph computation load balancing method for heterogeneous server structure |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201711274503.8A CN108089918B (en) | 2017-12-06 | 2017-12-06 | Graph computation load balancing method for heterogeneous server structure |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN108089918A CN108089918A (en) | 2018-05-29 |
| CN108089918B true CN108089918B (en) | 2020-07-14 |
Family
ID=62174116
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201711274503.8A Active CN108089918B (en) | 2017-12-06 | 2017-12-06 | Graph computation load balancing method for heterogeneous server structure |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN108089918B (en) |
Families Citing this family (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN110489229B (en) * | 2019-07-17 | 2020-06-30 | 长沙学院 | Multi-target task scheduling method and system |
| CN110532091B (en) * | 2019-08-19 | 2022-02-22 | 中国人民解放军国防科技大学 | Graph computation edge vector load balancing method and device based on graph processor |
| CN110515729B (en) * | 2019-08-19 | 2022-05-24 | 中国人民解放军国防科技大学 | Graph computing node vector load balancing method and device based on graph processor |
| TWI729606B (en) * | 2019-12-05 | 2021-06-01 | 財團法人資訊工業策進會 | Load balancing device and method for an edge computing network |
| CN111459914B (en) * | 2020-03-31 | 2023-09-05 | 北京金山云网络技术有限公司 | Optimization method and device of distributed graph database and electronic equipment |
Citations (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN102244685A (en) * | 2011-08-11 | 2011-11-16 | 中国科学院软件研究所 | Distributed type dynamic cache expanding method and system supporting load balancing |
| CN103081416A (en) * | 2010-09-08 | 2013-05-01 | 瑞典爱立信有限公司 | Automated traffic engineering for multi-protocol label switching (MPLS) with link utilization as feedback into the tie-breaking mechanism |
| CN103546530A (en) * | 2013-06-20 | 2014-01-29 | 江苏大学 | Method and system for balancing loads on peer-to-peer network nodes on basis of group resource management |
| CN104270402A (en) * | 2014-08-25 | 2015-01-07 | 浪潮电子信息产业股份有限公司 | Adaptive data loading method for heterogeneous cluster storage |
Family Cites Families (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US8792633B2 (en) * | 2012-09-07 | 2014-07-29 | Genesys Telecommunications Laboratories, Inc. | Method of distributed aggregation in a call center |
| US9934323B2 (en) * | 2013-10-01 | 2018-04-03 | Facebook, Inc. | Systems and methods for dynamic mapping for locality and balance |
-
2017
- 2017-12-06 CN CN201711274503.8A patent/CN108089918B/en active Active
Patent Citations (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN103081416A (en) * | 2010-09-08 | 2013-05-01 | 瑞典爱立信有限公司 | Automated traffic engineering for multi-protocol label switching (MPLS) with link utilization as feedback into the tie-breaking mechanism |
| CN102244685A (en) * | 2011-08-11 | 2011-11-16 | 中国科学院软件研究所 | Distributed type dynamic cache expanding method and system supporting load balancing |
| CN103546530A (en) * | 2013-06-20 | 2014-01-29 | 江苏大学 | Method and system for balancing loads on peer-to-peer network nodes on basis of group resource management |
| CN104270402A (en) * | 2014-08-25 | 2015-01-07 | 浪潮电子信息产业股份有限公司 | Adaptive data loading method for heterogeneous cluster storage |
Also Published As
| Publication number | Publication date |
|---|---|
| CN108089918A (en) | 2018-05-29 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN108089918B (en) | Graph computation load balancing method for heterogeneous server structure | |
| CN108829494B (en) | Container cloud platform intelligent resource optimization method based on load prediction | |
| CN108182105B (en) | Local dynamic migration method and control system based on Docker container technology | |
| CN110347498B (en) | Load dynamic migration method in container and virtual machine mixed cloud environment | |
| CN110231976B (en) | Load prediction-based edge computing platform container deployment method and system | |
| WO2018000991A1 (en) | Data balancing method and device | |
| CN112486690A (en) | Edge computing resource allocation method suitable for industrial Internet of things | |
| CN106681839B (en) | Elastic calculation dynamic allocation method | |
| CN111131486B (en) | Load adjustment method and device of execution node, server and storage medium | |
| CN107220108B (en) | Method and system for realizing load balance of cloud data center | |
| CN105117292B (en) | STOCHASTIC DIFFUSION dynamic load balancing method | |
| CN106528270A (en) | Automatic migration method and system of virtual machine based on OpenStack cloud platform | |
| CN105893155B (en) | Virtual machine control method for equalizing load and device | |
| CN112148492A (en) | Service deployment and resource allocation method considering multi-user mobility | |
| CN113033800A (en) | Distributed deep learning method and device, parameter server and main working node | |
| CN104104621A (en) | Dynamic adaptive adjustment method of virtual network resources based on nonlinear dimensionality reduction | |
| CN106059940B (en) | A kind of flow control methods and device | |
| CN113965569A (en) | High-energy-efficiency low-delay edge node calculation migration framework and configuration system | |
| CN113315669A (en) | Cloud edge cooperation-based throughput optimization machine learning inference task deployment method | |
| US9749219B2 (en) | Method of optimizing routing in a cluster comprising static communication links and computer program implementing that method | |
| CN102480502A (en) | I/O load balancing method and I/O server | |
| CN107479968B (en) | Load balancing method and system for incremental calculation of dynamic graph | |
| TW201627873A (en) | Method and Apparatus of Processing Retransmission Request in Distributed Computing | |
| CN110990059B (en) | Stream type calculation engine operation method and system for tilt data | |
| US9203733B2 (en) | Method of pseudo-dynamic routing in a cluster comprising static communication links and computer program implementing that method |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant |