Στην παρούσα διπλωματική, κύριος στόχος ήταν η παραλληλοποίηση
ενός αλγορίθμου σχεδιασμού κίνησης για κάρτες γραφικών. Για το σκοπό
αυτό, χρησιμοποιήθηκε ο 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.
| Identifer | oai:union.ndltd.org:upatras.gr/oai:nemertes:10889/7518 |
| Date | 16 May 2014 |
| Creators | Πάσχος, Ανδρέας |
| Contributors | Ψαράκης, Εμμανουήλ, Paschos, Andrew, Ψαράκης, Εμμανουήλ, Ασπράγκαθος, Νικόλαος |
| Source Sets | University of Patras |
| Language | gr |
| Detected Language | Greek |
| Type | Thesis |
| Rights | 0 |
Page generated in 0.0024 seconds