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

Περίληψη

ΣΤΗΝ ΔΙΑΤΡΙΒΗ ΕΞΕΤΑΖΕΤΑΙ ΤΟ ΠΡΟΒΛΗΜΑ ΤΗΣ ΑΝΑΘΕΣΗΣ ΤΩΝ ΕΡΓΑΣΙΩΝ ΜΙΑΣ ΥΠΟΛΟΓΙΣΤΙΚΗΣ ΕΦΑΡΜΟΓΗΣ ΣΤΟΥΣ ΕΠΕΞΕΡΓΑΣΤΕΣ ΕΝΟΣ ΚΑΤΑΝΕΜΗΜΕΝΟΥ ΥΠΟΛΟΓΙΣΤΙΚΟΥ ΣΥΣΤΗΜΑΤΟΣ, ΜΕΚΡΙΤΗΡΙΟ ΤΗΝ ΕΛΑΧΙΣΤΟΠΟΙΗΣΗ ΤΟΥ ΑΘΡΟΙΣΜΑΤΟΣ ΤΟΥ ΧΡΟΝΟΥ ΕΚΤΕΛΕΣΗΣ ΚΑΙ ΤΟΥ ΧΡΟΝΟΥ ΕΠΙΚΟΙΝΩΝΙΩΝ. ΑΠΟΔΕΙΚΝΥΕΤΑΙ ΟΤΙ ΤΟ ΠΡΟΒΛΗΜΑ, ΓΙΑ ΤΡΕΙΣ 'Η ΠΕΡΙΣΣΟΤΕΡΟΥΣ ΕΠΕΞΕΡΓΑΣΤΕΣ, ΑΝΗΚΕΙ ΣΤΑ ΓΝΩΣΤΑ ΣΑΝ ΝΡ-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 ...
περισσότερα
Πρέπει να είστε εγγεγραμένος χρήστης για έχετε πρόσβαση σε όλες τις υπηρεσίες του ΕΑΔΔ  Είσοδος /Εγγραφή

Όλα τα τεκμήρια στο ΕΑΔΔ προστατεύονται από πνευματικά δικαιώματα.

DOI
10.12681/eadd/1201
Διεύθυνση Handle
http://hdl.handle.net/10442/hedi/1201
Εναλλακτικός τίτλος
TASK ASSIGNMENT IN DISTRIBUTED COMPUTING SYSTEMS:ALGORITHMS AND COMPLEXITY
Συγγραφέας
ΜΗΛΗΣ, ΙΩΑΝΝΗΣ
Ημερομηνία
1989
Ίδρυμα
Οικονομικό Πανεπιστήμιο Αθηνών. Τμήμα Στατιστικής
Εξεταστική επιτροπή
ΚΑΛΑΜΠΟΥΚΗΣ ΘΕΟΔΩΡΟΣ
ΛΥΠΙΤΑΚΗΣ ΗΛΙΑΣ
ΜΑΓΕΙΡΟΥ ΕΥΑΓΓΕΛΟΣ
ΜΗΛΙΩΤΗΣ ΠΑΝΑΓΙΩΤΗΣ
ΑΦΡΑΤΗ ΦΩΤΩ
Επιστημονικό πεδίο
Κοινωνικές Επιστήμες
Άλλες Κοινωνικές Επιστήμες
Λέξεις-κλειδιά
ΑΝΑΘΕΣΗ ΕΡΓΑΣΙΩΝ; Δυναμικός προγραμματισμός; ΕΛΑΧΙΣΤΗ ΤΟΜΗ ΓΡΑΦΗΜΑΤΟΣ; Ευρετικοί αλγόριθμοι; Κατανεμημένα συστήματα; ΜΕΘΟΔΟΣ ΔΙΑΚΛΑΔΩΣΗΣ ΚΑΙ ΦΡΑΓΜΑΤΟΣ; Πολυπλοκότητα; ΣΕΙΡΙΑΚΑ ΠΑΡΑΛΛΗΛΑ ΓΡΑΦΗΜΑΤΑ
Χώρα
Ελλάδα
Γλώσσα
Ελληνικά