National and Kapodistrian University of Athens
Ανάπτυξη αλγόριθμου Closest Pair με CUDA API
Abstract
dc:descriptionΑντικείμενο της παρούσας εργασίας είναι ο σχεδιασμός και η υλοποίηση γνωστού προβλήματος της υπολογιστικής γεωμετρίας δισδιάστατου πλησιέστερου ζεύγους- closest pair, χρησιμοποιώντας τη μονάδα επεξεργασίας γραφικών (GPU) της NVidia με το CUDA API. Πιο συγκεκριμένα, μια πρώτη ανάλυση αφορά την απλή προσέγγιση στο πρόβλημα, δηλαδή με έλεγχο για κάθε δυνατό ζεύγος σημείων, τετραγωνικής ασυμπτωτικής πολυπλοκότητας. Στην δεύτερη και ταχύτερη μέθοδο αλγόριθμου αναλύουμε την προσέγγιση του διαίρει και βασίλευε. Λαμβάνοντας υπόψη ένα σύνολο σημείων στο επίπεδο S, η προσέγγισή μας θα είναι να χωριστεί το σύνολο σε δύο περίπου ίσα μέρη (S1 και S2) για τις οποίες ήδη έχουμε τις λύσεις, και στη συνέχεια, να συγχωνεύσει τα μισά σε γραμμικό χρόνο για να έχουμε τελικά ασυμπτωτική πολυπλοκότητα O(nlogn). Ωστόσο, η πραγματική λύση απέχει πολύ από το προφανές. Είναι πιθανό ότι το επιθυμητό ζεύγος θα μπορούσε να έχει ένα σημείο στο S1 και ένα στο S2, αλλά αυτό δεν μας αναγκάζει να ελέγξουμε όλα τα πιθανά ζεύγη σημείων. Η προσέγγιση που παρουσιάζεται στην παρούσα εργασία είναι bottom-up. Ο αλγόριθμος closest pair είναι ένα βασικό πρόβλημα με πληθώρα εφαρμογών αλλά και με πολύ σημαντικό ρόλο κλειδί σε πολλούς αλγόριθμους. Η μελέτη του και η παραλληλοποίηση του με χρήση GPU μπορεί να μειώσει σημαντικά τον χρόνο εκτέλεσης του αλγορίθμου, προσφέροντας έτσι ιδανική λύση για real-time συστήματα αλλά και για εφαρμογές όπου παίζει σημαντικό ρόλο ο χρόνος υπολογισμού μεγάλου όγκου δεδομένων.
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Παπαγεωργάκης Γεώργιος
Rights
- Language dc:language
- Ελληνικά, Greek
Identifiers
dc:identifier.*- Identifier
- uoadl:1315832