Στην παρούσα διπλωματική, κύριος στόχος ήταν η παραλληλοποίηση ενός αλγορίθμου σχεδιασμού κίνησης για κάρτες γραφικών. Για το σκοπό αυτό, χρησιμοποιήθηκε ο Probabilistic Road Map (PRM), ένας αλγόριθμος που προσφέρει μεγάλο βαθμό παραλληλισμού και, συνεπώς, προτείνεται για υλοποίηση σε πολυπύρηνους επεξεργαστές. Το πλαίσιο εργασίας που χρησιμοποιήθηκε για τον προγραμματισμό στην κάρτα γραφικών ήταν το OpenCL επειδή προσφέρει ένα αφαιρετικό επίπεδο προγραμματισμού ανεξαρτήτως υλικού και μπορεί να μεταφερθεί σε κάρτες γραφικών από διαφορετικούς κατασκευαστές. Ο αλγόριθμος αποσυντέθηκε στα δομικά του μέρη και καθένα από αυτά μελετήθηκε ξεχωριστά, ώστε να παραλληλοποιηθεί. Κατά τη διαδικασία αυτή, λοιπόν, υλοποιήθηκαν οι εξής αλγόριθμοι: • Ταξινόμηση • Αναζήτηση Γράφου κατά Πλάτος • Κατακερματισμός • Αναζήτηση Κοντινότερων Γειτόνων Οι παραπάνω αλγόριθμοι έχουν γραφτεί με τέτοιο τρόπο ώστε να μπορούν να χρησιμοποιηθούν αυτόνομα, ως ξεχωριστά κομμάτια. / In this thesis work, the main objective was the parallelization of a motion planning algorithm for graphics card units. For this purpose, the Probabilistic Road Map (PRM) was chosen, an algorithm that offers a high degree of parallelism and, consequently, is suggested for implementation in many core processing units. The framework used for GPU programming was OpenCL because it provides an abstraction programming layer independent of hardware and is portable among GPUs. The algorithm was decomposed in its structural components and each one of them was processed indepedently with the purpose of massive parallelization. During this process, the following algorithms were implemented: • Sorting • Breadth First Traversal • Hashing • Nearest Neighbours Search The above algorithms have been written in such a way so that they can be used as separate parts.

Η διατριβή αυτή εξετάζει την χρήση γενετικών αλγορίθμων (ΓΑ) για την επίλυση του προβλήματος του σχεδιασμού κίνησης ρομποτικών συστημάτων τα οποία εκτελούν εργασίες εφοδιαστικής (όπως εργασίες λήψης και μεταφοράς από σημείο σε σημείο, μετακίνησης υλικών επί συνεχούς διαδρομής, κ.α.) στα πλαίσια λειτουργίας τους εντός ενός ευέλικτου συστήματος παραγωγής (ΕΣΠ). Το πρόβλημα του σχεδιασμού κίνησης (ΠΣΚ) είναι ένα υπολογιστικά άλυτο συνδυαστικό πρόβλημα βελτιστοποίησης (έχει αποδειχτεί PSPACE-hard) το οποίο μπορεί να οριστεί ως εξής: «Πως μπορεί ένα ρομπότ να αποφασίσει ποιες κινήσεις πρέπει να αποδώσει προκειμένου να εκτελέσει με επιτυχία επιθυμητές εργασίες στο περιβάλλον εργασίας του;» Προς τον σκοπό αυτό αναπτύχθηκε ένας αριθμός νέων, πρωτότυπων αλγορίθμων εμπνευσμένων από τη Βιολογία των οποίων η απόδοση μετρήθηκε τόσο μέσω πειραμάτων προσομοιωμένων σε υπολογιστή, όσο και σε πραγματικά ρομποτικά περιβάλλοντα στο εργαστήριο του Τμήματος. Συγκρινόμενοι με τις κλασσικές από τη βιβλιογραφία μεθόδους επίλυσης του ΠΣΚ, οι ΓΑ βρέθηκαν ανώτεροι τόσο από πλευράς ποιότητας των λύσεων που παρήγαγαν, όσο και από πλευράς ταχύτητας σύγκλησης (δηλαδή του χρόνου που χρειάστηκαν για τον εντοπισμό αυτών των λύσεων). Επιπρόσθετα, εξετάστηκαν και αντιμετωπίστηκαν με επιτυχία πολύπλοκα προβλήματα κινηματικής που αναφύονται κατά τον σχεδιασμό κίνησης ρομποτικών βραχιόνων σε ένα ΕΣΠ, όπως: Το αντίστροφο κινηματικό πρόβλημα ρομποτικών βραχιόνων με πλεονάζοντες βαθμούς ελευθερίας, η μεγιστοποίηση της επιδεξιότητας του ρομπότ κατά την εκτέλεση των εργασιών του και η παραγωγή με το άκρο εργασίας του ρομπότ ασφαλών και αξιόπιστων τροχιών επί προκαθορισμένων επιθυμητών διαδρομών. Η επίλυση αυτών των προβλημάτων είναι πολύ σημαντική σε πολλές πραγματικές βιομηχανικές εφαρμογές όπως εργασίες συγκόλλησης, βαψίματος ή επάλειψης με ψεκασμό, λείανσης, κ.α. / The use of genetic algorithms (GAs) for the solution of motion planning of robotic systems which perform logistics operations within a flexible manufacturing system (FMS), as well as, logistics tasks in indoors hazardous environments was investigated. Robot motion planning (RMP) is a PSPACE-hard combinatorial problem loosely stated as: How can a robot decide what motions to perform in order to achieve desired tasks in its environment? A number of new biological-inspired approaches were implemented and evaluated on computer simulated environments, as well as, on real industrial environments. In comparison to existing RMP methods, GAs were found superior in terms of both solutions quality and speed of convergence. Furthermore, focusing on RMP of robot manipulators, the proposed approaches tackled with high success difficult kinematics problems such as: the inverse kinematics for robots with redundant degrees of freedom, the maximization of robot’s manipulability, the path following by the robot’s end-effector on demanded trajectories.

Στην παρούσα διατριβή παρουσιάζονται παράλληλοι αλγόριθμοι και εφαρμογές σε πολυπύρηνες μονάδες επεξεργασίας γραφικών. Πιο συγκεκριμένα, εξετάζονται οι μέθοδοι σχεδίασης ενός παράλληλου αλγορίθμου για την επίλυση τόσο απλών και κοινών προβλημάτων, όπως η ταξινόμηση, όσο και υπολογιστικά απαιτητικών προβλημάτων, έτσι ώστε να εκμεταλλευτούμε πλήρως την τεράστια υπολογιστική δύναμη που προσφέρουν οι σύγχρονες μονάδες επεξεργασίας γραφικών. Πρώτο πρόβλημα που εξετάστηκε είναι η ταξινόμηση, η οποία είναι ένα από τα πιο συνηθισμένα προβλήματα στην επιστήμη των υπολογιστών. Υπάρχει σαν εσωτερικό πρόβλημα σε πολλές εφαρμογές, επομένως πετυχαίνοντας πιο γρήγορη ταξινόμηση πετυχαίνουμε πιο καλή απόδοση γενικότερα. Στο Κεφάλαιο 3 περιγράφονται όλα τα βήματα σχεδιασμού για την εκτέλεση ενός αλγορίθμου ταξινόμησης για ακεραίους, της count sort, σε μια μονάδα επεξεργασίας γραφικών. Σημαντική επίδραση στην απόδοση είχε η αποφυγή του συγχρονισμού των νημάτων στο τελευταίο βήμα του αλγορίθμου. Στη συνέχεια παρουσιάζονται εφαρμογές παράλληλων αλγορίθμων σε υπολογιστικά απαιτητικά προβλήματα. Στο Κεφάλαιο 4, εξετάζεται το πρόβλημα χρονοπρογραμματισμού εξετάσεων Πανεπιστημίων, το οποίο είναι ένα πρόβλημα συνδυαστικής βελτιστοποίησης. Για την επίλυσή του χρησιμοποιείται ένας υβριδικός εξελικτικός αλγόριθμος, ο οποίος εκτελείται εξ' ολοκλήρου στην μονάδα επεξεργασίας γραφικών. Η τεράστια υπολογιστική δύναμη της GPU και ο παράλληλος προγραμματισμός δίνουν τη δυνατότητα χρήσης μεγάλων πληθυσμών έτσι ώστε να εξερευνήσουμε καλύτερα τον χώρο λύσεων και να πάρουμε καλύτερα ποιοτικά αποτελέσματα. Στο επόμενο κεφάλαιο γίνεται επίλυση του προβλήματος σχεδιασμού κίνησης για υποθαλάσσια οχήματα με βραχίονα. Εξετάζεται το πρόβλημα τόσο του ολικού σχεδιασμού όσο και του τοπικού. Στην πρώτη περίπτωση είναι σημαντική η καλή λύση και η ακρίβεια και ο παράλληλος αλγόριθμος που χρησιμοποιείται για την αναπαράσταση του περιβάλλοντος εργασίας σε μια Bump-επιφάνεια βοηθάει προς αυτή την κατεύθυνση. Στη δεύτερη περίπτωση, το πρόβλημα είναι πρόβλημα πραγματικού χρόνου και μας ενδιαφέρει η ταχύτητα εύρεσης της επόμενης θέσης του οχήματος. Ο παράλληλος προγραμματισμός και η GPU βοηθούν σημαντικά σε αυτό. Τελευταία εφαρμογή που εξετάστηκε είναι η μελέτη ενός συστήματος ημιφθοριωμένων αλκανίων με την μοριακή προσομοίωση Monte Carlo. Η παραλληλοποίηση ενός μέρους, του πιο χρονοβόρου, του αλγορίθμου έδωσε τη δυνατότητα εξέτασης ενός πολύ μεγαλύτερου συστήματος σε αποδεκτό χρόνο. Σε γενικές γραμμές, γίνεται φανερό ότι ο παράλληλος προγραμματισμός και οι σύγχρονες πολυπύρηνες αρχιτεκτονικές, όπως οι μονάδες επεξεργασίας γραφικών, δίνουν νέες δυνατότητες στην αντιμετώπιση καθημερινών προβλημάτων, προβλημάτων πραγματικού χρόνου και προβλημάτων συνδυαστικής βελτιστοποίησης. / In this thesis, parallel algorithms and applications in manycore graphics processing units are presented. More specifically, we examine methods of designing a parallel algorithm for solving both simple and common problems such as sorting, and computationally demanding problems, so as to fully exploit the enormous computing power of modern graphics processing units (GPUs). First problem considered is sorting, which is one of the most common problems in computer science. It exists as an internal problem in many applications. Therefore, sorting faster, results in better performance in general. Chapter 3 describes all design options for the implementation of a sorting algorithm for integers, count sort, on a graphics processing unit. The elimination of thread synchronization in the last step of the algorithm had a significant effect on the performance. Chapter 4 addresses the examination timetabling problem for Universities, which is a combinatorial optimization problem. A hybrid evolutionary algorithm, which runs entirely on GPU, was used to solve the problem. The tremendous computing power of GPU and parallel programming enable the use of large populations in order to explore better the solution space and get better quality results. In the next chapter, the problem of motion planning for underwater vehicle manipulator systems is examined. In the gross motion planning problem, it is important to achieve a good solution with high accuracy. The parallel algorithm used for the representation of the working environment in a Bump-surface is a step towards this direction. In the local motion planning problem, which is a real-time problem, the time needed to find the next configuration of the vehicle is crucial. Parallel programming and the GPU greatly assist in this online problem. Last application considered is the atomistic Monte Carlo simulation of semifluorinated alkanes. The parallelization of part of the algorithm, the most time-consuming, enabled the study of a much larger system in an acceptable execution time. In general, it becomes obvious that parallel programming and new novel manycore architectures, such as graphics processing units, give new capabilities for solving everyday problems, real time and combinatorial optimization problems.