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

Abstract

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

THIS DISSERTATION ADDRESSES THE PROBLEM OF MAPPING ALGORITHMS ONTO PROCESSOR ARRAYS AND NEW METHODS ARE DEVELOPED. THE PROPOSED TECHNIQUES CAN BE APPLIED TOALGORITHMS EXPRESSED IN THE FORM OF NESTED LOOPS. ALGORITHMS CHARACTERIZED BY CONSTANT DEPENDENCIES ARE STUDIED FIRST AND A METHODOLOGY BASED ON THE EXISTENCE OF INDEPENDENT GROUPS OF VARIABLES IN THE INDEX SPACE, IS PROPOSED. THE MAPPING OF THE DEPENDENCE GRAPH (DG) OF EACH GROUP IS ACCOMPLISHED, AFTER APPLICATION OF ORTHONORMALIZATION, BY USING A LINEAR TRANSFORM. THE NOTION OFTHE AUGMENTED DG (ADG) IS INTRODUCED FOR THE DISTINCTION BETWEEN VARIABLES WITH IDENTICAL INDICES IN A MULTIPLE STATEMENT LOOP. THE DESIGN OF FIXED-SIZE PROCESSOR ARRAYS IS ACHIEVED BY THE USE OF QUASI-LINEAR FUNCTIONS FOR THE ALLOCATION AND THE TIMING OF THE OPERATIONS WITHIN THE ARRAY. FINALLY, ALGORITHMS WITH NON-CONSTANT DEPENDENCIES ARE HANDLED AND THE CONCEPT OF SPACE-TIME REPRESENTATION IS INTRODUCED. FOR THE FIRST TIME, THE EVALUATION TIME OF EACH VARIABLE IS USED AS A COORDINATE IN THE DG AND THUS A SPACE-TIME DG (STDG) IS CONSTRUCTED. THE MAPPING OF THE STDG ONTO THE PROCESSOR ARRAY ARCHITECTURE IS ACHIEVED BY A LINEAR TRANSFORM. THIS METHOD AVOIDS THE NEED FOR FULLY INDEXING OF THE VARIABLES AND GUARANTEES THE EXISTENCE OF A LINEAR TRANSFORM SINCE OPPOSITE DEPENDENCE VECTORS DO NOT EXIST. ARRAYS DESIGNED USING THE PROPOSED TECHNIQUES EXHIBIT REDUCED COMPLEXITY OF THE PROCESSING ELEMENTSAND THE INTERCONNECTIONS AND REQUIRE LESS TIME FOR THE EXECUTION OF THE ALGORITHM.