Dynamic maximal clique enumeration device and method based on FPGA with HBM

Patent metadata

Field	Value
Publication number	US-12380176-B2
Application number	US-202318833896-A
Country	US
Kind code	B2
Filing date	Nov 28, 2023
Priority date	Nov 7, 2023
Publication date	Aug 5, 2025
Grant date	Aug 5, 2025

Abstract

Disclosed in the present invention are a dynamic maximal clique enumeration device and method based on an FPGA with an HBM, the method including: the HBM stores a dynamic edge flow, a complete graph adjacency matrix, and candidate cliques; a matrix computing unit updates the complete graph adjacency matrix based on the dynamic edge flow, transmits the updated complete graph adjacency matrix to the HBM for storage, and determines header nodes, of which the corresponding candidate clique needs to be updated; a sequence computing unit constructs, according to the updated complete graph adjacency matrix and each header node to be updated, the sorted data set for reconstructing candidate cliques by data block sequencing; and an update computing unit executes, in parallel, an update task of the candidate clique corresponding to each header node to be updated based on the sorted data set, transmits the updated candidate cliques to the HBM for storage, and transmits the updated candidate cliques to the PC host to extract maximal cliques by means of a filtering operation. The present invention supports the computation of pipelined-type incremental maximal clique, thereby improving the overall computing efficiency of the task.

First claim

What is claimed is:

1. A dynamic maximal clique enumeration device based on an Field Programmable Gate Array (FPGA) with an High Bandwidth Memory (HBM), wherein the device comprises the FPGA with the HBM; and a matrix computing unit, a sequence computing unit and an update computing unit which are constructed by means of function isolation and division and algorithm function division of First-In-First-Outs (FIFOs) of the FPGA;
the HBM is used to store a dynamic edge flow, a complete graph adjacency matrix, and a candidate clique which are transmitted from an external PC host and used for updating a graph structure, wherein the dynamic edge flow is a data flow formed by dynamic edges, each dynamic edge is e +/− (v i , v j ), where, v i and v j are all nodes to be updated, e + (v i , v j ) indicates that an edge is added between v i and v j , and e − (v i , v j ) indicates that an edge between v i and v j is deleted;
the matrix computing unit is used to update the complete graph adjacency matrix based on the dynamic edge flow, transmit the updated complete graph adjacency matrix to the HBM for storage, and determine a header node to be updated that needs to update the candidate clique;
the sequence computing unit is used to construct, according to the updated complete graph adjacency matrix and each header node to be updated, a sorted data set for reconstructing candidate cliques by data block sequencing; and
the update computing unit is used to execute, in parallel, an update task of the candidate clique corresponding to each header node to be updated based on the sorted data set for reconstructing candidate cliques, transmit the updated candidate cliques to the HBM for storage, and transmit the updated candidate cliques to the PC host to extract maximal cliques by means of a filtering operation.

2. The dynamic maximal clique enumeration device based on an FPGA with an HBM according to claim 1 , wherein the matrix computing unit comprises a first FIFO and is used for updating the complete graph adjacency matrix based on the dynamic edge flow, comprising:
caching the dynamic edge flow obtained from the HBM in the first FIFO; determining a node to be updated and a neighbor node set of the node to be updated according to the dynamic edge flow; obtaining an old adjacency list of all the nodes to be updated from the complete graph adjacency matrix of the HBM; updating the old adjacency list according to the neighbor node set; and writing the updated adjacency list in the HBM for storage to realize the update of the complete graph adjacency matrix, wherein the neighbor node set comprises a small neighbor node set and a large neighbor node set of the node to be updated.

3. The dynamic maximal clique enumeration device based on an FPGA with an HBM according to claim 2 , wherein in the matrix computing unit, determining the header node to be updated that needs to update the candidate clique comprises:
determining, according to the small neighbor node set of the node to be updated, the header node to be updated which is generated by a current batch of dynamic edge flow and needs to update the candidate clique, and using an index to record a node corresponding to a rollback position of the candidate clique of each header node to be updated.

4. The dynamic maximal clique enumeration device based on an FPGA with an HBM according to claim 3 , wherein the sequence computing unit comprises a plurality of second FIFOs, and wherein constructing, according to the updated complete graph adjacency matrix and each header node to be updated, a sorted data set for reconstructing candidate cliques by data block sequencing, comprises:
obtaining the updated adjacency list corresponding to each header node to be updated in an index record from the updated complete graph adjacency matrix in the HBM, and computing the large neighbor node set required for updating the candidate clique of each header node to be updated according to the index record and the updated adjacency list; and
obtaining small neighbor node sets corresponding to each large neighbor node from the HBM, and intersecting each small neighbor node set with the large neighbor node set respectively, and determining a common neighbor node set of each large neighbor node; and
constructing a second FIFO of the plurality of second FIFOs for each header node to be updated, and sequencing the large neighbor node of each header node to be updated and the corresponding common neighbor node set according to node sequence numbers, then storing the sequenced large neighbor node and corresponding common neighbor node set in the second FIFO to form a sorted data set for reconstructing candidate cliques.

5. The dynamic maximal clique enumeration device based on an FPGA with an HBM according to claim 3 , wherein the update computing unit comprises a plurality of third FIFOs and a plurality of Block Random Access Memory (BRAM) blocks, and wherein executing, in parallel, an update task of the candidate clique corresponding to each header node to be updated based on the sorted data set for reconstructing candidate cliques, comprises:
establishing one sub-task and three FIFO queues of the plurality of third FIFOs and BRAM blocks corresponding to the sub-task for each header node to be updated in the index record, wherein one FIFO queue is used to store the large neighbor node and the common neighbor node set thereof obtained from the sorted data set, and the other two FIFO queues are alternatively a temporary queue and an active queue; the temporary queue stores a candidate clique queue corresponding to the node to be updated, and the active queue stores a candidate clique queue in updating; the BRAM block comprises a node set record block and three length record blocks, wherein the node set record block is used to store an intersection set of the current common neighbor node set and the current candidate clique, and the three length record blocks record the length of the current common neighbor node set, the length of the current candidate clique and the length of the intersection set respectively; and
on the basis of a node order corresponding to each header node to be updated obtained from the sorted data set, the sub-tasks corresponding to all the header nodes to be updated use the three FIFO queues and the BRAM blocks to execute, in parallel, the update task of the candidate cliques.

6. The dynamic maximal clique enumeration device based on an FPGA with an HBM according to claim 5 , wherein the process that each sub-task executes the update of the candidate clique comprises:
obtaining an old candidate clique corresponding to each header node to be updated from the HBM and storing the old candidate clique in the active queue, and obtaining the large neighbor node corresponding to each header node to be updated and the common neighbor node set thereof from the sorted data set and storing the large neighbor node and the common neighbor node set thereof in the first FIFO queue; and
sequentially accessing each large neighbor node and the corresponding common neighbor node set in the FIFO queue; using each large neighbor node and the corresponding common neighbor node set to update the old candidate clique in the active queue; transferring the updated large group to the temporary queue for storage; and exchanging marks of the temporary queue and the active queue for the next round of update operation.

7. The dynamic maximal clique enumeration device based on an FPGA with an HBM according to claim 6 , wherein the update operation process comprises:
if the candidate clique queue in the active queue is null, or the common neighbor node set is null, directly adding the large neighbor node corresponding to the current common neighbor node set to the temporary queue

Assignees

• Zhejiang Lab

Inventors

• Yu Ting
• Li Dong
• Zhang Yu
• Qi Hao
• Jiang Ting
• Xu Zenghui
• Hou Linlin
• Zhao Jin
• Zhang Ji

Classifications

• G06F16/9024 Primary

  Graphs; Linked lists (G06F16/9027 takes precedence) · CPC title

• G06F17/11 Primary

  for solving equations {, e.g. nonlinear equations, general mathematical optimization problems (optimization specially adapted for a specific administrative, business or logistic context G06Q10/04)} · CPC title