Σκοπός της διπλωματικής εργασίας είναι η ανάπτυξη εργαλείου το οποίο θα δέχεται ως είσοδο C πρόγραμμα και θα βρίσκει όλη τη πληροφορία η οποία σχετίζεται με την επαναχρησιμοποίηση των δεδομένων. Τα δεδομένα αφορούν πίνακες μέσα σε βρόχους. Η επαναχρησιμοποίηση δεδομένων χωρίζεται σε τρεις κατηγορίες: α) Εύρεση της επαναχρησιμοποίησης για κάθε πίνακα ξεχωριστά. β) Εύρεση της επαναχρησιμοποίησης στοιχείων πίνακα που χρησιμοποιούνται σε διάφορες εκφράσεις. γ) Εύρεση χρήσης στοιχείων μεταξύ διαφορετικών πινάκων στην ίδια έκφραση. Η εύρεση των χαρακτηριστικών της επαναχρησιμοποίησης χρησιμεύει για την εύρεση αποδοτικού χρονοπρογραμματισμού (scheduling) του προγράμματος το οποίο θα έχει καλύτερη τοπικότητα (data locality). Η επαναχρησιμοποίηση δεδομένων εφαρμόζεται στο πρόβλημα πολλαπλασιασμού πίνακα επί διάνυσμα. Συμβατικές και μη τεχνικές υλοποίησης του προβλήματος έχουν συγκριθεί με τη προτεινόμενη. Η σύγκριση πραγματοποιήθηκε με τον εξομοιωτή SimpleScalar στον οποίο μπορούμε να τροποποιήσουμε την αρχιτεκτονική και σε υπολογιστή Desktop Pentium 4. / -

Οι υπάρχοντες μεταγλωττιστές, έχουν τρία βασικά μειονεκτήματα i) όλα τα υπό-προβλήματα της μεταγλώττισης (π.χ. μετασχηματισμοί, εύρεση χρονοπρογραμματισμού, ανάθεση καταχωρητών) βελτιστοποιούνται ξεχωριστά (εκτός από μεμονωμένες περιπτώσεις όπου βελτιστοποιούνται κάποια στάδια μαζί - συνήθως 2), παρόλο που υπάρχει εξάρτηση μεταξύ τους, ii) δεν εκμεταλλεύονται αποδοτικά όλα τα χαρακτηριστικά του προγράμματος εισόδου (π.χ. δομή του εκάστοτε αλγορίθμου, επαναχρησιμοποίηση δεδομένων), iii) δεν εκμεταλλεύονται αποδοτικά τις παραμέτρους της αρχιτεκτονικής. Στη παρούσα διδακτορική διατριβή, αναπτύχθηκαν μεθοδολογίες οι οποίες αντιμετωπίζουν τα προβλήματα εύρεσης χρονοπρογραμματισμών με τον ελάχιστο αριθμό i) προσβάσεων στην κρυφή μνήμη δεδομένων L1, ii) προσβάσεων στην κρυφή μνήμη L2, iii) προσβάσεων στην κύρια μνήμη, iv) πράξεων διευθυνσιοδότησης, μαζί σαν ενιαίο πρόβλημα και όχι ξεχωριστά, για ένα kernel. Αυτό επιτυγχάνεται αντιμετωπίζοντας τα χαρακτηριστικά του λογισμικού και τις τις βασικές παραμέτρους της αρχιτεκτονικής μαζί σαν ενιαίο πρόβλημα. Είναι η πρώτη φορά που μια μεθοδολογία αντιμετωπίζει τα παραπάνω προβλήματα με αυτό τον τρόπο. Οι προτεινόμενες μεθοδολογίες εκμεταλλεύονται τα χαρακτηριστικά του προγράμματος εισόδου. Η δομή του εκάστοτε αλγορίθμου (π.χ. ο FFT αποτελείται από πράξεις πεταλούδων ενώ ο αλγόριθμος αφαίρεσης θορύβου - Gauss Blur αποτελείται από πράξεις μάσκας στοιχείων), τα ιδιαίτερα χαρακτηριστικά του (π.χ. συμμετρία Toeplitz πίνακα), η ύπαρξη προτύπων-patterns (π.χ. στοιχεία πινάκων πολλαπλασιάζονται με μάσκα), η επαναχρησιμοποίηση των δεδομένων, η παραγωγή-κατανάλωση ενδιάμεσων αποτελεσμάτων και η παραλληλία του αλγορίθμου, αντιμετωπίζονται μαζί σαν ενιαίο πρόβλημα. Οι προτεινόμενες μεθοδολογίες εκμεταλλεύονται τις βασικές παραμέτρους της αρχιτεκτονικής. Η αρχιτεκτονική της μνήμης (π.χ. κοινή L2, L3), το πλήθος των καταχωρητών, ο αριθμός των κρυφών μνημών δεδομένων, τα μεγέθη, οι συσχετιστικότητες (assosiativity) και τα μεγέθη των γραμμών των κρυφών μνημών, ο αριθμός των λειτουργικών μονάδων, ο αριθμός των λειτουργικών μονάδων που λειτουργούν παράλληλα και ο αριθμός των πυρήνων (cores) του επεξεργαστή, αντιμετωπίζονται μαζί σαν ενιαίο πρόβλημα. Με την αξιοποίηση των χαρακτηριστικών του εκάστοτε αλγορίθμου και των παραμέτρων της αρχιτεκτονικής, αποκλείονται πιθανές λύσεις και ο χώρος εξερεύνησης μειώνεται ραγδαία (τάξεις μεγέθους). Στη παρούσα διδακτορική διατριβή, αναπτύχθηκαν μεθοδολογίες αύξησης της ταχύτητας του λογισμικού α) του Πολλαπλασιασμού Πίνακα επί Πίνακα (ΠΠΠ), β) του Πολλαπλασιασμού Πίνακα επί διάνυσμα (ΠΠΔ), γ) του Fast Fourier Transform (FFT), δ) του αλγορίθμου Canny και του μετασχηματισμού του Hough (αλγόριθμοι ανίχνευσης ακμών και ευθειών αντίστοιχα). Επίσης, αναπτύχθηκε μεθοδολογία μεταγλώττισης η οποία εκμεταλλεύεται τα χαρακτηριστικά του λογισμικού και τις παραμέτρους της ιεραρχίας μνήμης. Η μεθοδολογία μπορεί να εφαρμοστεί σε πυρήνες λογισμικού, στους οποίους α) τα μονοπάτια εκτέλεσης είναι γνωστά κατά τη μεταγλώττιση και συνεπώς δεν εξαρτώνται από τα δεδομένα, β) οι δείκτες όλων των sub- scripts να είναι γραμμικές εξισώσεις των iterators (που ισχύει στις περισσότερες περιπτώσεις). Οι μεθοδολογίες αφορούν ενσωματωμένους και γενικού σκοπού επεξεργαστές (χρήση μονάδας SIMD για περαιτέρω αύξηση της ταχύτητας). Ακολουθεί σύντομη περίληψη αυτών. Μεθοδολογία αύξησης της ταχύτητας του Πολλαπλασιασμού Πίνακα επί Πίνακα (ΠΠΠ): Αναπτύχθηκε μεθοδολογία αύξησης της ταχύτητας του ΠΠΠ για α) μονοπύρηνους επεξεργαστές (1 core), β) επεξεργαστές με πολλούς πυρήνες οι οποίοι συνδέονται με κοινή μνήμη. Η προτεινόμενη μεθοδολογία χωρίζει του πίνακες του αλγορίθμου σε μικρότερους οι οποίοι χωράνε στις κρυφές μνήμες και στο αρχείο καταχωρητών. Είναι η πρώτη φορά για τον ΠΠΠ που εισάγονται εξισώσεις οι οποίες αξιοποιούν τα associativities των κρυφών μνημών. Για τη πλήρη αξιοποίηση της ιεραρχίας της μνήμης προτείνεται νέος τρόπος αποθήκευσης των στοιχείων στη κύρια μνήμη (data array layout). Επίσης, προτείνεται διαφορετικός χρονοπρογραμματισμός σε επίπεδο στοιχείων και σε επίπεδο υπό-πινάκων. Η προτεινόμενη μεθοδολογία επιτυγχάνει από 1.1 έως 3.5 φορές μικρότερο χρόνο εκτέλεσης από τη βιβλιοθήκη του ATLAS, η οποία αποτελεί μια από τις ταχύτερες βιβλιοθήκες. Μεθοδολογία αύξησης της ταχύτητας του Fast Fourier Transform (FFT): Αναπτύχθηκε μεθοδολογία αύξησης της ταχύτητας του FFT αξιοποιώντας πλήρως τα ιδιαίτερα χαρακτηριστικά του αλγορίθμου και τις παραμέτρους της ιεραρχίας της μνήμης. Το διάγραμμα ροής δεδομένων (Data Flow Graph – DFG) του FFT, χωρίζεται σε πρότυπα (patterns) και σε υπό- FFTs. Κάθε πρότυπο, αποτελείται από πεταλούδες, σύμφωνα με το πλήθος των καταχωρητών του επεξεργαστή. Η επιλογή των πεταλούδων κάθε προτύπου έχει γίνει με τέτοιο τρόπο ώστε να μεγιστοποιείται η παραγωγή-κατανάλωση των ενδιάμεσων αποτελεσμάτων. Η σειρά εκτέλεσης των προτύπων είναι αυτή η οποία δίνει τη μέγιστη επαναχρησιμοποίηση των συντελεστών του FFT. Ο DFG του FFT χωρίζεται σε υπό-FFTs σύμφωνα με τον αριθμό και τα μεγέθη των κρυφών μνημών δεδομένων. Η προτεινόμενη μεθοδολογία δίνει από 1.1 μέχρι 1.8 φορές μικρότερο χρόνο εκτέλεσης από τη βιβλιοθήκη του FFTW, η οποία παρέχει ταχύτατο χρόνο εκτέλεσης. Είναι η πρώτη φορά για τον FFT που μια μεθοδολογία λαμβάνει υπόψη τις παραμέτρους της ιεραρχίας μνήμης και του αρχείου καταχωρητών. Μεθοδολογία αύξησης της ταχύτητας του Πολλαπλασιασμού Πίνακα επί Διάνυσμα (ΠΠΔ) για Toeplitz, Bisymetric (BT), Toeplitz (Τ) και κανονικούς πίνακες: Αναπτύχθηκε μεθοδολογία αύξησης της ταχύτητας του ΠΠΔ. Οι παραπάνω πίνακες έχουν ιδιαίτερη δομή, μικρό αριθμό διαφορετικών στοιχείων και μεγάλη επαναχρησιμοποίηση, χαρακτηριστικά τα οποία αξιοποιούνται πλήρως. Η προτεινόμενη μεθοδολογία χωρίζει τους πίνακες του αλγορίθμου σε μικρότερους οι οποίοι χωράνε στις κρυφές μνήμες και στο αρχείο καταχωρητών σύμφωνα με τον αριθμό τα μεγέθη και τα associativities των κρυφών μνημών. Για τη πλήρη αξιοποίηση της ιεραρχίας μνήμης προτείνεται νέος τρόπος αποθήκευσης των στοιχείων του πίνακα (data array layout) στη κύρια μνήμη. Η προτεινόμενη μεθοδολογία χρησιμοποιεί τον κανονικό αλγόριθμο ΠΠΔ (γραμμή επί στήλη). Ωστόσο, για BT και T πίνακες, ο ΠΠΔ μπορεί να υλοποιηθεί με χρήση του FFT επιτυγχάνοντας μικρότερη πολυπλοκότητα για μεγάλα μεγέθη πινάκων (έγινε ανάλυση και σύγκριση των δύο αλγορίθμων θεωρητικά και πειραματικά). Η προτεινόμενη μεθοδολογία για κανονικούς πίνακες συγκρίνεται με τη βιβλιοθήκη του ATLAS, επιτυγχάνοντας από 1.2 μέχρι 4.4 φορές μικρότερο χρόνο εκτέλεσης. Μεθοδολογία αύξησης της ταχύτητας του αλγόριθμου ανίχνευσης ακμών και ευθειών (αλγόριθμος του Canny και μετασχηματισμός του Hough): Αναπτύχθηκε μεθοδολογία η οποία επιτυγχάνει i) μικρότερο αριθμό εντολών ανάγνωσης/εγγραφής και διευθυνσιοδότησης, ii) μικρότερο αριθμό προσβάσεων και αστοχιών στην ιεραρχία μνήμης και iii) μικρότερο μέγεθος απαιτούμενης μνήμης του αλγορίθμου, εν συγκρίσει με την βιβλιοθήκη OpenCV η οποία παρέχει ταχύτατο χρόνο εκτέλεσης στους αλγορίθμους επεξεργασίας εικόνων. Τα παραπάνω επιτυγχάνονται: α) αξιοποιώντας την παραγωγή-κατανάλωση των στοιχείων των πινάκων και την παραλληλία του αλγορίθμου - τα τέσσερα kernels του Canny συγχωνεύονται σε ένα, διασωληνώνοντας (pipelining) τους πυρήνες για να διατηρηθούν οι εξαρτήσεις των δεδομένων, β) μειώνοντας τον αριθμό και το μέγεθος των πινάκων, γ) γράφοντας τα δεδομένα σε νέους μειωμένων διαστάσεων πίνακες με κυκλικό τρόπο, δ) χωρίζοντας τους πίνακες σε μικρότερους οι οποίοι χωράνε στο αρχείο καταχωρητών και στη κρυφή μνήμη δεδομένων σύμφωνα με το μέγεθος των κρυφών μνημών και του associativity, ε) βρίσκοντας τον βέλτιστο τρόπο αποθήκευσης των πινάκων (data array layout) στην κύρια μνήμη σύμφωνα με τη συσχετιστικότητα (associativity) της κρυφής μνήμης. Η προτεινόμενη μεθοδολογία δίνει από 1.27 μέχρι 2.2 φορές μικρότερο χρόνο εκτέλεσης από τη βιβλιοθήκη OpenCV (αναπτύχθηκε από την Intel και είναι γραμμένη σε χαμηλό επίπεδο), η οποία παρέχει ταχύτατο χρόνο εκτέλεσης. Μεθοδολογία μεταγλώττισης: Αναπτύχθηκε μεθοδολογία μεταγλώττισης η οποία αντιμετωπίζει τα προβλήματα εύρεσης χρονοπρογραμματισμών με τον ελάχιστο αριθμό i) προσβάσεων στην κρυφή μνήμη δεδομένων L1, ii) προσβάσεων στην κρυφή μνήμη L2, iii) προσβάσεων στην κύρια μνήμη, iv) πράξεων διευθυνσιοδότησης, μαζί σαν ενιαίο πρόβλημα και όχι ξεχωριστά, για ένα kernel. Η προτεινόμενη μεθοδολογία λαμβάνει ως είσοδο ker- nels σε C-κώδικα και παράγει νέα επιτυγχάνοντας είτε υψηλή απόδοση είτε τον ελάχιστο αριθμό προσβάσεων σε δεδομένη μνήμη. Αρχικά βρίσκεται ο χώρος εξερεύνησης με βάση τα χαρακτηριστικά του λογισμικού. Ο χώρος εξερεύνησης περιγράφεται από μαθηματικές εξισώσεις και ανισότητες οι οποίες προέρχονται από τα subscripts των πινάκων, τους iterators, τα όρια των βρόχων και τις εξαρτήσεις των δεδομένων. Αυτός ο χώρος εξερεύνησης δεν μπορεί να παραχθεί με την εφαρμογή υπαρχόντων μετασχηματισμών στον αρχικό C-κώδικα. Κατόπιν, ο χώρος εξερεύνησης μειώνεται τάξεις μεγέθους εφαρμόζοντας διάδοση περιορισμών (constraint propagation) των παραμέτρων του λογισμικού και αυτών της αρχιτεκτονικής της μνήμης. Το αρχείο καταχωρητών (register file) και τα μεγέθη των κρυφών μνημών αξιοποιούνται πλήρως παράγοντας ανισότητες για κάθε μνήμη οι οποίες περιέχουν α) τα μεγέθη των tiles που απαιτούνται για κάθε πίνακα, β) το σχήμα κάθε tile. Επίσης, βρίσκεται ο βέλτιστος τρόπος αποθήκευσης των στοιχείων των πινάκων στη κύρια μνήμη, σύμφωνα με τη συσχετιστικότητα (associativity) των κρυφών μνημών. Η προτεινόμενη μεθοδολογία εφαρμόστηκε σε 5 ευρέως διαδεδομένους αλγορίθμους και επιτυγχάνει αύξηση της ταχύτητας (speedup) από 2 έως 18 φορές (έγινε σύγκριση του αρχικού C κώδικα και του C κώδικα έπειτα από την εφαρμογή της προτεινόμενης μεθοδολογίας – η μεταγλώττιση έγινε με τον gcc compiler). / The existing state of the art (SOA) compilers, have 3 major disadvantages. Firstly, the back-end compiler phases - subproblems (e.g. transformations, scheduling, register allocation) are optimized separately; these subproblems depend on each other and they should be optimized together as one problem and not separately. Secondly, the existing SOA compilers do not effectively utilize the software characteristics (e.g. algorithm structure, data reuse). Thirdly, they do not effectively utilize the hardware parameters. In this PhD dissertation, new methodologies have been developed speeding up software kernels, by solving the sub-problems of finding the schedules with the minimum numbers of i) L1 data cache accesses, ii) L2 data cache accesses, iii) main memory accesses and iv) addressing instructions, as one problem and not separately. This is achieved by fully exploiting the software information and the memory hierarchy parameters. This is the first time a methodology optimizes the above sub-problems in this way. The proposed methodologies fully utilize the software characteristics. The algorithm structure (e.g. FFT data flow graph consists of butterfly operations while the gauss blur algorithm consists of array mask operations), the algorithm individual characteristics (e.g. symmetry of Toeplitz matrix), the data patterns (e.g. matrix elements are multiplied by a mask), data reuse, production-consumption of intermediate results and algorithm's parallelism, are utilized as one problem and not separately. The proposed methodologies fully utilize the major architecture parameters. The memory archi- tecture (e.g. shared L2/L3 cache), the size of the register file, the number of the levels of data cache hierarchy, the data cache sizes, the data cache associativities, the data cache line sizes, the number of the function units, the number of the function units can run in parallel and the number of the CPU cores are utilized as one problem and not separately. By utilizing the hardware and software constraints the exploration space is orders of magnitude decreased. In this PhD dissertation, new speeding-up methodologies are developed for i) Matrix Matrix Multi- plication (MMM) algorithm, ii) Matrix Vector Multiplication (MVM) algorithm, iii) Fast Fourier Trans- form (FFT), iv) Canny algorithm and Hough Transform. Also, a new compilation methodology which fully exploits the memory architecture and the software characteristics, is developed. This methodology can be applied in software kernels whose i) execution paths are known at compile time and thus they do not depend on the data, ii) all array subscripts are linear equations of the iterators (which in most cases do). The above methodologies refer to both embedded and general purpose processors (usage of the SIMD technology). The summary of the above methodologies is given below. A Methodology for speeding-up Matrix Matrix Multiplication (MMM) algorithm: A new methodol- ogy for Matrix Matrix Multiplication using SIMD (Single Instruction Multiple Data) unit and not, at one and more cores having a shared cache, is presented. The proposed methodology partitions the MMM matrices into smaller sub-matrices fitting in the data cache memories and into register file according to the memory hierarchy architecture parameters. This is the first time for MMM algorithm that equations containing the data cache associativity values, are given. To fully utilize the memory hierarchy, a new the data array layout is proposed. The proposed methodology is from 1.1 up to 3.5 times faster than one of the SOA software libraries for linear algebra, ATLAS. A Fast Fourier Transform (FFT) speeding-up methodology: A new Fast Fourier Transform method- ology is presented which fully utilizes the individual algorithm characteristics and the memory hierarchy architecture parameters. FFT data flow graph (DFG) is partitioned into patterns and into sub-FFTs. Each pattern consists of butterflies according to the number of the registers. The selection of the exact butter- flies each pattern contains, has been made by maximizing the production-consumption of the butterflies intermediate results. Also, the patterns are executed in that order, minimizing the data reuse of the FFT twiddle factors. The FFT data flow graph is partitioned into sub-FFTs according to the number of the levels and the sizes of data cache. The proposed methodology is faster from 1.1 up to 1.8 times in con- trast to the SOA FFT library, FFTW. This is the first time that an FFT methodology fully utilizes the memory hierarchy architecture parameters. A methodology for speeding-up Matrix Vector Multiplication (MVM) algorithm for regular, Toeplitz and Bisymmetric Toeplitz matrices: A new methodology for MVM including different types of matrices, is presented. The above matrices have a special structure, a small number of different elements and large data reuse. The proposed methodology partitions the MVM matrices into smaller sub-matrices fitting in the data cache memories and into register file according to the memory hierarchy architecture parameters. To fully utilize the memory hierarchy, a new data array layout is proposed. The proposed methodology uses the standard algorithm for matrix vector multiplication, i.e. each row of A is multiplied by X. However, for Bisymmetric Toeplitz (BT) and Toeplitz (T) matrices, MVM can also be implemented by using FFT; although in this paper we use the standard MVM algorithm, we show that for large input sizes, the MVM using FFT performs much better. The proposed methodology achieves speedup from 1.2 up to 4.4 over the SOA libraries, ATLAS. A Methodology for Speeding Up Edge and Line Detection Algorithms: A new Methodology for Speeding Up Edge and Line Detection Algorithms focusing on memory architecture utilization is pre- sented. This methodology achieves i) a smaller number of load/store and arithmetic instructions, ii) a smaller number of data cache accesses and data cache misses in memory hierarchy and iii) a smaller algorithm memory size, in contrast to the SOA library of OpenCV. This is achieved by: i) utilizing the production-consumption of intermediate results - merging all Canny kernels to one and pipelining the kernels to comply with the data dependences, ii) reducing the number and the size of the arrays, iii) writing the data into the new reduced size arrays in a circular way, iv) applying loop tiling for the register file and data cache, according to the size of the memories and associativity and v) finding the data arrays layout according to the data cache associativity. The proposed methodology achieves speedup from 1.27 up to 2.2 over the OpenCV SOA library. Compilation methodology: A new compilation methodology which fully exploits the memory archi- tecture and the software characteristics is presented. This is the first time that a methodology optimizes the subproblems explained above as one problem and not separately, for a loop-kernel. The proposed methodology takes as input C-code kernels and it produces new software kernels with a new iteration space, which may not be given by applying existing compiler transformations to original code. Firstly, the exploration space is found according to the s/w characteristics; it is described by mathematical equations and inequalities that are derived from the array subscripts, the combination of common array references, loop iterators, loop bounds and data dependences. Then, the exploration space is orders of magnitude decreased by applying constraint propagation of the h/w and s/w parameters. The register file and the data cache sizes are fully exploited by producing register file and data cache inequalities which contain i) the tiles sizes of each array, ii) the shape of each array tile. Also, new data array layouts are found, according to the data cache associativity. The final schedule is found by choosing the best combination of the number of i) L1 data cache accesses, ii) L2 data cache accesses, iii) main memory data accesses and iv) addressing instructions. The proposed methodology is evaluated to five well-known algorithms and speedups from 2 up to 18 over the target gcc compiler are obtained.

Τις τελευταίες δεκαετίες παρατηρείται ραγδαία εξέλιξη των τεχνολογιών πληροφορικής και επικοινωνιών, ενώ συγχρόνως η διάθεση εκπαιδευτικού υλικού μέσω συστημάτων ηλεκτρονικής μάθησης αυξάνεται συνεχώς. Τα μαθησιακά αντικείμενα (ΜΑ) αποτελούν ένα νέο τρόπο προσέγγισης της οργάνωσης του εκπαιδευτικού περιεχομένου και βρίσκονται στον πυρήνα του νέου διδακτικού σχεδιασμού (Νικολόπουλος, Πιερρακέας, & Καμέας, 2011), αποτελώντας τη βάση για τη δημιουργία και το χειρισμό ψηφιακού εκπαιδευτικού περιεχομένου στην τεχνολογικά ενισχυμένη μάθηση (Sampson, & Zervas, 2011). Έχοντας μια σχετικά σύντομη ζωή στο χώρο της ηλεκτρονικής μάθησης, έχουν γίνει σήμερα ο επικρατέστερος ανάμεσα σε διάφορους άλλους όρους οι οποίοι προσπαθούν να περιγράψουν την ποικιλία των διαθέσιμων ψηφιακών πόρων που μπορούν να αξιοποιηθούν στην εκπαιδευτική διαδικασία (Βορβυλάς, 2013). Ο στόχος της συγκεκριμένης εργασίας είναι η μελέτη των ΜΑ, η αναλυτική περιγραφή των διαδικασιών επαναχρησιμοποίησης ΜΑ και η αξιολόγηση, μέσω χρήσης κατάλληλων μετρικών, του κόστους της επαναχρησιμοποίησης για τη δημιουργία μαθημάτων, ενοτήτων και προγραμμάτων σπουδών. Γνωστά στη διεθνή βιβλιογραφία ως αντικείμενα επικοινωνίας (Norton 1996), εκπαιδευτικά αντικείμενα (Friesen, 1996), επαναχρησιμοποιήσιμα αντικείμενα μάθησης (Barritt, Lewis and Wieseler 1999), γνωστικά αντικείμενα (Merrill, 1998), αντικείμενα πληροφοριών (Gibbons, Nelson, & Richards, 2000), διδακτικές μονάδες (Koper, 2001) κ.ά., τα ΜΑ έχουν εμφανισθεί τις δύο τελευταίες δεκαετίες και αποτελούν τη βάση για τη δημιουργία και το χειρισμό εκπαιδευτικού ψηφιακού περιεχομένου για τις ανάγκες της εκπαίδευσης, της μάθησης και της εξάσκησης των μαθητών. Ορισμοί έχουν δοθεί για τα ΜΑ, όπως για παράδειγμα από τον J. L’Allier (1997), το Institute of Electrical and Electronics Engineers (2000), τον David A. Wiley (2002), τους Rehak & Mason (2003), τον Polsani (2003), τον Andres Chiappe (2007), κ.ά. Παρόλα αυτά, οι προσπάθειες για την ανάπτυξη ή αποδοχή ενός κοινού εννοιολογικού ορισμού για τα ΜΑ από την εκπαιδευτική κοινότητα και τους εμπλεκόμενους φορείς, δεν έχουν καρποφορήσει. Εντούτοις, έχουν γίνει κοινά αποδεκτά κάποια λειτουργικά χαρακτηριστικά των ΜΑ, τα οποία σύμφωνα με τον Polsani (2003) είναι: • Προσβασιμότητα (Accessibility) • Επαναχρησιμοποίηση (Reusability) • Διαλειτουργικότητα (Interoperability) Ποικίλες θεωρήσεις κυριαρχούν αναφορικά με τη δομή και το μέγεθος ενός ΜΑ, η οποία πρέπει να περιλαμβάνει οπωσδήποτε την εκπαιδευτική προσέγγιση (ένα ΜΑ πρέπει να συνδέεται με έναν ή περισσότερους μαθησιακούς στόχους και πρέπει να υποστηρίζει την εκπαιδευτική διαδικασία (Νικολόπουλος κ.ά, 2011)), τις τεχνικές προδιαγραφές (μέγεθος-επίπεδο συνάθροισης), τα μεταδεδομένα, τον κύκλο ζωής, καθώς και την, βασισμένη σε κατάλληλες μετρικές, αξιολόγηση του κόστους επαναχρησιμοποίησής του. Θα μελετηθεί η διαδικασία επαναχρησιμοποίησης ΜΑ, η οποία αποτελεί ένα από τα βασικά χαρακτηριστικά των ΜΑ. Η βασική ιδέα αφορά στη χρήση μικρών, διακριτών ΜΑ ή/και το συνδυασμό τους για τη δημιουργία νέων, τα οποία να αποτελούν ένα ενιαίο εκπαιδευτικό σενάριο που να μπορεί να λειτουργήσει σε διαφορετικά εκπαιδευτικά πλαίσια, καθώς και σε διαφορετικά άτομα. Από τη μια, ένα σημαντικό πλεονέκτημα που συνεπάγεται η επαναχρησιμοποίηση ενός ΜΑ είναι η σημαντική μείωση του κόστους σχεδιασμού και ανάπτυξης των απαιτούμενων πόρων, διατηρώντας παράλληλα την ποιότητα, και από την άλλη μπορεί να αποτελέσει ένα δείκτη της υψηλής ποιότητας των διαθέσιμων ΜΑ, με την παραδοχή ότι όσο περισσότερο επαναχρησιμοποιείται ένα ΜΑ, τόσο μεγαλύτερη θα είναι η ποιότητά του (Sampson, & Zervas, 2011). Εντούτοις, υπάρχουν και μειονεκτήματα από την επαναχρησιμοποίηση ΜΑ. Το βασικότερο είναι ότι μερικές φορές το κόστος της επαναχρησιμοποίησης μπορεί να είναι μεγαλύτερο από το κόστος για τη δημιουργία νέων ΜΑ. Επίσης, πολλές φορές δεν είναι εύκολο να εμπιστευτεί κάποιος την ποιότητα των συστατικών μερών ΜΑ, τα οποία έχουν δημιουργηθεί από άλλους. Έτσι, δύσκολα είναι άμεσα μετρήσιμη η μείωση του κόστους και άρα το όφελος που προκύπτει κατά την επαναχρησιμοποίηση, κατά συνέπεια πολλές φορές συμφέρει η δημιουργία νέων ΜΑ από την επαναχρησιμοποίηση υφιστάμενων ΜΑ (Sommerville, 2006). Παρά τη σπουδαιότητα της έννοιας της επαναχρησιμοποίησης ΜΑ δεν υπάρχει κάποιος απλός τρόπος επακριβούς μέτρησης του κόστους-οφέλους που μπορεί να έχουμε σε αυτή τη διαδικασία. Η ύπαρξη μετρικών για την εκτίμηση του κόστους αποδοτικής επαναχρησιμοποίησης εκπαιδευτικών ΜΑ είναι δυνατό να διευκολύνει στον τομέα της συστηματικής αξιολόγησής τους και να δώσουν απάντηση στο ερώτημα: «Πότε αξίζει τον κόπο να επαναχρησιμοποιήσουμε και να ενσωματώσουμε ΜΑ ώστε να δημιουργήσουμε νέα;». Έτσι τελικά, θα γίνει μια μελέτη εντοπισμού και προσαρμογής μετρικών που σχετίζονται με τον τομέα της τεχνολογίας λογισμικού για την εκτίμηση του κόστους δημιουργίας εκπαιδευτικών σεναρίων και γενικότερα εκπαιδευτικού λογισμικού με επαναχρησιμοποίηση ΜΑ. Συνδέοντας αυτές τις μετρικές άμεσα με τα διάφορα στάδια του κύκλου ζωής των ΜΑ, είναι δυνατή η τελική εκτίμηση του κόστους επαναχρησιμοποίησης τους. Αυτό θα μπορούσε να δώσει τη δυνατότητα σε εκπαιδευτικούς, ιδρύματα και οργανισμούς να αξιολογήσουν αποτελεσματικά τη δημιουργία εκπαιδευτικών σεναρίων και εκπαιδευτικού λογισμικού με επαναχρησιμοποιήσιμα ΜΑ, καθώς και τη βελτίωσή τους (Sampson, & Zervas, 2011). / Over the last decades a rapid development of information technologies and communications in education is observed, while simultaneously the disposal of educational material through systems of e-learning is increasing continuously. Learning objects (LOs) constitute a new way of approaching the systematization of instructional content and are found in the core of a new educational development, constituting the base for the creation and the handling of digital educational content in technology-enhanced learning. Having a relatively short life in the area of e-learning, they have become today the most prevalent between various other terms that try to describe the variety of available digital resources that can be developed in the didactic processes. In this work, our basic goal is the study of LOs, the comprehensive description of LOs reuse processes and the evaluation of LOs reuse cost for the development of lessons, units and courses using appropriate metrics. Mostly known in the academic bibliography as media objects (Norton, 1996), educational objects (Friesen, 1996), reusable learning objects (Barritt, Lewis and Wieseler, 1999), knowledge objects (Merrill, 1998), data objects (Gibbons, Nelson, & Richards, 2000), instructional objects (Gibbons et al., 2000) or units of learning (Koper, 2001), LOs have appeared over the last decades and constitute the base for the creation and the handling of educational digital content for the needs of education, learning and students practice. Various definitions have been given for the LOs, for example from the J. L' Allier (1997), the Institute of Electrical and Electronics Engineers (2000), David A. Wiley (2002), Rehak and Mason (2003), Polsani (2003), Andres Chiappe (2007). All efforts for the development or recognition of a common conceptual definition of LOs by the educational community and the involved institutions have not thrived. However, there is a broad understanding among the members of the LO community about the functional requirements of LOs: • Accessibility • Reusability • Interoperability Various endorsements refer to the structure and the size of a LO, which should include the instructional approach (a LO should be based on one or more learning objectives and should support the educational processes), the technical specifications (level of aggregation), the metadata records, the lifecycle and the evaluation of LOs cost effective reuse that is based in suitable metrics. We will study the processes of LOs reuse, which is one of the basic characteristics of LOs. The basic idea concerns in the use of small and distinguishable LOs and/or their combination for the creation of new LOs which constitute a single educational script that could function in different educational frames as well as in different individuals. From the one hand, an important advantage that involves the re-use of MA is the important reduction of cost of planning and growth of required resources, maintaining at the same time the quality, and from the other hand, LO reuse can be an indicator for a high quality LO, under the assumption that the more a LO is reused the more likely is to be of a high quality. However, there are also disadvantages from LOs reuse. The most critical is that sometimes the cost of LO reuse can be larger than the cost of the creation of new one. Also, it is not often easy for a teacher to trust the quality of an existing LO which has been created by others. Thus, it is very difficult to measure the reduction of cost and hence the profit that results from the reuse. As an effect, many times it is easier to create new LOs than reuse existing LOs. Despite the importance of LOs reuse, there does not exist a simple way of precise measurement of the cost effectiveness in this process. The existence metrics for the estimation of the cost effectiveness of LOs reuse is possible to facilitate in the sector of their systematic evaluation and give an answer in the question: “When is it worth to reuse and incorporate existing LOs in order to create new?” Therefore, we will make a study of identification and adaptation of metrics that are related to the sector of software engineering in order to estimate the cost of creation instructional scripts and generally educational software with reusing LOs. Relating these metrics with the various stages of LOs lifecycle the final estimation of their cost reuse will be possible. This could give the chance to teachers, schools and organisms of evaluating effectively the creation and improvement of educational scripts and instructional software using reusable LOs.

Στην παρούσα μελέτη εξετάζεται η δυνατότητα επαναχρησιμοποίησης των επεξεργασμένων αστικών λυμάτων και ιλύος από Εγκαταστάσεις Επεξεργασίας Λυμάτων του νομού Αιτωλ/νίας σε γεωργικές εκτάσεις του νομού. Στο πρώτο μέρος της εργασίας γίνεται μια εισαγωγή στην επαναχρησιμοποίηση των αστικών λυμάτων στην γεωργία. Περιγράφονται τα χαρακτηριστικά των λυμάτων, οι διεργασίες που συντελούνται στις Εγκαταστάσεις Επεξεργασίας Λυμάτων, τα κριτήρια ποιότητας που πρέπει να πληρούν τα λύματα (προκειμένου να χρησιμοποιηθούν για άρδευση). Αναλύονται τα αγρονομικά κριτήρια και τα κριτήρια για την διασφάλιση της δημόσιας υγείας, που πρέπει να τηρούν τα επεξεργασμένα λύματα, ώστε να εφαρμόζονται στα εδάφη με ασφάλεια. Επίσης, στο πρώτο μέρος αναλύονται τα κριτήρια επιλογής θέσεων για την εφαρμογή των λυμάτων, καθώς και το νομοθετικό πλαίσιο που ισχύει στην Ελλάδα σχετικά με την επαναχρησιμοποίηση. Τέλος, γίνεται μια επισκόπηση της διεθνούς πρακτικής σχετικά με την επαναχρησιμοποίηση και περιγράφεται και η κατάσταση που επικρατεί στον Ελλαδικό χώρο. Στο δεύτερο μέρος γίνεται αναφορά στους υδατικούς πόρους του νομού Αιτωλ/νίας. Περιγράφεται το υδατικό δυναμικό του νομού Αιτωλ/νίας, οι ανάγκες νερού για διάφορες χρήσεις στον νομό, καθώς και οι υποδομές δικτύων άρδευσης σην Αιτωλ/νία. Το τρίτο μέρος αναφέρεται στην χρήση της ιλύος στην γεωργία. Γίνεται περιγραφή των χαρακτηριστικών της λυματολάσπης, του νομικού πλαισίου που ισχύει κατά την χρήση της στην γεωργία και τονίζονται τα κρίσιμα σημεία ελέγχου κατά την εφαρμογή της λάσπης στα γεωργικά εδάφη. Στο τέταρτο μέρος γίνεται η οριοθέτηση και η περιγραφή των περιοχών μελέτης και παρουσιάζεται ο τρόπος, με τον οποίο προσδιορίζονται οι καλλιεργούμενες εκτάσεις μέσα σε κάθε περιοχή μελέτης, ώστε στην συνέχεια να εκτιμηθούν οι υδατικές απαιτήσεις. Οι Εγκαταστάσεις Επεξεργασίας Αστικών Λυμάτων, που εξετάζονται στην παρούσα μελέτη, είναι αυτές των Δήμων Μεσολογγίου, Αιτωλικού, Θέρμου, Αγρινίου και Ναυπάκτου. Ενώ οι επιλεγείσες περιοχές μελέτης βρίσκονται πλησίον των ανωτέρω εγκαταστάσεων. Γίνεται επίσης σύντομη αναφορά στον τρόπο λειτουργίας της κάθε ΕΕΛ. Στο πέμπτο μέρος γίνεται αναφορά στους παράγοντες που επηρεάζουν την υδατοκατανάλωση των καλλιεργειών, αναλύεται η μεθοδολογία με την βοήθεια της οποίας προσδιορίζονται οι υδατικές απαιτήσεις των καλλιεργειών σύμφωνα με την εξίσωση των Penman Monteith κατά FAO. Προσδιορίζονται οι υδατικές απαιτήσεις των καλλιεργειών και οι συνολικές ανάγκες σε αρδευτικό νερό για κάθε περιοχή μελέτης, ακολουθεί η συσχετισή του με τις ετήσιες εκροές της κάθε ΕΕΛ, ώστε να προκύψει το ποσοστό κάλυψης των αρδευτικών αναγκών με επεξεργασμένες εκροές για την κάθε περιοχή. Τέλος, στο έκτο μέρος γίνεται μια προσπάθεια εκτίμησης της δυνατότητας χρήσης της λυματολάσπης στα εδάφη του νομού Αιτωλ/νίας. / This study examines the potential reuse of treated municipal wastewater and sludge from Waste Water Treatment Plants (WWTPs) in agricultural areas of Aitoloakarnania prefecture. The first part of the study is an introduction to the reuse of urban wastewater in agriculture. Describes the characteristics of wastewater, the processes occurring in the wastewater treatment plants, the quality criteria that wastewater should have for safe use in irrigation. Also, the first part analyzes the criteria for selecting areas to apply wastewater. The legislative framework in Greece for waste water reuse is also analyzed. Finally, a review of international and domestic practices on agricultural reuse is given. The second part refers to the water resources of the Aitoloakarnania prefecture. The third part refers to the use of sludge in agriculture. Describes the characteristics of the sludge, the legal framework applicable for use in agriculture and highlights the critical control points in the application of sludge on soils. The fourth part describes each study area and shows how we can specify in each area the cultivated species (crops) in order to calculate the water requirements of the crops. The study areas are sited near by the WWTPs of Messolongi, Aitoliko, Thermo, Agrinio, Naupaktos. The fifth part refers to the factors affecting water requirements of the crops, and analyzes the methodology used to calculate water requirements of crops (FAO Penman – Monteith equation). At the end of the part there is a correlation between the water requirements of the crops and the annual output of each WWTP, resulting in the percentage of coverage of irrigation demands of crops in each studied area. Finally, the sixth part is an attempt to assess the usability of sludge to soils of the Aitoloakarnania prefecture.

Στην εργασία αυτή γίνεται μια αναφορά αρχικά στα GSM δίκτυα κινητής τηλεφωνίας (χαρακτηριστικά-λειτουργίες). Στη συνέχεια περιγράφεται ο τρόπος υπολογισμού της κυτταρικής ακτίνας με βάση τα μοντέλα Okumura-Hata και Ikegami. Τέλος αναφέρονται παραδείγματα υπολογισμού της ακτίνας των κυττάρων αλλά και διαστασιοποίησης των καναλιών σε αυτά ώστε να εξυπηρετείται συγκεκριμένη τηλεπικοινωνιακή κίνηση. / The purpose of this project is to examine the major steps in cell planning process such as cell coverage, frequency planning and calculations of traffic and channel needs for the given areas.

Ο αριθμός των συνδρομητών κινητής τηλεφωνίας έχει αυξηθεί σημαντικά τα τελευταία χρόνια. Σε μεγάλο βαθμό οι φωνητικές υπηρεσίες εξυπηρετούνται από κινητά δίκτυα, ενώ παράλληλα αυξήθηκε σε μεγάλο βαθμό η χρήση των δεδομένων στα δίκτυα εκείνα που εφαρμόστηκε το 3GPP High Speed Packet Access (HSPA), αποδεικνύοντας ότι οι χρήστες επιδοκιμάζουν τη χρήση δεδομένων που παρέχονται ασύρματα με ευρυζωνικές ταχύτητες. Ο μέσος αριθμός χρήσης δεδομένων ξεπερνά τα εκατοντάδες megabytes ανά χρήστη κάθε μήνα. Τα ασύρματα δίκτυα πρέπει να αυξήσουν τις ταχύτητες μετάδοσης δεδομένων έτσι ώστε να πλησιάσουν εκείνες της ενσύρματης επικοινωνίας. Οι χρήστες είναι συνηθισμένοι να χρησιμοποιούν ενσύρματα δίκτυα και έτσι περιμένουν από τα ασύρματα δίκτυα να προσφέρουν συγκρίσιμες αποδόσεις με χαμηλό κόστος μετάδοσης δεδομένων. Το 3GPP Long Term Evolution (LTE) είναι σχεδιασμένο να επιτύχει αυτούς τους στόχους. Η τεχνολογία LTE προσφέρει κλιμακωτό εύρος ζώνης (απο 1.25 έως 20 MHz) με ρυθμούς μετάδοσης στα 100 Mbps για τον κατερχόμενο σύνδεσμο και στα 50 Mbps για τον ανερχόμενο. Αυτές οι πτυχές συνοδευόμενες από την τεχνολογία πρόσβασης που χρησιμοποιείται, η οποία είναι η OFDM (Orthogonal frequency division multiplexing), βελτιώνουν τη ρυθμαπόδοση του χρήστη και τη χωρητικότητα, ενώ μειώνουν τις καθυστερήσεις προσφέροντας παράλληλα βελτιωμένες συνθήκες κατά την κινητικότητα του χρήστη. Η OFDM προσφέρει επίσης μεγαλύτερη ανέχεια σε φαινόμενα όπως η εξασθένιση και το multipath σε σύγκριση με τεχνολογίες που εφαρμόζονταν σε προηγούμενα δίκτυα. Επίσης, είναι σημαντικό να αναφερθεί ότι το LTE χρησιμοποιεί τη μεταγωγή πακέτων και χρησιμοποιεί την τεχνολογία πολλαπλών κεραιών καθώς επίσης πολυπλεξία στο επίπεδο του χρόνου και της συχνότητας. Τέλος, υποστηρίζει unicast και multicast μετάδοση, τόσο σε microcell (κελιά μικρότερου εύρους) όσο και macrocell (μεγαλύτερα κελιά) περιβάλλον. Το αντικείμενο που μελετάται σε αυτή τη διπλωματική είναι το πρόβλημα του περιορισμού των παρεμβολών οι οποίες επηρεάζουν σε μεγάλο βαθμό την απόδοση των LTE συστημάτων. Ιδιαίερη μελέτη γίνεται όσο αφορά στην Inter Cell παρεμβολή και στις Inter Cell Interference Coordination τεχνικές. Συγκεκριμένα, η έρευνα εστιάζει στη βελτίωση της απόδοσης των χρηστών μειώνοντας την παρεμβολή μέσω διαφόρων σχημάτων επαναχρησιμοποίησης συχνότητας. / The number of mobile subscribers has increased tremendously in recent years. Voice communication has become mobile in a massive way and the mobile is the preferred way for voice communication. At the same time the data usage has grown fast in those networks where 3GPP High Speed Packet Access (HSPA) was introduced indicating that the users find value in broadband wireless data. The average data consumption exceeds hundreds of Megabytes per subscriber per month. Wireless networks must make data rates higher in order to match the user experience provided by wireline networks. When customers are used to wireline performance, they expect the wireless network to offer comparable performance with low cost of data delivery. 3GPP Long Term Evolution (LTE) is designed to meet those targets. LTE technology offers scalable bandwidth (from 1.25 up to 20 MHz), with transmission rates of 100 Mbps in downlink and 50 Mbps in uplink. These aspects accompanied with the access technology used, which is the OFDM (Orthogonal frequency division multiplexing), improves end-user throughputs, sector capacity and reduces user plane latency, bringing significantly improved user experience with full mobility. OFDM also offers bigger tolerance in phenomena such as multipath and fading compared to technologies used in previous mobile networks. It is also important to be mentioned that LTE is fully packet switched and uses multiple antenna techniques along with FDD and TDD duplexing. Finally, it supports unicast and multicast transmission, in both microcell and macrocell environment. The subject studied in this thesis is the problem of mitigating Interferences which dramatically affects the performance of LTE system. Extensive study is done concerning Inter Cell Interference and Inter Cell Interference Coordination techniques. In particular, research focuses in enhancing users’ performance by reducing interference via varius schemes of frequency reuse.

Το αντικείμενο της παρούσας διδακτορικής διατριβής εστιάζεται στην ανάπτυξη αποδοτικών τεχνικών μεταγλώττισης για επαναπροσδιοριζόμενα ολοκληρωμένα συστήματα αρχιτεκτονικών πίνακα. Χρησιμοποιήθηκαν εφαρμογές που κυριαρχούνται από δεδομένα για τον έλεγχο των μεθοδολογιών. Σκοπός είναι να βελτιστοποιηθεί η εκτέλεση των εφαρμογών ως προς χαρακτηριστικά των επαναπροσδιοριζόμενων συστημάτων όπως η απόδοση, ο αριθμός εντολών ανά κύκλο ρολογιού, η επιφάνεια ολοκλήρωσης και ο βαθμός χρησιμοποίησης των επεξεργαστικών πόρων. Αυτό επιτυγχάνεται με την εισαγωγή πρωτότυπων τεχνικών χαρτογράφησης αλλά και την εύρεση βέλτιστων αρχιτεκτονικών. Στο πρώτο τμήμα της διατριβής υλοποιήθηκε η έρευνα, ανάπτυξη και αυτοματοποίηση τεχνικών μεταγλώττισης για επαναπροσδιοριζόμενα συστήματα αρχιτεκτονικών πίνακα. Κύριο χαρακτηριστικό αυτών των αρχιτεκτονικών είναι ύπαρξη μεγάλου αριθμού επεξεργαστικών στοιχείων που δουλεύουν παράλληλα με αποτέλεσμα να επιταχύνουν την εκτέλεση εφαρμογών που εμφανίζουν παραλληλία πράξεων. Η λειτουργία τους σε ενσωματωμένα συστήματα είναι αυτή ενός συνεπεξεργαστή. Η έρευνα πάνω σε επαναπροσδιοριζόμενες αρχιτεκτονικές πίνακα έχει αποκτήσει μεγάλο ενδιαφέρον λόγω της ευελιξίας, της επεκτασιμότητας και της απόδοσής τους, ιδιαίτερα σε εφαρμογές που κυριαρχούνται από δεδομένα. Η μεταγλώττιση, όμως, εφαρμογών πάνω σε αυτές χαρακτηρίζεται από υψηλή πολυπλοκότητα. Απαιτούνται κατάλληλα εργαλεία και ειδικές μεθοδολογίες χαρτογράφησης για την εκμετάλλευση των χαρακτηριστικών αυτών των αρχιτεκτονικών. Με αυτό το σκεπτικό, προτάθηκε μια πρωτότυπη επαναστοχεύσιμη μεθοδολογία χαρτογράφησης εφαρμογών, η οποία επιπλέον έχει αυτοματοποιηθεί με τη χρήση ενός πρότυπου εργαλείου μεταγλώττισης που στοχεύει σε ένα αρχιτεκτονικό παραμετρικό πρότυπο. Αποτέλεσμα ήταν η εύρεση των βέλτιστων αρχιτεκτονικών με βάσει την απόδοση, τον αριθμό των εντολών ανά κύκλο ρολογιού και το χρόνο εκτέλεσης του εργαλείου, για μια ομάδα εφαρμογών. Η αποδοτικότητα μιας επαναπροσδιοριζόμενης αρχιτεκτονικής πίνακα ως προς την ταχύτητα και το κόστος σε υλικό είναι δύσκολο να μετρηθεί, για αυτό έχουν υπάρξει λίγες έρευνες που μελετούν την επίδραση αρχιτεκτονικών παραμέτρων πάνω σε παράγοντες όπως η επιφάνεια ολοκλήρωσης και ο αριθμός εντολών ανά κύκλο ρολογιού. Επιπλέον, καμιά εργασία δεν έχει εξετάσει την επίδραση πολλαπλασιαστών ενσωματωμένων στα επεξεργαστικά στοιχεία των επαναπροσδιοριζόμενων αρχιτεκτονικών. Χρησιμοποιώντας την υπάρχουσα επαναστοχεύσιμη μεθοδολογία μεταγλώττισης και μια παραμετρική υλοποίηση της αρχιτεκτονικής σε γλώσσα περιγραφής υλικού, εξετάζουμε την επίδραση των πολλαπλασιαστών από τη μεριά της χαρτογράφησης και της αρχιτεκτονικής. Επίσης, περιγράφεται η πρωτότυπη μεθοδολογία χαρτογράφησης που εισήχθη με σκοπό την αποδοτική λειτουργία του αλγορίθμου Fast Fourier Transform (FFT) πάνω σε επαναπροσδιοριζόμενα συστήματα αρχιτεκτονικών πίνακα. Ο αλγόριθμος FFT χαρακτηρίζεται από μεγάλο αριθμό πράξεων κυρίως πολλαπλασιασμών που επιβραδύνουν την απόδοση μιας επαναπροσδιοριζόμενης αρχιτεκτονικής. Εκμεταλλευόμενοι την ύπαρξη εσωτερικής επαναληπτικής δομής μέσα στον αλγόριθμο και χρησιμοποιώντας μια επαναπροσδιοριζόμενη αρχιτεκτονική 16 επεξεργαστικών στοιχείων, αναπτύξαμε μια πρωτότυπη τεχνική χαρτογράφησης. Επιπρόσθετα, η τεχνική μας λαμβάνει υπόψη την ιεραρχία μνήμης μεταξύ κύριας μνήμης και επαναπροσδιοριζόμενης αρχιτεκτονικής για την περαιτέρω επιτάχυνση εκτέλεσης του αλγορίθμου FFT. Η χρήση της προτεινόμενης τεχνικής χαρτογράφησης οδηγεί σε επίτευξη βαθμού χρησιμοποίησης των επεξεργαστικών στοιχείων άνω του 90%, τιμή που είναι τουλάχιστον 37% υψηλότερη από την καλύτερη τιμή της βιβλιογραφίας. / The object of this PhD thesis focuses on developing efficient mapping techniques for coarse grain reconfigurable build arrays. Data intensive applications were used to evaluate the proposed methodologies. The aim is to optimize the applications’ performance on characteristics targeting reconfigurable characteristics such as performance, instructions per cycle, area of integration and processing resource utilization. This is achieved by introducing novel mapping techniques and finding optimal architectures. In the first part of the thesis research, development and automation of mapping techniques was carried out targeting coarse grain reconfigurable arrays. The main feature of these architectures is the presence of a large number of processing elements working in parallel thus speeding up the execution of applications featuring parallel operations. The function of these processing elements in embedded systems resembles that of a coprocessor. The research on reconfigurable array architectures has gained considerable interest because of their flexibility, scalability and performance, particularly in data intensive applications. Nevertheless, compiling these applications on reconfigurable architectures is characterized by high degree of complexity. Appropriate tools and special mapping methodologies are needed to exploit the characteristics of these architectures. Bearing this in mind, we proposed a novel reconfigurable methodology for mapping applications, which has also been automated with the use of a prototype compiler tool aiming at a parametric architectural model. The result was finding the best architectures on the basis of performance, the instructions per cycle term and the tool execution time for a sample set of applications. It is difficult to evaluate the efficiency of a reconfigurable array architecture table in terms of speed and area of integration, so there have been few cases studying the effect of architectural parameters on factors such as surface integration and the number of instructions per clock cycle. Moreover, no work has examined the multipliers’ impact embedded in reconfigurable architectures processing elements. Using the existing reconfigurable mapping methodology and a parametric implementation of the architecture in hardware description language, we examine the effect of multipliers on the part of the mapping phase and architecture. We also describe an original mapping methodology introduced for the purpose of efficiently mapping the Fast Fourier Transform (FFT) algorithm on reconfigurable array architectures. The FFT algorithm is characterized by a large number of operations primarily multiplications that slow the performance of a reconfigurable architecture. Exploiting the existence of an internal structure inside the FFT algorithm and by the use of a reconfigurable architecture template of 16 processing elements, we developed a novel mapping technique. Additionally, our technique takes into account the memory hierarchy between main memory and reconfigurable architecture in order to further accelerate the implementation of the FFT algorithm. Using the proposed mapping technique results in processing elements utilization of over 90% value which is at least 37% better than the best value of the related literature.

Στην εργασία, αυτή, εξετάζονται οι μέθοδοι συμπίεσης του συνόλου δοκιμής με τη χρήση πινάκων που έχουν ήδη προταθεί και προτείνεται μία νέα μέθοδος συμπίεσης δεδομένων δοκιμής για πυρήνες που ο έλεγχος ορθής λειτουργίας υλοποιείται μέσω μονοπατιών ολίσθησης. Η νέα μέθοδος επαναχρησιμοποιεί μπλοκ του πίνακα για τη σύνθεση διανυσμάτων δοκιμής. Δύο νέοι αλγόριθμοι παρουσιάζονται για επιλεκτική και πλήρη καταχώρηση τμημάτων του συνόλου δοκιμής σε πίνακα. Η προτεινόμενη μέθοδος συγκρίνεται με τις υπάρχουσες μεθόδους ως προς το ποσοστό συμπίεσης αλλά και ως προς το κόστος υλοποίησης. Για την αξιολόγηση της μεθόδου λαμβάνονται υπόψη σύνολα δοκιμής που έχουν παραχθεί για την ανίχνευση απλών σφαλμάτων μόνιμης τιμής, απλών σφαλμάτων μόνιμης τιμής με πολλαπλότητα ανίχνευσης Ν (Ν-detect) και σφαλμάτων καθυστέρησης μετάβασης. / In this work we refer to dictionary based test data compression methods. At first the already known dictionary based test data compression methods are comparably presented. Then we propose a new method and we show that the test data compression achieved by a dictionary based method can be improved significantly by suitably reusing parts of the dictionary entries. To this end two new algorithms are proposed, suitable for partial and complete dictionary coding respectively. For the evaluation of the proposed method, test sets have been generated and used based on the stuck-at fault model for single and N detection of each fault as well as on the transition fault model.