Approximate triangle counting with vertex coloring on the UPMEM architecture

Due to the need in recent years to analyze an ever-increasing amount of data, the restrictions posed by DRAM memory bandwidth and latency limit the scalability of computing systems and impede faster execution of memory-bound workloads. To address these limitations, in the past decades, a paradigm known as Processing-In-Memory (PIM) has been proposed, which allows for part of the computation to be moved closer to where the data resides. This thesis presents an implementation of an algorithm for approximate triangle counting in a graph specifically designed for the UPMEM PIM architecture, the first PIM architecture commercialized in real hardware. Through a series of comprehensive tests, the capabilities of the PIM architecture are highlighted, and the potential improvements it offers compared to traditional hardware solutions are demonstrated. Furthermore, this thesis presents additional improvements that could be made to the proposed algorithm, taking advantage of all the capabilities of the UPMEM PIM architecture.

A causa della necessità, negli ultimi anni, di analizzare una quantità sempre crescente di dati, le restrizioni poste dalla larghezza di banda e dalla latenza della memoria DRAM limitano la scalabilità dei sistemi computazionali e impediscono un'esecuzione più rapida di processi memory-bound. Per ovviare a queste limitazioni, negli ultimi decenni è stato proposto un paradigma noto come Processing-In-Memory (PIM), che consente di spostare parte delle operazioni computazionali più vicino a dove risiedono i dati. Questa tesi presenta un'implementazione di un algoritmo di conteggio approssimato dei triangoli in un grafo specificamente progettato per l'architettura PIM di UPMEM, la prima architettura PIM commercializzata in hardware reale. Attraverso una serie di test, vengono evidenziate le capacità dell'architettura PIM e vengono dimostrati i potenziali miglioramenti che offre rispetto alle soluzioni hardware tradizionali. Inoltre, questa tesi presenta ulteriori miglioramenti che potrebbero essere apportati all'algoritmo proposto, sfruttando tutte le capacità dell'architettura PIM di UPMEM.