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 Field | Value | Language |
---|---|---|
dc.contributor.author | Βασίλειος-ορέστης Παπαδιγενόπουλος | |
dc.date.accessioned | 2018-07-23T08:48:46Z | - |
dc.date.available | 2018-07-23T08:48:46Z | - |
dc.date.issued | 2015-9-29 | |
dc.date.submitted | 2015-7-16 | |
dc.identifier.uri | http://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.language | English | |
dc.subject | χρονοδρομολόγηση και οργάνωση πόρων | |
dc.subject | προσεγγιστικοί αλγόριθμοι | |
dc.subject | αλγοριθμική ανάλυση | |
dc.subject | map-reduce | |
dc.title | Προσεγγιστικοί Αλγόριθμοι Δρομολόγησης Mapreduce Εργασιών | |
dc.type | Diploma Thesis | |
dc.description.pages | 82 | |
dc.contributor.supervisor | Φωτάκης Δημήτριος | |
dc.department | Τομέας Τεχνολογίας Πληροφορικής & Υπολογιστών | |
dc.organization | ΕΜΠ, Τμήμα Ηλεκτρολόγων Μηχανικών & Μηχανικών Υπολογιστών | |
Appears in Collections: | Διπλωματικές Εργασίες - Theses |
Files in This Item:
File | Size | Format | |
---|---|---|---|
DT2015-0267.pdf | 766.45 kB | Adobe PDF | View/Open |
Items in Artemis are protected by copyright, with all rights reserved, unless otherwise indicated.