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

Abstract

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) LOOPS WITH UNIFORM DEPENDENCIES. FOR A GENERALIZED FORM OF GRIDS, THE PROBLEM OF FINDING AN OPTIMAL SCHEDULE, ASSUMING NO COMMUNICATION COST (UET CASE) OR ASSUMING UNIT COMMUNICATION COST (UET - UCT CASE) WAS SOLVED AND AN EFFICIENT ALGORITHM THAT PRODUCES THE OPTIMAL SCHEDULE WAS PROPOSED.

ΑΝΤΙΚΕΙΜΕΝΟ ΤΗΣ ΔΙΑΤΡΙΒΗΣ ΕΙΝΑΙ Η ΒΕΛΤΙΣΤΗ ΠΑΡΑΛΛΗΛΟΠΟΙΗΣΗ ΦΩΛΙΑΣΜΕΝΩΝ FOR (DO) ΒΡΟΓΧΩΝ ΜΕ ΟΜΟΙΟΜΟΡΦΕΣ ΕΞΑΡΤΗΣΕΙΣ. ΒΕΛΤΙΣΤΗ ΠΑΡΑΛΛΗΛΟΠΟΙΗΣΗ ΕΙΝΑΙ ΕΝΑΣ ΧΡΟΝΟΠΡΟΓΡΑΜΜΑΤΙΣΜΟΣ ΠΟΥ ΕΠΙΤΥΓΧΑΝΕΙ ΤΟΝ ΕΛΑΧΙΣΤΟ ΠΑΡΑΛΛΗΛΟ ΧΡΟΝΟ ΧΡΗΣΙΜΟΠΟΙΩΝΤΑΣ ΤΟΝ ΕΛΑΧΙΣΤΟ ΑΡΙΘΜΟ ΕΠΕΞΕΡΓΑΣΤΩΝ. ΑΠΟΔΕΙΚΝΥΟΝΤΑΙ ΑΝΩ ΚΑΙ ΚΑΤΩ ΟΡΙΑ ΓΙΑ ΤΟ ΒΕΛΤΙΣΤΟ ΑΡΙΘΜΟ ΕΠΕΞΕΡΓΑΣΤΩΝ ΚΑΙ ΠΡΟΤΕΙΝΕΤΑΙ ΜΙΑ ΜΕΘΟΔΟΣ ΑΠΕΙΚΟΝΙΣΗΣ ΣΕ ΣΥΣΤΟΛΙΚΕΣ ΔΙΑΤΑΞΕΙΣ ΠΟΥ ΤΑ ΕΠΙΤΥΓΧΑΝΕΙ. ΙΔΙΑΙΤΕΡΗ ΕΜΦΑΣΗ ΔΙΝΕΤΑΙ ΣΤΟΥΣ ΓΡΑΜΜΙΚΟΥΣ ΧΡΟΝΟΠΡΟΓΡΑΜΜΑΤΙΣΜΟΥΣ. ΟΙ ΥΠΑΡΧΟΝΤΕΣ ΑΛΓΟΡΙΘΜΟΙ ΗΤΑΝ ΕΚΘΕΤΙΚΟΙ ΩΣ ΠΡΟΣ ΤΟΝ ΑΡΙΘΜΟ ΤΩΝ ΔΙΑΝΥΣΜΑΤΩΝ ΕΞΑΡΤΗΣΗΣ ΚΑΙ ΤΗ ΔΙΑΣΤΑΣΗ ΤΟΥ ΧΩΡΟΥ ΔΕΙΚΤΩΝ. ΓΙΑ 2 - ΔΙΑΣΤΑΤΟ ΚΑΙ 3 - ΔΙΑΣΤΑΤΟ ΧΩΡΟ ΔΕΙΚΤΩΝ, ΠΟΥ ΚΥΡΙΩΣ ΕΝΔΙΑΦΕΡΟΥΝ ΓΙΑ ΤΗΝ ΑΠΕΙΚΟΝΙΣΗ ΣΕ ΣΥΣΤΟΛΙΚΕΣ ΔΙΑΤΑΞΕΙΣ, ΠΡΟΤΕΙΝΟΝΤΑΙ ΑΛΓΟΡΙΘΜΟΙ ΠΟΛΥΩΝΥΜΙΚΟΙ ΩΣ ΠΡΟΣ ΤΟΝ ΑΡΙΘΜΟ ΤΩΝ ΔΙΑΝΥΣΜΑΤΩΝ ΕΞΑΡΤΗΣΗΣ. ΟΙ ΠΡΟΤΕΙΝΟΜΕΝΟΙ ΑΛΓΟΡΙΘΜΟΙ ΛΥΝΟΥΝ ΤΟ ΠΡΟΒΛΗΜΑ ΤΟΥ ΒΕΛΤΙΣΤΟΥ ΓΡΑΜΜΙΚΟΥ ΧΡΟΝΟΠΡΟΓΡΑΜΜΑΤΙΣΜΟΥ ΓΙΑ ΟΙΚΟΓΕΝΕΙΕΣ ΑΛΓΟΡΙΘΜΩΝ. ΠΟΛΛΟΙ ΕΥΡΕΩΣ ΧΡΗΣΙΜΟΠΟΙΟΥΜΕΝΟΙ ΑΛΓΟΡΙΘΜΟΙ ΑΝΑΠΑΡΙΣΤΑΝΤΑΙ ΩΣ ΠΛΕΓΜΑΤΑ, ΠΟΥ ΕΙΝΑΙ ΕΙΔΙΚΗ ΠΕΡΙΠΤΩΣΗ ΦΩΛΙΑΣΜΕΝΩΝ ΒΡΟΓΧΩΝ ΜΕ ΟΜΟΙΟΜΟΡΦΕΣ ΕΞΑΡΤΗΣΕΙΣ. ΓΙΑ ΤΑ ΠΛΕΓΜΑΤΑ ΛΥΘΗΚΕ ΤΟ ΠΡΟΒΛΗΜΑ ΤΟΥ ΒΕΛΤΙΣΤΟΥ ΧΡΟΝΟΠΡΟΓΡΑΜΜΑΤΙΣΜΟΥ, ΧΩΡΙΣ ΚΑΙ ΜΕ ΚΟΣΤΟΣ ΕΠΙΚΟΙΝΩΝΙΑΣ, ΣΤΗ ΓΕΝΙΚΟΤΕΡΗ ΔΥΝΑΤΗ ΠΕΡΙΠΤΩΣΗ, ΜΕ ΤΗΝ ΕΥΡΕΣΗ ΚΛΕΙΣΤΟΥ ΤΥΠΟΥ ΠΟΥ ΔΙΝΕΙ ΤΟΝ ΕΛΑΧΙΣΤΟ ΑΡΙΘΜΟ ΕΠΕΞΕΡΓΑΣΤΩΝ ΠΟΥ ΑΠΑΙΤΟΥΝΤΑΙ ΓΙΑ ΤΗΝ ΕΠΙΤΕΥΞΗ ΤΟΥ ΒΕΛΤΙΣΤΟΥ ΠΑΡΑΛΛΗΛΟΥ ΧΡΟΝΟΥ.