Παραλληλοποίηση μεθευρετικού αλγόριθµου για τα προβλήματα διαχείρισης αποθεμέτων: μια υπολογιστική μελέτη με OPENMP και OPENACC
Αντωνιάδης, Νικόλαος
Πρόγραμμα Μεταπτυχιακών Σπουδών Ειδίκευσης στην Εφαρμοσμένη Πληροφορική
Σιφαλέρας, Άγγελος
Η παρούσα εργασία έχει ως στόχο την παραλληλοποίηση ενός NP-Hard προβλήµατος διαχείρισης αποθεµάτων, χρησιµοποιώντας τα µοντέλα παράλληλου προγραµµατισµού OpenMP
και OpenACC. Στην πορεία της εργασίας, ϑα δοθεί η σηµασία των µεθευρετικών αλγορίθµων
(metaheuristics) και ϑα αναλυθεί ιδιαίτερα ο αλγόριθµος Αναζήτησης Μεταβλητής Γειτονιάς
(VNS). Γίνεται, επίσης, µια παρουσίαση των προβληµάτων διαχείρισης αποθεµάτων. Αφού
αποτυπωθεί το πλαίσιο το οποίο πραγµατεύεται η παρούσα εργασία, γίνεται ανάλυση των
παράλληλων µεθευρετικών αλγορίθµων και των τεχνολογιών µε τις οποίες µπορούν να υλοποιηθούν, ιδιαιτέρως των OpenMP, OpenACC, καθώς και παραδείγµατα παραλληλοποίησης
του αλγορίθµου VNS στον οποίο και ϑα ϐασιστούµε. Μελετώντας τους αλγορίθµους και τις
τεχνικές παραλληλοποίησης καταλήγουµε στο µοντέλο που ταιριάζει καλύτερα στο πρόβληµά
µας και το υλοποιούµε, αποτυπώνοντας τις τεχνικές λεπτοµέρειες. Αφού ολοκληρωθεί η υλοποίηση, διενεργούνται δοκιµές του παραλληλοποιηµένου αλγορίθµου τόσο µε την τεχνολογία
OpenMP όσο και µε την τεχνολογία OpenACC και τα αποτελέσµατα παρουσιάζονται µε σχετικούς πίνακες και διαγράµµατα. Η εργασία ολοκληρώνεται µε τα συµπεράσµατα της έρευνας
και τις µελλοντικές κατευθύνσεις της.
