Dynamic maximal clique enumeration device and method based on fpga with hbm

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 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+/−(vi,vj), where, vi and vj are all nodes to be updated, e+(vi,vj) indicates that an edge is added between vi and vj, and e−(vi,vj) indicates that an edge between vi and vj 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.