Βέλτιστη εκτέλεση εργασιών σε παράλληλα ετερογενή υπολογιστικά περιβάλλοντα
Loading...
Date
Authors
Σαλωνίτη, Αγγελική
Journal Title
Journal ISSN
Volume Title
Publisher
Σχολή Πληροφορικής και Τηλεπικοινωνιών, Τμήμα Πληροφορικής και Τηλεπικοινωνιών
Abstract
Type
Type of the conference item
Journal type
Educational material type
Conference Name
Journal name
Book name
Book series
Book edition
Alternative title / Subtitle
Description
Στα πλαίσια αυτής της εργασίας μελετήθηκαν διάφορες ακριβείς και ευρετικές τεχνικές που αποσκοπούν στη βέλτιστη εκτέλεση εργασιών σε παράλληλα ετερογενή υπολογιστικά περιβάλλοντα. Αναπτύχθηκε ένας ευρετικός αλγόριθμος, ο CPHEFT, που βασίζεται σε μια τεχνική η οποία ονομάζεται list scheduling. Αποτελεί μια τροποποίηση του αλγορίθμου HEFT, η οποία έγκειται στην ταξινόμηση των εργασιών με βάση την κρίσιμη διαδρομή στο γράφημα των εργασιών. Με την ταξινόμηση αυτή, ορίζεται η προτεραιότητα με την οποία πραγματοποιείται η ανάθεση των εργασιών σε καθέναν από τους διαθέσιμους επεξεργαστές ενός ετερογενούς συστήματος. Ο CPHEFT ανήκει στους αλγορίθμους οι οποίοι προγραμματίζουν την ανάθεση ενός κόμβου στον επεξεργαστή, που υποστηρίζει τον σχετικά προγενέστερο χρόνο έναρξης της εκτέλεσης αυτού του κόμβου (earliest start-time). Ο κύριος στόχος του αλγορίθμου είναι να ελαχιστοποιήσει τον συνολικό χρόνο εκτέλεσης των συσχετιζόμενων εργασιών (makespan). Οι εισροές, που χρησιμοποιήθηκαν για σύγκριση, ήταν DAGs τυχαία παραγόμενα από γεννήτρια, η οποία αναπτύχθηκε στα πλαίσια της εργασίας γι αυτό το σκοπό. Παρατηρήθηκε ότι ο αλγόριθμος CPHEFT επιτυγχάνει συγκρίσιμη απόδοση με τον αλγόριθμο HEFT και μπορεί να επιτύχει καλύτερη απόδοση για γράφους, οι οποίοι περιγράφουν προβλήματα με αυξημένο κόστος επικοινωνίας μεταξύ των εργασιών, καθώς οι μεταφορές δεδομένων διαδραματίζουν ουσιαστικό ρόλο στην εκτέλεση ροών εργασιών.
In this work, various exact methods and heuristic techniques that aim at optimal task scheduling in parallel heterogeneous computing environments have been studied. A new heuristic algorithm called CPHEFT, which is based on the list scheduling technique, was developed. The main difference between CPHEFT and HEFT algorithm is that CPHEFT orders the tasks based on the critical path of the associated DAG. This ordering specifies the priority assignment of tasks to each of the available processors of a heterogeneous system. CPHEFT belongs to a category of algorithms that program the assignment of a node to a processor that supports the earlier start-time of this node. The main target of the algorithm is to minimize the overall execution time of the associated tasks known as schedule length or makespan. The inputs, used for comparison, were DAGs randomly generated by a generator, developed especially for this purpose. It was observed that the CPHEFT algorithm achieves comparable performance to the HEFT algorithm and can achieve better performance for graphs that represent problems with increased cost of communication between tasks. This feature of CPHEFT is significant, since data transfers play an essential role in executing workflows.
In this work, various exact methods and heuristic techniques that aim at optimal task scheduling in parallel heterogeneous computing environments have been studied. A new heuristic algorithm called CPHEFT, which is based on the list scheduling technique, was developed. The main difference between CPHEFT and HEFT algorithm is that CPHEFT orders the tasks based on the critical path of the associated DAG. This ordering specifies the priority assignment of tasks to each of the available processors of a heterogeneous system. CPHEFT belongs to a category of algorithms that program the assignment of a node to a processor that supports the earlier start-time of this node. The main target of the algorithm is to minimize the overall execution time of the associated tasks known as schedule length or makespan. The inputs, used for comparison, were DAGs randomly generated by a generator, developed especially for this purpose. It was observed that the CPHEFT algorithm achieves comparable performance to the HEFT algorithm and can achieve better performance for graphs that represent problems with increased cost of communication between tasks. This feature of CPHEFT is significant, since data transfers play an essential role in executing workflows.
Description
Keywords
Ετερογενή συστήματα, Κατευθυνόμενοι μη κυκλικοί γράφοι, Αλγόριθμοι, Ακέραιος προγραμματισμός
Subject classification
Προγραμματισμός κατευθυνόμενων μη κυκλικών γράφων
Citation
Link
Language
el
Publishing department/division
Σχολή Πληροφορικής και Τηλεπικοινωνιών, Τμήμα Πληροφορικής και Τηλεπικοινωνιών
Advisor name
Γκόγκος, Χρήστος
Examining committee
Γκόγκος, Χρήστος
Στύλιος, Χρυσόστομος
Λιαροκάπης, Δημήτριος
Στύλιος, Χρυσόστομος
Λιαροκάπης, Δημήτριος
General Description / Additional Comments
Institution and School/Department of submitter
Τ.Ε.Ι. Ηπείρου
Table of contents
Sponsor
Bibliographic citation
Σαλωνίτη, Α., 2019. Βέλτιστη εκτέλεση εργασιών σε παράλληλα ετερογενή υπολογιστικά περιβάλλοντα. Άρτα: Πανεπιστήμιο Ιωαννίνων, Σχολή Πληροφορικής και Τηλεπικοινωνιών, Τμήμα Πληροφορικής και Τηλεπικοινωνιών.
Name(s) of contributor(s)
Number of Pages
102
Course details
Endorsement
Review
Supplemented By
Referenced By
Creative Commons license
Except where otherwised noted, this item's license is described as Αναφορά Δημιουργού-Μη Εμπορική Χρήση-Όχι Παράγωγα Έργα 3.0 Ελλάδα