ΑΝΑΘΕΣΗ ΕΡΓΑΣΙΩΝ ΣΕ ΚΑΤΑΝΕΜΗΜΕΝΑ ΥΠΟΛΟΓΙΣΤΙΚΑ ΣΥΣΤΗΜΑΤΑ: ΑΛΓΟΡΙΘΜΟΙ ΚΑΙ ΠΟΛΥΠΛΟΚΟΤΗΤΑ

Abstract

THE PROBLEM OF ASSIGNING THE TASKS OF A SOFTWARE SYSTEM TO THE PROCESSORS OF A DISTRIBUTED ENVIRONMENT IS EXAMINED. THE AIM OF THE ASSIGNMENT IS THE MINIMIZATION OF THE SUM OF EXECUTION TIME PLUS THE COMMUNICATION OVERHEADS. IN THE THESIS WE FORMALLY SHOW THAT THE PROBLEM, FOR THREE OR MORE PROCESSORS, IS NP-COMPLETE. UNDER THIS MAIN RESTRICTION WE PRESENT THREE NEW ALGORITHMS FOR THE PROBLEM. THE FIRST IS A POLYNOMIAL DYNAMIC PROGRAMMING ALGORITHM FOR THE SPECIAL CASE IN WHICH THE COMMUNICATION PATTERN BETWEEN THE TASKS FORMS A SERIES-PARALLEL GRAPH. THE SECOND, AN EXHAUSTIVE SEARCH ALGORITHM, RELIES ON AN EFFICIENT LOWER BOUND THAT WE GENERATE BY DISREGARDING A NUMBER OF COMMUNICATION LINKS REDUCING THUS THE ORIGINAL COMMUNICATION STRUCTURE TO A TREE FOR WHICH THE OPTIMIZATION PROBLEM IS POLYNOMIALLY SOLVABLE.THESE BOUNDS SERVE AS THE BASIS FOR A BRANCH AND BOUND ALGORITHM FOR THE GENERAL PROBLEM. WE DISCUSS THE IMPLEMENTATION OF THE ALGORITHM AND PROVIDE REPRESENTATIVE RESULTS. THE THIRD IS A HEURISTIC ALGORITHM. THE ALGORITHM USING MIN- CUT TECHNIQUES ACHIEVES A VERY GOOD APPROXIMATION OF THE OPTIMAL SOLUTION, AS SHOWN FROM NUMERICAL RESULTS, WITHIN POLYNOMIAL TIME.

ΣΤΗΝ ΔΙΑΤΡΙΒΗ ΕΞΕΤΑΖΕΤΑΙ ΤΟ ΠΡΟΒΛΗΜΑ ΤΗΣ ΑΝΑΘΕΣΗΣ ΤΩΝ ΕΡΓΑΣΙΩΝ ΜΙΑΣ ΥΠΟΛΟΓΙΣΤΙΚΗΣ ΕΦΑΡΜΟΓΗΣ ΣΤΟΥΣ ΕΠΕΞΕΡΓΑΣΤΕΣ ΕΝΟΣ ΚΑΤΑΝΕΜΗΜΕΝΟΥ ΥΠΟΛΟΓΙΣΤΙΚΟΥ ΣΥΣΤΗΜΑΤΟΣ, ΜΕΚΡΙΤΗΡΙΟ ΤΗΝ ΕΛΑΧΙΣΤΟΠΟΙΗΣΗ ΤΟΥ ΑΘΡΟΙΣΜΑΤΟΣ ΤΟΥ ΧΡΟΝΟΥ ΕΚΤΕΛΕΣΗΣ ΚΑΙ ΤΟΥ ΧΡΟΝΟΥ ΕΠΙΚΟΙΝΩΝΙΩΝ. ΑΠΟΔΕΙΚΝΥΕΤΑΙ ΟΤΙ ΤΟ ΠΡΟΒΛΗΜΑ, ΓΙΑ ΤΡΕΙΣ 'Η ΠΕΡΙΣΣΟΤΕΡΟΥΣ ΕΠΕΞΕΡΓΑΣΤΕΣ, ΑΝΗΚΕΙ ΣΤΑ ΓΝΩΣΤΑ ΣΑΝ ΝΡ-COMPLETE ΠΡΟΒΛΗΜΑΤΑ. ΠΑΡΟΥΣΙΑΖΟΝΤΑΙ ΤΡΕΙΣ ΝΕΟΙ ΑΛΓΟΡΙΘΜΟΙ ΑΝΤΙΜΕΤΩΠΙΣΗΣ ΤΟΥ. ΟΤΑΝ ΟΙ ΕΠΙΚΟΙΝΩΝΙΕΣ ΜΕΤΑΞΥ ΤΩΝ ΕΡΓΑΣΙΩΝ ΠΟΥ ΑΠΟΤΕΛΟΥΝ ΜΙΑ ΕΦΑΡΜΟΓΗ ΕΧΟΥΝ ΜΟΡΦΗ SERIES-PARALLEL ΓΡΑΦΗΜΑΤΟΣ, Ο ΠΡΩΤΟΣ ΑΠΟ ΤΟΥΣ ΑΛΓΟΡΙΘΜΟΥΣ ΠΑΡΕΧΕΙ ΣΕ ΠΟΛΥΩΝΥΜΙΚΟ ΧΡΟΝΟ ΤΗΝ ΒΕΛΤΙΣΤΗ ΛΥΣΗ. Ο ΔΕΥΤΕΡΟΣ ΧΡΗΣΙΜΟΠΟΙΕΙ ΤΗ ΓΝΩΣΤΗ ΣΑΝ BRANCH-AND-BOUND ΜΕΘΟΔΟ ΕΜΜΕΣΗΣ ΑΠΑΡΙΘΜΗΣΗΣ. Ο ΤΡΟΠΟΣ ΕΦΑΡΜΟΓΗΣ ΤΗΣ Ο ΟΠΟΙΟΣ ΠΡΟΤΕΙΝΕΤΑΙ, ΚΑΙ ΕΙΔΙΚΟΤΕΡΑ Ο ΤΡΟΠΟΣ ΥΠΟΛΟΓΙΣΜΟΥ ΟΡΙΩΝ, ΠΑΡΕΧΕΙ ΜΙΑ ΙΔΙΑΙΤΕΡΑ ΑΠΟΤΕΛΕΣΜΑΤΙΚΗ ΑΝΤΙΜΕΤΩΠΙΣΗ ΤΟΥ ΠΡΟΒΛΗΜΑΤΟΣ, ΣΤΗ ΓΕΝΙΚΗ ΤΟΥ ΜΟΡΦΗ . ΠΑΡΟΥΣΙΑΖΟΝΤΑΙ ΥΠΟΛΟΓΙΣΤΙΚΑ ΑΠΟΤΕΛΕΣΜΑΤΑ ΑΠΟ ΤΑ ΟΠΟΙΑ ΔΙΑΠΙΣΤΩΝΕΤΑΙ Η ΑΠΟΤΕΛΕΣΜΑΤΙΚΟΤΗΤΑ ΤΟΥ ΑΛΓΟΡΙΘΜΟΥ. Ο ΤΡΙΤΟΣ, ΤΕΛΟΣ, ΕΙΝΑΙ ΕΝΑΣ ΕΥΡΕΤΙΚΟΣ ΑΛΓΟΡΙΘΜΟΣΜΕ ΙΔΙΑΙΤΕΡΟ ΧΑΡΑΚΤΗΡΙΣΤΙΚΟ ΤΗΝ ΠΟΛΥΩΝΥΜΙΚΗ ΤΟΥ ΠΟΛΥΠΛΟΚΟΤΗΤΑ. ΧΡΗΣΙΜΟΠΟΙΕΙΤΑΙΕΠΑΝΑΛΗΠΤΙΚΑ ΕΝΑΣ ΑΛΓΟΡΙΘΜΟΣ ΕΛΑΧΙΣΤΗΣ-ΤΟΜΗΣ/ΜΕΓΙΣΤΗΣ-ΡΟΗΣ ΚΑΙ ΠΡΟΣΦΕΡΟΝΤΑΙ ΛΥΣΕΙΣ ΜΕ ΜΙΚΡΗ ΑΠΟΚΛΙΣΗ ΑΠΟ ΤΗ ΒΕΛΤΙΣΤΗ.