Implemention - 2023.2 English

Vitis Libraries
Release Date
2023-12-20
Version
2023.2 English

The input matrix should ensure that the following conditions hold:

  1. Undirected graph.
  2. No self edges.
  3. All edges are oriented (src ID is greater than dst ID for compressed sparse column (CSC) format or dst ID is greater than src ID for compressed sparse row (CSR) format).
  4. No duplicate edges.

The algorithm implemention is shown as the figure below:

Figure 1 TriangleCount architecture on FPGA

As we can see from the figure:

  1. Module row1CopyImpl and its previous module: first get the rows corresponding to the order of increasing columns, and then copy the rows according to the number of rows.
  2. Module row2Impl and its previous module: frist get the rows corresponding to the order of increasing columns, and then use the rows as columns to obtain their corresponding rows.
  3. Module mergeImpl and tcAccUnit: count the number of intersections of rows from module row1CopyImpl and module row2Impl in the order of the columns. The cumulative result is the number of triangles.