Distributed graph calculation method based on disk

Abstract

The invention discloses a distributed graph calculation method based on a disk. The method adopts a distributed calculation model based on the disk, and partitions an original graph into P sub-graphs by a graph partitioning algorithm, one graph algorithm operation is finished through N-frequency iteration, one execution of each sub-graph is one task, and (P*N) pieces of tasks are contained; one task comprises the following steps: (1) loading and constructing the sub-graphs; (2) calculating the sub-graphs; and (3) storing a result, and sending relevant data to other sub-graphs. The method schedules tasks in a running water way, the tasks can be subjected to overlapping execution to hide the time delay of disk read, write and communication in a system execution process, the execution process causes the operation time of the whole system to be almost shortened to calculation time, system performance is greatly improved, and the system can still keep an extremely small system scale by facing to the graphs of different scales so as to greatly save the hardware cost of the system.

Description

technical field [0001] The invention belongs to the technical field of computers, and more specifically relates to a disk-based distributed graph computing method. Background technique [0002] Graph is the most commonly used abstract data structure in computer science. It is more complex than linear tables and trees in terms of structure and semantics, and has more general representation capabilities. In the context of today's big data, there are more and more large-scale graph analysis application requirements; for various large-scale graph computing application requirements, computing models are often used for processing; computing models are related to the hardware cost of the graph processing system, Performance, efficiency and other important features, the current graph processing system mainly uses the following calculation models: [0003] Memory-based large-scale synchronous parallel processing model (BulkSynchronousParallelmodel, BSP): A graph computing job (job) ...

AI Technical Summary

Problems solved by technology

[0004] One is that after the end of each superstep, the system needs to execute a high-cost synchronization process for message exchange between vertices; the other is that only the calculation results of the previous superstep can be observed, which reduces the convergence speed of calculation, and even Some graph algorithms cannot converge; third, the strong coupling between graph data vertices and the lack of parallelism of graph algorithms make it difficult for the parallel processing capabilities of large-scale clusters to play a role; fourth, the degree distribution of natural graphs is extremely uneven, namely Very few vertices have most of the degrees. These "high degree" vertices become an important performance bottleneck in the BSP calculation model. The system cannot perform synchronous message exchange until the slowest vertex calculation is completed; therefore, the model is less efficient , and as the size of the processed graph increases, this disadvantage becomes more obvious

[0005] Memory-based large-scale asynchronous parallel computing model (BulkAsynchronousParallelmodel, BAP): The BAP computing model also performs parallel computing in units of vertices, and the vertices can observe the latest value of the neighbor vertices of the current iteration during the computing process; the BAP computing model cancels the synchronization In the process of message exchange, a vertex directly updates the values ​​of its neighbor vertices and edges during the calculation process; this method has the following defects: two vertices cannot update the same vertex at the same time, and the data correlation between vertices makes the large-scale parallel processing capability It cannot be fully utilized, and the system efficiency is low. For larger-scale graphs, the system needs larger-scale clusters

[0006] Serial computing model based on a single disk node: This computing model divides the vertices of the graph into multiple disconnected intervals, and the system executes these intervals serially in one round of iterations; the execution of each interval is divided into Three stages: (1) Loading and construction of subgraphs, (2) Calculation (CPU time), (3) Saving results; this method saves hardware costs and the system efficiency is very high; however, since each interval is executed, the system The subgraph needs to be loaded from the disk to the memory, and the result needs to be saved to the disk after the calculation is completed. The reading and writing time of the system usually reaches 90% of the entire running time, and the high reading and writing overhead reduces the performance of the system.

Images