polito.it
Politecnico di Torino (logo)

Improving the scalability of modern applications by parallel multi-core and many-core programming

Alessandro Borione

Improving the scalability of modern applications by parallel multi-core and many-core programming.

Rel. Stefano Quer. Politecnico di Torino, Corso di laurea magistrale in Ingegneria Informatica (Computer Engineering), 2022

[img]
Preview
PDF (Tesi_di_laurea) - Tesi
Licenza: Creative Commons Attribution Non-commercial No Derivatives.

Download (3MB) | Preview
Abstract:

In recent years, the production and usage of vast graphs from different disciplines—social networks, geographical navigation, and internet routing to name a few—has required fast and scalable algorithms. Reachability, single source shortest path, partitioning, and coloring are some of the problems that are commonly applied to graphs. In this thesis, we focus on the problem of graph coloring. To color a graph, we assign a label, called color, to each of its nodes. Colors must be assigned so that no two nodes connected by an edge share the same color. Many scalable algorithms have been proposed; we select, discuss and implement a suite of algorithms for both multi-core CPU and many-core GPU architectures. In particular, we implement the Greedy, Gebremedhin-Manne, and Jones-Plassmann algorithms for multi-core CPU architectures, and the Jones-Plassmann-Luby algorithm for many-core GPU architectures with the help of the CUDA framework. For the latter, we propose a cost-free technique, called index shifting, to lower computation time and reduce the number of colors produced for the solution. We compare the results of our software with cuSPARSE's csrcolor and Gunrock's state-of-the-art implementations, both in terms of computation time and quality of the solution, i.e., the number of colors. We show how our fastest implementation on the GPU produces on average 10% fewer colors than Gunrock's implementation, while also being 2.5 times faster.

Relatori: Stefano Quer
Anno accademico: 2022/23
Tipo di pubblicazione: Elettronica
Numero di pagine: 81
Soggetti:
Corso di laurea: Corso di laurea magistrale in Ingegneria Informatica (Computer Engineering)
Classe di laurea: Nuovo ordinamento > Laurea magistrale > LM-32 - INGEGNERIA INFORMATICA
Aziende collaboratrici: NON SPECIFICATO
URI: http://webthesis.biblio.polito.it/id/eprint/25659
Modifica (riservato agli operatori) Modifica (riservato agli operatori)