Internal Design of Sparse Similarity¶
Interface¶
The input should be a directed/undirected graph in compressed sparse row (CSR) format. The result will return a vertex list with each vertex corresponding similarity value. The config contains several boolean value to control the similarityType (0:Jaccard Similarity, 1:Cosine Similarity), dataType(0:uint, 1:float).
Implemention¶
The detail algorithm implemention is illustrated as below:
As it is shown in the aboved pictures, every PE directly have 3 AXI port for the input of offset, indice and weight (CSR format data) and the data should be partitioned in host side. The internal function in the PE perform searching and matching index to find out the similarity between reference vertex and the others. The overall diagram of sparse similarity kernel have a insert sort module which return the top K number of similarity values. The maximum number of K is a template number which can be changed by rebuilding the xclbin. The default value of top K is 32.
Profiling and Benchmarks¶
The Sparse Similarity Kernel is validated on Alveo U50 board at 295MHz frequency. The hardware resource utilization and benchmark results are shown in the two table below.
Name | LUT | Register | BRAM | URAM | DSP |
sparseSimilarityKernel | 123017 | 190284 | 310.5 | 128 | 127 |
Datasets | Vertex | Edges | Similarity Type | FPGA Time / ms | TigerGraph (32 core 512 GB) | |
Time / ms | Speed up | |||||
as-Skitter | 1694616 | 11094209 | Cosine | 12.3 | 278 | 22.6 |
Jaccard | 12.2 | 271 | 22.3 | |||
coPaperDBLP | 540486 | 15245729 | Cosine | 13.7 | 289 | 21.1 |
Jaccard | 13.5 | 271 | 20.1 | |||
coPaperCiteseer | 434102 | 16036720 | Cosine | 17.6 | 282 | 16.0 |
Jaccard | 17.7 | 283 | 15.9 | |||
cit-Patents | 3774768 | 16518948 | Cosine | 24.8 | 268 | 10.8 |
Jaccard | 24.7 | 262 | 10.6 | |||
europe_osm | 50912018 | 54054660 | Cosine | 105.0 | 309 | 2.94 |
Jaccard | 104.9 | 315 | 3.0 | |||
hollywood | 1139905 | 57515616 | Cosine | 68.7 | 280 | 4.07 |
Jaccard | 68.8 | 329 | 4.78 | |||
soc-LiveJournal1 | 4847571 | 68993773 | Cosine | 75.5 | 293 | 3.88 |
Jaccard | 75.4 | 288 | 3.82 | |||
ljournal-2008 | 5363260 | 79023142 | Cosine | 83.6 | 281 | 3.36 |
Jaccard | 83.8 | 384 | 4.58 | |||
GEOMEAN | 50.1 | 292.7 | 5.84 |
Note