MAPPING OF SOFTWARE STRUCTURES ONTO ALTERNATIVE ARRAY PROCESSOR ARCHITECTURES

 
Το τεκμήριο παρέχεται από τον φορέα :

Αποθετήριο :
Εθνικό Αρχείο Διδακτορικών Διατριβών
δείτε την πρωτότυπη σελίδα τεκμηρίου
στον ιστότοπο του αποθετηρίου του φορέα για περισσότερες πληροφορίες και για να δείτε όλα τα ψηφιακά αρχεία του τεκμηρίου*
κοινοποιήστε το τεκμήριο




1994 (EL)

ΑΠΕΙΚΟΝΙΣΗ ΔΟΜΩΝ ΛΟΓΙΣΜΙΚΟΥ ΣΕ ΕΝΑΛΛΑΚΤΙΚΕΣ ΑΡΧΙΤΕΚΤΟΝΙΚΕΣ ΔΙΑΤΑΞΕΩΝ ΕΠΕΞΕΡΓΑΣΤΩΝ
MAPPING OF SOFTWARE STRUCTURES ONTO ALTERNATIVE ARRAY PROCESSOR ARCHITECTURES

Κυριάκης-Μπιτζάρος, Ευστάθιος

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.
Η ΔΙΑΤΡΙΒΗ ΠΡΑΓΜΑΤΕΥΕΤΑΙ ΤΟ ΠΡΟΒΛΗΜΑ ΤΗΣ ΑΠΕΙΚΟΝΙΣΗΣ ΑΛΓΟΡΙΘΜΩΝ ΣΕ ΔΙΑΤΑΞΕΙΣ ΕΠΕΞΕΡΓΑΣΤΩΝ ΚΑΙ ΠΡΟΤΕΙΝΟΝΤΑΙ ΝΕΕΣ ΤΕΧΝΙΚΕΣ ΓΙΑ ΤΗΝ ΑΝΤΙΜΕΤΩΠΙΣΗ ΤΟΥ. ΟΙ ΠΡΟΤΕΙΝΟΜΕΝΕΣ ΜΕΘΟΔΟΙ ΕΦΑΡΜΟΖΟΝΤΑΙ ΣΕ ΑΛΓΟΡΙΘΜΟΥΣ ΕΚΦΡΑΣΜΕΝΟΥΣ ΜΕ ΤΗ ΜΟΡΦΗ ΒΡΟΧΩΝ.ΑΡΧΙΚΑ, ΜΕΛΕΤΩΝΤΑΙ ΑΛΓΟΡΙΘΜΟΙ ΜΕ ΣΤΑΘΕΡΕΣ ΕΞΑΡΤΗΣΕΙΣ ΚΑΙ ΑΝΑΠΤΥΣΣΕΤΑΙ ΜΕΘΟΔΟΣ ΠΟΥ ΒΑΣΙΖΕΤΑΙ ΣΤΗΝ ΥΠΑΡΞΗ ΑΝΕΞΑΡΤΗΤΩΝ ΟΜΑΔΩΝ ΜΕΤΑΒΛΗΤΩΝ ΣΤΟ ΧΩΡΟ ΤΩΝ ΔΕΙΚΤΩΝ. Η ΑΠΕΙΚΟΝΙΣΗ ΤΟΥ ΓΡΑΦΗΜΑΤΟΣ ΕΞΑΡΤΗΣΕΩΝ ΚΑΘΕ ΟΜΑΔΑΣ ΓΙΝΕΤΑΙ, ΜΕΤΑ ΑΠΟ ΚΑΝΟΝΙΚΟΠΟΙΗΣΗ, ΜΕ ΧΡΗΣΗ ΓΡΑΜΜΙΚΟΥ ΜΕΤΑΣΧΗΜΑΤΙΣΜΟΥ. ΕΠΙΣΗΣ, ΕΙΣΑΓΕΤΑΙ Η ΕΝΝΟΙΑ ΤΟΥ ΕΠΑΥΞΗΜΕΝΟΥ ΓΕ ΓΙΑ ΤΟ ΔΙΑΧΩΡΙΣΜΟ ΜΕΤΑΒΛΗΤΩΝ ΜΕ ΤΟΥΣ ΙΔΙΟΥΣ ΔΕΙΚΤΕΣ ΣΕ ΑΛΓΟΡΙΘΜΟΥΣ ΜΕ ΠΟΛΛΕΣ ΠΡΟΤΑΣΕΙΣ. ΤΟ ΠΡΟΒΛΗΜΑ ΤΟΥ ΣΧΕΔΙΑΣΜΟΥ ΔΙΑΤΑΞΕΩΝ ΜΕ ΚΑΘΟΡΙΣΜΕΝΟ ΜΕΓΕΘΟΣ ΑΝΤΙΜΕΤΩΠΙΖΕΤΑΙ ΜΕ ΤΗ ΧΡΗΣΗ ΣΧΕΔΟΝ ΓΡΑΜΜΙΚΩΝ ΣΥΝΑΡΤΗΣΕΩΝ ΤΟΠΟΘΕΤΗΣΗΣ ΚΑΙ ΧΡΟΝΙΣΜΟΥ ΤΩΝ ΠΡΑΞΕΩΝ ΣΤΗ ΔΙΑΤΑΞΗ. ΤΟ ΠΡΟΒΛΗΜΑ ΤΩΝ ΑΛΓΟΡΙΘΜΩΝ ΜΕ ΜΗ ΣΤΑΘΕΡΕΣ ΕΞΑΡΤΗΣΕΙΣ ΑΝΤΙΜΕΤΩΠΙΖΕΤΑΙ ΜΕ ΤΗΝ ΕΙΣΑΓΩΓΗ ΤΗΣ ΕΝΝΟΙΑΣ ΤΗΣ ΧΩΡΟΧΡΟΝΙΚΗΣ ΑΝΑΠΑΡΑΣΤΑΣΗΣ ΤΩΝ ΑΛΓΟΡΙΘΜΩΝ. ΓΙΑ ΠΡΩΤΗ ΦΟΡΑ ΠΡΟΤΕΙΝΕΤΑΙ Η ΧΡΗΣΗ ΤΟΥ ΧΡΟΝΟΥ ΩΣ ΜΙΑΣ ΕΠΙΠΛΕΟΝ ΣΥΝΤΕΤΑΓΜΕΝΗΣ ΣΤΟ ΓΕ ΤΟΥ ΑΛΓΟΡΙΘΜΟΥ ΚΑΙ Η ΚΑΤΑΣΚΕΥΗ ΕΝΟΣ ΧΩΡΟΧΡΟΝΙΚΟΥ ΓΕ (ΧΧΓΕ). Η ΑΠΕΙΚΟΝΙΣΗ ΤΟΥ ΧΧΓΕ ΣΤΗΝ ΕΠΙΘΥΜΗΤΗ ΔΙΑΤΑΞΗ ΕΠΙΤΥΓΧΑΝΕΤΑΙ ΜΕ ΓΡΑΜΜΙΚΟ ΜΕΤΑΣΧΗΜΑΤΙΣΜΟ. Η ΜΕΘΟΔΟΛΟΓΙΑ ΑΥΤΗ ΑΠΟΦΕΥΓΕΙ ΤΟ ΣΤΑΔΙΟ ΤΗΣ ΠΛΗΡΟΥΣ ΔΕΙΚΤΟΔΟΤΗΣΗΣ ΤΩΝ ΜΕΤΑΒΛΗΤΩΝ ΚΑΙ ΕΓΓΥΑΤΑΙ ΤΗΝ ΥΠΑΡΞΗ ΤΟΥ ΓΡΑΜΜΙΚΟΥ ΜΕΤΑΣΧΗΜΑΤΙΣΜΟΥ ΓΙΑΤΙ ΔΕΝ ΥΠΑΡΧΟΥΝ ΕΞΑΡΤΗΣΕΙΣ ΜΕ ΑΝΤΙΘΕΤΗ ΦΟΡΑ. ΟΙ ΔΙΑΤΑΞΕΙΣ ΠΟΥ ΣΧΕΔΙΑΖΟΝΤΑΙ, ΠΑΡΟΥΣΙΑΖΟΥΝ ΜΙΚΡΟΤΕΡΟ ΧΡΟΝΟ ΕΚΤΕΛΕΣΗΣ ΤΟΥ ΑΛΓΟΡΙΘΜΟΥ ΚΑΙΜΕΙΩΜΕΝΗ ΠΟΛΥΠΛΟΚΟΤΗΤΑ ΣΤΗ ΔΟΜΗ ΤΩΝ ΕΠΕΞΕΡΓΑΣΤΩΝ ΚΑΙ ΣΤΙΣ ΔΙΑΣΥΝΔΕΣΕΙΣ.

PhD Thesis

ΑΝΕΞΑΡΤΗΤΕΣ ΟΜΑΔΕΣ ΜΕΤΑΒΛΗΤΩΝ
ΔΙΑΤΑΞΕΙΣ ΚΑΘΟΡΙΣΜΕΝΟΥ ΜΕΓΕΘΟΥΣ
Επιστήμη Ηλεκτρολόγου Μηχανικού, Ηλεκτρονικού Μηχανικού, Μηχανικού Η/Υ
Electrical Engineering, Electronic Engineering, Information Engineering
ΣΧΕΔΟΝ ΓΡΑΜΜΙΚΟΣ ΜΕΤΑΣΧΗΜΑΤΙΣΜΟΣ
SPACE TIMEDEPENDENCE GRAPH
ΧΩΡΟΧΡΟΝΙΚΟ ΓΡΑΦΗΜΑ ΕΞΑΡΤΗΣΕΩΝ
INDEPENDENT GROUP OF VARIABLES
Επιστήμες Μηχανικού και Τεχνολογία
NESTED-LOOPALGORITHMS
Engineering and Technology
INDEX SPACE
ΑΛΓΟΡΙΘΜΟΙ ΜΕ ΜΟΡΦΗ ΒΡΟΧΩΝ
ΓΡΑΜΜΙΚΟΣ ΜΕΤΑΣΧΗΜΑΤΙΣΜΟΣ
LINEAR TRANSFORMATION
ΧΩΡΟΣ ΔΕΙΚΤΩΝ
Κανονικές διατάξεις επεξεργαστών
FIXED-SIZE ARRAYS
Regular processor arrays
QUASI-LINEAR TRANSFORMATION


Ελληνική γλώσσα

1994


Πανεπιστήμιο Πατρών
University of Patras




*Η εύρυθμη και αδιάλειπτη λειτουργία των διαδικτυακών διευθύνσεων των συλλογών (ψηφιακό αρχείο, καρτέλα τεκμηρίου στο αποθετήριο) είναι αποκλειστική ευθύνη των αντίστοιχων Φορέων περιεχομένου.