Please use this identifier to cite or link to this item:
http://artemis.cslab.ece.ntua.gr:8080/jspui/handle/123456789/13245
Title: | Προσεγγιστικοί Αλγόριθμοι Δρομολόγησης Παραλληλοποιήσιμων Εργασιών |
Authors: | Τσεπενέκας Λεωνίδας Φωτάκης Δημήτριος |
Keywords: | χρονοδρομολόγηση προσεγγιστικοί αλγόριθμοι ανάθεση πόρων malleable/parallelizable/multiprocessor εργασίες μοντέλο μίας εργασίας σε πολλές μηχανές |
Issue Date: | 27-Sep-2016 |
Abstract: | Μια τυπική υπόθεση στα κλασσικά προβλήματα χρονοδρομολόγησης είναι ότι οι εργα-σίες, χρησιμοποιούν μόνο μια επεξεραστική μονάδα για την εκτέλεσή τους. Παρόλα αυτά,υπάρχει πληθώρα προβλημάτων που εμφανίζονται σε πολλούς και διαφορετικούς τομείς, σταοποία η εν λόγω υπόθεση δεν είναι επαρκής για να μοντελοποιήσει τις ιδιαίτερες απαιτήσειςπου παρουσιάζουν. Σε αυτές τις περιπτώσεις θα πρέπει να επεκτείνουμε το κλασικό μον-τέλο, επιτρέποντας σε μια εργασία να εκτελείται ταυτόχρονα σε περισσότερους του ενόςεπεξεργαστές και μάλιστα ενιαία. Αυτό σημαίνει ότι η εργασία θα έχει κοινό χρόνο εκκίνη-σης και ολοκλήρωσης σε όλους τους επεξεργαστές που της έχουν ανατεθεί και μάλισταο χρόνος εκτέλεσης της θα είναι συνάρτηση αυτών. Στην αλγοριθμική βιβλιογραφία προ-βλήματα της παραπάνω μορφής συναντώνται ως malleable ή multiprocessor ή parallelizablejob scheduling.Οπως και στο κλασικό μοντέλο μιας εργασίας σε μια μηχανή, έτσι και εδώ υπάρχει ηανάγκη σχεδίασης αποδοτικών αλγορίθμων. Στη διπλωματική αυτή, μελετάμε το πρόβληματης χρονοδρομολόγησης σε τέτοια μοντέλα από τη σκοπιά της θεωρίας δρομολόγησης καιτων προσεγγιστικών αλγορίθμων. Ξεκινάμε παρουσιάζοντας τα πιο γνωστά αποτελέσματα,επεκτείνοντας παράλληλα μερικά από αυτά. Η βασική συνεισφορά μας είναι η δημιουργίαενός μοντέλου για malleable job scheduling που γενικεύει την ιδέα του uniform machinescheduling και η παρουσίαση προσεγγιστικών αλγορίθμων σταθερού παράγοντα για αυτό |
URI: | http://artemis-new.cslab.ece.ntua.gr:8080/jspui/handle/123456789/13245 |
Appears in Collections: | Διπλωματικές Εργασίες - Theses |
Files in This Item:
File | Size | Format | |
---|---|---|---|
DT2016-0228.pdf | 1.36 MB | Adobe PDF | View/Open |
Items in Artemis are protected by copyright, with all rights reserved, unless otherwise indicated.