Παραλληλοποίηση Αλγορίθμου Branch And Bound Σε Υπολογιστικά Συστήματα Μοιραζόμενης Μνήμης

Abstract

Στόχος της διπλωματικής εργασίας είναι η μελέτη του τρόπου παραλληλοποίησης του αλγορίθμου Branch and Bound σε υπολογιστικά συστήματα μοιραζόμενης μνήμης και η μέτρηση της επιτάχυνσης της εκτέλεσης που είναι δυνατό να επιτευχθεί. Για το σκοπό αυτό, αναπτύχθηκε προγραμματιστική βιβλιοθήκη σε γλώσσα C++ για την επίλυση προβλημάτων βελτιστοποίησης με τη μέθοδο Branch and Bound και υλοποιήθηκαν με βάση αυτή αλγόριθμοι για την επίλυση του διακριτού προβλήματος του σακιδίου και του προβλήματος του πλανόδιου πωλητή. Έγιναν μετρήσεις της απόδοσης του παράλληλου αλγορίθμου και της βιβλιοθήκης σε υπολογιστικό σύστημα με δύο επεξεργαστές Intel Xeon E5-2697 v3, με ιδιαίτερη έμφαση στον τρόπο υλοποίησης του δένδρου του αλγορίθμου Branch and Bound, με ομάδες ουρών προτεραιότητας διαφόρων χαρακτηριστικών. Προέκυψε ότι τεχνικές, όπως η χρήση ιδιωτικών ουρών με δυνατότητα κλοπής εργασιών, ιδιωτικά όρια, ανάρτηση νημάτων, καθώς και εκμετάλλευση της τεχνολογίας ταυτόχρονης πολυνηματοποίησης, μπορούν να βελτιώσουν σημαντικά την επιτάχυνση που μπορεί να επιτευχθεί.