Edge-Connected Jaccard Similarity for Graph Link Prediction on FPGA
| dc.contributor.author | Sathre, Paul | en |
| dc.contributor.author | Gondhalekar, Atharva | en |
| dc.contributor.author | Feng, Wu-chun | en |
| dc.date.accessioned | 2024-03-04T15:12:52Z | en |
| dc.date.available | 2024-03-04T15:12:52Z | en |
| dc.date.issued | 2022-01-01 | en |
| dc.description.abstract | Graph analysis is a critical task in many fields, such as social networking, epidemiology, bioinformatics, and fraud de-tection. In particular, understanding and inferring relationships between graph elements lies at the core of many graph-based workloads. Real-world graph workloads and their associated data structures create irregular computational patterns that compli-cate the realization of high-performance kernels. Given these complications, there does not exist a de facto 'best' architecture, language, or algorithmic approach that simultaneously balances performance, energy efficiency, portability, and productivity. In this paper, we realize different algorithms of edge-connected Jaccard similarity for graph link prediction and characterize their performance across a broad spectrum of graphs on an Intel Stratix 10 FPGA. By utilizing a high-level synthesis (HLS)-driven, high-productivity approach (via the C++-based SYCL language) we rapidly prototype two implementations - a from-scratch edge-centric version and a faithfully-ported commodity GPU implementation - which would have been intractable via a hardware description language. With these implementations, we further consider the benefit and necessity of four HLS-enabled optimizations, both in isolation and in concert - totaling seven distinct synthesized hardware pipelines. Leveraging real-world graphs of up to 516 million edges, we show empirically-measured speedups of up to 9.5 x over the initial HLS implementations when all optimizations work in concert. | en |
| dc.description.version | Accepted version | en |
| dc.format.extent | Pages 1-10 | en |
| dc.identifier.doi | https://doi.org/10.1109/HPEC55821.2022.9926326 | en |
| dc.identifier.isbn | 9781665497862 | en |
| dc.identifier.orcid | Feng, Wu-chun [0000-0002-6015-0727] | en |
| dc.identifier.uri | https://hdl.handle.net/10919/118251 | en |
| dc.publisher | IEEE | en |
| dc.rights | In Copyright | en |
| dc.rights.uri | http://rightsstatements.org/vocab/InC/1.0/ | en |
| dc.title | Edge-Connected Jaccard Similarity for Graph Link Prediction on FPGA | en |
| dc.title.serial | 2022 IEEE High Performance Extreme Computing Conference, HPEC 2022 | en |
| dc.type | Conference proceeding | en |
| dc.type.other | Conference Proceeding | en |
| pubs.finish-date | 2022-09-23 | en |
| pubs.organisational-group | /Virginia Tech | en |
| pubs.organisational-group | /Virginia Tech/Engineering | en |
| pubs.organisational-group | /Virginia Tech/Engineering/Computer Science | en |
| pubs.organisational-group | /Virginia Tech/Faculty of Health Sciences | en |
| pubs.organisational-group | /Virginia Tech/All T&R Faculty | en |
| pubs.organisational-group | /Virginia Tech/Engineering/COE T&R Faculty | en |
| pubs.start-date | 2022-09-19 | en |