- / -

Γνωριμία με την διαδικασία εξόρυξης γνώσης από δεδομένα και εφαρμογή των τεχνικών εξόρυξης γνώσης σε ιατρικά δεδομένα ασθενών με την χρήση της πλατφόρμας αλγορίθμων μηχανικής μάθησης Weka. / Getting to the process of data mining and applying data mining techniques in medical data of patients with the use of machine learning algorithms platform Weka.

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

Η διπλωματική εργασία αφορά στη δημιουργία βάσης δεδομένων για ινδολοκαρβαζολικά και φλαβονοειδικά παράγωγα. Τα δεδομένα που εισήχθησαν στη βάση αφορούν κυρίως στη δράση ινδολοκαρβαζολικών και φλαβονοειδικών αναλόγων στα σύμπλοκα CDKs/κυκλινών σε πολυάριθμες κυτταρικές σειρές. / The purpose of my master was the creation of a database for indolocarbazole and flavones derivates. The data were about the role of indolocarbazole and flavones derivates to the CDKW/cyclin complexes in many cell lines.

Αρχικά, γίνεται γενική αναφορά στις κατολισθητικές κινήσεις του Ελλαδικού χώρου, τα αίτια παραγωγής και γένεσης τους, τις συνέπειες από αυτό το αρκετά μεγάλο πρόβλημα της χώρας μας, καθώς επίσης και στη σημασία των μέτρων προστασίας που πρέπει να λαμβάνει η πολιτεία και οι κατά περίπτωση αρμόδιοι φορείς, για την αποφυγή και την θεραπεία των συνεπειών των κατολισθήσεων. Επίσης, γίνεται προσπάθεια ταξινόμησης των κατολισθητικών κινήσεων σε σχέση με τον τύπο κίνησης που εμφανίζουν αλλά και τον γεωλογικό σχηματισμό στον οποίο εκδηλώνονται, λαμβανομένων υπόψη των ιδιαίτερων συνθηκών που επικρατούν στα δύο μεγάλα τεχνικογεωλογικά διαμερίσματα του Ελληνικού χώρου (Ανατολικό-Δυτικό). Κατόπιν αυτού εξετάζονται συγκεκριμένα οι επι μέρους σχηματισμοί που δομούν την περιοχή μελέτης σχετικά με το είδος των κατολισθητικών κινήσεων που εκδηλώνονται σε αυτούς. Στην συνέχεια, γίνεται προσπάθεια δημιουργίας βάσης δεδομένων κατολισθήσεων στις πυρόπληκτες από τις μεγάλες πυρκαγιές του 2007 περιοχές του Νομού Ηλείας. Συγκεντρώθηκαν στοιχεία για 352 συνολικά κατολισθητικές κινήσεις στις εν λόγω περιοχές τα οποία και καταχωρήθηκαν σε βάση δεδομένων που έχει σχεδιασθεί με το λογισμικό Microsoft Access στο εργαστήριο Τεχνικής Γεωλογίας του Πανεπιστημίου Πατρών. Τέλος, στα στοιχεία αυτά έγινε στατιστική επεξεργασία με στόχο την εξαγωγή κρίσιμων συμπερασμάτων για την εκτίμηση της κατανομής των κατολισθήσεων σε σχέση με τα τεχνικογεωλογικά δεδομένα της περιοχής αλλά και την επίδραση που είχαν τα φαινόμενα των πυρκαγιών στην εκδήλωση των κατολισθητικών φαινομένων. Ιδιαίτερη σημασία δίνεται στα προτεινόμενα μέτρα προστασίας από τις κατολιθητικές κινήσεις των οποίων η επιλογή έχει γίνει με βάση το χαμηλό κόστος κατασκευής και την μέγιστη δυνατή αποτελεσματικότητα. / This project have been carried out in the framework of the Postgraduate studies of "Applied and Environmental Geology" of the Geology Department of the University of Patras. Firstly there is an overview of the landslides in the greater Greek Region, the landslide causes, the consequences of this major problem and the meaning of the remedial measures that the state must take in order to avoid those consequences, as well. Also there is an attempt of classification of landslides in relation with the type of the movement and the geological data at the unstable areas, considering the prevailing circumstances at the two major geological parts of our country (East and West). After that, there is a distinctly inspect of the geological data in the project area. Secondly there is an attempt of creation a landslide Database which is filled of clues from landslides that they took place at the areas that were harmed by the 2007 blazes at the Ilias Prefecture. The clues have been gathered from 352 landslides that they happened in the period 2007-2009. Those clues have been registered at the landslide Database which was designed with the Microsoft Access software at the Technical Geology Laboratory at the University of Patras. Finally the clues have been statistical processed and analyzed in order to extract some conclusions for the evaluation of the landslides allocation according to geological data and the influence of the blazes. A particular importance reference is done for the remedial measures that they were chosen by the low cost of construction and the maximum effectiveness.

- / -

Είδαμε τα μοντέλα της DEA και της worst practice DEA. Δείξαμε πώς το μοντέλο της DEA, στοχεύοντας στον προσδιορισμό των εταιρειών που είναι αναποτελεσματικές στο να είναι καλές και το μοντέλο της worst practice DEA, στοχεύοντας στον προσδιορισμό των εταιρειών που είναι αποτελεσματικές στο να είναι κακές, μπορούν να χρησιμοποιηθούν για να εντοπίσουν τις χειρότερες επιδόσεις, δίνοντας σημαντικές πληροφορίες για την αξιολόγηση του πιστωτικού κινδύνου. Επιπλέον, δείξαμε πώς η χρήση μιας τεχνικής διαστρωμάτωσης δίνει μεγάλη ακρίβεια την ταξινόμηση. Η προσέγγιση της διαστρωμάτωσης έχει επίσης το πλεονέκτημα της ευελιξίας, αφού δίνει την δυνατότητα της επιλογής των επιπέδων που κάποιος επιθυμεί να εξετάσει το ενδεχόμενο. Με αυτό τον τρόπο επιτρέπεται η ενσωμάτωση των συμπεριφορών κινδύνου και η δυνατότητα της τιμολόγησης με βάση τον κίνδυνο, με διαφορετικές τιμές (επιτόκια) στα διάφορα επίπεδα. Τέλος, συνδυάζοντας κανονικά και worst practice μοντέλα αναμέναμε πιο σαφή αποτελέσματα για τις χειρότερες αποδοτικές εταιρείες και το επίπεδο κινδύνου που κατέχουν, λόγω όμως του μικρού αριθμού εταιρειών που είχαμε προς εξέταση δεν είχαμε τα αναμενόμενα αποτελέσματα. Η ιδέα της χρησιμοποίησης των χειρότερων πρακτικών DEA αποσκοπεί ειδικά στην καταγραφή των χειρότερων αποδόσεων και προφανώς σχετίζεται με την αξιολόγηση της πιστοληπτικής ικανότητας, αλλά έχει και μια γενικότερη χρήση. Σε μια τυποποιημένη ανάλυση της παραγωγικότητας χρησιμοποιώντας ένα συνδυασμό των κανονικών και των worst practice DEA μοντέλων σημαίνει την εξεύρεση τόσο των καλών επιδόσεων που θα πρέπει να ανταμείβονται και να χρησιμοποιηθούν ως στόχοι για τις άλλες, καθώς και των χειρότερων που είναι οι μεγαλύτερες δυνατότητες εξοικονόμησης που μπορεί να βρεθούν. Μία ενδιαφέρουσα συνέχεια της προσέγγισης θα ήταν, εάν είχαμε τα στοιχεία των εταιρειών του έτους 2007, να εφαρμόζαμε με τον ίδιο τρόπο το κανονικό μοντέλο DEA, το μοντέλο worst practice DEA και τον συνδυασμό τους ώστε να επικυρώσουμε την προσέγγιση που δοκιμάζουμε με το να επιτυγχάναμε το ίδιο επίπεδο ταξινόμησης στο νέο σύνολο δεδομένων. Παρουσιάσαμε επίσης τα μοντέλα του WPF-SBM και HypoSBM στην έννοια της χειρότερης πρακτικής. Η εφαρμογή του μοντέλου HypoSBM όχι μόνο κάνει διάκριση μεταξύ εκείνων που λαμβάνονται ως χειρότερες επιδόσεις από το WPF-SBM μοντέλο, αλλά ανταποκρίνεται και στην πραγματική κατάσταση, όπου υπάρχει μόνο ένα μικρό μέρος των επιχειρήσεων που καταθέτουν πτώχευση σε ένα μέσο έτος. Η αναλογία πτωχυμένων προς υγιείς επιχειρήσεις πρέπει να εξαρτάται από την περιοχή ή χώρα όπου η βιομηχανία βρίσκεται και τον οικονομικό κύκλο (ύφεση ή ανάκαμψη). Στη συνέχεια παίρνουμε μια πλήρη κατάταξη για τις χειρότερες αποδόσεις στο χειρότερο σενάριο. Τα αποτελέσματα από την αριθμητική εικόνα σχετικά με την αξιολόγηση του επενδυτικού κινδύνου επικυρώνουν τα μοντέλα WPF-SBM και HypoSBM. Έτσι ο καλύτερος συνδυασμός της στρωματοειδούς WPF-SBM και HypoSBM μοντέλα αποδίδουν εντυπωσιακή πρόβλεψη πτώχευσης. Αυτό που θα μπορούσαμε να πούμε σχετικά με τον κατασκευαστικό κλάδο είναι ότι σύμφωνα με τα αποτελέσματα, φάνηκε να υπάρχει πρόβλημα στον κλάδο αφού οι εταιρείες που εμφανίζονται ως δυνητικά αποτυχημένες είναι οι 5 από τις 18 που εξετάσαμε και αυτό αποτελεί ένα αρκετά μεγάλο ποσοστό. Θα θέλαμε να αναφέρουμε ότι δεν υπάρχει τέλειο μοντέλο ή προσέγγιση για την αξιολόγηση των επιδόσεων, την αξιολόγηση των κινδύνων ή της πτώχευσης. Η προτεινόμενη προσέγγιση παρέχει μια νέα μεγάλη λεωφόρο για μελλοντικές έρευνες. Εάν ήταν εφικτό να είχαμε πρόσβαση σε δεδομένα περισσότερων εταιρειών, έτσι ώστε οι υγιείς εταιρείες να είναι αναλογικά πολύ περισσότερες από τις αποτυχημένες εταιρείες, θα μπορούσαμε να έχουμε ακόμη πιο ικανοποιητικά αποτελέσματα. Επίσης στην συγκεκριμένη πρακτική εφαρμογή, ενδιαφέρουσα μελλοντική εξέλιξη στην έρευνα θα ήταν να θέταμε κάποιους περιορισμούς στις εισροές και εκροές που χρησιμοποιούμαι αλλά και η σύγκριση των αποτελεσμάτων με άλλες τεχνικές. Για τις περιπτώσεις με ασαφή στοιχεία, αναμένονται νέα μοντέλα χειρότερης πρακτικής DEA. Πολλά από τα υπάρχοντα μοντέλα βέλτιστης πρακτικής DEA που χρησιμοποιούνται για την αντιμετώπιση των προβλημάτων θα μπορούσαν να αναθεωρηθούν σε μοντέλα χειρότερης πρακτικής DEA για να εξετάσουν το πρόβλημα από διαφορετική οπτική γωνία. Το μοντέλο μπορεί να χρησιμοποιηθεί για άλλες βιομηχανίες ανάληψης κινδύνου, όπως ο ασφαλιστικός κλάδος. Άλλες κατάλληλες διατυπώσεις επέκτασης του WPF-DEA μοντέλου, μαζί με άλλες προσεγγίσεις και εφαρμογές, είναι επίσης σημαντικό για να τονίσει την πρακτικότητα του. / This paper includes the use of combination of models which are called Worst Practice DEA (Data Envelopment Analysis)in slacks based measurement for the detection of potential bankrupt business with a practical example in construction industry.

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

Η εξόρυξη χώρο-χρονικών δεδομένων αποτελεί πλέον μία από τις σημαντικότερες κατευθύνσεις του κλάδου της εξόρυξης γνώσης. Κάποια από τα βασικά προβλήματα που καλείται να αντιμετωπίσει είναι η ανακάλυψη περιοχών που εμφανίζουν ομοιότητες στην χρονική τους εξέλιξη, η αναγνώριση προτύπων που εμφανίζονται τόσο στην χωρική όσο και στη χρονική πληροφορία, η πρόβλεψη μελλοντικών τιμών και η αποθήκευση σε εξειδικευμένες βάσεις δεδομένων με σκοπό την αποδοτική απάντηση χωροχρονικών ερωτημάτων. Οι μέθοδοι που προσεγγίζουν τα παραπάνω προβλήματα καθώς και οι βασικές εργασίες της εξόρυξης γνώσης, όπως η κατηγοριοποίηση και η ομαδοποίηση, εμφανίζονται στον πυρήνα της πλειονότητας των εργαλείων ανάλυσης και επεξεργασίας χώρο-χρονικών δεδομένων. Βασικός στόχος της παρούσας εργασίας είναι η εφαρμογή μεθόδων εξόρυξης χώρο-χρονικών δεδομένων στο Ηλεκτροεγκεφαλογράφημα (ΗΕΓ), το οποίο αποτελεί μία από τις πιο διαδεδομένες τεχνικές ανάλυσης της εγκεφαλικής λειτουργίας. Τα δεδομένα που προκύπτουν από το ΗΕΓ περιέχουν τόσο χωρική όσο και χρονική πληροφορία καθώς αποτελούνται από ηλεκτρικά σήματα που προέρχονται από ηλεκτρόδια τοποθετημένα σε συγκεκριμένες θέσεις στο κρανίο. Τα βασικά προβλήματα που μελετήθηκαν στην επεξεργασία του ΗΕΓ είναι η μοντελοποίηση και η συσταδοποίηση χώρο-χρονικών δεδομένων, τα οποία οδήγησαν στην ανάπτυξη των αντίστοιχων μεθόδων. Στα πλαίσια της παρούσας εργασίας μελετήθηκε επίσης το πρόβλημα της διαχείρισης των δεδομένων ΗΕΓ και τη ανάλυσης ροών δεδομένων σε πραγματικό χρόνο. Η ενασχόληση με τα συγκεκριμένα προβλήματα οδήγησε α) στη δημιουργία καινοτόμων μεθόδων μοντελοποίησης και συσταδοποίησης χωρο-χρονικών δεδομένων, β) στον σχεδιασμό μιας βάσης δεδομένων, γ) στην μελέτη της βιβλιογραφίας στο θέμα της εξόρυξης και της διαχείρισης ροών δεδομένων και δ) στην δημιουργία μιας εφαρμογής για την ανάλυση δεδομένων σε πραγματικό χρόνο πάνω σε ένα σύστημα διαχείρισης ροών δεδομένων. Η παρούσα εργασία περιλαμβάνει ένα ένα σύνολο μεθόδων και εργαλείων ανάλυσης και διαχείρισης δεδομένων που εξετάστηκαν και χρησιμοποιήθηκαν προκειμένου να μελετηθεί η καταλληλότητά της εφαρμογής τους στις καταγραφές ΗΕΓ. Με τον τρόπο αυτό επιτυγχάνεται ο πρωταρχικός στόχος της εργασίας: η προώθηση υπαρχόντων και η δημιουργία καινοτόμων μεθόδων ανάλυσης από τον κλάδο της εξόρυξης γνώσης στα δεδομένα του ηλεκτροεγκεφαλογραφήματος. / Mining spatiotemporal data is one of the most significant topics in the field of data mining and knowledge discovery. Detecting locations that exhibit similarities in their temporal evolution, recognizing patterns that appear in both spatial and temporal information and storing spatiotemporal data in specialized databases are some of the fundamental problems tackled by researchers in this specific area. Methods and algorithms that address such problems along with the common data mining tasks (e.g. classification and clustering) are critical in the development of applications for analyzing spatiotemporal data, fact that highlights the necessity of continuous advancements of these algorithms in terms of usability, accuracy and performance. The most significant objective of the work performed during this thesis is the application of spatiotemporal data mining methods on the analysis of EEG, in order to exploit the both the spatial and the temporal nature of these data (i.e. electrodes placed on specific locations on the scalp that continuously record the electrical activity of the brain). Towards this direction the problems of modeling and clustering spatiotemporal data were extensively studied and the major outcome was the development of two corresponding methods. Furthermore, during this work the problem of managing EEG data was investigated both in the offline and the online scenario and within the latter, the state of the art in mining data streams was studied. The outcomes of this thesis related to the aforementioned problems include a) the development of a graph-based method for modeling spatiotemporal data, b) a method for clustering spatiotemporal data based on this model, c) the design of a database schema for storing eeg recording data and meta-data and d) the development of an application for online spindle detection over a data stream management system. Finally, this work aims towards the development of new and the adaptation of existing data mining methods in the context of spatiotemporal EEG analysis.

Στα τέλη του 20ου αιώνα, οι παράλληλες εξελίξεις και η ανάπτυξη καινοτόμων μεθόδων και εργαλείων σε διαφορετικές ερευνητικές περιοχές είχε ως αποτέλεσμα την εμφάνιση των λεγόμενων "αναδυόμενων τεχνολογιών" (emerging technologies). Σε αυτό το πλαίσιο λοιπόν, των αναδυόμενων τεχνολογιών, εμφανίστηκε στο προσκήνιο η επιστήμη της Βιοπληροφορικής (Bioinformatics) η οποία αποτελεί την τομή των επιστημών της βιολογίας και της πληροφορικής. Η ραγδαία ανάπτυξη της τεχνολογίας έχει οδηγήσει στην εκρηκτική αύξηση του ρυθμού παραγωγής βιολογικών δεδομένων, γεγονός που καθιστά επιτακτική την ανάγκη της αποδοτικής και αποτελεσματικής διαχείρισης τους. Για την κάλυψη αυτής ακριβώς της ανάγκης δημιουργήθηκαν οι βιολογικές βάσεις δεδομένων που έχουν σήμερα εξαιρετική δυναμική και περιθώρια εφαρμογών. Οι βασικοί τομείς έρευνας στο πλαίσιο των βιολογικών βάσεων δεδομένων μπορούν να ταξινομηθούν σε τρεις μεγάλες κατηγορίες. Η πρώτη κατηγορία αφορά στην όσο το δυνατόν πιο αποδοτική οργάνωση των βιολογικών δεδομένων ώστε να είναι δυνατή η αποτελεσματική αποθήκευση τους. Αυτός ακριβώς είναι και ο λόγος δημιουργίας των βιολογικών βάσεων δεδομένων. Η δεύτερη κατηγορία αφορά στην ανάπτυξη εργαλείων και μεθόδων που επιτρέπουν την ανάλυση και την επεξεργασία των βιολογικών δεδομένων έτσι ώστε να διευκολυνθεί η διαδικασία ανακάλυψης γνώσης από αυτά. Σε αυτή την κατηγορία, σημαντικό ρόλο παίζουν οι τεχνικές εξόρυξης γνώσης οι οποίες εφαρμόζονται πάνω σε μεγάλες συλλογές βιολογικών δεδομένων και συνήθως οδηγούν στην ανακάλυψη νέων σχέσεων και προτύπων που κρύβονται ανάμεσα στα δεδομένα. Τέλος, η τρίτη κατηγορία αφορά στην ανάπτυξη εργαλείων που διευκολύνουν την διαδικασία της βιολογικής ερμηνείας των αποτελεσμάτων της εξόρυξης. Εδώ, ουσιαστικό ρόλο κατέχουν οι τεχνικές οπτικοποίησης της παραγόμενης γνώσης για την όσο το δυνατόν πιο κατανοητή παρουσίαση των συμπερασμάτων στον άνθρωπο ο οποίος στην συνέχεια θα επιλέξει ποια από αυτά είναι πραγματικά χρήσιμα. Η δημιουργία ενός ολοκληρωμένου συστήματος που θα αποτελεί τον απότοκο της τεχνολογικής σύζευξης των τεχνικών των τριών παραπάνω κατηγοριών σε συνδυασμό με την ανάγκη αξιοποίησης μιας μέχρι πρότινος ανεκμετάλλευτης μεγάλης συλλογής βιολογικών δεδομένων αποτέλεσαν το κίνητρο για την εκπόνηση της παρούσας διπλωματικής εργασίας. Στόχος της εργασίας είναι η ανάπτυξη ενός ολοκληρωμένου συστήματος το οποίο χρησιμοποιώντας την τεχνολογία Microsoft PivotViewer θα απεικονίζει την παραπάνω συλλογή δεδομένων προσφέροντας ένα υψηλό επίπεδο αναπαράστασης και θα καταγράφει τις συχνότητες εμφάνισης των μεταλλάξεων και άλλων γενετικών παραλλαγών ανά πληθυσμιακές ομάδες σε παγκόσμια κλίμακα. Το σύστημα αυτό θα μπορεί να λειτουργήσει ως ένα σύγχρονο εκπαιδευτικό και διαγνωστικό εργαλείο για την πληθυσμιακή μελέτη της παθογένειας και της θεραπείας ασθενειών που οφείλονται σε κάποια γενετική διαταραχή. Ο χρήστης διαμέσου ενός εύχρηστου και φιλικού περιβάλλοντος διεπαφής θα μπορεί να εστιάσει από μια μεγάλη συλλογή δεδομένων σε ένα εξειδικευμένο υποσύνολό της που ενδεχομένως σχετίζεται με μία συγκεκριμένη ασθένεια, μία συγκεκριμένη μελέτη ή έναν συγκεκριμένο πληθυσμό παρατηρώντας έτσι τα δεδομένα αυτά από μια διαφορετική οπτική γωνία που ενδεχομένως να τον βοηθήσει να ανακαλύψει νέα πρότυπα και σχέσεις ανάμεσα τους αξιόλογης βιολογικής σημασίας. / In the late 20th century, parallel advances and the development of innovative methods and tools in different research areas resulted in the appearance of the so-called "emerging technologies". In the framework of emerging technologies, the science of Bioinformatics came to the fore which is the intersection of the sciences of biology and informatics. The rapid growth of technology has led to the explosive increase in the rate of production of biological data, which dictates the need for efficient and effective data management. Biological databases have been created to satisfy exactly this need and they have extremely dynamic and potential applications today. The main research areas in biological databases can be classified into three broad categories. The first category concerns the better organization of the biological data so as to enable efficient storage. This is the reason for the development of the biological databases. The second category concerns the development of tools and methods that allow analysis and processing of biological data to facilitate the process of discovering knowledge from them. In this category, data mining techniques play an important role. They are applied over large collections of biological data and often lead to the discovery of new relationships and patterns that lie between the data. Finally, the third category involves the development of tools that facilitate the process of understanding and visualizing the biological meaning of the data mining results. Here, the visualization techniques have an essential role in presenting the data mining results in a meaningful way to the scientists who will eventually decide which of these results are really useful and reliable. The development of an integrated system which will be the result of the technological coupling of the three above categories in conjunction with the need of utilization a previously unexploited large collection of biological data was the motivation for the elaboration of this thesis. This work aims to develop an integrated system which represents the above collection providing a high level visualization and records the frequencies of causative genetic variations worldwide by utilizing the Microsoft PivotViewer technology. This system can serve as a modern educational and diagnostic tool for the population-based study of the pathogenesis and treatment of diseases caused by a genetic disorder. The user through a user-friendly interface can zoom in from the massive amounts of data to particular disease-specific, study-specific, or population-specific data so that he can begin observing the data from a different perspective that may enable him to discover new patterns and relationships between them of remarkable biological importance.