Please use this identifier to cite or link to this item: http://artemis.cslab.ece.ntua.gr:8080/jspui/handle/123456789/12913
Full metadata record
DC FieldValueLanguage
dc.contributor.authorΒασίλειος-ορέστης Παπαδιγενόπουλος
dc.date.accessioned2018-07-23T08:48:46Z-
dc.date.available2018-07-23T08:48:46Z-
dc.date.issued2015-9-29
dc.date.submitted2015-7-16
dc.identifier.urihttp://artemis-new.cslab.ece.ntua.gr:8080/jspui/handle/123456789/12913-
dc.description.abstractΤο MapReduce αποτελεί ένα προγραμματιστικό μοντέλο καθώς και μια σχετική υλοποίηση για την παράλληλη επεξεργασία μεγάλων ποσοτήτων δεδομένων σε συστάδες πολυπύρηνων υπολογιστικών συστημάτων. Στο MapReduce, κάθε εργασία περιλαμβάνει δυο σύνολα υποεργασιών, τις map και τις reduce. Ενώ οι υποεργασίες κάθε συνόλου μπορούν να εκτελεστούν παράλληλα, τα δύο αυτά σύνολα οφείλουν να εκτελεστούν ακολουθιακά. Με άλλα λόγια, κάθε reduce υποεργασία μπορεί να ξεκινήσει την εκτέλεσή της μόνο μετά την ολοκλήρωση των αντίστοιχων map υποεργασιών. Ο δρομολογητής MapReduce εργασιών παίζει ένα πολύ ουσιαστικό ρόλο στην απόδοση του όλου συστήματος. Στη διπλωματική αυτή, μελετάμε το πρόβλημα της δρομολόγησης MapReduce εργασιών από τη σκοπιά της θεωρίας δρομολόγησης και των προσεγγιστικών αλγορίθμων. Παρουσιάζουμε μερικά γνωστά αποτελέσματα σχετικά με τη δρομολόγηση εργασιών σε παράλληλες μηχανές καθώς και με τη δρομολόγηση MapReduce εργασιών. Η βασική συνεισφορά της εργασίας αυτής είναι η πειραματική αξιολόγηση ενός πολυωνυμικού χρόνου 54-προσεγγιστικού αλγορίθμου για το πρόβλημα δρομολόγησης MapReduce εργασιών σε ασυσχέτιστες μηχανές με στόχο την ελαχιστοποίηση του βεβαρημένου μέσου χρόνου ολοκλήρωσης. Στη μελέτη αυτή δείχνουμε ότι σε πειραματικές συνθήκες ο "εμπειρικός" λόγος προσέγγισης αποδεικνύεται πολύ καλύτερος από αυτόν που έχει δειχθεί θεωρητικά για διαφορετικές κατανομές χρόνων εκτέλεσης και αριθμούς εργασιών. Επιπλέον, προτείνουμε ένα γρήγορο και "άπληστο" αλγόριθμο για το ίδιο πρόβλημα ο οποίος αποδεικνύεται αρκετά ανταγωνιστικός για συγκεκριμένες εισόδους. Τέλος, περιλαμβάνουμε στα πειράματά μας την μοντελοποίηση της μεταφοράς δεδομένων από map σε reduce υποεργασίες μέσω της εισαγωγής των "shuffle" υποεργασιών.
dc.languageEnglish
dc.subjectχρονοδρομολόγηση και οργάνωση πόρων
dc.subjectπροσεγγιστικοί αλγόριθμοι
dc.subjectαλγοριθμική ανάλυση
dc.subjectmap-reduce
dc.titleΠροσεγγιστικοί Αλγόριθμοι Δρομολόγησης Mapreduce Εργασιών
dc.typeDiploma Thesis
dc.description.pages82
dc.contributor.supervisorΦωτάκης Δημήτριος
dc.departmentΤομέας Τεχνολογίας Πληροφορικής & Υπολογιστών
dc.organizationΕΜΠ, Τμήμα Ηλεκτρολόγων Μηχανικών & Μηχανικών Υπολογιστών
Appears in Collections:Διπλωματικές Εργασίες - Theses

Files in This Item:
File SizeFormat 
DT2015-0267.pdf766.45 kBAdobe PDFView/Open


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