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

Περίληψη

ΑΝΤΙΚΕΙΜΕΝΟ ΤΗΣ ΔΙΑΤΡΙΒΗΣ ΕΙΝΑΙ Η ΒΕΛΤΙΣΤΗ ΠΑΡΑΛΛΗΛΟΠΟΙΗΣΗ ΦΩΛΙΑΣΜΕΝΩΝ FOR (DO) ΒΡΟΓΧΩΝ ΜΕ ΟΜΟΙΟΜΟΡΦΕΣ ΕΞΑΡΤΗΣΕΙΣ. ΒΕΛΤΙΣΤΗ ΠΑΡΑΛΛΗΛΟΠΟΙΗΣΗ ΕΙΝΑΙ ΕΝΑΣ ΧΡΟΝΟΠΡΟΓΡΑΜΜΑΤΙΣΜΟΣ ΠΟΥ ΕΠΙΤΥΓΧΑΝΕΙ ΤΟΝ ΕΛΑΧΙΣΤΟ ΠΑΡΑΛΛΗΛΟ ΧΡΟΝΟ ΧΡΗΣΙΜΟΠΟΙΩΝΤΑΣ ΤΟΝ ΕΛΑΧΙΣΤΟ ΑΡΙΘΜΟ ΕΠΕΞΕΡΓΑΣΤΩΝ. ΑΠΟΔΕΙΚΝΥΟΝΤΑΙ ΑΝΩ ΚΑΙ ΚΑΤΩ ΟΡΙΑ ΓΙΑ ΤΟ ΒΕΛΤΙΣΤΟ ΑΡΙΘΜΟ ΕΠΕΞΕΡΓΑΣΤΩΝ ΚΑΙ ΠΡΟΤΕΙΝΕΤΑΙ ΜΙΑ ΜΕΘΟΔΟΣ ΑΠΕΙΚΟΝΙΣΗΣ ΣΕ ΣΥΣΤΟΛΙΚΕΣ ΔΙΑΤΑΞΕΙΣ ΠΟΥ ΤΑ ΕΠΙΤΥΓΧΑΝΕΙ. ΙΔΙΑΙΤΕΡΗ ΕΜΦΑΣΗ ΔΙΝΕΤΑΙ ΣΤΟΥΣ ΓΡΑΜΜΙΚΟΥΣ ΧΡΟΝΟΠΡΟΓΡΑΜΜΑΤΙΣΜΟΥΣ. ΟΙ ΥΠΑΡΧΟΝΤΕΣ ΑΛΓΟΡΙΘΜΟΙ ΗΤΑΝ ΕΚΘΕΤΙΚΟΙ ΩΣ ΠΡΟΣ ΤΟΝ ΑΡΙΘΜΟ ΤΩΝ ΔΙΑΝΥΣΜΑΤΩΝ ΕΞΑΡΤΗΣΗΣ ΚΑΙ ΤΗ ΔΙΑΣΤΑΣΗ ΤΟΥ ΧΩΡΟΥ ΔΕΙΚΤΩΝ. ΓΙΑ 2 - ΔΙΑΣΤΑΤΟ ΚΑΙ 3 - ΔΙΑΣΤΑΤΟ ΧΩΡΟ ΔΕΙΚΤΩΝ, ΠΟΥ ΚΥΡΙΩΣ ΕΝΔΙΑΦΕΡΟΥΝ ΓΙΑ ΤΗΝ ΑΠΕΙΚΟΝΙΣΗ ΣΕ ΣΥΣΤΟΛΙΚΕΣ ΔΙΑΤΑΞΕΙΣ, ΠΡΟΤΕΙΝΟΝΤΑΙ ΑΛΓΟΡΙΘΜΟΙ ΠΟΛΥΩΝΥΜΙΚΟΙ ΩΣ ΠΡΟΣ ΤΟΝ ΑΡΙΘΜΟ ΤΩΝ ΔΙΑΝΥΣΜΑΤΩΝ ΕΞΑΡΤΗΣΗΣ. ΟΙ ΠΡΟΤΕΙΝΟΜΕΝΟΙ ΑΛΓΟΡΙΘΜΟΙ ΛΥΝΟΥΝ ΤΟ ΠΡΟΒΛΗΜΑ ΤΟΥ ΒΕΛΤΙΣΤΟΥ ΓΡΑΜΜΙΚΟΥ ΧΡΟΝΟΠΡΟΓΡΑΜΜΑΤΙΣΜΟΥ ΓΙΑ ΟΙΚΟΓΕΝΕΙΕΣ ΑΛΓΟΡΙΘΜΩΝ. ΠΟΛΛΟΙ ΕΥΡΕΩΣ ΧΡΗΣΙΜΟΠΟΙΟΥΜΕΝΟΙ ΑΛΓΟΡΙΘΜΟΙ ΑΝΑΠΑΡΙΣΤΑΝΤΑΙ Ω ...
περισσότερα

Περίληψη σε άλλη γλώσσα

THIS DISSERTATION STUDIES THE PROBLEM OF OPTIMAL PARALLELIZATION OF NESTED FOR(DO) LOOPS WITH UNIFORM DEPENDENCIES. AN OPTIMAL PARALLELIZATION IS A SCHEDULE THAT ACHIEVES THE MINIMUM PARALLEL EXECUTION TIME WHILE USING THE MINIMUM NUMBER OF PROCESSORS. UPPER AND LOWER BOUNDS ON THE NUMBER OF PROCESSORS NECESSARY TO ACCOMPLISH THE OPTIMAL PARALLEL TIME ARE PROVED. A GENERAL METHODOLOGYTHAT MAPS ALGORITHMS OF THIS CLASS INTO SYSTOLIC ARRAYS AND ACHIEVES THE ABOVEBOUDS IS PROPOSED. PARTICULAR EMPHASIS IS GIVEN TO LINEAR SCHEDULES. THE EXISTING ALGORITHMS FOR CALCULATING THE OPTIMAL LINEAR SCHEDULE WERE EXPONENTIAL IN THE NUMBER OF DEPENDENCE VECTORS AND THE DIMENSION OF THE INDEX SPACE. FOR 2 - DIMENSIONAL AND 3 - DIMENSIONAL INDEX SPACES, ALGORITHMS WITH POLYNOMIAL TIME COMPLEXITY IN THE NUMBER OF DEPENDENCE VECTORS ARE PROPOSED. THESE ALGORITHMS ACTUALLY SOLVE THE OPTIMAL LINEAR SCHEDULE PROBLEM FOR FAMILIES OF ALGORITHMS. GRIDS ARE A SPECIAL CASE OF NESTED FRO (DO) LOO ...
περισσότερα
Πρέπει να είστε εγγεγραμένος χρήστης για έχετε πρόσβαση σε όλες τις υπηρεσίες του ΕΑΔΔ  Είσοδος /Εγγραφή

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

DOI
10.12681/eadd/8870
Διεύθυνση Handle
http://hdl.handle.net/10442/hedi/8870
Εναλλακτικός τίτλος
AUTOMATIC PARALLELIZATION OF SEQUENTIAL ALGORITHMS
Συγγραφέας
ΑΝΔΡΟΝΙΚΟΣ, ΘΕΟΔΩΡΟΣ
Ημερομηνία
1997
Ίδρυμα
Εθνικό Μετσόβιο Πολυτεχνείο (ΕΜΠ). Τμήμα Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών
Εξεταστική επιτροπή
ΠΑΠΑΚΩΝΣΤΑΝΤΙΝΟΥ ΓΕΩΡΓΙΟΣ
ΣΚΟΡΔΑΛΑΚΗΣ ΕΜΜΑΝΟΥΗΛ
ΖΑΧΟΣ ΕΥΣΤΑΘΙΟΣ
ΣΕΛΛΗΣ ΤΙΜΟΛΕΩΝ
ΠΕΚΜΕΣΤΖΗ ΚΕΜΑΛ
ΣΤΑΦΥΛΟΠΑΤΗΣ ΑΝΔΡΕΑΣ
ΤΣΑΝΑΚΑΣ ΠΑΝΑΓΙΩΤΗΣ
Επιστημονικό πεδίο
Μηχανική & Τεχνολογία
Επιστήμες Ηλεκτρολόγου Μηχανικού, Ηλεκτρονικού Μηχανικού & Μηχανικού Η/Υ
Λέξεις-κλειδιά
ΒΕΛΤΙΣΤΟΣ ΠΑΡΑΛΛΗΛΟΣ ΧΡΟΝΟΣ; ΒΕΛΤΙΣΤΟΣ ΧΡΟΝΟΠΡΟΓΡΑΜΜΑΤΙΣΜΟΣ; ΕΛΑΧΙΣΤΟΣ ΑΡΙΘΜΟΣ ΕΠΕΞΕΡΓΑΣΤΩΝ; ΕΛΑΧΙΣΤΟΣ ΠΑΡΑΛΛΗΛΟΣ ΧΡΟΝΟΣ; ΜΕΤΑΣΧΗΜΑΤΙΣΜΟΙ ΑΛΓΟΡΙΘΜΩΝ; ΠΑΡΑΛΛΗΛΟΠΟΙΗΣΗ ΦΩΛΙΑΣΜΕΝΩΝ FOR (DO) ΒΡΟΓΧΩΝ; Πλέγματα; Συστολικές διατάξεις
Χώρα
Ελλάδα
Γλώσσα
Ελληνικά