Παραλληλοποίηση αλγορίθμου branch and bound σε υπολογιστικά συστήματα μοιραζόμενης μνήμης - Ζιώγας, Αλέξανδρος-Νικόλαος (Εθνικό Μετσόβιο Πολυτεχνείο. Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών. Τομέας Τεχνολογίας Πληροφορικής και Υπολογιστών, 2016)
Στόχος της διπλωματικής εργασίας είναι η μελέτη του τρόπου παραλληλοποίησης του αλγορίθμου Branch and Bound σε υπολογιστικά συστήματα μοιραζόμενης μνήμης και η μέτρηση της επιτάχυνσης της εκτέλεσης που είναι δυνατό να επιτευχθεί. Για το σκοπό αυτό, αναπτύχθηκε προγραμματιστική βιβλιοθήκη σε γλώσσα C++ για την επίλυση προβλημάτων βελτιστοποίησης με τη μέθοδο Branch and Bound και υλοποιήθηκαν με βάση αυτή αλγόριθμοι για την επίλυση του διακριτού προβλήματος του σακιδίου και του προβλήματος του πλανόδιου πωλητή. Έγιναν μετρήσεις της απόδοσης του παράλληλου αλγορίθμου και της βιβλιοθήκης σε υπολογιστικό σύστημα με δύο επεξεργαστές Intel Xeon E5-2697 v3, με ιδιαίτερη έμφαση στον τρόπο υλοποίησης του δένδρου του αλγορίθμου Branch and Bound, με ομάδες ουρών προτεραιότητας διαφόρων χαρακτηριστικών. Προέκυψε ότι τεχνικές, όπως η χρήση ιδιωτικών ουρών με δυνατότητα κλοπής εργασιών, ιδιωτικά όρια, ανάρτηση νημάτων, καθώς και εκμετάλλευση της τεχνολογίας ταυτόχρονης πολυνηματοποίησης, μπορούν να βελτιώσουν σημαντικά την επιτάχυνση που μπορεί να επιτευχθεί.