Σκοπός αυτής της διπλωματικής εργασίας είναι να μελετηθούν, να σχεδιαστούν και να υλοποιηθούν τεχνικές παράλληλης επεξεργασίας απαιτητικών χωρικών ερωτημάτων.
Οι περισσότερες ερευνητικές προσπάθειες στην περιοχή αυτή επικεντρώνουν το ενδιαφέρον τους στα κατανεμημένα υπολογιστικά συστήματα. Αντίθετα, σε αυτή την εργασία, το ενδιαφέρον μας εστιάζεται στα συστήματα διαμοιραζόμενης μνήμης που αποτελούν και την πλειοψηφία των κοινών προσωπικών υπολογιστών. Ο στόχος είναι να εκμεταλλευθούμε τους σύγχρονους πολυπύρηνους επεξεργαστές καθώς και τα μεγάλα μεγέθη κύριας μνήμης των σύγχρονων υπολογιστικών συστημάτων. Ανάμεσα στο πλήθος των απαιτητικών χωρικών ερωτημάτων επιλέξαμε συγκεκριμένα να μελετήσουμε το πρόβλημα εύρεσης «Όλων των k πλησιέστερων γειτόνων» για δυσδιάστατα σύνολα δεδομένων. Η μελέτη του προβλήματος έγινε σε προγραμματιστικό περιβάλλον C++ χρησιμοποιώντας δύο μεθόδους παραλληλισμού: OpenMP και Intel TBB. Για κάθε μια από τις δύο αυτές μεθόδους αναπτύχθηκαν παράλληλες υλοποιήσεις των αλγορίθμων Brute Force, Plane Sweep, Plane Sweep με λωρίδες και διαφόρων παραλλαγών τους.
Αρχικά χρησιμοποιήθηκαν σύνολα δεδομένων που χωράνε στην κύρια μνήμη του συστήματος και βρέθηκε ότι ο ταχύτερος αλγόριθμος είναι ο Plane Sweep με λωρίδες. Ο αλγόριθμος αυτός με κατάλληλη επιλογή του πλήθους λωρίδων παρουσιάζει σχεδόν γραμμική πολυπλοκότητα χρόνου σε σχέση με το πλήθος σημείων των δύο σημειοσυνόλων του προβλήματος.
Τελικά ο αλγόριθμος Plane Sweep με λωρίδες προσαρμόστηκε έτσι ώστε να μπορεί να χειριστεί σύνολα δεδομένων που δεν χωράνε εξ’ ολοκλήρου στην κύρια μνήμη του συστήματος αλλά επεξεργάζονται τμηματικά με ανάγνωση και εγγραφή στο σκληρό δίσκο. Για την υλοποίηση χρησιμοποιήθηκε η βιβλιοθήκη STXXL που παρέχει δυνατότητα χρήσης παράλληλων δίσκων. Στην περίπτωση αυτή ο αλγόριθμος διατηρεί τη σχεδόν γραμμική πολυπλοκότητα χρόνου και επιπλέον είναι πρακτικά ανεπηρέαστος από τη διαθέσιμη κύρια μνήμη εφόσον αυτή υπερβαίνει κάποιο ελάχιστο όριο.
The aim of this thesis is to study, design and implement techniques for parallel processing of demanding spatial queries.
Most research efforts in this area focus on distributed computing systems. On the contrary, in this work, our interest is focused on shared memory systems that make up the majority of common personal computers. The goal is to take advantage of the modern multi-core processors as well as the large RAM memory sizes of modern computing systems. Among the vast number of demanding spatial queries, we specifically chose to look at the problem of finding "All k Nearest Neighbors" for two-dimensional datasets. The investigation of the problem was implemented in a C++ programming environment by using two methods for parallelization: OpenMP and Intel TBB. For each one of these methods, parallel implementations of Brute Force, Plane Sweep, Striped Plane Sweep algorithms and their variants were developed.
Initially, we used datasets that fit into the system's main memory and the fastest algorithm was found to be the Striped Plane Sweep. This algorithm with an appropriate selection of the number of stripes exhibits nearly linear time complexity with respect to the count of points of the two problem datasets.
Finally, we adapted the Striped Plane Sweep algorithm to handle datasets that do not fit entirely into the system's main memory but are processed in several stages by reading and writing to the hard disk. The STXXL library was used for the implementation which can take advantage of parallel hard disks. In this case, the algorithm maintains the nearly linear time complexity and is also practically unaffected by the available amount of main memory when it exceeds a minimum threshold.
Περιγραφή: ΠΑΡΑΛΛΗΛΗ ΕΠΕΞΕΡΓΑΣΙΑ ΑΠΑΙΤΗΤΙΚΩΝ ΕΡΩΤΗΜΑΤΩΝ ΣΕ ΧΩΡΙΚΕΣ ΒΑΣΕΙΣ ΔΕΔΟΜΕΝΩΝ.pdf (pdf) Book Reader
Περιγραφή: source.zip (zip)