Back to search

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

Chain of custody

source
Harvested from
National and Kapodistrian University of Athens
Base URL
pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Παπαγεωργάκης Γεώργιος. Ανάπτυξη αλγόριθμου Closest Pair με CUDA API. 2014. https://pergamos.lib.uoa.gr/uoa/dl/object/1315832