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

Made available in DSpace on 2014-06-12T15:53:11Z (GMT). No. of bitstreams: 2 arquivo1906_1.pdf: 1728491 bytes, checksum: 711dbaf0713ac324ffe904a6dace38d7 (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2009 / Conselho Nacional de Desenvolvimento Científico e Tecnológico / Albertins de Lima, Lucas; Cezar Alves Sampaio, Augusto. Test case prioritization based on data reuse for Black-box environments. 2009. Dissertação (Mestrado). Programa de Pós-Graduação em Ciência da Computação, Universidade Federal de Pernambuco, Recife, 2009.

BACKGROUND:Scientists rarely reuse expert knowledge of phylogeny, in spite of years of effort to assemble a great "Tree of Life" (ToL). A notable exception involves the use of Phylomatic, which provides tools to generate custom phylogenies from a large, pre-computed, expert phylogeny of plant taxa. This suggests great potential for a more generalized system that, starting with a query consisting of a list of any known species, would rectify non-standard names, identify expert phylogenies containing the implicated taxa, prune away unneeded parts, and supply branch lengths and annotations, resulting in a custom phylogeny suited to the user's needs. Such a system could become a sustainable community resource if implemented as a distributed system of loosely coupled parts that interact through clearly defined interfaces.RESULTS:With the aim of building such a "phylotastic" system, the NESCent Hackathons, Interoperability, Phylogenies (HIP) working group recruited 2 dozen scientist-programmers to a weeklong programming hackathon in June 2012. During the hackathon (and a three-month follow-up period), 5 teams produced designs, implementations, documentation, presentations, and tests including: (1) a generalized scheme for integrating components / (2) proof-of-concept pruners and controllers / (3) a meta-API for taxonomic name resolution services / (4) a system for storing, finding, and retrieving phylogenies using semantic web technologies for data exchange, storage, and querying / (5) an innovative new service, DateLife.org, which synthesizes pre-computed, time-calibrated phylogenies to assign ages to nodes / and (6) demonstration projects. These outcomes are accessible via a public code repository (GitHub.com), a website (http://www.phylotastic.org webcite), and a server image.CONCLUSIONS:Approximately 9 person-months of effort (centered on a software development hackathon) resulted in the design and implementation of proof-of-concept software for 4 core phylotastic components, 3 controllers, and 3 end-user demonstration tools. While these products have substantial limitations, they suggest considerable potential for a distributed system that makes phylogenetic knowledge readily accessible in computable form. Widespread use of phylotastic systems will create an electronic marketplace for sharing phylogenetic knowledge that will spur innovation in other areas of the ToL enterprise, such as annotation of sources and methods and third-party methods of quality assessment.

acase@tulane.edu / The technological advances of past decades have led to the accumulation of large amounts of genomic and neuroimaging data, enabling novel strategies in precision medicine. These largely rely on machine learning algorithms and modern statistical methods for big biological datasets, which are data-driven rather than hypothesis-driven. These methods often lack guarantees on the validity of the research findings. Because it can be a matter of life and death, when computational methods are deployed in clinical practice in medicine, establishing guarantees on the validity of the results is essential for the advancement of precision medicine. This thesis proposes several novel sparse regression and sparse canonical correlation analysis techniques, which by design include guarantees on the false discovery rate in variable selection. Variable selection on biomedical data is essential for many areas of healthcare, including precision medicine, population stratification, drug development, and predictive modeling of disease phenotypes. Predictive machine learning models can directly affect the patient when used to aid diagnosis, and therefore they need to be thoroughly evaluated before deployment. We present a novel approach to validly reuse the test data for performance evaluation of predictive models. The proposed methods are validated in the application on large genomic and neuroimaging datasets, where they confirm results from previous studies and also lead to new biological insights. In addition, this work puts a focus on making the proposed methods widely available to the scientific community though the release of free and open-source scientific software. / 1 / Alexej Gossmann

abstract: Scientific workflows allow scientists to easily model and express the entire data processing steps, typically as a directed acyclic graph (DAG). These scientific workflows are made of a collection of tasks that usually take a long time to compute and that produce a considerable amount of intermediate datasets. Because of the nature of scientific exploration, a scientific workflow can be modified and re-run multiple times, or new scientific workflows are created that might make use of past intermediate datasets. Storing intermediate datasets has the potential to save time in computations. Since storage is limited, one main problem that needs a solution is determining which intermediate datasets need to be saved at creation time in order to minimize the computational time of the workflows to be run in the future. This research thesis proposes the design and implementation of Pingo, a system that is capable of managing the computations of scientific workflows as well as the storage, provenance and deletion of intermediate datasets. Pingo uses the history of workflows submitted to the system to predict the most likely datasets to be needed in the future, and subjects the decision of dataset deletion to the optimization of the computational time of future workflows. / Dissertation/Thesis / Masters Thesis Computer Science 2017

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

A ciência moderna, apoiada pela e-science, tem enfrentado desafios de lidar com o grande volume e variedade de dados, gerados principalmente pelos avanços tecnológicos nos processos de coleta e processamento dos dados científicos. Como consequência, houve também um aumento na complexidade dos processos de análise e experimentação. Estes processos atualmente envolvem múltiplas fontes de dados e diversas atividades realizadas por grupos de pesquisadores geograficamente distribuídos, que devem ser compreendidas, reutilizadas e reproduzíveis. No entanto, as iniciativas da comunidade científica que buscam disponibilizar ferramentas e conscientizar os pesquisadores a compartilharem seus dados e códigos-fonte, juntamente com as publicações científicas, são, em muitos casos, insuficientes para garantir a reprodutibilidade e o reuso das contribuições científicas. Esta pesquisa objetiva definir uma estratégia computacional para o apoio ao reuso e a reprodutibilidade dos dados científicos, por meio da gestão da proveniência dos dados durante o seu ciclo de vida. A estratégia proposta nesta pesquisa é apoiada em dois componentes principais, um perfil de aplicação, que define um modelo padronizado para a descrição da proveniência dos dados, e uma arquitetura computacional para a gestão dos metadados de proveniência, que permite a descrição, armazenamento e compartilhamento destes metadados em ambientes distribuídos e heterogêneos. Foi desenvolvido um protótipo funcional para a realização de dois estudos de caso que consideraram a gestão dos metadados de proveniência de experimentos de modelagem de distribuição de espécies. Estes estudos de caso possibilitaram a validação da estratégia computacional proposta na pesquisa, demonstrando o seu potencial no apoio à gestão de dados científicos. / Modern science, supported by e-science, has faced challenges in dealing with the large volume and variety of data generated primarily by technological advances in the processes of collecting and processing scientific data. Therefore, there was also an increase in the complexity of the analysis and experimentation processes. These processes currently involve multiple data sources and numerous activities performed by geographically distributed research groups, which must be understood, reused and reproducible. However, initiatives by the scientific community with the goal of developing tools and sensitize researchers to share their data and source codes related to their findings, along with scientific publications, are often insufficient to ensure the reproducibility and reuse of scientific results. This research aims to define a computational strategy to support the reuse and reproducibility of scientific data through data provenance management during its entire life cycle. Two principal components support our strategy in this research, an application profile that defines a standardized model for the description of provenance metadata, and a computational architecture for the management of the provenance metadata that enables the description, storage and sharing of these metadata in distributed and heterogeneous environments. We developed a functional prototype for the accomplishment of two case studies that considered the management of provenance metadata during the experiments of species distribution modeling. These case studies enabled the validation of the computational strategy proposed in the research, demonstrating the potential of this strategy in supporting the management of scientific data.

Introduction : les effets indésirables associés à un traitement médicamenteux ou à la pose d'un dispositif médical implantable doivent être recherchés systématiquement après le début de leur commercialisation. Les études réalisées pendant cette phase sont des études observationnelles qui peuvent s'envisager à partir des bases de données hospitalières. L'objectif de ce travail est d'étudier l'intérêt de la ré-utilisation de données hospitalières pour la mise en évidence de tels effets indésirables.Matériel et méthodes : deux bases de données hospitalières sont ré-utilisées pour les années 2007 à 2013 : une première contenant 171 000 000 de séjours hospitaliers incluant les codes diagnostiques, les codes d'actes et des données démographiques, ces données étant chaînées selon un identifiant unique de patient ; une seconde issue d'un centre hospitalier contenant les mêmes types d'informations pour 80 000 séjours ainsi que les résultats de biologie médicale, les administrations médicamenteuses et les courriers hospitaliers pour chacun des séjours. Quatre études sont conduites sur ces données afin d'identifier d'une part des évènements indésirables médicamenteux et d'autre part des évènements indésirables faisant suite à la pose d'un dispositif médical implantable.Résultats : la première étude démontre l'aptitude d'un jeu de règles de détection à identifier automatiquement les effets indésirables à type d'hyperkaliémie. Une deuxième étude décrit la variation d'un paramètre de biologie médicale associée à la présence d'un motif séquentiel fréquent composé d'administrations de médicaments et de résultats de biologie médicale. Un troisième travail a permis la construction d'un outil web permettant d'explorer à la volée les motifs de réhospitalisation des patients ayant eu une pose de dispositif médical implantable. Une quatrième et dernière étude a permis l'estimation du risque thrombotique et hémorragique faisant suite à la pose d'une prothèse totale de hanche.Conclusion : la ré-utilisation de données hospitalières dans une perspective pharmacoépidémiologique permet l'identification d'effets indésirables associés à une administration de médicament ou à la pose d'un dispositif médical implantable. L'intérêt de ces données réside dans la puissance statistique qu'elles apportent ainsi que dans la multiplicité des types de recherches d'association qu'elles permettent. / Introduction:The adverse events associated with drug administration or placement of an implantable medical device should be sought systematically after the beginning of the commercialisation. Studies conducted in this phase are observational studies that can be performed from hospital databases. The objective of this work is to study the interest of the re-use of hospital data for the identification of such an adverse event.Materials and methods:Two hospital databases have been re-used between the years 2007 to 2013: the first contains 171 million inpatient stays including diagnostic codes, procedures and demographic data. This data is linked with a single patient identifier; the second database contains the same kinds of information for 80,000 stays and also the laboratory results and drug administrations for each inpatient stay. Four studies were conducted on these pieces of data to identify adverse drug events and adverse events following the placement of an implantable medical device.Results:The first study demonstrates the ability of a set of detection of rules to automatically identify adverse drug events with hyperkalaemia. The second study describes the variation of a laboratory results associated with the presence of a frequent sequential pattern composed of drug administrations and laboratory results. The third piece of work enables the user to build a web tool exploring on the fly the reasons for rehospitalisation of patients with an implantable medical device. The fourth and final study estimates the thrombotic and bleeding risks following a total hip replacement.Conclusion:The re-use of hospital data in a pharmacoepidemiological perspective allows the identification of adverse events associated with drug administration or placement of an implantable medical device. The value of this data is the amount statistical power they bring as well as the types of associations they allow to analyse.

A ciência moderna, apoiada pela e-science, tem enfrentado desafios de lidar com o grande volume e variedade de dados, gerados principalmente pelos avanços tecnológicos nos processos de coleta e processamento dos dados científicos. Como consequência, houve também um aumento na complexidade dos processos de análise e experimentação. Estes processos atualmente envolvem múltiplas fontes de dados e diversas atividades realizadas por grupos de pesquisadores geograficamente distribuídos, que devem ser compreendidas, reutilizadas e reproduzíveis. No entanto, as iniciativas da comunidade científica que buscam disponibilizar ferramentas e conscientizar os pesquisadores a compartilharem seus dados e códigos-fonte, juntamente com as publicações científicas, são, em muitos casos, insuficientes para garantir a reprodutibilidade e o reuso das contribuições científicas. Esta pesquisa objetiva definir uma estratégia computacional para o apoio ao reuso e a reprodutibilidade dos dados científicos, por meio da gestão da proveniência dos dados durante o seu ciclo de vida. A estratégia proposta nesta pesquisa é apoiada em dois componentes principais, um perfil de aplicação, que define um modelo padronizado para a descrição da proveniência dos dados, e uma arquitetura computacional para a gestão dos metadados de proveniência, que permite a descrição, armazenamento e compartilhamento destes metadados em ambientes distribuídos e heterogêneos. Foi desenvolvido um protótipo funcional para a realização de dois estudos de caso que consideraram a gestão dos metadados de proveniência de experimentos de modelagem de distribuição de espécies. Estes estudos de caso possibilitaram a validação da estratégia computacional proposta na pesquisa, demonstrando o seu potencial no apoio à gestão de dados científicos. / Modern science, supported by e-science, has faced challenges in dealing with the large volume and variety of data generated primarily by technological advances in the processes of collecting and processing scientific data. Therefore, there was also an increase in the complexity of the analysis and experimentation processes. These processes currently involve multiple data sources and numerous activities performed by geographically distributed research groups, which must be understood, reused and reproducible. However, initiatives by the scientific community with the goal of developing tools and sensitize researchers to share their data and source codes related to their findings, along with scientific publications, are often insufficient to ensure the reproducibility and reuse of scientific results. This research aims to define a computational strategy to support the reuse and reproducibility of scientific data through data provenance management during its entire life cycle. Two principal components support our strategy in this research, an application profile that defines a standardized model for the description of provenance metadata, and a computational architecture for the management of the provenance metadata that enables the description, storage and sharing of these metadata in distributed and heterogeneous environments. We developed a functional prototype for the accomplishment of two case studies that considered the management of provenance metadata during the experiments of species distribution modeling. These case studies enabled the validation of the computational strategy proposed in the research, demonstrating the potential of this strategy in supporting the management of scientific data.

No / Brochs are monumental Iron Age (c.400–200 BC) drystone towers or roundhouses. They are only found in Scotland, particularly the Atlantic north and west. Whilst the structural layout of brochs has long been debated, few measured surveys have been conducted. Three significant broch sites form the tentative World Heritage site of “Mousa, Old Scatness and Jarlshof: the Zenith of Iron Age Shetland” (UNESCO in Mousa, Old Scatness and Jarlshof: the zenith of Iron Age Shetland, UNESCO (2019) Mousa, Old Scatness and Jarlshof: the zenith of Iron Age Shetland. http://whc.unesco.org/en/tentativelists/5677. Accessed 9 Aug 2019). All three sites have undergone new surveys as part of a collaborative doctoral partnership research project. This chapter presents a diachronic perspective using digital documentation techniques to detect stone displacement and weathering at the site of Old Scatness using historic imagery, including photographs from the Old Scatness excavations (1995–2006) and regular condition monitoring undertaken by Shetland Amenity Trust to undertake retrospective digital structure-from-motion (SfM) photogrammetry. Whilst point clouds and 3D meshes were successfully generated from low-resolution digital images, analogue film transparencies without metadata could not produce accurate geospatial data without manually trying to extant reference data. It was possible to detect displacements in stonework over time by comparing two meshes together and measuring the distances between vertex point pairs. The reliability and accuracy of these results were dependent on how well pairs of meshes could be aligned.