Please use this identifier to cite or link to this item: http://artemis.cslab.ece.ntua.gr:8080/jspui/handle/123456789/13060
Title: Παραλληλοποίηση Αλγορίθμου Branch And Bound Σε Υπολογιστικά Συστήματα Μοιραζόμενης Μνήμης
Authors: Αλέξανδρος-νικόλαος Ζιώγας
Γκούμας Γεώργιος
Keywords: branch and bound
παραλληλοποίηση
υπολογιστικά συστήματα μοιραζόμενης μνήμης
διακριτό πρόβλημα του σακιδίου
πρόβλημα του πλανόδιου πωλητή
ουρές προτεραιότητας
κλοπή εργασιών
ανάρτηση νημάτων
ταυτόχρονη πολυνηματοποίηση
Issue Date: 22-Mar-2016
Abstract: Στόχος της διπλωματικής εργασίας είναι η μελέτη του τρόπου παραλληλοποίησης του αλγορίθμου Branch and Bound σε υπολογιστικά συστήματα μοιραζόμενης μνήμης και η μέτρηση της επιτάχυνσης της εκτέλεσης που είναι δυνατό να επιτευχθεί. Για το σκοπό αυτό, αναπτύχθηκε προγραμματιστική βιβλιοθήκη σε γλώσσα C++ για την επίλυση προβλημάτων βελτιστοποίησης με τη μέθοδο Branch and Bound και υλοποιήθηκαν με βάση αυτή αλγόριθμοι για την επίλυση του διακριτού προβλήματος του σακιδίου και του προβλήματος του πλανόδιου πωλητή. Έγιναν μετρήσεις της απόδοσης του παράλληλου αλγορίθμου και της βιβλιοθήκης σε υπολογιστικό σύστημα με δύο επεξεργαστές Intel Xeon E5-2697 v3, με ιδιαίτερη έμφαση στον τρόπο υλοποίησης του δένδρου του αλγορίθμου Branch and Bound, με ομάδες ουρών προτεραιότητας διαφόρων χαρακτηριστικών. Προέκυψε ότι τεχνικές, όπως η χρήση ιδιωτικών ουρών με δυνατότητα κλοπής εργασιών, ιδιωτικά όρια, ανάρτηση νημάτων, καθώς και εκμετάλλευση της τεχνολογίας ταυτόχρονης πολυνηματοποίησης, μπορούν να βελτιώσουν σημαντικά την επιτάχυνση που μπορεί να επιτευχθεί.
URI: http://artemis-new.cslab.ece.ntua.gr:8080/jspui/handle/123456789/13060
Appears in Collections:Διπλωματικές Εργασίες - Theses

Files in This Item:
File SizeFormat 
DT2016-0040.pdf2.15 MBAdobe PDFView/Open


Items in Artemis are protected by copyright, with all rights reserved, unless otherwise indicated.