Στην παρούσα διατριβή παρουσιάζονται παράλληλοι αλγόριθμοι και εφαρμογές σε πολυπύρηνες μονάδες επεξεργασίας γραφικών. Πιο συγκεκριμένα, εξετάζονται οι μέθοδοι σχεδίασης ενός παράλληλου αλγορίθμου για την επίλυση τόσο απλών και κοινών προβλημάτων, όπως η ταξινόμηση, όσο και υπολογιστικά απαιτητικών προβλημάτων, έτσι ώστε να εκμεταλλευτούμε πλήρως την τεράστια υπολογιστική δύναμη που προσφέρουν οι σύγχρονες μονάδες επεξεργασίας γραφικών. Πρώτο πρόβλημα που εξετάστηκε είναι η ταξινόμηση, η οποία είναι ένα από τα πιο συνηθισμένα προβλήματα στην επιστήμη των υπολογιστών. Υπάρχει σαν εσωτερικό πρόβλημα σε πολλές εφαρμογές, επομένως πετυχαίνοντας πιο γρήγορη ταξινόμηση πετυχαίνουμε πιο καλή απόδοση γενικότερα. Στο Κεφάλαιο 3 περιγράφονται όλα τα βήματα σχεδιασμού για την εκτέλεση ενός αλγορίθμου ταξινόμησης για ακεραίους, της count sort, σε μια μονάδα επεξεργασίας γραφικών. Σημαντική επίδραση στην απόδοση είχε η αποφυγή του συγχρονισμού των νημάτων στο τελευταίο βήμα του αλγορίθμου. Στη συνέχεια παρουσιάζονται εφαρμογές παράλληλων αλγορίθμων σε υπολογιστικά απαιτητικά προβλήματα. Στο Κεφάλαιο 4, εξετάζεται το πρόβλημα χρονοπρογραμματισμού εξετάσεων Πανεπιστημίων, το οποίο είναι ένα πρόβλημα συνδυαστικής βελτιστοποίησης. Για την επίλυσή του χρησιμοποιείται ένας υβριδικός εξελικτικός αλγόριθμος, ο οποίος εκτελείται εξ' ολοκλήρου στην μονάδα επεξεργασίας γραφικών. Η τεράστια υπολογιστική δύναμη της GPU και ο παράλληλος προγραμματισμός δίνουν τη δυνατότητα χρήσης μεγάλων πληθυσμών έτσι ώστε να εξερευνήσουμε καλύτερα τον χώρο λύσεων και να πάρουμε καλύτερα ποιοτικά αποτελέσματα. Στο επόμενο κεφάλαιο γίνεται επίλυση του προβλήματος σχεδιασμού κίνησης για υποθαλάσσια οχήματα με βραχίονα. Εξετάζεται το πρόβλημα τόσο του ολικού σχεδιασμού όσο και του τοπικού. Στην πρώτη περίπτωση είναι σημαντική η καλή λύση και η ακρίβεια και ο παράλληλος αλγόριθμος που χρησιμοποιείται για την αναπαράσταση του περιβάλλοντος εργασίας σε μια Bump-επιφάνεια βοηθάει προς αυτή την κατεύθυνση. Στη δεύτερη περίπτωση, το πρόβλημα είναι πρόβλημα πραγματικού χρόνου και μας ενδιαφέρει η ταχύτητα εύρεσης της επόμενης θέσης του οχήματος. Ο παράλληλος προγραμματισμός και η GPU βοηθούν σημαντικά σε αυτό. Τελευταία εφαρμογή που εξετάστηκε είναι η μελέτη ενός συστήματος ημιφθοριωμένων αλκανίων με την μοριακή προσομοίωση Monte Carlo. Η παραλληλοποίηση ενός μέρους, του πιο χρονοβόρου, του αλγορίθμου έδωσε τη δυνατότητα εξέτασης ενός πολύ μεγαλύτερου συστήματος σε αποδεκτό χρόνο. Σε γενικές γραμμές, γίνεται φανερό ότι ο παράλληλος προγραμματισμός και οι σύγχρονες πολυπύρηνες αρχιτεκτονικές, όπως οι μονάδες επεξεργασίας γραφικών, δίνουν νέες δυνατότητες στην αντιμετώπιση καθημερινών προβλημάτων, προβλημάτων πραγματικού χρόνου και προβλημάτων συνδυαστικής βελτιστοποίησης. / In this thesis, parallel algorithms and applications in manycore graphics processing units are presented. More specifically, we examine methods of designing a parallel algorithm for solving both simple and common problems such as sorting, and computationally demanding problems, so as to fully exploit the enormous computing power of modern graphics processing units (GPUs). First problem considered is sorting, which is one of the most common problems in computer science. It exists as an internal problem in many applications. Therefore, sorting faster, results in better performance in general. Chapter 3 describes all design options for the implementation of a sorting algorithm for integers, count sort, on a graphics processing unit. The elimination of thread synchronization in the last step of the algorithm had a significant effect on the performance. Chapter 4 addresses the examination timetabling problem for Universities, which is a combinatorial optimization problem. A hybrid evolutionary algorithm, which runs entirely on GPU, was used to solve the problem. The tremendous computing power of GPU and parallel programming enable the use of large populations in order to explore better the solution space and get better quality results. In the next chapter, the problem of motion planning for underwater vehicle manipulator systems is examined. In the gross motion planning problem, it is important to achieve a good solution with high accuracy. The parallel algorithm used for the representation of the working environment in a Bump-surface is a step towards this direction. In the local motion planning problem, which is a real-time problem, the time needed to find the next configuration of the vehicle is crucial. Parallel programming and the GPU greatly assist in this online problem. Last application considered is the atomistic Monte Carlo simulation of semifluorinated alkanes. The parallelization of part of the algorithm, the most time-consuming, enabled the study of a much larger system in an acceptable execution time. In general, it becomes obvious that parallel programming and new novel manycore architectures, such as graphics processing units, give new capabilities for solving everyday problems, real time and combinatorial optimization problems.

Το αντικείμενο της διδακτορικής διατριβής αφορά στην ανάπτυξη μιας ευέλικτης και επεκτάσιμης αρχιτεκτονικής που θα αξιοποιηθεί στον σχεδιασμό συστημάτων για την διεξαγωγή πειραμάτων από απόσταση. Τα συστήματα αυτά αναφέρονται ως RLs (Remote Laboratories) και επιτρέπουν στους χρήστες να χειρίζονται απομακρυσμένα τον διαθέσιμο εργαστηριακό εξοπλισμό με σκοπό την διεξαγωγή πειραμάτων. Στην διεθνή βιβλιογραφία έχουν καταγραφεί σημαντικές ερευνητικές προσπάθειες που σχετίζονται με την ανάπτυξη RLs σε διάφορα γνωστικά αντικείμενα. Όμως ακόμη και σήμερα δεν έχει υιοθετηθεί από την επιστημονική κοινότητα κάποια κοινά αποδεκτή αρχιτεκτονική για την ανάπτυξη RLs. Αρχικά προτείνεται μια αρχιτεκτονική για την ανάπτυξη RLs η οποία ονομάζεται ARIAL (Architecture of Internet Accessible Laboratories) η οποία είναι ανεξάρτητη από το γνωστικό αντικείμενο των υποστηριζόμενων από απόσταση πειραμάτων. Η συγκεκριμένη αρχιτεκτονική είναι επίσης ανεξάρτητη τόσο από το υλικό (hardware) όσο και από το λογισμικό (software) που θα αξιοποιηθεί για την ανάπτυξη ενός RL. Η ARIAL αποτελείται από δύο δομικά στοιχεία, τον MWS (Main Web Server) και το WS (WorkStation). Ο MWS αναλαμβάνει κυρίως την διαχείριση των χρηστών και των διαθέσιμων WSs. Ενώ τα WSs που συνήθως βρίσκονται σε πολλαπλότητα, αναλαμβάνουν αποκλειστικά την διεξαγωγή των υποστηριζόμενων από απόσταση πειραμάτων. Η επικοινωνία μεταξύ του MWS και των WSs επιτυγχάνεται μέσω μιας βάσης δεδομένων που επιτρέπει την πρόσβαση μέσω διαδικτύου. Επομένως, τα WSs μπορούν να εγκατασταθούν σε οποιαδήποτε γεωγραφική τοποθεσία επιτρέποντας την ανάπτυξη ομοσπονδιακών RLs. Όμως το σημαντικότερο χαρακτηριστικό της προτεινόμενης αρχιτεκτονικής το οποίο συμβάλει αποφασιστικά στην βιωσιμότητα ενός RL, είναι η υποστήριξη από απόσταση πειραμάτων που έχουν σχεδιαστεί και υλοποιηθεί από τους χρήστες. Με στόχο την επιβεβαίωση της ARIAL προτείνεται ένα RL στην ψηφιακή επεξεργασία σήματος με DSPs που ονομάζεται R-DSP Lab (Remote Digital Signal Processors Laboratory). Το R-DSP Lab παρέχει στους χρήστες την δυνατότητα είτε να διεξάγουν ένα από τα προκαθορισμένα από απόσταση πειράματα είτε να επιβεβαιώσουν την ορθή λειτουργία μιας DSP εφαρμογής που ανέπτυξαν οι ίδιοι. Το συγκεκριμένο RL επιτρέπει επίσης την ανάπτυξη από απόσταση πειραμάτων από τους χρήστες. Στην περίπτωση αυτή οι χρήστες εκτός από την DSP εφαρμογή που επιθυμούν, θα πρέπει να υλοποιήσουν και το GUI (Graphical User Interface) που αναλαμβάνει τον απομακρυσμένο έλεγχο της παραπάνω DSP εφαρμογής. Κατά την διεξαγωγή οποιουδήποτε από τα παραπάνω απόσταση πειράματα οι χρήστες μέσω μιας κατάλληλα σχεδιασμένης ιστοσελίδας έχουν την δυνατότητα να ελέγχουν απομακρυσμένα τα διαθέσιμα εργαστηριακά όργανα. Στην συνέχεια προτείνεται ένα RL στην ψηφιακή επεξεργασία εικόνας με DSPs που ονομάζεται R-DImPr Lab (Remote Digital Image Processing Laboratory). Το συγκεκριμένο RL επιτρέπει την επιβεβαίωση μιας DSP εφαρμογής που αναπτύχθηκε από τον χρήστη αξιοποιώντας το API (Application Program Interface) του R-DImPr Lab. Η DSP εφαρμογή αναλαμβάνει την ψηφιακή επεξεργασία εικόνων που λαμβάνονται από τον διαθέσιμο αισθητήρα εικόνας. Κατά την διεξαγωγή του από απόσταση πειράματος ο χρήστης μέσω της ιστοσελίδας του RL αφού επιλέξει τις ρυθμίσεις του αισθητήρα εικόνας, έχει την δυνατότητα να παρατηρήσει τόσο στην αρχική όσο και στην επεξεργασμένη εικόνα. Με σκοπό την διεύρυνση των δυνατοτήτων του R-DimPr Lab σχεδιάστηκε και αναπτύχθηκε ένα σύστημα επεξεργασίας εικόνας με DSPs το οποίο παρέχει στους χρήστες την δυνατότητα να διεξάγουν από απόσταση πειράματα ελέγχοντας απομακρυσμένα, τόσο την λειτουργία της αντίστοιχης DSP εφαρμογής όσο και την θέση του αισθητήρα εικόνας. Ο έλεγχος της θέσης του αισθητήρα εικόνας επιτυγχάνεται μέσω ενός μηχανισμού κίνησης που βασίζεται σε δύο βηματικούς κινητήρες και επιτρέπει την περιστροφή του αισθητήρα εικόνας σε δύο άξονες. Επιπρόσθετα, διερευνείται η δυνατότητα ανάπτυξης από απόσταση πειραμάτων στην ψηφιακή επεξεργασία εικόνας με DSPs από τους χρήστες αξιοποιώντας το R-DSP Lab. Τέλος, προτείνεται ένα RL στην αρχιτεκτονική των υπολογιστών που επιτρέπει στους χρήστες να προγραμματίσουν σε assembly μια από τις δύο διαθέσιμες CPUs (Central Processing Units). Κατά την διαδικασία επιβεβαίωσης, αρχικά φορτώνεται στο FPGA (Field Programmable Gate Array) της διαθέσιμης αναπτυξιακής πλατφόρμας η υλοποίηση του συστήματος που βασίζεται στην επιλεγμένη CPU. Στην συνέχεια μέσω του GUI της ιστοσελίδας του προτεινόμενου RL, οι χρήστες έχουν την δυνατότητα να παρατηρήσουν βήμα προς βήμα τις μικρο-λειτουργίες που λαμβάνουν χώρα στην επιλεγμένη CPU κατά την εκτέλεση του προγράμματος. / The subject of this Ph.D. dissertation deals with the development of a flexible and expandable architecture which will be exploited in the design of systems for the conduction of remote experiments. These systems are referred as RLs (Remote Laboratories) and allow the users to handle remotely the available laboratory equipment in order to perform remote experiments. Significant scientific efforts which deal with the development of RLs in several cognitive fields, have been documented in the international literature. However, even today a commonly accepted architecture for the development of RLs has not been adopted by the scientific community. At the beginning, an architecture for the development of RLs which is called ARIAL (ARchitecture of Internet Accessible Laboratories) and is independent of the cognitive field of the supported remote experiments, is proposed. This architecture is also independent of both the hardware and the software which will be utilized for the development of the corresponding RL. The ARIAL consists of two structural elements, the MWS (Main Web Server) and the WS (WorkStation). The MWS undertakes the management of the users and the available WSs. Each one of the multiple WSs is exclusively responsible for the conduction of the supported remote experiments. The communication between the MWS and the WSs is achieved through an internet accessible database. Therefore, the WSs can be installed in any geographic location allowing the development of federal RLs. However, the most important feature of the proposed architecture which contributes decisively to the sustainability of a RL, is the support of remote experiments designed and implemented by the users. In order to confirm the ARIAL, this Ph.D. dissertation also proposes a RL in digital signal processing with DSPs which is called R-DSP Lab (Remote Digital Signal Processors Laboratory). The R-DSP Lab provides the users with the ability either to perform one of the predefined remote experiments or to confirm the operation of a DSP application which is developed by them. In addition, the proposed RL allows the development of remote experiments by the users. In this case, the users implement offline both the desired DSP application and the GUI (Graphical User Interface) which undertakes the remote control of the above DSP application. During the conduction of the above remote experiments, the users are able to remote control the available laboratory instruments through a carefully designed web page. Subsequently, a RL in digital image processing with DSPs which is called R-DImPr Lab (Remote Digital Image Processing Laboratory), is also proposed. This RL allows the verification of a DSP application developed by the user utilizing the API (Application Program Interface) of R-DImPr Lab. The DSP application undertakes the digital process of images which are captured by the available image sensor. During the conduction of the remote experiment, the user through the web page of the proposed RL, selects the parameters of the image sensor and observes both the original and the processed image. In order to expand the features of the R-DImPr Lab, a digital image processing system based on DSPs was designed and developed. This system allows the users to perform remote experiments by controlling remotely both the DSP application and the position of the image sensor. The control of the image sensor’s position is achieved through a motion actuator which is based on two stepper motors and allows the rotation of the image sensor in two axes. In addition, this Ph.D. dissertation explores the possibility of the development of remote experiments in digital image processing with DSPs by the users utilizing the features of the R-DSP Lab. Finally, a RL in computer architecture which allows the users to program in assembly language one of the two available CPUs (Central Processing Units), is proposed. During the verification process, the implementation of the system which is based on the selected CPU, is loaded into the FPGA (Field Programmable Gate Array) of the available development platform. The users through the GUI of the proposed RL’s web page, are able to observe the micro-operations which take place in the selected CPU during the step by step program execution.

Οι σημερινές εφαρμογές έχουν ολοένα και μεγαλύτερες ανάγκες επεξεργαστικής ισχύος προκειμένου να εκτελεστούν σε συντομότερο χρονικό διάστημα. Για να την ικανοποίηση αυτών των χρονικών περιορισμών απαιτείται η ανάπτυξη βελτιστοποιημένων τεχνικών σχεδιασμού. Το αντικείμενο της παρούσας διατριβής σχετίζεται με την ανάπτυξη αρχιτεκτονικών και τεχνικών μεταφραστών με σκοπό την γρηγορότερη τροφοδότηση του επεξεργαστή με δεδομένα από την ιεραρχία μνήμης. α) Μεθοδολογία επιτάχυνσης εκτέλεσης εφαρμογής πολλαπλασιασμού πινάκων Παρουσιάζεται μία μεθοδολογία που βασίζεται στην τοπικότητα των δεδομένων με σκοπό την επιτάχυνση εκτέλεσης του πολλαπλασιασμού πινάκων. Μετά από διερεύνηση, παράγεται ο βέλτιστος τρόπος χρονοπρογραμματισμού των προσπελάσεων στη μνήμη λαμβάνοντας υπόψη την τοπικότητα των δεδομένων και τα μεγέθη των επιπέδων ιεραρχίας μνήμης. Ο χρόνος διερεύνησης είναι σύντομος καθώς απορρίπτονται όλες οι μη-βέλτιστες λύσεις. Η προτεινόμενη μεθοδολογία συγκρίνεται με άλλες υπάρχουσες και παρατηρείται αύξηση της απόδοσης μέχρι 55%. β)Mεθοδολογία αποδοτικής υλοποίησης του Fast Fourier Transform (FFT) Παρουσιάζεται μια νέα μεθοδολογία, που επιτυγχάνει βελτιωμένη απόδοση στην υλοποίηση του FFT, έχοντας ως γνώμονα την ελαχιστοποίηση των προσπελάσεων που πραγματοποιούνται στα δεδομένα. Η προτεινόμενη μεθοδολογία έχει σημαντικά πλεονεκτήματα. Πρώτον, την πλήρη αξιοποίηση της παραγωγής και της κατανάλωσης των αποτελεσμάτων των πεταλούδων του FFT αλγορίθμου, της επαναχρησιμοποίησης δεδομένων και της συμμετρίας των twiddle συντελεστών του FFT αλγορίθμου. Δεύτερον, η βέλτιστη λύση χρονοπρογραμματισμού βρίσκεται λαμβάνοντας υπόψη τόσο τον αριθμό των καταχωρητών, όσο και το μέγεθος της κρυφής μνήμης κάθε επιπέδου, αναζητώντας μόνο τον αριθμό του επιπέδου του tiling του FFT. Τρίτον, ο χρόνος μετάφρασης και το μέγεθος του πηγαίου κώδικα είναι πολύ μικροί συγκρινόμενοι με την SOA βιβλιοθήκη υλοποίησης του FFT αλγορίθμου, την FFTW. Η προτεινόμενη μεθοδολογία επιτυγχάνει αύξηση της απόδοσης μέχρι και 63% σε σχέση με την βιβλιοθήκη FFTW. γ)Ανάπτυξη Αρχιτεκτονικών για Διαχείριση Μνήμης Παρουσιάζεται μια αποσυζευγμένη αρχιτεκτονική επεξεργαστών με μια ιεραρχία μνήμης που αποτελείται μόνο από μνήμες scratch-pad, και μια κύρια μνήμη. Η αρχιτεκτονική αυτή εκμεταλλεύεται τα οφέλη των scratch-pad μνημών και τον παραλληλισμό μεταξύ της επεξεργασίας δεδομένων και υπολογισμού διευθύνσεων. Η αρχιτεκτονική συγκρίνεται στην απόδοση με την αρχιτεκτονική MIPS με cache και με scratch-pad ιεραρχίες μνήμης και παρουσιάζεται η υψηλότερη απόδοσή της. Τα πειραματικά αποτελέσματα δείχνουν ότι η απόδοση αυξάνεται μέχρι 3,7 φορές. Στη συνέχεια γίνεται περαιτέρω έρευνα σε αρχιτεκτονικές με Scratch-pad μνήμες. Παρουσιάζεται μια αρχιτεκτονική που είναι σε θέση να παρέχει πληροφορίες για το ακριβές περιεχόμενο δεδομένων της scratch-pad, κατά τη διάρκεια της εκτέλεσης και μπορεί επίσης να εκτελέσει όλες τις απαραίτητες ενέργειες για την τοποθέτηση των νέων δεδομένων στη scratch-pad. Με αυτόν τον τρόπο, αξιοποιείται η επαναχρησιμοποίηση δεδομένων που εμφανίζεται τυχαία και δεν μπορεί να προσδιοριστεί από το μεταγλωττιστή. Συγκρίνεται με αρχιτεκτονική MIPS που περιέχει cache και με scratch-pad μνήμες και αναδεικνύεται η μεγαλύτερη απόδοσή της. Τα πειραματικά αποτελέσματα δείχνουν ότι η απόδοση αυξάνεται μέχρι 5 φορές έναντι των αρχιτεκτονικών με scratch-pad και 2.5 φορές έναντι των αρχιτεκτονικών με cache. / Modern applications have indence needs in processing power in order to be executed in short time. For satisfying the time limits, there have to be generated new techniques for optimizing the designs. The object of the present thesis is about developing new compiler techniques and hardware architectures which aim to transfer data faster, from the memory hierarchy to the CPU. a) Methdology for accelerating the execution of matrix multiplications A new methodology using the standard MMM algorithm is presented, achieving improved performance by focusing on data locality (both temporal and spatial). This methodology finds the scheduling which conforms with the optimum memory management. The scheduling used for the tile level is different from the element level’s one, having better data locality, suited to the sizes of memory hierarchy. Its exploration time is short, because it searches only for the number of the level of tiling used for finding the best tile size for each cache level. Compared with the best existing related work, which we implemented, better performance up to 55% β)Methodology for increasing performance on Fast Fourier Transform (FFT) A new methodology is presented based on minimizing the memory accesses for FFT. It exploits, the production and comsumption of the FFT batterfly results and the reuse of data. The optimum scheduling solution is found taking into account the number of registers and the cache memory size. The compile time and source code size are short comparing to SOA library. The methodology performance gains are up to 63% comparing to FFTW library. γ)Ανάπτυξη Αρχιτεκτονικών για Διαχείριση Μνήμης A decoupled processors architecture with a memory hierarchy is presented consisting only of scratch–pad memories, and a main memory. This architecture exploits both the benefits of scratch-pad memories and the parallelism between address computation and application data processing. The architecture is compared in performance with the MIPS architecture with cache and with scratch-pad memory hierarchies and with the existing decoupled architectures showing its higher normalized performance. Experimental results show that the performance is increased up to 3.7 times. Continuing, more research is done on Scratch-pad memories. We present an architecture that is able to provide information about the exact data contents of scratch-pad during execution and can also do all the necessary operations for placing the new data blocks in scratch-pad. Thereby, the temporal locality which occurs randomly and can not be identified by the compiler is exploited. It is compared with the MIPS architecture with cache and with scratch-pad memories showing its higher normalized performance. Experimental results show that the performance is increased up to 5 times compared to cache architectures and 2,5 times compared to existing scratch-pad architectures.

Μια από τις συνεχώς εξελισσόμενες περιοχές της επιστήμης των υπολογιστών είναι η Υπολογιστική Όραση, σκοπός της οποίας είναι η δημιουργία έξυπνων συστημάτων για την ανάκτηση πληροφοριών από πραγματικές εικόνες. Πολλές σύγχρονες εφαρμογές της υπολογιστικής όρασης βασίζονται στην αντιστοίχιση εικόνων. Την πλειοψηφία των αλγορίθμων αντιστοίχισης συνθέτουν παραμετρικές τεχνικές, σύμφωνα με τις οποίες υιοθετείται ένα παραμετρικό μοντέλο, το οποίο εφαρμοζόμενο στη μια εικόνα δύναται να παρέχει μια προσέγγιση της άλλης. Στο πλαίσιο της διατριβής μελετάται εκτενώς το πρόβλημα της Στερεοσκοπικής Αντιστοίχισης και το γενικό πρόβλημα της Ευθυγράμμισης Εικόνων. Για την αντιμετώπιση του πρώτου προβλήματος προτείνεται ένας τοπικός αλγόριθμος διαφορικής αντιστοίχισης που κάνει χρήση μιας νέας συνάρτησης κόστους, του Τροποποιημένου Συντελεστή Συσχέτισης (ECC), η οποία ενσωματώνει το παραμετρικό μοντέλο μετατόπισης στον κλασικό συντελεστή συσχέτισης. Η ενσωμάτωση αυτή καθιστά τη νέα συνάρτηση κατάλληλη για εκτιμήσεις ανομοιότητας με ακρίβεια μικρότερη από αυτήν του εικονοστοιχείου. Αν και η συνάρτηση αυτή είναι μη γραμμική ως προς την παράμετρο μετατόπισης, το πρόβλημα μεγιστοποίησης έχει κλειστού τύπου λύση με αποτέλεσμα τη μειωμένη πολυπλοκότητα της διαδικασίας της αντιστοίχισης με ακρίβεια υπο-εικονοστοιχείου. Ο προτεινόμενος αλγόριθμος παρέχει ακριβή αποτελέσματα ακόμα και κάτω από μη γραμμικές φωτομετρικές παραμορφώσεις, ενώ η απόδοσή του υπερτερεί έναντι γνωστών στη διεθνή βιβλιογραφία τεχνικών αντιστοίχισης ενώ φαίνεται να είναι απαλλαγμένος από το φαινόμενο pixel locking. Στην περίπτωση του προβλήματος της ευθυγράμμισης εικόνων, η προτεινόμενη συνάρτηση γενικεύεται με αποτέλεσμα τη δυνατότητα χρήσης οποιουδήποτε δισδιάστατου μετασχηματισμού. Η μεγιστοποίησή της, η οποία αποτελεί ένα μη γραμμικό πρόβλημα, επιτυγχάνεται μέσω της επίλυσης μιας ακολουθίας υπο-προβλημάτων βελτιστοποίησης. Σε κάθε επανάληψη επιβάλλεται η μεγιστοποίηση μιας μη γραμμικής συνάρτησης του διανύσματος διορθώσεων των παραμέτρων, η οποία αποδεικνύεται ότι καταλήγει στη λύση ενός γραμμικού συστήματος. Δύο εκδόσεις του σχήματος αυτού προτείνονται: ο αλγόριθμος Forwards Additive ECC (FA-ECC) και o αποδοτικός υπολογιστικά αλγόριθμος Inverse Compositional ECC (IC-ECC). Τα προτεινόμενα σχήματα συγκρίνονται με τα αντίστοιχα (FA-LK και SIC) του αλγόριθμου Lucas-Kanade, ο οποίος αποτελεί σημείο αναφοράς στη σχετική βιβλιογραφία, μέσα από μια σειρά πειραμάτων. Ο αλγόριθμος FA-ECC παρουσιάζει όμοια πολυπλοκότητα με τον ευρέως χρησιμοποιούμενο αλγόριθμο FA-LΚ και παρέχει πιο ακριβή αποτελέσματα ενώ συγκλίνει με αισθητά μεγαλύτερη πιθανότητα και ταχύτητα. Παράλληλα, παρουσιάζεται πιο εύρωστος σε περιπτώσεις παρουσίας προσθετικού θορύβου, φωτομετρικών παραμορφώσεων και υπερ-μοντελοποίησης της γεωμετρικής παραμόρφωσης των εικόνων. Ο αλγόριθμος IC-ECC κάνει χρήση της αντίστροφης λογικής, η οποία στηρίζεται στην αλλαγή των ρόλων των εικόνων αντιστοίχισης και συνδυάζει τον κανόνα ενημέρωσης των παραμέτρων μέσω της σύνθεσης των μετασχηματισμών. Τα δύο αυτά χαρακτηριστικά έχουν ως αποτέλεσμα τη δραστική μείωση του υπολογιστικού κόστους, ακόμα και σε σχέση με τον SIC αλγόριθμο, με τον οποίο βέβαια παρουσιάζει παρόμοια συμπεριφορά. Αν και ο αλγόριθμος FA-ECC γενικά υπερτερεί έναντι των τριών άλλων αλγορίθμων, η επιλογή μεταξύ των δύο προτεινόμενων σχημάτων εξαρτάται από το λόγο μεταξύ ακρίβειας αντιστοίχισης και υπολογιστικού κόστους. / Computer Vision has been recently one of the most active research areas in computer society. Many modern computer vision applications require the solution of the well known image registration problem which consist in finding correspondences between projections of the same scene. The majority of registration algorithms adopt a specific parametric transformation model, which is applied to one image, thus providing an approach of the other one. Towards the solution of the Stereo Correspondence problem, where the goal is the construction of the disparity map, a local differential algorithm is proposed which involves a new similarity criterion, the Enhanced Correlation Coefficient (ECC). This criterion is invariant to linear photometric distortions and results from the incorporation of a single parameter model into the classical correlation coefficient, defining thus a continuous objective function. Although the objective function is non-linear in translation parameter, its maximization results in a closed form solution, saving thus much computational burden. The proposed algorithm provides accurate results even under non-linear photometric distortions and its performance is superior to well known conventional stereo correspondence techniques. In addition, the proposed technique seems not to suffer from pixel locking effect and outperforms even stereo techniques, dedicated to the cancellation of this effect. For the image alignment problem, the maximization of a generalized version of ECC function that incorporates any 2D warp transformation is proposed. Although this function is a highly non-linear function of the warp parameters, an efficient iterative scheme for its maximization is developed. In each iteration of the new scheme, an efficient approximation of the nonlinear objective function is used leading to a closed form solution of low computational complexity. Two different iterative schemes are proposed; the Forwards Additive ECC (FA-ECC) and the Inverse Compositional ECC (IC-ECC) algorithm. Τhe proposed iterative schemes are compared with the corresponding schemes (FA-LK and SIC) of the leading Lucas-Kanade algorithm, through a series of experiments. FA-ECC algorithm makes use of the known additive parameter update rule and its computational cost is similar to the one required by the most widely used FA-LK algorithm. The proposed iterative scheme exhibits increased learning ability, since it converges faster with higher probability. This superiority is retained even in presence of additive noise and photometric distortion, as well as in cases of over-modelling the geometric distortion of the images. On the other hand, IC-ECC algorithm makes use of inverse logic by swapping the role of images and adopts the transformation composition update rule. As a consequence of these two options, the complexity per iteration is drastically reduced and the resulting algorithm constitutes the most computationally efficient scheme than three other above mentioned algorithms. However, empirical learning curves and probability of convergence scores indicate that the proposed algorithm has a similar performance to the one exhibited by SIC. Though FA-ECC seems to be clearly more robust in real situation conditions among all the above mentioned alignment algorithms, the choice between two proposed schemes necessitates a trade-off between accuracy and speed.

Η ασφάλεια των υπολογιστικών συστημάτων αποτελεί πλέον μια πολύ ενεργή περιοχή και αναμένεται να γίνει μια νέα παράμετρος σχεδίασης ισάξια μάλιστα με τις κλασσικές παραμέτρους σχεδίασης των συστημάτων, όπως είναι η απόδοση, η κατανάλωση ισχύος και το κόστος. Οι φερέγγυες υπολογιστικές πλατφόρμες έχουν προταθεί σαν μια υποσχόμενη λύση, ώστε να αυξήσουν τα επίπεδα ασφάλειας των συστημάτων και να παρέχουν προστασία από μη εξουσιοδοτημένη άδεια χρήσης των πληροφοριών που είναι αποθηκευμένες σε ένα σύστημα. Ένα φερέγγυο σύστημα θα πρέπει να διαθέτει τους κατάλληλους μηχανισμούς, ώστε να είναι ικανό να αντιστέκεται στο σύνολο, τόσο γνωστών όσο και νέων, επιθέσεων άρνησης υπηρεσίας. Οι επιθέσεις αυτές μπορεί να έχουν ως στόχο να βλάψουν το υλικό ή/και το λογισμικό του συστήματος. Ωστόσο, η μεγαλύτερη βαρύτητα στην περιοχή έχει δοθεί στην αποτροπή επιθέσεων σε επίπεδο λογισμικού. Στην παρούσα διατριβή προτείνονται έξι μεθοδολογίες σχεδίασης ικανές να θωρακίσουν ένα υπολογιστικό σύστημα από επιθέσεις άρνησης υπηρεσίας που έχουν ως στόχο να πλήξουν το υλικό του συστήματος. Η κύρια έμφαση δίνεται στο υποσύστημα της μνήμης (κρυφές μνήμες). Στις κρυφές μνήμες αφιερώνεται ένα μεγάλο μέρος της επιφάνειας του ολοκληρωμένου, είναι αυτές που καλούνται να "αποκρύψουν" τους αργούς χρόνους απόκρισης της κύριας μνήμης και ταυτόχρονα σε αυτές οφείλεται ένα μεγάλο μέρος της συνολικής κατανάλωσης ισχύος. Ως εκ τούτου, παρέχοντας βελτιστοποιήσεις στις κρυφές μνήμες καταφέρνουμε τελικά να μειώσουμε τον χρόνο εκτέλεσης του λογισμικού, να αυξήσουμε το ρυθμό μετάδοσης των ψηφιακών δεδομένων και να θωρακίσουμε το σύστημα από επιθέσεις άρνησης υπηρεσίας σε επίπεδο υλικού. / Data security concerns have recently become very important, and it can be expected that security will join performance, power and cost as a key distinguish factor in computer systems. Trusted platforms have been proposed as a promising approach to enhance the security of the modern computer system and prevent unauthorized accesses and modifications of the sensitive information stored in the system. Unfortunately, previous approaches only provide a level of security against software-based attacks and leave the system wide open to hardware attacks. This dissertation thesis proposes six design methodologies to shield a uniprocessor or a multiprocessor system against a various number of Denial of Service (DoS) attacks at the architectural and the operating system level. Specific focus is given to the memory subsystem (i.e. cache memories). The cache memories account for a large portion of the silicon area, they are greedy power consumers and they seriously determine system performance due to the even growing gap between the processor speed and main memory access latency. As a result, in this thesis we propose methodologies to optimize the functionality and lower the power consumption of the cache memories. The goal in all cases is to increase the performance of the system, the achieved packet throughput and to enhance the protection against a various number of passive and Denial of Service attacks.

Οι ενσωματωμένες συσκευές αποτελούν μια κατηγόρια υπολογιστών ειδικού σκοπού με ραγδαία αύξηση τα τελευταία χρόνια. Σε αντίθεση με τους γνωστούς σε όλους υπολογιστές γενικού σκοπού που μπορούν να επιτελέσουν σχεδόν οποιαδήποτε λειτουργία, οι ενσωματωμένες συσκευές επιτελούν μόνο συγκεκριμένες λειτουργίες, οι οποίες είναι προκαθορισμένες κατά τον σχεδιασμό τους. Η διαχείριση τέτοιων και μη συσκευών αποτελεί ένα τεράστιο κεφάλαιο αφού η διαφορετικότητα των λειτουργιών τους, δημιουργεί ένα διαφορετικό τρόπο αντιμετώπισης τους κατά την πρακτική της διαχείρισης. Υπάρχει περιορισμός στα διαθέσιμα εργαλεία για την διαχείριση όλων των ενσωματωμένων συστημάτων με ένα εργαλείο, αλλά η ερεύνα μας επικεντρώνεται στη διαχείριση οικογενειών τέτοιων συσκευών με κριτήριο τη λειτουργία του ειδικού σκοπού που επιτελούν. Σκοπός λοιπόν της εργασίας είναι ο σχεδιασμός και η ανάπτυξη λογισμικού για την ομαδική διαχείριση οικογένειας ενσωματωμένων συσκευών και κοινών υπολογιστών γενικού σκοπού οπουδήποτε λειτουργικού συστήματος. Η συνεισφορά της υπάρχουσας εργασίας συνοψίζεται στις εξής συνιστώσες: 1. Οι ενσωματωμένες συσκευές στις οποίες επικεντρωθήκαμε αφορούν δικτυακές συσκευές (ασύρματες ή ενσύρματες) πολλών λειτουργιών (Access Points, Clients, Repeaters,Points to Points, WDS, Transparent Clients, Routers). 2. Το λογισμικό για υπολογιστές ειδικού σκοπού που δημιουργήθηκε μπορεί να εκτελεστεί τόσο σε λειτουργικά συστήματα MS Windows όσο και σε *ΝΙΧ. 3. Η ανάπτυξη του λογισμικού έγινε βάση του συστήματος ORSM, το οποίο είναι ένα εργαλείο ανοικτού κώδικα για την απομακρυσμένη διαχείριση συστημάτων και δικτύων. (Με αστερίσκο * τόσο στα περιεχόμενα όσο και στο κύριο μέρος της εργασίας δείχνουμε τις δυνατότητες του νέου λογισμικού σε σχέση με το σύστημα ORSM). Συνοπτικά οι δυνατότητες διαχείρισης αφορά τις παρακάτω λειτουργίες: • Ανακάλυψη περιουσιακών στοιχείων (Inventory Process). • Παρακολούθηση απόδοσης συστημάτων (Monitoring). • Εγκατάσταση και απεγκατάσταση λογισμικού (Software Deployment). • Απομακρυσμένο έλεγχο (Remote Desktop). • Εκτέλεση εντολών κελύφους (Remote Command). / An embedded system is a special-purpose computer system designed to perform one or a few dedicated functions, often with real-time computing constraints. It is usually embedded as a part of a complete device including hardware and mechanical parts. In contrast, a general-purpose computer, such as a personal computer, can do many different tasks depending on programming. Embedded systems control many of the common devices in use today. Managing infrastructure with such devices (embedded and general purpose computers) is usually demanding and expensive but nevertheless essential for organizations. There is a limit in tools which achieve effective management to those infrastructure topologies. At present, open management solutions are few and immature however there are tools such as OpenRSM aiming to deliver lightweight, remote and customizable management, easily customizable to cover the needs of small organizations. OpenRSM implements a generic management framework that models generalized use cases that can be exploited by users to adapt the tool to their needs. However, given maturity of the tool, it is unclear how easy it would be for users to extend it in order to include management of new types of devices. As network environments grow to digital ecosystems, the management targets increase in number and diversity. Wireless active elements, handheld systems or embedded devices are becoming common and need to be brought under standard management practices in the same manner as routers or workstations. This paper describes how the OpenRSM management functionality can be extended in order to provide customizable management of embedded devices and more specifically of wireless access points (the symbol * shows the new extension of ORSM). In general the management capabilities which are embed to OPENRSM system and target to wireless active elements are: (Inventory process, monitoring, firmware upgrade, save/reload configuration settings, remote commands, and discovery process).