Graphic calculation iteration processing method based on SCC-DAG

Abstract

The invention discloses a graphic calculation iteration processing method based on SCC-DGA. The method comprises the processing step and the calculation step; specifically, in the stage of preprocessing, all SCCs in a given graph are obtained, and the SCC-DGA is constructed through connection among the SCCs; in the stage of calculation, according to the topological sorting of the SCCs in the SCC-DGA, iteration is performed inside the SCCs of the SCC-DGA in sequence till convergence of all the SCCs is achieved, and data in the convergence status is output as a computational result of a corresponding algorithm. According to the graphic calculation iteration processing method based on SCC-DGA, iteration processing is defined inside the SCCs, and iteration operation is performed independently inside each SCC; when all the SCCs inside the SCC-DGA are subjected to convergence, the whole graph is in the convergence status; according to the graphic calculation iteration processing method, the low preprocessing cost is needed for increasing the graph convergence speed, calculation redundancy is reduced, and the IO resource cost is lowered.

Description

technical field [0001] The invention belongs to the field of graph computing for computer big data processing, and more specifically relates to a graph computing iterative processing method based on SCC-DAG. Background technique [0002] "Graph" is a data structure that expresses the connection relationship between objects in the real world. Based on the structure of the graph, running the graph algorithm to analyze the graph can obtain useful information contained in it. For example, the importance of vertices in the graph can be obtained through the PageRank algorithm; the shortest path between vertices can be obtained through the SSSP algorithm; these algorithms finally reach a state of convergence through multiple rounds of iterations; the data of the convergence state is the result of the algorithm operation. [0003] The iterative method includes synchronous iteration and asynchronous iteration; the synchronous iterative method is based on the traditional BSP model, wh...

AI Technical Summary

Problems solved by technology

Synchronous iteration has the following problems: (1) Unbalanced load: Due to the difference in the number of edges of the vertices in the graph, the calculation amount of the vertices of the graph is different. Each iteration needs to wait for the entire graph to be traversed, making the number of edges very small. The vertices need to wait for the calculation of vertices with a large number of edges to complete; (2) the convergence is slow, and the essence of the iterative convergence of the graph algorithm is to allow the data to be fully transmitted between the vertices according to the structure of the vertex links in the graph; since each round of iteration is based on The iterative data of the previous round makes each round of iterative operation only able to transfer data to the neighbor vertices of the vertex, and the data transfer efficiency is slow, which makes the graph converge slowly

However, asynchronous iteration still has the following problems: (1) Computation is not saturated: because the vertices can be calculated when they meet the conditions, some vertices start to calculate before accumulating enough data, resulting in unsaturated calculation; (2) Unstable: The transmission of data between vertices is not simultaneous, but is transmitted between vertices separately, causing data to oscillate back and forth between vertices, and the convergence of the graph cannot be effectively completed

That is, during iteration, most of the converged vertices will be affected by a small number of unconverged vertices, and become non-convergent, and each iteration needs to calculate most or all of the entire graph, which brings a lot of computational redundancy, resulting in A lot of CPU resource consumption

Moreover, in the big data environment, the scale of graph data reaches tens of billions or even hundreds of billions of records, which makes computing redundancy consume a lot of IO resources, because the memory can no longer meet the storage of graph data, and peripherals are needed Resources, and then there are a large number of IO swapping in and swapping out operations during iteration, resulting in huge IO resource consumption

Images