Pergamos - Library and Information Center of National and Kapodistrian University of Athens

Unit:

Τομέας Υπολογιστικών Συστημάτων και Εφαρμογών
Library of the School of Science

Deposit date:

2016-09-08

Year:

2016

Author:

Αναστασόπουλος Δημήτριος
Μεγκραμπιάν Αρσάκ

Supervisors info:

Ιωάννης Κοτρώνης

Original Title:

Απεικόνιση γράφων στην κάρτα γραφικών υλοποιήση των αλγορίθμων boruvka και dijkstra

Languages:

Greek

Summary:

In this thesis, we present parallel implementations of Boruvka and Dijkstra
algorithms along with
the use of the Compressed Sparse Row (CSR) format to display our input graphs
in the main
or graphics memory. Our implementations are based on Unix operating systems and
are using
the CUDA library of NVIDIA as well as the OpenMP library. We test our
applications on graphs
that represent road maps of cities and states of the USA.
The purpose of this thesis is to determine whether the speed ups we gain in
execution time
using our GPU are enough to surpass our CPU execution times for both the
algorithms used.
We start by explaining the concept of minimum spanning trees and the CSR
format. After
that, we describe in depth both the Boruvka algorithm and our implementations
in CUDA and
OpenMP, emphasizing the necessity of the CSR format. We then show our
executions times
using figures followed by our comments on them.
Afterwards we analyze the concept of shortest path. Similar to Boruvka
algorithm, we describe
step by step the Dijkstra algorithm and we present our implementations in CUDA
and OpenMP.
Measurements and execution times are also being displayed using figures
followed by our
comments on them.
Finally, we summarize the results we gathered from parallelizing the two
algorithms in order to
write our conclusions. In the majority of our tests we observed significant
speed ups of Boruvka
algorithm running on CUDA against multithreaded executions on CPU. However, the
speed ups
we gained in Dijkstra algorithm were not that impressive but were promising
enough for further
investigation.

Keywords:

Compressed Sparse Row, boruvka, dijkstra, spanning tree, shortest paths

Index:

Yes

Number of index pages:

7-8

Contains images:

Yes

Number of references:

Number of pages:

File:

https://pergamos.lib.uoa.gr/uoa/dl/object/1324106/file.pdf