Επικάλυψη Υπολογισμών Και Επικοινωνίας Σε Συστοιχίες Από Πολυνηματικούς Επεξεργαστές

Abstract

Ένα από τα πιο σημαντικά προβλήματα που παρουσιάζεται στα παράλληλα συστήματα επεξεργασίας αποτελεί η εύρεση νέων μεθόδων για την καλύτερη αξιοποίηση των διαθέσιμων υπολογιστικών πόρων. Σκοπός αυτής της διπλωματικής εργασίας μας είναι η καλύτερη αξιοποίηση παράλληλων αρχιτεκτονικών Simultaneous Multithreading (SMT) για την εκτέλεση δύσκολων υπολογισμών με εφαρμογή επικαλυπτόμενης δρομολόγησης και χρήση μετασχηματισμού υπερκόμβων (tiling). Στην προσέγγιση μας, επιλέγουμε ένα χρονικό μετασχηματισμό που εκμεταλλεύεται την εγγενή επικάλυψη μεταξύ των φάσεων επικοινωνίας και εκτέλεσης υπολογισμών μεταξύ διαδοχικών, ατομικών στιγμιότυπων του βρόχου (tile). Με αυτό τον τρόπο επιτυγχάνεται η πιο αποδοτική εκτέλεση των στιγμιότυπων του βρόχου, με την προϋπόθεση ότι κάποιο μέρος της κάθε φάσης επικοινωνίας μπορεί να επικαλυφθεί αποδοτικά με ατομικούς υπολογισμούς σε κάθε στιγμιότυπο. Εφαρμόζουμε την παραπάνω δρομολόγηση για την παράλληλη εκτέλεση στιγμιότυπων βρόχου υπολογισμού διακριτών Μερικών Διαφορικών Εξισώσεων. Προσπαθούμε να εκμεταλλευτούμε την παραλληλία σε επίπεδο νημάτων (TLP) του αλγόριθμου δρομολόγησης τοποθετώντας τους δύο ετερογενής φόρτους εργασίας επικοινωνίας και επεξεργασίας σε διαφορετικούς λογικούς επεξεργαστές που ανήκουν στον ίδιο φυσικό πολυνηματικό επεξεργαστή. Για το σκοπό αυτό υλοποιήσαμε διάφορες εκδόσεις παράλληλου προγράμματος (πολυνηματικές και μη), χρησιμοποιώντας μεταξύ άλλων το μετασχηματισμό υπερκόμβων (tiling) που αποτελεί τον πιο διαδεδομένο μετασχηματισμό κώδικα για την αναδιάταξη των επαναλήψεων σε φωλιασμένους βρόχους. Από τα πειραματικά αποτελέσματα που πήραμε σε μία συστοιχία από Xeons με τεχνολογία Hyper-Threading χρησιμοποιώντας διάφορες πρωτογενείς εντολές MPI_Send, φαίνεται ότι μειώνεται σημαντικά ο ολικός παράλληλος χρόνος εκτέλεσης όταν οι δύο ετερογενές φόρτοι εργασίας επικοινωνίας και υπολογισμού, που παρουσιάζουν υψηλή παραλληλία TLP, τοποθετηθούν στους δύο λογικούς επεξεργαστές ενός φυσικού πολυνηματικού επεξεργαστή.