Nicola Basciu
Accelerated Triangle Counting for Massive Graphs On GPUs.
Rel. Stefano Quer, Lorenzo Cardone. Politecnico di Torino, Corso di laurea magistrale in Ingegneria Informatica (Computer Engineering), 2026
|
Preview |
PDF (Tesi_di_laurea)
- Tesi
Licenza: Creative Commons Attribution Non-commercial No Derivatives. Download (9MB) | Preview |
Abstract
Triangle counting is a fundamental primitive in graph analysis, serving as a building block for higher-level metrics like the local clustering coefficient. It is fundamental in different scenarios, including social network community detection, biological protein- protein interaction, fraud detection, and cybersecurity for threat and anomaly identification. GPUs offer massive parallelism and high memory bandwidth, representing a suitable platform for these types of algorithms, but with the cost of introducing several challenges. First, the CSR format commonly used to store sparse graphs leads to irregular, non-coalesced memory accesses when performing neighbor-list intersections, severely limiting achievable memory bandwidth. Second, real-world graphs typically exhibit highly skewed degree distributions, causing significant load imbalance across GPU threads and warps.
Third, approaches based on full bitmaps to accelerate intersection tests, incur prohibitive memory overhead on large graphs, often exceeding the limited device memory available on GPUs
Relatori
Anno Accademico
Tipo di pubblicazione
Numero di pagine
Corso di laurea
Classe di laurea
Aziende collaboratrici
URI
![]() |
Modifica (riservato agli operatori) |
