Μέθοδοι Και Τεχνικές Αυτόματης Παραγωγής Παράλληλου Κώδικα Για Αλγοριθμικές Περιγραφές Φωλιασμένων Βρόχων

Abstract

Αντικείμενο της διατριβής ήταν η προτυποποίηση προγραμματιστικών μέθοδων και τεχνικών για την αποδοτική παραλληλοποίηση αλγοριθμικών περιγραφών πλήρως αντιμεταθέσιμων βρόχων σε σύγχρονες παράλληλες αρχιτεκτονικές κατανεμημένης μοιραζόμενης μνήμης, όπως είναι οι συστοιχίες πολυεπεξεργαστικών στοιχείων. Στο πλαίσιο της διατριβής μας απασχόλησαν κυρίως δύο ζητήματα: αρχικά, επιχειρήσαμε να αξιοποιήσουμε το χώρο επαναλήψεων και τις εξαρτήσεις δεδομένων ενός συγκεκριμένου αλγορίθμου φωλιασμένων βρόχων κατά την παράλληλη απεικόνιση του σε μια τοπολογία διεργασιών ελάχιστης επικοινωνίας υπό δεδομένη επεξεργαστική υποδομή. Στη συνέχεια, διερευνήθηκαν υβριδικά μοντέλα παράλληλου προγραμματισμού για αλγορίθμους φωλιασμένων βρόχων. Εξετάστηκαν αφενός η συνήθης στη βιβλιογραφία προσέγγιση της επαυξητικής υβριδικής παραλληλοποίησης λεπτού κόκκου (fine-grain, masteronly) και αφετέρου η SPMD εναλλακτική προσέγγιση του υβριδικού παραλληλισμού χονδρού κόκκου (coarse-grain), τόσο υπό μερική (funneled) όσο και υπό πλήρη (multiple) πολυνηματική υποστήριξη από τη βιβλιοθήκη ανταλλαγής μηνυμάτων. Αναπτύξαμε στατικές και δυναμικές τεχνικές για την εξισορρόπηση του φορτίου μεταξύ των νημάτων στο funneled υβριδικό μοντέλο χονδρού κόκκου. Οι προτεινόμενες βελτιστοποιήσεις αξιολογήθηκαν πειραματικά σε συστοιχίες πολυεπεξεργαστικών στοιχείων με τη βοήθεια τυπικών εφαρμογών.