Στην εργασία αυτή εξετάζουμε την επίδραση της τοπικότητας στην απόδοση των κρυφών μνημών για πολυπύρηνες αρχιτεκτονικές x86. Στόχος μας είναι η βελτίωση των επιδόσεων και της απόδοσης σε αυτά τα συστήματα. Προτείνουμε ένα πρωτύτυπο, παράλληλο, σύστημα χρόνου εκτέλεσης που βασίζεται σε εργασίες (tasks), το TPR (Task Parallel Runtime), που στοχεύει σε μικρό χρόνο απόκρισης στην εκτέλεση των εργασιών και μικρή προσπάθεια από τον προγραμματιστή στην περιγραφή του παραλληλισμού. Το TPR επιτυγχάνει χαμηλό κόστος για την δημιουργεία, χειρισμό και συγχρονισμό νέων εργασιών. Το σύστημα έχει σχεδιαστεί για να διευκολύνει τον προγραμματιστή με λειτουργίες όπως η ρητή περιγραφή των δεδομένων για βελτίωση της τοπικότητας μέσω προανάκλησης (prefetching) και ρητή ανάθεση κάποιας εργασίας σε ένα πυρήνα για τη βελτίωση τησ τοπικότητας μέσς προσαρμοσμένων πολιτικών εκτέλεσης (scheduling). Στην εργασία αυτή διευρύνουμε επιπλέον τις παραμέτρους που επηρεάζουν την τοπικότητα σε μεγάλο βαθμό και την επίδραση στην απόδοση της κάθε μιας. Καταλήγουμε στο συμπέρασμα ότι οι σημαντικότερες παράμετροι της τοπικότητας είναι η διάταξη της μνήμης, το μέγεθος των δεδομένων της εργασίας, η πολιτική προγραμματισμού της και η προανάκληση. Για την αξιολόγηση χρησιμοποιούμε τόσο μικροεφαρμογές γραμμικής άλγεβρας (GEMM, LU, Cholesky και Jacobi) οσο και πραγματικές εφαρμογές (PBPI, FixedGrid και FFT). Τέλος, συγκρίνουμε την δουλειά μας με άλλα συστήματα χρόνου εκτέλεσης και βελτιστοοιημένες από τον προγραμματιστή εφαρμογές σε pthreads ή MPI. Καταφέρνουμε μια μέση βελτίωση των επιδόσεων σε σχέση με άλλα συτήματα χρόνου εκτέλεσης από 1% εώς 40%, ανάλογα με την εφαρμογή. Συνολικά, η συνεισφορά της εργασίας αυτής είναι να καθορίσει το ελάχιστο υποσύνολο απαιτήσεων ενός συστήματος χρόνου εκτέλεσης για να χειριστεί αποτελσματικά την τοπικότητα, να ταξινομήσουμε τις εφαρμογές και να αναθέσουμε σε κάθε μια την βασικότερη βελτιστοποίηση.
(EL)
In this thesis we discuss the oerformance impact of cache locality on multicore x86 architectures. Our goal is to improve performance and efficiency on these systems. We suggest a novel task-based, parallel runtime system (TPR), that allows programmer to create custom scheduling policies and perform guided prefetching on the task arguments with minimal training effort requirements. TPR is targeted on very low overhead task creation, issue and synchronization. This system is designed to facilitate the programmer with utilities such as explicit data annotations to improve locality via prefetching and task binding to implement custom scheduling policies. Using that system we explore the parameters that affects locality in a major degree and the performance impact of each one. We coclude that the most important locality parameters are memory layout, task size, scheduling policy and SW prefetching. For the evaluation we use both linear algebra kernels and real applications. The kernels discussed are GEMM, LU, Cholesky and Jacobi. The applications are PBPI, FixedGrid, and FFT. Finally we compare our work with other based runtime systems and hand tuned applications written using pthreads or MPI. We manage an average performance improvement over other runtime systems from 1% to 40% depending on the application. The contribution of this work is to set a minimal subset of requirements for a runtime system to efficiently handle locality and to categorize applications and assign their primary optimization technique.
(EN)
