In this thesis, we design, develop and implement parallel algorithms for irregular problems on heterogeneous multi-core architectures. Irregular problems exhibit random and unpredictable memory access patterns, poor spatial locality and input dependent control flow. Heterogeneous multi-core processors vary in: clock frequency, power dissipation, programming model (MIMD vs. SIMD), memory design and computing units, scalar versus vector units. The heterogeneity of the processors makes designing efficient parallel algorithms for irregular problems on heterogeneous multicore processors challenging. Techniques of mapping tasks or data on traditional parallel computers can not be used as is on heterogeneous multi-core processors due to the varying hardware. In an attempt to understand the efficiency of futuristic heterogeneous multi-core architectures on applications we study several computation and bandwidth oriented irregular problems on one heterogeneous multi-core architecture, the IBM Cell Broadband Engine (Cell BE). The Cell BE consists of a general processor and eight specialized processors and addresses vector/data-level parallelism and instruction-level parallelism simultaneously. Through these studies on the Cell BE, we provide some discussions and insight on the performance of the applications on heterogeneous multi-core architectures. Verifying these experimental results require some performance modeling. Due to the diversity of heterogeneous multi-core architectures, theoretical performance models used for homogeneous multi-core architectures do not provide accurate results. Therefore, in this thesis we propose an analytical performance prediction model that considers the multitude architectural features of heterogeneous multi-cores (such as DMA transfers, number of instructions and operations, the processor frequency and DMA bandwidth). We show that the execution time from our prediction model is comparable to the execution time of the experimental results for a complex medical imaging application.

In this thesis, we design, develop and implement parallel algorithms for irregular problems on heterogeneous multi-core architectures. Irregular problems exhibit random and unpredictable memory access patterns, poor spatial locality and input dependent control flow. Heterogeneous multi-core processors vary in: clock frequency, power dissipation, programming model (MIMD vs. SIMD), memory design and computing units, scalar versus vector units. The heterogeneity of the processors makes designing efficient parallel algorithms for irregular problems on heterogeneous multicore processors challenging. Techniques of mapping tasks or data on traditional parallel computers can not be used as is on heterogeneous multi-core processors due to the varying hardware. In an attempt to understand the efficiency of futuristic heterogeneous multi-core architectures on applications we study several computation and bandwidth oriented irregular problems on one heterogeneous multi-core architecture, the IBM Cell Broadband Engine (Cell BE). The Cell BE consists of a general processor and eight specialized processors and addresses vector/data-level parallelism and instruction-level parallelism simultaneously. Through these studies on the Cell BE, we provide some discussions and insight on the performance of the applications on heterogeneous multi-core architectures. Verifying these experimental results require some performance modeling. Due to the diversity of heterogeneous multi-core architectures, theoretical performance models used for homogeneous multi-core architectures do not provide accurate results. Therefore, in this thesis we propose an analytical performance prediction model that considers the multitude architectural features of heterogeneous multi-cores (such as DMA transfers, number of instructions and operations, the processor frequency and DMA bandwidth). We show that the execution time from our prediction model is comparable to the execution time of the experimental results for a complex medical imaging application.

Με την τομογραφία επιχειρείται η δημιουργία μιας εικόνας-τομής των ιδιοτήτων ενός αντικειμένου χρησιμοποιώντας μετρήσεις της ενέργειας που διαδόθηκε μέσω του αντικειμένου, σε δέκτες στην περιφέρειά του. Έχει αποδειχθεί ότι ένα αντικείμενο είναι δυνατόν να απεικονισθεί με ακρίβεια από ένα πλήρες σύνολο περιμετρικών προβολών του. Η τομογραφική ανάλυση είναι δυνατό να γίνει αξιοποιώντας κυματική ενέργεια που έχει διαδοθεί μέσω του υπό μελέτη αντικειμένου (ακτινική τομογραφία) ή προέρχεται από ανάκλαση, περίθλαση κ.ο.κ. σε ανομοιογενή τμήματα του αντικειμένου (περιθλαστική τομογραφία). Στην παρούσα εργασία γίνεται πειραματική εφαρμογή της μεθόδου της σεισμικής τομογραφικής απεικόνισης σε αρχαιολογικά προβλήματα, όπως στην ανίχνευση αρχαιολογικών αντικειμένων στο υπέδαφος ή σε περιβάλλον τεχνητών λόφων (τύμβων -ταφικών μνημείων). Η εφαρμογή αυτή συνιστά ενδιαφέρουσα πρόκληση λόγω του ιδιαίτερα ανομοιογενούς περιβάλλοντος στο οποίο επιχειρείται η ανίχνευση των αντικειμένων καθώς και των μικρών γενικά, αλλά και συχνά απροσδιόριστων, διαστάσεων των αντικειμένων αυτών. Ο μη καταστρεπτικός χαρακτήρας της εφαρμογής είναι ιδιαίτερα ευνοϊκός και αποδεκτός στην αρχαιολογική έρευνα, τόσο σε αναγνωριστικό όσο και σε ανασκαφικό/ σωστικό επίπεδο. Παρουσιάζονται αναλυτικά οι αρχές και το θεωρητικό μέρος της τομογραφικής μεθοδολογίας, με ιδιαίτερη αναλυτική αναφορά στις δύο κύριες μεθόδους ανασύνθεσης των χαρακτηριστικών του εσωτερικού του ερευνώμενου μέσου (χώρου), την ακτινική τομογραφία και περίθλασης, καθώς και τις σχετικές τεχνικές και αλγόριθμους αντιστροφής. Τέλος γίνεται εφαρμογή της ακτινικής τομογραφίας σε 3 διαστάσεις, σε σεισμικές καταγραφές από αρχαιολογικούς-μνημειακούς χώρους, με τη χρήση του αλγόριθμου SIRT (τεχνική ταυτόχρονης επαναληπτικής ανασύνθεσης). Τα δεδομένα ήταν χρόνοι πρώτης άφιξης καθώς και πλάτη σε μια περίπτωση. Kατά την εφαρμογή της ακτινικής τομογραφίας, γίνονται δοκιμές ρύθμισης των παραμέτρων και μεταβλητών κατά τη διαδικασία της αντιστροφής, ώστε να διερευνηθεί η επίδρασή τους στο αποτέλεσμα. Επίσης, διερευνάται η αποτελεσματικότητα της μεθόδου με κατασκευή μοντέλων με βάση πληροφορίες για τους χώρους έρευνας, υπολογισμό συνθετικών χρόνων και αντιστροφή των συνθετικών χρόνων για σύγκριση με τα αποτελέσματα των πραγματικών χρόνων και εξαγωγή συμπερασμάτων. Λαμβάνοντας υπόψη τα στοιχεία από τις ανωτέρω δοκιμές, επιλέγονται τελικές τιμές παραμέτρων για την αντιστροφή των πραγματικών δεδομένων και γίνεται αξιολόγηση και ερμηνεία των αποτελεσμάτων. Γίνεται επίσης δοκιμαστική εφαρμογή τεχνικών επεξεργασίας / ενίσχυσης εικόνας στα αποτελέσματα της αντιστροφής, για την ενίσχυση κυρίως των μικρών, τοπικών, μεταβολών της σεισμικής ταχύτητας και την πληρέστερη απεικόνιση των χώρων έρευνας. Παρουσιάζονται τα αποτελέσματα από την έρευνα του προϊστορικού οικισμού Παλαμαρίου Σκύρου, του χώρου θεμελίωσης του Καθολικού (Ναού) της Ι.Μ. Δαφνίου Αττικής, του εσωτερικού του τεχνητού λόφου – πιθανού τύμβου Καστά Μεσολακκιάς Σερρών και των νεκροταφείων της περιοχής Chatby της Αλεξάνδρειας Αιγύπτου. / With tomography is attempted the creation of an image – slice of the internal properties of a medium / object with use of measurements of the energy which was transmitted through the medium, at receivers on the outside of it. It has been proved that a medium can be imaged with precision by a set of perimetric projections. Tomographic analysis is possible by employing wave energy that has been transmitted through the medium under investigation (ray tomography) or has been reflected or diffracted at various inhomegeneities within the medium (diffraction tomography). In the present study, an experimental application of the seismic tomographic imaging method is made in the field of archaeological exploration, such as detection of archaeological remains in the subsurface or in artificial hills (tumuli). The application poses an interesting challenge, because of the highly inhomogeneous environment where the detection is tried and the small and unknown, in general, dimensions of the target objects. The non-destructive character of the application makes it quite attractive and acceptable in archaeological exploration, both at reconnaissance and later stages of excavation. The principles and theoretical foundations of the tomographic methodology are presented, with particular reference to the two main methods of reconstruction of the internal character of the investigated medium and included objects, that is ray and diffraction tomography, as well as the relevant inversion techniques and algorithms. Finally, an application of ray tomography on seismic recordings from archaeological / monumental sites is made, with use of the simultaneous iterative reconstruction technique (SIRT). In the application of ray tomography, adjustment tests of inversion parameters and variables are made, in order to study their effect on the inversion result. The effectiveness of the method and of the algorithm is investigated with the aid of synthetic models based on possible information from the test sites and the bibliography. Using the models as starting models, synthetic travel times are calculated and are then inverted, while the resulting image is compared with the synthetic starting model and conclusions are drawn. Based on the results of the above tests, final parameter values are set for the inversion of real field data and an assessment and an interpretation of the results is made. Image processing and enhancement is applied to the resulting tomograms, in order to enhance and clarify the small (hidden) variations of seismic velocity, which may reflect important subsurface information, mainly related to particular archaeological targets. There are presented the results from the investigation of the subsurface of a part of the prehistoric settlement of Palamari (Skyros isl., Greece) of the foundations of the church of Dafni Monastery (Attica, Greece), of the interior of the artificial hill / possible tumulus at Kasta Messolakia (Serrae, Greece) and of the subsurface of the cemeteries of Chatby area (Alexandria, Egypt).