Παραλληλοποίηση Αλγόριθμων Γραμμικής Άλγεβρας Για Αρχιτεκτονικές Υψηλής Επίδοσης

Abstract

Ο σκοπός της διπλωματικής εργασίας ήταν η μελέτη, υλοποίηση και παραλληλοποίηση αλγόριθμων γραμμικής άλγεβρας για αρχιτεκτονικές υψηλής επίδοσης. Η εργασία περιλαμβάνει θεωρητικό και προγραμματιστικό μέρος, ενώ ακολουθούν πειραματικά αποτελέσματα και μελέτη της επίδοσης των παράλληλων υλοποιήσεων.Το θεωρητικό μέρος της εργασίας περιλαμβάνει κατ’ αρχήν μελέτη των κυριότερων παράλληλων αρχιτεκτονικών. Περιγράφονται τα χαρακτηριστικά των αρχιτεκτονικών, τα διαθέσιμα προγραμματιστικά μοντέλα, τα πλεονεκτήματα και ταμειονεκτήματα κάθε αρχιτεκτονικής. Επίσης, πραγματοποιείται μία σύγκριση ανάμεσα στα δύο κύρια μοντέλα, κατανεμημένης και μοιραζόμενης μνήμης, ώστε να επεξηγηθεί η επιλογή του πρώτου, ως το μοντέλο που χρησιμοποιήθηκε στην παρούσα εργασία. Στη συνέχεια, παρέχεται το απαραίτητο θεωρητικό υπόβαθρο για την κατανόηση των μεθόδων επίλυσης συστημάτων γραμμικών εξισώσεων. Παρουσιάζονται οι σημαντικότερες άμεσες και επαναληπτικές μέθοδοι επίλυσης συστημάτων, καθώς και οι εφαρμογές στις οποίες χρησιμοποιούνται αυτές οιμέθοδοι.Το προγραμματιστικό κομμάτι της εργασίας περιλαμβάνει την υλοποίηση δύο αλγόριθμων σειριακά, και στη συνέχεια την υλοποίηση παράλληλων εκδόσεων. Ο πρώτος αλγόριθμος αφορά στην εκτίμηση κατάστασης συστημάτων ηλεκτρικής ενέργειας με τη μέθοδο των ελαχίστων τετραγώνων και ο δεύτερος αποτελεί την υλοποίηση της μεθόδου Conjugate Gradientγια την επίλυση γραμμικών συστημάτων.Η υλοποίηση των προγραμμάτων έγινε σε γλώσσα C, με τη χρήση των προγραμματιστικών εργαλείων MPI, PETSc και BLAS, τα οποία περιγράφονται συνοπτικά στην εργασία.Τέλος, πραγματοποιήθηκαν μετρήσεις για διάφορα μεγέθη προβλημάτων σε συστοιχία υπολογιστικών κόμβων. Από τις μετρήσεις αυτές, κατασκευάστηκαν διαγράμματα, τα οποία βοηθούν στην εξαγωγή συμπερασμάτων για την απόδοση τωνπαράλληλων υλοποιήσεων, αλλά και για την κατανομή του χρόνου εκτέλεσης των προγραμμάτων σε χρόνο υπολογισμών και χρόνο επικοινωνίας.