{"id":{"repo_id":"athens","oai_identifier":"oai:lib.uoa.gr:uoadl:1315832"},"canonical_url":"https://search.ndltd.org/etd/athens/oai:lib.uoa.gr:uoadl:1315832","repository":{"repo_id":"athens","name":"National and Kapodistrian University of Athens","base_url":"https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh"},"display":{"title":"Ανάπτυξη αλγόριθμου Closest Pair με CUDA API","abstract":"Αντικείμενο της παρούσας εργασίας είναι ο σχεδιασμός και η υλοποίηση γνωστού προβλήματος της υπολογιστικής γεωμετρίας δισδιάστατου πλησιέστερου ζεύγους- closest pair, χρησιμοποιώντας τη μονάδα επεξεργασίας γραφικών (GPU) της NVidia με το CUDA API. Πιο συγκεκριμένα, μια πρώτη ανάλυση αφορά την απλή προσέγγιση στο πρόβλημα, δηλαδή με έλεγχο για κάθε δυνατό ζεύγος σημείων, τετραγωνικής ασυμπτωτικής πολυπλοκότητας. Στην δεύτερη και ταχύτερη μέθοδο αλγόριθμου αναλύουμε την προσέγγιση του διαίρει και βασίλευε. Λαμβάνοντας υπόψη ένα σύνολο σημείων στο επίπεδο S, η προσέγγισή μας θα είναι να χωριστεί το σύνολο σε δύο περίπου ίσα μέρη (S1 και S2) για τις οποίες ήδη έχουμε τις λύσεις, και στη συνέχεια, να συγχωνεύσει τα μισά σε γραμμικό χρόνο για να έχουμε τελικά ασυμπτωτική πολυπλοκότητα O(nlogn). Ωστόσο, η πραγματική λύση απέχει πολύ από το προφανές. Είναι πιθανό ότι το επιθυμητό ζεύγος θα μπορούσε να έχει ένα σημείο στο S1 και ένα στο S2, αλλά αυτό δεν μας αναγκάζει να ελέγξουμε όλα τα πιθανά ζεύγη σημείων. Η προσέγγιση που παρουσιάζεται στην παρούσα εργασία είναι bottom-up. Ο αλγόριθμος closest pair είναι ένα βασικό πρόβλημα με πληθώρα εφαρμογών αλλά και με πολύ σημαντικό ρόλο κλειδί σε πολλούς αλγόριθμους. Η μελέτη του και η παραλληλοποίηση του με χρήση GPU μπορεί να μειώσει σημαντικά τον χρόνο εκτέλεσης του αλγορίθμου, προσφέροντας έτσι ιδανική λύση για real-time συστήματα αλλά και για εφαρμογές όπου παίζει σημαντικό ρόλο ο χρόνος υπολογισμού μεγάλου όγκου δεδομένων.","abstract_html":"Αντικείμενο της παρούσας εργασίας είναι ο σχεδιασμός και η υλοποίηση γνωστού προβλήματος της υπολογιστικής γεωμετρίας δισδιάστατου πλησιέστερου ζεύγους- closest pair, χρησιμοποιώντας τη μονάδα επεξεργασίας γραφικών (GPU) της NVidia με το CUDA API. Πιο συγκεκριμένα, μια πρώτη ανάλυση αφορά την απλή προσέγγιση στο πρόβλημα, δηλαδή με έλεγχο για κάθε δυνατό ζεύγος σημείων, τετραγωνικής ασυμπτωτικής πολυπλοκότητας. Στην δεύτερη και ταχύτερη μέθοδο αλγόριθμου αναλύουμε την προσέγγιση του διαίρει και βασίλευε. Λαμβάνοντας υπόψη ένα σύνολο σημείων στο επίπεδο S, η προσέγγισή μας θα είναι να χωριστεί το σύνολο σε δύο περίπου ίσα μέρη (S1 και S2) για τις οποίες ήδη έχουμε τις λύσεις, και στη συνέχεια, να συγχωνεύσει τα μισά σε γραμμικό χρόνο για να έχουμε τελικά ασυμπτωτική πολυπλοκότητα O(nlogn). Ωστόσο, η πραγματική λύση απέχει πολύ από το προφανές. Είναι πιθανό ότι το επιθυμητό ζεύγος θα μπορούσε να έχει ένα σημείο στο S1 και ένα στο S2, αλλά αυτό δεν μας αναγκάζει να ελέγξουμε όλα τα πιθανά ζεύγη σημείων. Η προσέγγιση που παρουσιάζεται στην παρούσα εργασία είναι bottom-up. Ο αλγόριθμος closest pair είναι ένα βασικό πρόβλημα με πληθώρα εφαρμογών αλλά και με πολύ σημαντικό ρόλο κλειδί σε πολλούς αλγόριθμους. Η μελέτη του και η παραλληλοποίηση του με χρήση GPU μπορεί να μειώσει σημαντικά τον χρόνο εκτέλεσης του αλγορίθμου, προσφέροντας έτσι ιδανική λύση για real-time συστήματα αλλά και για εφαρμογές όπου παίζει σημαντικό ρόλο ο χρόνος υπολογισμού μεγάλου όγκου δεδομένων.","abstract_has_math":false,"creators":["Παπαγεωργάκης Γεώργιος"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2014,"date_issued":"2014","date_published":"2014","updated_at":"2026-11-19T05:24:19Z","subjects":[],"languages":["Ελληνικά","Greek"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:1315832"],"render_values":[{"text":"uoadl:1315832","href":null,"code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/1315832","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/1315832","record_label":"Repository record","record_kind":"record","record_source":"dc:identifier","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh?verb=GetRecord&metadataPrefix=oai_dc&identifier=oai%3Alib.uoa.gr%3Auoadl%3A1315832","prefix":"oai_dc"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Παπαγεωργάκης Γεώργιος"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2014"]},{"key":"dc:type","label":"Dc Type","values":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["Ελληνικά","Greek"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:1315832","https://pergamos.lib.uoa.gr/uoa/dl/object/1315832"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Αντικείμενο της παρούσας εργασίας είναι ο σχεδιασμός και η υλοποίηση γνωστού προβλήματος της υπολογιστικής γεωμετρίας δισδιάστατου πλησιέστερου ζεύγους- closest pair, χρησιμοποιώντας τη μονάδα επεξεργασίας γραφικών (GPU) της NVidia με το CUDA API. Πιο συγκεκριμένα, μια πρώτη ανάλυση αφορά την απλή προσέγγιση στο πρόβλημα, δηλαδή με έλεγχο για κάθε δυνατό ζεύγος σημείων, τετραγωνικής ασυμπτωτικής πολυπλοκότητας. Στην δεύτερη και ταχύτερη μέθοδο αλγόριθμου αναλύουμε την προσέγγιση του διαίρει και βασίλευε. Λαμβάνοντας υπόψη ένα σύνολο σημείων στο επίπεδο S, η προσέγγισή μας θα είναι να χωριστεί το σύνολο σε δύο περίπου ίσα μέρη (S1 και S2) για τις οποίες ήδη έχουμε τις λύσεις, και στη συνέχεια, να συγχωνεύσει τα μισά σε γραμμικό χρόνο για να έχουμε τελικά ασυμπτωτική πολυπλοκότητα O(nlogn). Ωστόσο, η πραγματική λύση απέχει πολύ από το προφανές. Είναι πιθανό ότι το επιθυμητό ζεύγος θα μπορούσε να έχει ένα σημείο στο S1 και ένα στο S2, αλλά αυτό δεν μας αναγκάζει να ελέγξουμε όλα τα πιθανά ζεύγη σημείων. Η προσέγγιση που παρουσιάζεται στην παρούσα εργασία είναι bottom-up. Ο αλγόριθμος closest pair είναι ένα βασικό πρόβλημα με πληθώρα εφαρμογών αλλά και με πολύ σημαντικό ρόλο κλειδί σε πολλούς αλγόριθμους. Η μελέτη του και η παραλληλοποίηση του με χρήση GPU μπορεί να μειώσει σημαντικά τον χρόνο εκτέλεσης του αλγορίθμου, προσφέροντας έτσι ιδανική λύση για real-time συστήματα αλλά και για εφαρμογές όπου παίζει σημαντικό ρόλο ο χρόνος υπολογισμού μεγάλου όγκου δεδομένων.","It is proved that the use of graphics processing units, in coordination with the central processing unit, can drastically improve the performance of intensive computing applications. The appropriate use of the GPU is still an open research topic. One of the problems is the appropriate setting of the system’s parameters in executing a GPU kernel which is also a main topic of the current thesis. That said, given a program that accepts different parameters, we seek out the number of threads per block and the number of blocks in the grid, which will result in the minimum total running time.The objective of this work is the parallel design and implementation of a known problem of computational geometry in a two-dimensional space, the closest pair of points, using the graphics processing unit (GPU) with the NVidia CUDA API. More specifically, a first analysis of the simple approach to the problem, ie control for each possible pair of points, executes at square asymptotic complexity.In the second and faster method, we analyze the approach of divide & conquer algorithm. Given a set of points in the plane S, our approach is to divide the whole set of points into two approximately sorted and equal parts (S1 and S2) for which we already have the adjacent distances, and then merge each half in linear time to get finally asymptotic complexity of O(nlogn). However, the real solution is far from obvious. It is possible that the desired pair might have a point in S1 and another one in S2, but it does not force us to examine all possible pairs of points. The approach presented in this thesis is a bottom-up.The closest pair algorithm is a fundamental problem with many applications and a very important role in many algorithms. The study and the parallelization of the problem using a GPU can significantly reduce the execution time of the algorithm, thus providing the ideal solution for real-time systems and for applications with large data sets.The difficulties encountered in the parallel implementation of the algorithm relate extensively to the algorithm divide & conquer in identifying the candidate closest pairs calculated in one of the recursive calls, or a candidate closest pair of points with a point in the right batch and the other on the left batch. Furthermore, there were technical difficulties regarding the optimal use of the GPU device and are also analyzed concurrently with the measured results."]},{"key":"dc:title","label":"Title","values":["Ανάπτυξη αλγόριθμου Closest Pair με CUDA API"]}]}],"canonical_facts":{"dc:creator":["Παπαγεωργάκης Γεώργιος"],"dc:date":["2014"],"dc:description":["Αντικείμενο της παρούσας εργασίας είναι ο σχεδιασμός και η υλοποίηση γνωστού προβλήματος της υπολογιστικής γεωμετρίας δισδιάστατου πλησιέστερου ζεύγους- closest pair, χρησιμοποιώντας τη μονάδα επεξεργασίας γραφικών (GPU) της NVidia με το CUDA API. Πιο συγκεκριμένα, μια πρώτη ανάλυση αφορά την απλή προσέγγιση στο πρόβλημα, δηλαδή με έλεγχο για κάθε δυνατό ζεύγος σημείων, τετραγωνικής ασυμπτωτικής πολυπλοκότητας. Στην δεύτερη και ταχύτερη μέθοδο αλγόριθμου αναλύουμε την προσέγγιση του διαίρει και βασίλευε. Λαμβάνοντας υπόψη ένα σύνολο σημείων στο επίπεδο S, η προσέγγισή μας θα είναι να χωριστεί το σύνολο σε δύο περίπου ίσα μέρη (S1 και S2) για τις οποίες ήδη έχουμε τις λύσεις, και στη συνέχεια, να συγχωνεύσει τα μισά σε γραμμικό χρόνο για να έχουμε τελικά ασυμπτωτική πολυπλοκότητα O(nlogn). Ωστόσο, η πραγματική λύση απέχει πολύ από το προφανές. Είναι πιθανό ότι το επιθυμητό ζεύγος θα μπορούσε να έχει ένα σημείο στο S1 και ένα στο S2, αλλά αυτό δεν μας αναγκάζει να ελέγξουμε όλα τα πιθανά ζεύγη σημείων. Η προσέγγιση που παρουσιάζεται στην παρούσα εργασία είναι bottom-up. Ο αλγόριθμος closest pair είναι ένα βασικό πρόβλημα με πληθώρα εφαρμογών αλλά και με πολύ σημαντικό ρόλο κλειδί σε πολλούς αλγόριθμους. Η μελέτη του και η παραλληλοποίηση του με χρήση GPU μπορεί να μειώσει σημαντικά τον χρόνο εκτέλεσης του αλγορίθμου, προσφέροντας έτσι ιδανική λύση για real-time συστήματα αλλά και για εφαρμογές όπου παίζει σημαντικό ρόλο ο χρόνος υπολογισμού μεγάλου όγκου δεδομένων.","It is proved that the use of graphics processing units, in coordination with the central processing unit, can drastically improve the performance of intensive computing applications. The appropriate use of the GPU is still an open research topic. One of the problems is the appropriate setting of the system’s parameters in executing a GPU kernel which is also a main topic of the current thesis. That said, given a program that accepts different parameters, we seek out the number of threads per block and the number of blocks in the grid, which will result in the minimum total running time.The objective of this work is the parallel design and implementation of a known problem of computational geometry in a two-dimensional space, the closest pair of points, using the graphics processing unit (GPU) with the NVidia CUDA API. More specifically, a first analysis of the simple approach to the problem, ie control for each possible pair of points, executes at square asymptotic complexity.In the second and faster method, we analyze the approach of divide & conquer algorithm. Given a set of points in the plane S, our approach is to divide the whole set of points into two approximately sorted and equal parts (S1 and S2) for which we already have the adjacent distances, and then merge each half in linear time to get finally asymptotic complexity of O(nlogn). However, the real solution is far from obvious. It is possible that the desired pair might have a point in S1 and another one in S2, but it does not force us to examine all possible pairs of points. The approach presented in this thesis is a bottom-up.The closest pair algorithm is a fundamental problem with many applications and a very important role in many algorithms. The study and the parallelization of the problem using a GPU can significantly reduce the execution time of the algorithm, thus providing the ideal solution for real-time systems and for applications with large data sets.The difficulties encountered in the parallel implementation of the algorithm relate extensively to the algorithm divide & conquer in identifying the candidate closest pairs calculated in one of the recursive calls, or a candidate closest pair of points with a point in the right batch and the other on the left batch. Furthermore, there were technical difficulties regarding the optimal use of the GPU device and are also analyzed concurrently with the measured results."],"dc:identifier":["uoadl:1315832","https://pergamos.lib.uoa.gr/uoa/dl/object/1315832"],"dc:language":["Ελληνικά","Greek"],"dc:title":["Ανάπτυξη αλγόριθμου Closest Pair με CUDA API"],"dc:type":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]},"updated_at":"2026-11-19T05:24:19Z"}