FPGA coprocessor with sparsity and density modules for execution of low and high parallelism portions of graph traversals
US11263168B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Dec 20, 2019 |
| Grant date | Mar 1, 2022 |
| Priority date | — |
| Expiry date | Dec 20, 2039 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F2015/768
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
An FPGA-based graph data processing method is provided for executing graph traversals on a graph having characteristics of a small-world network by using a first processor being a CPU and a second processor that is a FPGA and is in communicative connection with the first processor, wherein the first processor sends graph data to be traversed to the second processor, and obtains result data of the graph traversals from the second processor for result output after the second processor has completed the graph traversals of the graph data by executing level traversals, and the second processor comprises a sparsity processing module and a density processing module, the sparsity processing module operates in a beginning stage and/or an ending stage of the graph traversals, and the density processing module with a higher degree of parallelism than the sparsity processing module operates in the intermediate stage of the graph traversals.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.