Περίληψη: | Στην παρούσα διπλωματική, κύριος στόχος ήταν η παραλληλοποίηση
ενός αλγορίθμου σχεδιασμού κίνησης για κάρτες γραφικών. Για το σκοπό
αυτό, χρησιμοποιήθηκε ο Probabilistic Road Map (PRM), ένας αλγόριθμος
που προσφέρει μεγάλο βαθμό παραλληλισμού και, συνεπώς, προτείνεται
για υλοποίηση σε πολυπύρηνους επεξεργαστές. Το πλαίσιο εργασίας που
χρησιμοποιήθηκε για τον προγραμματισμό στην κάρτα γραφικών ήταν
το OpenCL επειδή προσφέρει ένα αφαιρετικό επίπεδο προγραμματισμού
ανεξαρτήτως υλικού και μπορεί να μεταφερθεί σε κάρτες γραφικών από
διαφορετικούς κατασκευαστές. Ο αλγόριθμος αποσυντέθηκε στα δομικά
του μέρη και καθένα από αυτά μελετήθηκε ξεχωριστά, ώστε να παραλληλοποιηθεί. Κατά τη διαδικασία αυτή, λοιπόν, υλοποιήθηκαν οι εξής
αλγόριθμοι:
• Ταξινόμηση
• Αναζήτηση Γράφου κατά Πλάτος
• Κατακερματισμός
• Αναζήτηση Κοντινότερων Γειτόνων
Οι παραπάνω αλγόριθμοι έχουν γραφτεί με τέτοιο τρόπο ώστε να μπορούν να χρησιμοποιηθούν αυτόνομα, ως ξεχωριστά κομμάτια.
|