|
Περίληψη
ΣΤΗΝ ΔΙΑΤΡΙΒΗ ΕΞΕΤΑΖΕΤΑΙ ΤΟ ΠΡΟΒΛΗΜΑ ΤΗΣ ΑΝΑΘΕΣΗΣ ΤΩΝ ΕΡΓΑΣΙΩΝ ΜΙΑΣ ΥΠΟΛΟΓΙΣΤΙΚΗΣ ΕΦΑΡΜΟΓΗΣ ΣΤΟΥΣ ΕΠΕΞΕΡΓΑΣΤΕΣ ΕΝΟΣ ΚΑΤΑΝΕΜΗΜΕΝΟΥ ΥΠΟΛΟΓΙΣΤΙΚΟΥ ΣΥΣΤΗΜΑΤΟΣ, ΜΕΚΡΙΤΗΡΙΟ ΤΗΝ ΕΛΑΧΙΣΤΟΠΟΙΗΣΗ ΤΟΥ ΑΘΡΟΙΣΜΑΤΟΣ ΤΟΥ ΧΡΟΝΟΥ ΕΚΤΕΛΕΣΗΣ ΚΑΙ ΤΟΥ ΧΡΟΝΟΥ ΕΠΙΚΟΙΝΩΝΙΩΝ. ΑΠΟΔΕΙΚΝΥΕΤΑΙ ΟΤΙ ΤΟ ΠΡΟΒΛΗΜΑ, ΓΙΑ ΤΡΕΙΣ 'Η ΠΕΡΙΣΣΟΤΕΡΟΥΣ ΕΠΕΞΕΡΓΑΣΤΕΣ, ΑΝΗΚΕΙ ΣΤΑ ΓΝΩΣΤΑ ΣΑΝ ΝΡ-COMPLETE ΠΡΟΒΛΗΜΑΤΑ. ΠΑΡΟΥΣΙΑΖΟΝΤΑΙ ΤΡΕΙΣ ΝΕΟΙ ΑΛΓΟΡΙΘΜΟΙ ΑΝΤΙΜΕΤΩΠΙΣΗΣ ΤΟΥ. ΟΤΑΝ ΟΙ ΕΠΙΚΟΙΝΩΝΙΕΣ ΜΕΤΑΞΥ ΤΩΝ ΕΡΓΑΣΙΩΝ ΠΟΥ ΑΠΟΤΕΛΟΥΝ ΜΙΑ ΕΦΑΡΜΟΓΗ ΕΧΟΥΝ ΜΟΡΦΗ SERIES-PARALLEL ΓΡΑΦΗΜΑΤΟΣ, Ο ΠΡΩΤΟΣ ΑΠΟ ΤΟΥΣ ΑΛΓΟΡΙΘΜΟΥΣ ΠΑΡΕΧΕΙ ΣΕ ΠΟΛΥΩΝΥΜΙΚΟ ΧΡΟΝΟ ΤΗΝ ΒΕΛΤΙΣΤΗ ΛΥΣΗ. Ο ΔΕΥΤΕΡΟΣ ΧΡΗΣΙΜΟΠΟΙΕΙ ΤΗ ΓΝΩΣΤΗ ΣΑΝ BRANCH-AND-BOUND ΜΕΘΟΔΟ ΕΜΜΕΣΗΣ ΑΠΑΡΙΘΜΗΣΗΣ. Ο ΤΡΟΠΟΣ ΕΦΑΡΜΟΓΗΣ ΤΗΣ Ο ΟΠΟΙΟΣ ΠΡΟΤΕΙΝΕΤΑΙ, ΚΑΙ ΕΙΔΙΚΟΤΕΡΑ Ο ΤΡΟΠΟΣ ΥΠΟΛΟΓΙΣΜΟΥ ΟΡΙΩΝ, ΠΑΡΕΧΕΙ ΜΙΑ ΙΔΙΑΙΤΕΡΑ ΑΠΟΤΕΛΕΣΜΑΤΙΚΗ ΑΝΤΙΜΕΤΩΠΙΣΗ ΤΟΥ ΠΡΟΒΛΗΜΑΤΟΣ, ΣΤΗ ΓΕΝΙΚΗ ΤΟΥ ΜΟΡΦΗ . ΠΑΡΟΥΣΙΑΖΟΝΤΑΙ ΥΠΟΛΟΓΙΣΤΙΚΑ ΑΠΟΤΕΛΕΣΜΑΤΑ ΑΠΟ ΤΑ ΟΠΟΙΑ ΔΙΑΠΙΣΤΩΝΕΤΑΙ Η ΑΠΟΤΕΛΕΣΜΑΤΙΚΟΤΗΤΑ ΤΟΥ ΑΛΓΟΡΙΘΜΟΥ. Ο ΤΡΙΤΟΣ, ΤΕΛΟΣ, ΕΙΝΑΙ ...
ΣΤΗΝ ΔΙΑΤΡΙΒΗ ΕΞΕΤΑΖΕΤΑΙ ΤΟ ΠΡΟΒΛΗΜΑ ΤΗΣ ΑΝΑΘΕΣΗΣ ΤΩΝ ΕΡΓΑΣΙΩΝ ΜΙΑΣ ΥΠΟΛΟΓΙΣΤΙΚΗΣ ΕΦΑΡΜΟΓΗΣ ΣΤΟΥΣ ΕΠΕΞΕΡΓΑΣΤΕΣ ΕΝΟΣ ΚΑΤΑΝΕΜΗΜΕΝΟΥ ΥΠΟΛΟΓΙΣΤΙΚΟΥ ΣΥΣΤΗΜΑΤΟΣ, ΜΕΚΡΙΤΗΡΙΟ ΤΗΝ ΕΛΑΧΙΣΤΟΠΟΙΗΣΗ ΤΟΥ ΑΘΡΟΙΣΜΑΤΟΣ ΤΟΥ ΧΡΟΝΟΥ ΕΚΤΕΛΕΣΗΣ ΚΑΙ ΤΟΥ ΧΡΟΝΟΥ ΕΠΙΚΟΙΝΩΝΙΩΝ. ΑΠΟΔΕΙΚΝΥΕΤΑΙ ΟΤΙ ΤΟ ΠΡΟΒΛΗΜΑ, ΓΙΑ ΤΡΕΙΣ 'Η ΠΕΡΙΣΣΟΤΕΡΟΥΣ ΕΠΕΞΕΡΓΑΣΤΕΣ, ΑΝΗΚΕΙ ΣΤΑ ΓΝΩΣΤΑ ΣΑΝ ΝΡ-COMPLETE ΠΡΟΒΛΗΜΑΤΑ. ΠΑΡΟΥΣΙΑΖΟΝΤΑΙ ΤΡΕΙΣ ΝΕΟΙ ΑΛΓΟΡΙΘΜΟΙ ΑΝΤΙΜΕΤΩΠΙΣΗΣ ΤΟΥ. ΟΤΑΝ ΟΙ ΕΠΙΚΟΙΝΩΝΙΕΣ ΜΕΤΑΞΥ ΤΩΝ ΕΡΓΑΣΙΩΝ ΠΟΥ ΑΠΟΤΕΛΟΥΝ ΜΙΑ ΕΦΑΡΜΟΓΗ ΕΧΟΥΝ ΜΟΡΦΗ SERIES-PARALLEL ΓΡΑΦΗΜΑΤΟΣ, Ο ΠΡΩΤΟΣ ΑΠΟ ΤΟΥΣ ΑΛΓΟΡΙΘΜΟΥΣ ΠΑΡΕΧΕΙ ΣΕ ΠΟΛΥΩΝΥΜΙΚΟ ΧΡΟΝΟ ΤΗΝ ΒΕΛΤΙΣΤΗ ΛΥΣΗ. Ο ΔΕΥΤΕΡΟΣ ΧΡΗΣΙΜΟΠΟΙΕΙ ΤΗ ΓΝΩΣΤΗ ΣΑΝ BRANCH-AND-BOUND ΜΕΘΟΔΟ ΕΜΜΕΣΗΣ ΑΠΑΡΙΘΜΗΣΗΣ. Ο ΤΡΟΠΟΣ ΕΦΑΡΜΟΓΗΣ ΤΗΣ Ο ΟΠΟΙΟΣ ΠΡΟΤΕΙΝΕΤΑΙ, ΚΑΙ ΕΙΔΙΚΟΤΕΡΑ Ο ΤΡΟΠΟΣ ΥΠΟΛΟΓΙΣΜΟΥ ΟΡΙΩΝ, ΠΑΡΕΧΕΙ ΜΙΑ ΙΔΙΑΙΤΕΡΑ ΑΠΟΤΕΛΕΣΜΑΤΙΚΗ ΑΝΤΙΜΕΤΩΠΙΣΗ ΤΟΥ ΠΡΟΒΛΗΜΑΤΟΣ, ΣΤΗ ΓΕΝΙΚΗ ΤΟΥ ΜΟΡΦΗ . ΠΑΡΟΥΣΙΑΖΟΝΤΑΙ ΥΠΟΛΟΓΙΣΤΙΚΑ ΑΠΟΤΕΛΕΣΜΑΤΑ ΑΠΟ ΤΑ ΟΠΟΙΑ ΔΙΑΠΙΣΤΩΝΕΤΑΙ Η ΑΠΟΤΕΛΕΣΜΑΤΙΚΟΤΗΤΑ ΤΟΥ ΑΛΓΟΡΙΘΜΟΥ. Ο ΤΡΙΤΟΣ, ΤΕΛΟΣ, ΕΙΝΑΙ ΕΝΑΣ ΕΥΡΕΤΙΚΟΣ ΑΛΓΟΡΙΘΜΟΣΜΕ ΙΔΙΑΙΤΕΡΟ ΧΑΡΑΚΤΗΡΙΣΤΙΚΟ ΤΗΝ ΠΟΛΥΩΝΥΜΙΚΗ ΤΟΥ ΠΟΛΥΠΛΟΚΟΤΗΤΑ. ΧΡΗΣΙΜΟΠΟΙΕΙΤΑΙΕΠΑΝΑΛΗΠΤΙΚΑ ΕΝΑΣ ΑΛΓΟΡΙΘΜΟΣ ΕΛΑΧΙΣΤΗΣ-ΤΟΜΗΣ/ΜΕΓΙΣΤΗΣ-ΡΟΗΣ ΚΑΙ ΠΡΟΣΦΕΡΟΝΤΑΙ ΛΥΣΕΙΣ ΜΕ ΜΙΚΡΗ ΑΠΟΚΛΙΣΗ ΑΠΟ ΤΗ ΒΕΛΤΙΣΤΗ.
περισσότερα
Περίληψη σε άλλη γλώσσα
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 RESU ...
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.
περισσότερα
 | |
 | Κατεβάστε τη διατριβή σε μορφή PDF (5.09 MB)
(Η υπηρεσία είναι διαθέσιμη μετά από δωρεάν εγγραφή)
|  | Online παραγγελία της διατριβής (σε έντυπη ή ψηφιακή μορφή) (Η υπηρεσία είναι διαθέσιμη μετά από δωρεάν εγγραφή) |
Πρέπει να είστε εγγεγραμένος χρήστης για έχετε πρόσβαση σε όλες τις υπηρεσίες του ΕΑΔΔ
Είσοδος
/ Εγγραφή
Όλα τα τεκμήρια στο ΕΑΔΔ προστατεύονται από πνευματικά δικαιώματα.
DOI | 10.12681/eadd/1201 | Διεύθυνση Handle | http://hdl.handle.net/10442/hedi/1201 | Εναλλακτικός τίτλος | TASK ASSIGNMENT IN DISTRIBUTED COMPUTING SYSTEMS:ALGORITHMS AND COMPLEXITY
| Συγγραφέας | ΜΗΛΗΣ, ΙΩΑΝΝΗΣ | Ημερομηνία | 1989 |
Ίδρυμα | Οικονομικό Πανεπιστήμιο Αθηνών. Τμήμα Στατιστικής |
Εξεταστική επιτροπή | ΚΑΛΑΜΠΟΥΚΗΣ ΘΕΟΔΩΡΟΣ ΛΥΠΙΤΑΚΗΣ ΗΛΙΑΣ ΜΑΓΕΙΡΟΥ ΕΥΑΓΓΕΛΟΣ ΜΗΛΙΩΤΗΣ ΠΑΝΑΓΙΩΤΗΣ ΑΦΡΑΤΗ ΦΩΤΩ |
Επιστημονικό πεδίο | Κοινωνικές Επιστήμες Άλλες Κοινωνικές Επιστήμες |
Λέξεις-κλειδιά | ΑΝΑΘΕΣΗ ΕΡΓΑΣΙΩΝ; Δυναμικός προγραμματισμός; ΕΛΑΧΙΣΤΗ ΤΟΜΗ ΓΡΑΦΗΜΑΤΟΣ; Ευρετικοί αλγόριθμοι; Κατανεμημένα συστήματα; ΜΕΘΟΔΟΣ ΔΙΑΚΛΑΔΩΣΗΣ ΚΑΙ ΦΡΑΓΜΑΤΟΣ; Πολυπλοκότητα; ΣΕΙΡΙΑΚΑ ΠΑΡΑΛΛΗΛΑ ΓΡΑΦΗΜΑΤΑ | Χώρα | Ελλάδα |
Γλώσσα | Ελληνικά |
|
λιγότερα
περισσότερα
|