Παραλληλοποίηση Αλγορίθμου Επίλυσης Αραιών Γραμμικών Συστημάτων

Abstract

Στόχος αυτής της διπλωματικής εργασίας είναι να ασχοληθεί και να εξερευνήσει την επίδοση στη λύση αραιών συστημάτων γραμμικών εξισώσεων. Με αυτά τα προβλήματα έρχονται αντιμέτωπες οι φυσικές,οικονομικές και γενικά κάθε είδους επιστήμες. Η απαίτηση για αποδοτική και γρήγορη λύση αυτών των προβλημάτων ωθεί την Επιστήμη των Υπολογιστών να αναζητήσει αποδοτικές λύσεις. Ιδιαίτερα ο κλάδος που ασχολείται με συστήματα Υψηλής Επίδοσης προσπαθεί να παράγει μοντέλα που καθιστούν την χρονοβόρα διαδικασία εκτέλεσης τέτοιων απαιτητικών προβλημάτων βιώσιμη.Εξετάζεται η επαναληπτική μέθοδος σύγκλισης Conjugate Gradient,η οποία μπορεί να χειριστεί συμμετρικά συστήματα γραμμικών εξισώσεων. Αναλύεται ο αλγόριθμος που χρησιμοποιεί η μέθοδος,εντοπίζονται τα σημεία τα οποία μπορούν να παραλληλοποιηθούν με ορισμένα προγραμματιστικά μοντέλα και αναλύεται η επίδοση τους με στόχο να εξαχθεί συμπέρασμα όσο αφορά το κέρδος από την όποια παραλληλοποίησή τους.Η παραλληλοποίηση γίνεται σε συστήματα κοινής μνήμηςκατανεμημένης μνήμηςΚαι στις δύο αυτές πολύ διαφορετικές περιπτώσεις παραλληλισμού,προσπαθούμε να αναλύσουμε τις ιδιομορφίες που υπάρχουν,τις αδυναμίες και τις δυνατότητες με στόχο να εξάγουμε ένα συμπέρασμα για το βαθμό που κλιμακώνεται η επίδοση όσο αυξάνουμε την ισχύ του συστήματος.Αναλύεται η έννοια της συμμετρικότητας ενός αραιού πίνακα και μελετάμε την επίδοση δύο συμμετρικών εκδόσεων του πυρήνα SpMV που αξιοποιούν την ιδιότητα αυτή ενός συμμετρικού αραιού πίνακα.Ειδικότερα,στο κομμάτι του προγραμματισμού σε σύστημα κατανεμημένης μνήμης εξετάζεται ο βαθμός που θα διασπαστεί το αρχικό πρόβλημα σε υποπροβλήματα μικρότερου μεγέθους έτσι ώστε το κέρδος που θα έχουμε από τη διάσπαση του προβλήματος να μην εκτοπίζεται από το κόστος της επικοινωνίας που εισάγεται από τη φύση του κατανεμημένου συστήματος.Από την άλλη, στο σύστημα κοινής μνήμης,αναλύεται η βελτίωση της επίδοσης σε συνάρτηση με τον αριθμό των χρησιμοποιούμενων πυρήνων που ενυπάρχουν στους επεξεργαστές κι αναλύεται το φράγμα που τοποθετεί η ταχύτητα της κύριας μνήμης όταν εντοπίζεται αστοχία στα δεδομένα. Τέλος υλοποιούμε μια ιδέα που έχει να κάνει με τη συμπίεση των δεδομένων έτσι ώστε αυτά να καταφθάνουν ταχύτερα από την κύρια μνήμη σε περίπτωση αστοχίας κι αναλύουμε την επίδοσή της.