Degree-aware Kernels for computing Jaccard weights on GPUs

Alabsi Aljundi, Amro and Akyıldız, Taha Atahan and Kaya, Kamer (2022) Degree-aware Kernels for computing Jaccard weights on GPUs. In: IEEE International Parallel and Distributed Processing Symposium (IPDPS), Lyon, France

Full text not available from this repository. (Request a copy)


Graphs provide the ability to extract valuable met-rics from the structural properties of the underlying data they represent. One such metric is the Jaccard Weight of an edge, which is the ratio of the number of common neighbors of the edge's endpoints to the union of the endpoints' neighborhood. A naive implementation of Jaccard Weights computation has a complexity that scales with the number of edges in the graph times the square of the maximum degree. Recently, GPU-based parallel algorithms have been proposed for this problem. How-ever, these algorithms cannot overcome the structural variance within a graph, i.e., the sparsity pattern and degree imbalance, which directly translates to unbalanced work distribution across threads. In this work, we propose an optimized GPU-based algorithm with an ML-based work distribution model that mitigates the unbalanced work distribution. Our algorithm is shown to be up to 35x and on average 12x faster than the state of the art in practice while using less memory. In fact, we show that by manually tweaking the load distribution, a state-of-the-art implementation can be 5x faster. In addition, we propose a multi-core, shared-memory algorithm that applies a traditional but effective technique to improve the computation asymptotically and perform comparably to the GPU algorithms. Our code is available at
Item Type: Papers in Conference Proceedings
Uncontrolled Keywords: GPU; Jaccard Weights; parallel graph algorithms; work distribution
Divisions: Faculty of Engineering and Natural Sciences
Depositing User: Kamer Kaya
Date Deposited: 02 Sep 2022 10:32
Last Modified: 02 Sep 2022 10:32

Actions (login required)

View Item
View Item