ΑΠΕΙΚΟΝΙΣΗ ΦΩΛΙΑΣΜΕΝΩΝ ΒΡΟΧΩΝ ΣΕ ΑΡΧΙΤΕΚΤΟΝΙΚΕΣ ΠΑΡΑΛΛΗΛΗΣ ΕΠΕΞΕΡΓΑΣΙΑΣ

Abstract

Η ΔΙΑΤΡΙΒΗ ΑΥΤΗ ΑΣΧΟΛΕΙΤΑΙ ΜΕ ΤΟ ΠΡΟΒΛΗΜΑ ΤΗΣ ΒΕΛΤΙΣΤΗΣ ΑΠΕΙΚΟΝΙΣΗΣ ΕΝΟΣ ΠΟΛΥΔΙΑΣΤΑΤΟΥ ΦΩΛΙΑΣΜΕΝΟΥ ΒΡΟΧΟΥ ΣΕ ΔΙΑΦΟΡΕΣ ΑΡΧΙΤΕΚΤΟΝΙΚΕΣ ΠΑΡΑΛΛΗΛΗΣ ΕΠΕΞΕΡΓΑΣΙΑΣ, ΜΕ ΚΥΡΙΟ ΣΚΟΠΟ ΤΗΝ ΕΠΙΤΕΥΞΗ ΤΟΥ ΕΛΑΧΙΣΤΟΥ ΣΥΝΟΛΙΚΟΥ ΧΡΟΝΟΥ ΕΚΤΕΛΕΣΗΣ. ΟΙ ΦΩΛΙΑΣΜΕΝΟΙ ΒΡΟΧΟΙ ΠΟΥ ΕΞΕΤΑΖΟΝΤΑΙ ΣΤΟ ΠΛΑΙΣΙΟ ΤΗΣ ΔΙΑΤΡΙΒΗΣ, ΕΙΝΑΙ ΒΡΟΧΟΙ ΜΕ ΟΜΟΙΟΜΟΡΦΕΣ ΕΞΑΡΤΗΣΕΙΣ ΜΕΤΑΞΥ ΤΩΝ ΔΙΑΦΟΡΩΝ ΕΠΑΝΑΛΗΨΕΩΝ ΕΚΤΕΛΕΣΗΣ ΤΟΥΣ. ΑΥΤΟ ΣΗΜΑΙΝΕΙ ΟΤΙ ΤΑ ΔΙΑΝΥΣΜΑΤΑ ΤΩΝ ΕΞΑΡΤΗΣΕΩΝ ΕΙΝΑΙ ΣΤΑΘΕΡΑ, ΑΝΕΞΑΡΤΗΤΑ ΑΠΟ ΤΟΥΣ ΔΕΙΚΤΕΣΕΠΑΝΑΛΗΨΗΣ ΤΟΥ ΒΡΟΧΟΥ. ΟΙ ΠΑΡΑΛΛΗΛΕΣ ΑΡΧΙΤΕΚΤΟΝΙΚΕΣ ΠΟΥ ΕΞΕΤΑΖΟΝΤΑΙ ΣΤΗ ΔΙΑΤΡΙΒΗ, ΚΑΙ ΣΤΙΣ ΟΠΟΙΕΣ ΑΠΕΙΚΟΝΙΖΟΝΤΑΙ ΤΑ ΣΤΙΓΜΙΟΤΥΠΑ - ΕΠΑΝΑΛΗΨΕΙΣ ΕΚΤΕΛΕΣΗΣ ΤΟΥ ΒΡΟΧΟΥ, ΕΙΝΑΙ ΤΟΣΟ ΑΡΧΙΤΕΚΤΟΝΙΚΕΣ ΕΙΔΙΚΟΥ ΣΚΟΠΟΥ, ΟΠΩΣ ΣΥΣΤΟΛΙΚΕΣ ΔΙΑΤΑΞΕΙΣ, ΟΣΟ ΚΑΙ ΑΡΧΙΤΕΚΤΟΝΙΚΕΣ ΓΕΝΙΚΟΥ ΣΚΟΠΟΥ, ΟΠΩΣ ΜΗΧΑΝΕΣ MIMD ΜΟΙΡΑΖΟΜΕΝΗΣ ΚΑΙ ΚΑΤΑΝΕΜΗΜΕΝΗΣ ΜΝΗΜΗΣ. Η ΕΓΚΥΡΗ ΚΑΙ ΑΠΟΔΟΤΙΚΗ ΕΚΤΕΛΕΣΗ ΕΝΟΣ ΦΩΛΙΑΣΜΕΝΟΥ ΒΡΟΧΟΥ ΜΕ ΕΞΑΡΤΗΣΕΙΣ, ΕΚΜΕΤΑΛΛΕΥΕΤΑΙ ΤΟΥΣ ΔΙΑΘΕΣΙΜΟΥΣ ΥΠΟΛΟΓΙΣΤΙΚΟΥΣ ΠΟΡΟΥΣ ΤΗΣ ΕΚΑΣΤΟΤΕ ΑΡΧΙΤΕΚΤΟΝΙΚΗΣ (ΑΡΙΘΜΟΣ ΕΠΕΞΕΡΓΑΣΤΙΚΩΝ ΣΤΟΙΧΕΙΩΝ, ΤΟΠΟΛΟΓΙΑ ΔΙΚΤΥΟΥ ΔΙΑΣΥΝΔΕΣΗΣ ΚΛΠ.) ΔΙΑΤΗΡΩΝΤΑΣ ΤΗ ΣΩΣΤΗ ΣΕΙΡΑ ΕΚΤΕΛΕΣΗΣ. ΟΙ ΠΡΟΤΕΙΝΟΜΕΝΟΙ ΣΤΗ ΔΙΑΤΡΙΒΗ ΑΛΓΟΡΙΘΜΟΙ ΔΡΟΜΟΛΟΓΟΥΝ ΧΡΟΝΙΚΑ ΚΑΙ ΧΩΡΙΚΑ ΤΑ ΔΙΑΦΟΡΑ ΣΤΙΓΜΙΟΤΥΠΑ ΕΚΤΕΛΕΣΗΣ ΤΟΥ ΒΡΟΧΟΥ ΕΞΑΣΦΑΛΙΖΟΝΤΑΣ ΧΑΜΗΛΗ ΥΠΟΛΟΓΙΣΤΙΚΗ ΠΟΛΥΠΛΟΚΟΤΗΤΑ ΚΑΙ ΚΑΤΑ ΠΕΡΙΠΤΩΣΗ ΒΕΛΤΙΣΤΑ ΑΠΟΤΕΛΕΣΜΑΤΑ.

THIS THESIS IS CONCERNED WITH THE PROBLEM OF OPTIMAL MAPPING OF A MULTIDIMENSIONAL NESTED LOOP WITH LOOP - CARRIED DEPENDENCIES ONTO VARIOUS PARALLEL ARCHITECTURES, IN ORDER TO ACHIEVE THE MINIMUM OVERALL EXECUTION TIME. NESTED LOOPS WHICH ARE INVESTIGATED INTO THIS THESIS, ARE MAINLY LOOPS WITH UNIFORM LOOP- CARRIED DEPENDENCIES. THIS MEANS THAT THE DEPENDENCE VECTORS ARE CONSTANT,INDEPENDENT OF THE LOOP INDICES. THE PARALLEL ARCHITECTURES WHICH ARE EXAMINED THROUGHOUT THIS DISSERTATION AND WHERE THE LOOP INSTANCES ARE BEING MAPPED,CONSIST OF EITHER SPECIAL PURPOSE ARCHITECTURES, LIKE SYSTOLIC ARRAYS, OR GENERAL PURPOSE ONES, LIKE MIMD MACHINES WITH SHARED OR DISTRIBUTED MEMORY A VALID AND EFFICIENT EXECUTION OF A NESTED LOOP WITH LOOP - CARRIED DEPENDENCIES SHOULD EXPLOIT, AS BETTER AS POSSIBLE, THE AVAILABLE HARDWARE RESOURCES (NUMBER OF PROCESSING ELEMENTS, INTERCONNECTION NETWORK UTILIZATION), WHILE PRESERVING THE DEPENDENCE RELATIONS AMONG DIFFERENT ITERATIONS. IN EVERY CASE, THE IRREGULARITIES AND SPECIAL LIMITATIONS IMPOSED BY THE TARGET ARCHITECTURE ARE BEING CONSIDERED IN ORDER TO ACHIEVE THE OPTIMAL TIME AND SPACE SCHEDULE, WHILE THE PROPOSED METHOD HAS A LOW TIME COMPLEXITY.