Internal Design of CalcuDgree¶
CalcuDgree is an algorithm used to calculate indegree for CSR format input or outdegree for CSC format input. The algorithm is quite easy, but due to DDR limits, we cannot get one data per clock, so in our design, we use a cache with depth ajustable to get much better performance.
CalcuDgree algorithm implementation:
for each edge (u, v) in graph // calculate du degree degree(v) += 1
The input matrix should ensure that the following conditions hold:
- No duplicate edges
- compressed sparse column/row (CSC/CSR) format
The algorithm implemention is shown as the figure below:
Figure 1 : calculate degree architecture on FPGA
As we can see from the figure:
- Module calculate degree: first get the vertex node’s outdegree and keep them in one DDR buffer.
The hardware resource utilizations are listed in the following table.
Table 1 : Hardware resources for CalcuDegree with cache
Figure 2 : Cache depth’s influence to CalcDepth acceleration