Collective communication optimization method for global high-degree vertices, and application
US12417255B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Sep 30, 2024 |
| Grant date | Sep 16, 2025 |
| Priority date | — |
| Expiry date | Sep 30, 2044 |
Classification
- Technology area (CPC Y)Emerging Cross-Sectional Technologies
- CPC primaryY02D10/00
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
This disclosure provides a graph computation method based on distributed parallel computing, a distributed parallel computing system, and a computer-readable medium. The graph computation method includes the following steps: obtaining the data of the graph to be computed, where the graph consists of multiple vertices and edges. For a subgraph where the degrees of both the source vertex and the target vertex are greater than a predetermined threshold, and for the reduce-scatter type communication for the target vertex, the following operations are performed: for reductions along rows and columns, a ring algorithm is used; for global reductions, the message is first transposed locally to change the data order from row-major to column-major. Then, the row-wise reduce-scatter is performed first, followed by the column-wise reduce-scatter, to reduce communication across super node along columns. The graph computation method of this disclosure optimizes collective communication to reduce communication across super node along columns. The hierarchical reduce-scatter eliminates redundant data within the super node in the first step of row-wise reduction, so that the communication across th…
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.