Three-class vertex degree aware-based 1.5-dimensional graph division method and application

A distributed parallel computing system with multiple super nodes, each super node is composed of multiple nodes, each node is a computing device with computing capabilities, inter-node communication within the super node is faster than communication between nodes across the super node, the nodes are divided into grids, each grid has one node, and the internal nodes of a super node are logically arranged in a row, the distributed parallel computing system stores graphs and performs graph calculations according to the following rules:

• obtain data for a graph to be computed, the graph including a plurality of vertices and edges, wherein each vertex represents a corresponding operation, wherein each edge connects a corresponding first vertex to a corresponding second vertex, the operation represented by the corresponding second vertex receives the output of the operation represented by the corresponding first vertex as input, and edge X→Y represents the edge from vertex X to vertex Y,
• divide the vertices into a first extremely high degree class, a second high degree class and a third ordinary class according to degree of the vertice, wherein vertices with degrees greater than a first threshold are marked as E and are divided into the first extremely high degree class, vertices with degree between the first threshold and a second threshold are marked as H and are divided into the second high degree class, the vertices with degrees lower than the second threshold are marked as R and are divided into the third ordinary class, and the first threshold is greater than the second threshold;
• for directed graphs, vertices are divided according to in-degree and out-degree respectively, an in-degree partition set and an out-degree partition set are marked Xi and Xo respectively, where X is E, H or R,
• divide the vertices evenly to each node according to their serial number, vertices Ri and Ro are maintained by the nodes to which they belong, Ho vertex status is maintained synchronously on the column that the Ho vertex belongs to, the Hi vertex state is maintained synchronously on the column that the Hi vertex belongs to and row that the Hi vertex belongs to, and Eo vertex status and Ei vertex status are globally synchronously maintained, Eo and Ho are collectively called EHo, and Ei and Hi are collectively called EHi.