# US 2025/0097282 A1 · Three-class vertex degree aware-based 1.5-dimensional graph division method and application

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2025/0097282 A1
- Document ID: US20250097282A1
- Status: Published application
- Kind: A1
- Application number: 18/901,324
- Filed: 2024-09-30
- Published: 2025-03-20
- Earliest claimed: 2022-03-31
- Assignees: Research Institute of Tsinghua University in Shenzhen
- Applicants: Research Institute of Tsinghua University in Shenzhen
- Inventors: Huanqi CAO; Yuanwei WANG
- Web page: https://patentgrep.com/patent/US20250097282A1

## CPC

- H04L 67/10: in which an application is distributed across nodes in the network (software deployment G06F8/60; multiprogramming arrangements G06F9/46)
- G06F 9/5066: {Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs (mappping at compile time, see G06F8/451)}
- G06F 2209/501: Performance criteria
- G06F 2209/5011: Pool
- G06F 2209/505: Clust
- Y02D 10/00: Energy efficient computing, e.g. low power processors, power management or thermal management
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- Y02D: CLIMATE CHANGE MITIGATION TECHNOLOGIES IN INFORMATION AND COMMUNICATION TECHNOLOGIES [ICT], I.E. INFORMATION AND COMMUNICATION TECHNOLOGIES AIMING AT THE REDUCTION OF THEIR OWN ENERGY USE

## Abstract

Provided are a distributed parallel computing-based graph computing method, a distributed parallel computing system, and a computer readable medium. The graph computing method comprises: obtaining data of a graph to be computed, dividing vertexes into a first extremely high degree class E, a second high degree class H, and a third regular class R, forming a super node by a predetermined number of compute nodes, the communication between nodes in a super node being faster than the communication between nodes across the super node, and dividing the nodes into grids, one node in each grid, the internal nodes in one super node being logically arranged in a row, vertices being evenly divided into the nodes according to numbers, Ri and Ro being maintained by the nodes to which Ri and Ro belong, the state of an Ho vertex being synchronously maintained on a column, the state of an Hi vertex being synchronously maintained on the column and the row, and the states of Eo and Ei vertexes being globally and synchronously maintained. According to the three-level vertex division method, sub-graphs are well balanced between the nodes, thereby facilitating elimination of repeated sending of a message to a same super node, and avoiding a high-cost global delegate.

## Claims

### Claim 1

A graph computing method based on distributed parallel computing, including:
obtaining data of 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 an edge X→Y represents the edge from vertex X to vertex Y,
dividing the vertices into a first extremely high degree class, a second high degree class and a third ordinary class according to degree of the vertices, 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, 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 as Xi and Xo respectively, where X is E, H or R, at the same time, a super node is composed of a predetermined number of nodes, each node being a computing device with computing power, wherein communication speed between nodes within a super node is faster than the communication speed between nodes across the super node, nodes being divided into grids, with one node in each grid and internal nodes in a super node being logically arranged in a row, vertices being evenly distributed to each node according to their serial numbers, vertices Ri and Ro being maintained by nodes they belong to, Ho vertex status is synchronously maintained on the column that the Ho vertex belongs to, the Hi vertex state being synchronously maintained 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 synchronously maintained globally, Eo and Ho being collectively called EHo, and Ei and Hi being collectively called EHi.

### Claim 2 (depends on 1)

The graph computing method of claim 1, allocation and storage of vertex-corresponding delegates is performed according to edge conditions as follows:
for the edge EHo→EHi, this type of edge is stored on such a node that the node is on the grid column where the source vertex is located and the node is on the grid row where the target vertex is located;
for the edge Eo→Ri, this type of edge is stored on the node where the R vertex is located to allow global maintenance of extremely high degree vertices during calculation and aggregation of their communication messages;
for the edge Ho→Ri, this type of edge is stored on such a node, that the node is on the grid column where the H vertex is located, and the node is on the grid row where the R vertex is located, to allow the maintain of high-degree vertices on columns during calculation and aggregation of communication messages in communication across the super node, when for the Ho vertex, a message needs to be sent to multiple target vertices of the same super node, because the source vertex has an available delegate node in its own column and on the row of its target vertices, so a message is first sent to the available delegate node across the super node and then sent to all target vertices by the available delegate node through the fast network within the super node;
for the edge Ro→Ei, this type of edge is stored on the node where the R vertex is located to allow global maintenance of extremely high degree vertices during calculation and aggregation of their communication messages;
for the edge Ro→Hi, this type of edge is stored on the node where the R vertex is located, but the H vertex is stored according to the number on the column, so as to allow the calculation to accumulate its update messages on the node in the row where R is located and the column where H is located, and the aggregation of network communication across super nodes;
for the edge Ro→Ri, forward and reverse edges for this type of edges are stored at the source vertices and target vertices respectively, and edge messages are implemented by rows forwarding and columns forwarding on communication grids.

### Claim 3 (depends on 1)

The graph computing method of claim 1, wherein the first threshold is the total number of nodes multiplied by a constant coefficient, and the second threshold is the number of nodes in the super node multiplied by the second constant coefficient.

### Claim 4 (depends on 1)

The graph computing method of claim 1, two traversal modes of “push” and “pull” are implemented, and the traversal mode is automatically selected according to the proportion of active vertices, for three types of locally calculated edges EHo→EHi, Eo→Ri, Ro→Ei, “pull” or “push” mode is select based on whether the activity ratio of the target vertex exceeds a configurable threshold; for three types of locally calculated edges Ho→Ri, Ro→Hi, and Ro→Ri, “Pull” or “Push” mode is selected according to whether the ratio of the activity ratio of the target vertices to the activity ratio of the source vertices exceeds a configurable threshold.

### Claim 5 (depends on 1)

The graph computing method of claim 1, wherein
in the breadth-first search, it is judged whether the iteration is at the head or tail or in the middle, when it is judged that the iteration is at the head or tail, the graph traversal is performed by “pulling” from the target vertex to the source vertex; when it is judged that the iteration is in the middle, the manner of the source vertex “pushing” to the target vertex is used for graph traversal; and
in PageRank, subgraphs that locally traverse the graph and reduce use the “pull” mode to achieve optimal computing performance, while subgraphs involving remote edge messages use the “push” mode to minimize communication volume.

### Claim 6 (depends on 5)

The graph computing method of claim 5, further comprising:
in the pull mode, setting the status mark of the vertex to determine whether the status of a vertex has reached the dead state, in the dead state, the vertex will not respond to more messages;
after confirming that the dead state has been reached, processing of the remaining messages is skipped.

### Claim 7 (depends on 2)

The graph computing method of claim 2, for a subgraph in which both the source vertex and the target vertex belong to the first extremely high-degree class and the second high-degree class, the forward graph is segmented according to the target vertex, and the reverse graph is segmented according to the source vertices, and a graph is divided into multiple segmented subgraphs SSG (Segmented Sub-Graph), so that the target vertices in each segmented subgraph are limited to a certain range.

### Claim 8 (depends on 7)

The graph computing method of claim 7 is performed on a general-purpose multi-core processor, and the predetermined range is a size that can be stored in a last level cache LLC (Last Level Cache).

### Claim 9 (depends on 7)

The graph computing method of claim 7, wherein edge processing in pull mode is performed on heterogeneous many-core processors, using the remote access mechanism of local data memory LDM (Local Data Memory) to store a source vertex segmentation of a segmented subgraph SSG in the reverse graph into an LDM of the slave core array, and then during the graph traversal process, data is obtained from the slave core that owns the target vertex by slave core accessing RLD (Remote Load).

### Claim 10 (depends on 9)

The graph computing method of claim 9, wherein the source vertices of the first extremely high degree class and the second high-degree class are numbered according to the following rules:
from high bit to low bit: segment number; cache line number, slave core number, slave core local number.

### Claim 11 (depends on 10)

The graph computing method of claim 10, the number of digits in the cache line number is calculated according to the sum of the sizes of vertex data elements to ensure that the local data memory LDM can store all of them; the next six bits are used to distinguish the slave core number to which it belongs; the number of local number digits is calculated based on the vertex data element size minimum to ensure DMA efficiency.

### Claim 12 (depends on 11)

The graph computing method of claim 11, each slave core first uses a direct memory access DMA operation with stride to prefetch the vertex data in the segment according to the slave core number bit; during edge processing in pull mode, when reading the source vertex EHo of the first extremely high-degree class and the second high-degree class, the local data memory remote load (LDM RLD) is used to read the LDM corresponding address of the slave core to which the source vertex belongs.

### Claim 13 (depends on 1)

The graph computing method of claim 1, for Reduce Scatter type communication of the target vertex EHi of the first extremely high degree class and the second high degree class: for reduction on rows and columns, a ring algorithm is used; for global reduction, message is first transposed locally to change data from row-major to column-major, and then reduction scatter on the row is first called, and then reduction scatter on the column is called to reduce communication across supernodes on the column.

### Claim 14 (depends on 1)

The graph computing method of claim 1, the graph computing method is performed on a heterogeneous many-core processor, in the processing of edge messages, a message generation part and a message rearrangement part use bucketing steps to distribute messages to target nodes;
slave cores are divided into 2 categories by row, producers and consumers, the producer obtains data from memory and performs data processing at current stage, if there is data generated, it is placed in a sending buffer corresponding to the consumer that should process the message according to target address, when the buffer is full, it is passed to the corresponding consumer through RMA, the consumer receives the message delivered by RMA and performs subsequent operations that require mutual exclusion;
consumers of the same number in each core group are responsible for the same output bucket, and counting of bucket tail position is implemented between core groups through atomic fetch and addition on main memory.

### Claim 15 (depends on 1)

The graph computing method of claim 1, the graph computing method is performed on a heterogeneous many-core processor, in the processing of edge messages, a message update part uses two-stage sorting to implement random updates of local vertices:
first, perform bucket sorting on all update operations to be performed, cluster vertices into the same bucket according to number, and sort all messages into each bucket to ensure that the number of vertices in each bucket is small enough that vertex information can be placed in LDM of a core group, which is called coarse-grained sorting;
each in a core group processes messages from one bucket at a time, and delivers message groups to each consumer core through on-chip sorting, each consumer core is responsible for a different vertex range, and then performs mutually exclusive updates to the vertices.

### Claim 16

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.

### Claim 17 (depends on 1)

A computer-readable medium having instructions stored thereon that, when executed by a distributed parallel computing system, perform the method of claim 1.