Στα πλαίσια της παρούσας διπλωματικής εργασίας υλοποιήθηκε ένας εξομοιωτής κρυφών μνημών και ένας επεξεργαστής αρχιτεκτονικής τύπου MIPS σε γλώσσα προγραμματισμού Java. Με την χρήση του εξομοιωτή και ενός αλγορίθμου πολλαπλασιασμού πίνακα επί πίνακα γραμμένο σε συμβολική γλώσσα assembly αξιολογήθηκαν τα χαρακτηριστικά των κρυφών μνημών όπως συσχετιστικότητα, μέγεθος μπλοκ, μέγεθος μνήμης και ιεραρχία μνήμης. Ως αποτέλεσμα κατασκευάστηκε ένα εργαλείο αξιολόγησης τόσο της αρχιτεκτονικής του υλικού για έναν αλγόριθμο όσο και της αποδοτικότητας ενός αλγορίθμου που εισάγεται στο πρόγραμμα για μια αρχιτεκτονική. / In the context of the current thesis a cache memory simulator was implemented with a MIPS architecture processor in Java programming language. Using the simulator and a matrix by matrix multiplication algorithm written in assembly language supported by the simulator various features of the cache memories were evaluated such as associativity, block size, memory size and memory hierarchy. As a result an evaluation tool was built, capable of evaluating not only a memory hierarchy architecture but also the efficiency of an algorithm used on a specific architecture.

- / -

Η Κινάση του Αναπλαστικού Λεμφώματος(Alk) είναι ένας υποδοχέας κινάσης τυροσίνης(RTK)ο οποίος εμπλέκεται σε διάφορες μορφές καρκίνου στον άνθρωπο, και η λειτουργικότητά του δεν έχει διαλευκανθεί πλήρως. Γνωρίζουμε ότι, ο υποδοχέας dAlk εκφράζεται ευρέως στο ΚΝΣ των ενήλικων μυγών και ιδιαίτερα στα μισχοειδή σωμάτια της Drosophila melanogaster, νευρωνικές δομές απαραίτητες για τις διεργασίες της μνήμης και της μάθησης. Στόχος της διπλωματικής εργασίας είναι η διερεύνηση του ρόλου του υποδοχέα dAlk και του προσδέτη του Jeb στην μνήμη μακράς διαρκείας(LTM)και ο καθορισμός του υποσυνόλου των νευρώνων στους οποίους παράγεται τόσο το Alk όσο και ο προσδέτης του Jeb. Για την διεξαγωγή των πειραμάτων χρησιμοποιήθηκαν γενετικές μέθοδοι και συμπεριφορικές μελέτες στην Drosophila melanogaster. / The Receptor Tyrosine Kinase Alk is implicated in several human cancers, but with many unknown functions.It has already been demonstrated that the receptor Alk is widely expressed in the central nervous system of adult flies and especially in the Mushroom Bodies, neuronal structures essential for learning and memory. The main purpose of my undergraduate thesis is to elucidate the role of the receptor Alk and its ligand Jeb in Long Term Memory. Moreover, we focused on finding the specific subset of neurons in which the RTK dAlk and its ligand Jeb are produced.For this research we used genetic tools alongwith behavioural techniques.

Η κρυφή μνήμη αποτελεί έναν σημαντικό παράγοντα για την απόδοση του επεξεργαστή. Ταυτόχρονα όμως αποτελεί και ένα από τα δομικά μέρη πάνω στο chip στο οποίο καταναλώνεται σημαντικό κομμάτι της ισχύος. Στην παρούσα εργασία γίνεται μία ανάλυση πάνω στην κατανάλωση των διαφόρων επιπέδων της ιεαραρχίας της κρυφής μνήμη του επεξεργαστή και παρουσιάζονται ορισμένες τεχνικές που οδηγούν στην μείωση της ενώ παράλληλα διατηρείται η απόδοση του υπολογιστικού συστήματος όσο το δυνατόν πιο σταθερή. Η αποτίμηση των τεχνικών αυτών έγινε με την βοήθεια του SimpleScalar, εξομοιωτή υπερβαθμωτών αρχιτεκτονικών επεξεργαστή, και του εργαλείου CACTI της HP, το οποίο μοντελοποιεί διάφορα χαρακτηριστικά (χρόνο προσπέλασης, δυναμική κατανάλωση ισχύος κτλ.) της κρυφής και κύριας μνήμης του επεξεργαστή. / Cache memory plays an important role in the performance of the processor. Simultaneously, however, it is one of the core components of the chip which consume a significant percentage of the total power. In this thesis we present an analysis of the power dissipation of the different levels in cache memory hierarchy and we propose techniques that lead to a reduction of power consumption while maintaning the system performance. For the efficiency study of these techniques we use SimpleScalar, a superscalar architecture simulator, and CACTI, an enhanced cache access and cycle time model.

Η παρούσα διπλωματική εργασία έχει ως αντικείμενο την κατασκευή συστήματος ανίχνευσης κίνησης αυτοκινήτου και την καταγραφή των δεδομένων σε μνήμη SD ή MMC.Η καταγραφή της κίνησης γίνεται μέσω της μέτρησης της επιτάχυνσης και στους τρεις άξονες με χρήση του μικροελεγκτή STM32 Cortex-M3 της εταιρίας ST Microelectronics. Πιο συγκεκριμένα χρησιμοποιείται το STM32-103STK Development Board της εταιρίας Olimex το οποίο διαθέτει και κάποια ενσωματωμένα περιφερειακά. Αρχικά, περιγράφονται τα διάφορα χαρακτηριστικά του συστήματος και δίνονται σημαντικές πληροφορίες για τη λειτουργία του και τα πλεονεκτήματα που προσφέρει στο χρήστη.Στη συνέχεια, γίνεται αναφορά και ανάλυση σε κάποια από τα διαθέσιμα περιβάλλοντα για ανάπτυξη ενσωματωμένων εφαρμογών και τελικά παρουσιάζεται διεξοδικά ο αλγόριθμος που χρησιμοποιήθηκε για την ανάπτυξη της συγκεκριμένης εφαρμογής.Το σύστημα που υλοποιήθηκε λαμβάνει τιμές επιτάχυνσης μέσω ενός επιταχυνσιομέτρου τριών αξόνων,προβάλλει τις τιμές αυτές στην οθόνη προς ενημέρωση του χρήστη και τελικά αποθηκεύει αυτές τις τιμές σε κάρτα μνήμης τύπου SD(Secure Digital). / This diploma thesis is about the implementation of a tracking and acceleration data recording system in SD or MMC memories in order to examine the movement of an automobile. Movement tracking is performed through measurement of acceleration values in all three axis with an STM32 Cortex-M3 microcontroller provided by ST Microelectronics. Specifically, we use the STM32-103STK Development board by Olimex with its embedded peripherals. First of all, we give a description of system characteristics and important information about its operation and the advantages it offers to users. Moreover, there is a reference and analysis regarding the available development environments for creating and debugging embedded applications and finally there is a detailed presentation of the algorithm used for the development of this particular application. The implemented system measures the acceleration values through a 3-axis accelerometer, then presents those values on an LCD screen to inform the user and stores the values in an SD(Secure Digital) memory card.

Οι υπάρχοντες μεταγλωττιστές, έχουν τρία βασικά μειονεκτήματα 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.

Η παρούσα διπλωματική αποτελεί την προσπάθεια κατασκευής ενός cache controller βασισμένο στον AHB BUS. Η ανάπτυξή του έγινε ως επί το πλείστο στο Εργαστήριο Vlsi του τμήματος Μηχανικών Υπολογιστών και Πληροφορικής με την προοπτική να ενσωματωθεί σε ένα ευρύτερο υπάρχων σύστημα βασισμένο στον open source cpu της arm Cortex M0. Δοκιμάστηκε επιτυχώς σε FPGA του εργαστηρίου αλλά ακόμα δεν έχει χρησιμοποιηθεί σε «πραγματικές συνθήκες». Απώτερος στόχος είναι να χρησιμοποιηθεί στο εργαστήριο για την επιτάχυνση εφαρμογών που θα χρειαστούν εξωτερική μνήμη δηλ. μεγαλύτερη μνήμη από την embedded του FPGA. Αν και δεν δοκιμάστηκε σε κάποιο άλλο σύστημα έχει φτιαχτεί με γνώμονα το πρότυπο του AHB οπότε υποθετικά δεν θα έχει κάποιο πρόβλημα να ενσωματωθεί σε οποιοδήποτε συμβατό με τον δίαυλο σύστημα. Η λογική πίσω από την υλοποίηση του είναι να είναι σχετικά εύκολη η αλλαγή ορισμένων μεταβλητών ώστε να διαφοροποιείται ο controller βάση των αναγκών του καθενός. Οι προδιαγραφές δίνονται παρακάτω αν και πιθανόν εκτός των πλαισίων της διπλωματικής και εντός του 2014 να επανα-σχεδιαστεί ώστε να γίνει πλήρως modular. / Cache controller compatible with AHB bus in system Verilog.

Σκοπός της παρούσας μελέτης ήταν η διερεύνηση της σχέσης της λεκτικής εργαζόμενης μνήμης και της παραγωγής γραπτού λόγου από μαθητές Δ’ τάξης Δημοτικού είτε με κανονική επίδοση είτε με μαθησιακές δυσκολίες. Στα περισσότερα γνωστικά μοντέλα γραπτής έκφρασης επισημαίνεται ο καθοριστικός ρόλος της εργαζόμενης μνήμης κατά την παραγωγή γραπτού λόγου. Για τον σκοπό της έρευνας δημιουργήθηκαν δύο εξισωμένες ως προς το φύλο και τη χρονολογική ηλικία ομάδες, οι οποίες διέφεραν στη σχολική επίδοση. Κάθε ομάδα αποτελούταν από 27 μαθητές, οι οποίοι συμμετείχαν σε μια σειρά από δοκιμασίες λεκτικής εργαζόμενης μνήμης, ενώ κλήθηκαν να γράψουν και ένα αφηγηματικό κείμενο. Τα αποτελέσματα της έρευνας έδειξαν ότι υπάρχουν στατιστικώς σημαντικές διαφορές μεταξύ των δύο ομάδων στις δοκιμασίες εργαζόμενης μνήμης και στη γραπτή παραγωγή. Επιπλέον, υπάρχει συνάφεια μεταξύ της εργαζόμενης μνήμης και της γραπτής έκφρασης, ενώ η εργαζόμενη μνήμη επεξηγεί μεγάλα ποσοστά της συνολικής διακύμανσης της παραγωγής γραπτού λόγου. Περαιτέρω έρευνες κρίνονται απαραίτητες για επαλήθευση των αποτελεσμάτων σε μαθητές και άλλων ηλικιών, αλλά και για διερεύνηση της συνεισφοράς της μνήμης στην παραγωγή άλλων κειμενικών ειδών. / The purpose of the present thesis was to examine the relation between verbal working memory and writing ability in students attending fourth grade of elementary school with and without learning disabilities. Most cognitive models of writing suggest a central role for working memory during the writing of a text. For the purpose of the study, two groups of students matched in gender and chronological age, but differ in educational achievement. Each group consisted of 27 participants, who were tested using a series of verbal working memory tasks and wrote a narrative text. The results of the study indicated that there was statistically significant difference between the two groups in verbal working memory tasks and in written production. Furthermore, there were statistically significant correlations between the working memory tests and the students’ writing ability. Also, working memory interpreted a large percentage of the total variance of the written production. Further research is necessary in order to confirm the results in older school students and to investigate the contribution of working memory in the production of different text genres, in addition to narrative ones.

Η παρούσα διδακτορική διατριβή περιγράφει το σχεδιασμό και την ανάπτυξη ενός εκπτυσσόμενου Ενδομυελικού Ήλου Επιμήκυνσης των Μακρών Οστών των Κάτω Άκρων. Η επιμήκυνση των κάτω άκρων είναι μία χειρουργική διαδικασία βαθμιαίας επιμήκυνσης των μακρών οστών των κάτω άκρων και των μαλακών μορίων που τα περιβάλουν. Γενικά, η επιμήκυνση των κάτω άκρων στοχεύει στην εξίσωση των σκελών ή αύξηση του μήκους των οστών και στα δύο άκρα. Η τεχνική αύξησης του μήκους των οστών των κάτω άκρων επινοήθηκε από τις αρχές του περασμένου αιώνα [1] και έχει καταξιωθεί στη μοντέρνα χειρουργική από τις αρχές του 1960, λόγω της ενασχόλησης του G.A.Ilizarov. Ο επιστήμονας και χειρουργός G.A.Ilizarov αφιέρωσε όλη τη θεωρητική και πρακτική του έρευνα [2] στη βελτίωση της διαδικασίας επιμήκυνσης των οστών και την ανάπτυξη εξωτερικής συσκευής σταθεροποίησης που φέρει το όνομα του. Η μέθοδος αυτή καθώς και η συσκευή Ilizarov χρησιμοποιήθηκαν πάρα πολύ για να διορθώσουν τόσο βλάβες όσο και παραμορφώσεις των κάτω άκρων. Η ευελιξία αυτής της συσκευής την κάνει ένα εξαιρετικό εργαλείο το οποίο μπορεί να χρησιμοποιηθεί για τη διόρθωση διαφόρων βλαβών όπως π.χ. σταθεροποίηση συνθέτων καταγμάτων, στροφικές διορθώσεις, διορθώσεις οστών με διαφορές μήκους. Τόσο όμως η συσκευή του Ilizarov όσο και οι υπόλοιποι μονόπακτοι εξωτερικοί σταθεροποιητές που παρουσιάσθηκαν αργότερα παρουσιάζουν μειονεκτήματα [3] όπως είναι π.χ. οι σύνθετες χειρουργικές διαδικασίες, οι συνδέσεις και οι βελόνες που διαπερνούν το δέρμα και που οδηγούν σε μολύνσεις, η μειωμένη δυνατότητα φόρτισης και η ταλαιπωρία λόγω του μεγέθους του σταθεροποιητή ειδικά στις περιπτώσεις εκείνες που η ευελιξία του σταθεροποιητή δεν είναι απαραίτητη. Πολλοί ασθενείς που χρειάζονται μία διόρθωση του μήκους ενός άκρου χωρίς άλλες παραμορφώσεις θα μπορούσαν να βοηθηθούν και από μία συσκευή μικρότερης ευελιξίας χωρίς τα μειονεκτήματα των εξωτερικών μονόπακτων σταθεροποιητών. / The technique to increase the length of the long bones is the subject of research for the orthopedic surgeons for many years. The technique is used for the treatment of a limb shortening due to malformation or to a deficit for other reasons e.g. the fracture of a long bone after a car accident, osteomyelitis, or malignancy. The procedure to increase the length of a bone is difficult and may become quite hazardous for the soft tissues surrounding the area. The two parts of the bone are stabilized to eliminate the possibility of relative torsion and bending. Then they align axially with respect to each other and move with a constant rate of elongation of 1mm per day. The elongation is usually achieved by 4 steps of 0,25mm every 6 hours. The application of internal distraction osteogenesis using shape memory alloys has all the advantages of internal osteosynthesis. The only part of these mechanisms that is found externally is the activation mechanism that is connected by the necessary cables of activation with the interior of the bone where the internal distraction device is placed. The basic problem of all designs is the high constructional complexity of activation and control of shift of the two parts of the bone, something that makes this systems non user friendly and with continuous fractures and blockings of the elements of the mechanisms. In the present work, all the advantages of the mechanism of internal distraction osteogenesis are combined with the fundamental advantage; the simplicity of manufacture of the mechanism and the simplicity of operation via the restriction of the moving elements.

Αντικείμενο της παρούσας μεταπτυχιακής εργασίας είναι ο σχεδιασμός και η ανάπτυξη συστήματος κατανεμημένης διαμοιραζόμενης μνήμης ως τμήμα της αρχιτεκτονικής πολυεπεξεργαστικού συστήματος SiScape. Λόγω των ιδιαιτεροτήτων της αρχιτεκτονικής αυτής, το σύστημα μνήμης της και συγκεκριμένα η κρυφή μνήμη δευτέρου επιπέδου που καθιστά δυνατή τη λειτουργία του, κρίθηκε απαραίτητο να σχεδιαστεί και να αναπτυχθεί από το μηδέν, προκειμένου να ανταποκριθεί στις απαιτήσεις της. Ο σχεδιασμός της κρυφής μνήμης δευτέρου επιπέδου περιγράφηκε στη γλώσσα περιγραφής υλικού VHDL. / The purpose of this master thesis is the design and development of a shared distributed memory system as part of the multiprocessor architecture SiScape. Because of the architecture's irregular structure, it was imperative that the memory system and particularly the second level cache that enables its functionality, was designed from scratch, to fill all of its requirements. The design of the second level cache was described using the VHDL hardware description language.