Τομέας Υπολογιστικών Συστημάτων και Εφαρμογών
Βιβλιοθήκη Σχολής Θετικών Επιστημών

2016-09-08

2016

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

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

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

Ελληνικά

Στην παρούσα πτυχιακή εργασία παρουσιάζεται μια ενδιαφέρουσα δομή απεικόνισης
γράφων
στην κάρτα γραφικών και υλοποιούνται οι αλγόριθμοι του Boruvka και Dijkstra σε
υψηλό
επίπεδο παραλληλοποίησης. Οι υλοποιήσεις αυτές πραγματοποιήθηκαν σε
προγραμματιστικό
περιβάλλον Unix, με την βοήθεια των CUDA και OpenMP APIs και εκτελέστηκαν για
τα οδικά
δίκτυα πόλεων και πολιτειών των ΗΠΑ.
Σκοπός της εργασίας αυτής είναι να δούμε αν τελικά η απόδοση που παίρνουμε
αξιοποιώντας
την κάρτα γραφικών είναι τέτοια ώστε να μπορεί να ανταγωνιστεί την απόδοση του
επεξεργαστή
και να την ξεπεράσει, παίρνοντας την θέση του ως καλύτερη λύση για την επίλυση
προβλημάτων
που χρησιμοποιούν τους προαναφερθέντες αλγόριθμους.
Αρχικά, αναπτύσσονται οι βασικές έννοιες του δέντρου επικάλυψης ελαχίστου
κόστους και
της δομής συμπιεσμένων αραιών γραμμών (CSR). Επίσης, περιγράφεται ο αλγόριθμος
του
Boruvka, οπου διατυπώνεται ο αλγόριθμος και εξηγούνται όλα τα βήματα του σε
φυσική
γλώσσα. Στην συνέχεια, περιγράφεται αναλυτικά η υλοποίηση του με CUDA και
OpenMP και
με ποιο τρόπο χρησιμοποιείται η δομή CSR. Τέλος, παρουσιάζονται οι χρόνοι
εκτέλεσης του
αλγορίθμου και γίνεται σχολιασμός των αποτελεσμάτων.
Στην συνέχεια, αναλύεται η έννοια του ελάχιστου μονοπατιού, ακολουθούμενη από
την
περιγραφή του αλγορίθμου του Dijkstra. Όπως και στον αλγόριθμο του Boruvka,
έτσι και εδώ
αναλύονται λεπτομερώς όλα τα βήματα του αλγορίθμου και περιγράφονται οι
υλοποιήσεις του
με Cuda και openMP. Ακολουθούν και εδώ οι μετρήσεις των χρόνων εκτέλεσης του
αλγορίθμου
και ο σχολιασμός των αποτελεσμάτων.
Τέλος, παρουσιάζονται τα συμπεράσματα που προέκυψαν από την παραλληλοποίηση των
δύο αλγορίθμων, όπου διαπιστώνεται ότι, στην συντριπτική πλειοψηφία των
εκτελέσεων τους,
οι επιταχύνσεις που επιτυγχάνονται με την κάρτα γραφικών ξεπερνάνε άλλοτε
σημαντικά
(αλγόριθμος Dijkstra) και άλλοτε κατά πολύ (αλγόριθμος Boruvka) αυτές του
επεξεργαστή.

Compressed Sparse Row, boruvka, dijkstra, δέντρο επικάλυψης, ελάχιστα μονοπάτια

Ναι

7-8

Ναι

15

29

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

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