Χρονοδρομολογηση Φωλιασμενων Βροχων Σε Συστοιχια Πολυεπεξεργαστων Διασυνδεδεμενων Με Myrinet

Abstract

Περίληψη: H παρούσα διπλωματική εργασία έχει ως βασικό στόχο την σχεδίαση και υλοποίηση στατικών αλγορίθμων χρονοδρομολόγησης για την παράλληλη εκτέλεση προγραμμάτων με τέλεια φωλιασμένους βρόχους. Ο χώρος επαναλήψεων του αρχικού προγράμματος χωρίζεται σε ομάδες (tiles) με στόχο την ταυτόχρονη εκτέλεση ανεξάρτητων μεταξύ τους ομάδων υπολογισμού σε ένα παράλληλο σύστημα επεξεργαστών. Το πρόβλημα που εξετάζεται είναι είναι ο τρόπος ανάθεσης των tiles στους διαθέσιμους επεξεργαστές σε μεγάλους χώρους επαναλήψεων όπου απαιτείται η χρησιμοποίηση των επεξεργαστών για πολλαπλές σειρές από tiles. Αναλύονται 2 διαφορετικοί καταμερισμοί των tiles : το κυκλικό σχήμα ανάθεσης, που επιτυγχάνει χαμηλό χρόνο εκκίνησης του παράλληλου συστήματος και το σχήμα ομαδοποίησης που οδηγεί σε χαμηλό φορτίο επικοινωνίας ανάμεσα στους διαθέσιμους επεξεργαστές. Γενίκευση των αλγορίθμων αποτελεί το υβριδικό μπλοκ κυκλικό σχήμα που στοχεύει στη ρύθμιση της παραλληλίας και του φορτίου επικοινωνίας στο επίπεδο των tiles, προσπαθώντας να βρει την χρυσή τομή ανάμεσα στα δύο σχήματα. Η εργασία επικεντρώνεται στον σχεδιασμό και την υλοποίηση των σχημάτων χρονοδρομολόγησης για οποιοδήποτε χώρο επαναλήψεων σε αρχιτεκτονικές μη ομοιόμορφης προσπέλασης μνήμης.Οι αλγόριθμοι χρονοδρομολόγησης υλοποιούνται σε μια συστοιχία πολυεπεξεργαστικών κόμβων (SMPs) διασυνδεδεμένων με Myrinet, μια δικτυακή τεχνολογία επιπέδου χρήστη με υψηλό ρυθμό μεταφοράς δεδομένων και χαμηλή καθυστέρηση, ευρέως χρησιμοποιούμενο σε δικτυακές εφαρμογές. Μελετούμε την αλληλεπίδραση του επεξεργαστή και της κάρτας δικτύου και αναλύουμε τις δυνατότητες του συστήματος περάσματος μηνυμάτων Myrinet - GM για εφαρμογές παράλληλου προγραμματισμού. H υλοποίηση περιλαμβάνει την χρήση της βιβλιοθήκης GM για την επικοινωνία μεταξύ των κόμβων και της βιβλιοθήκης πολυνηματικού προγραμματισμού NPTL για τον συγχρονισμό και την επικοινωνία των επεξεργαστών του ίδιου κόμβου. Κάθε αλγόριθμος υλοποίεται με δύο μοντέλα: εκτέλεση με επικάλυψη, στην οποία πραγματοποιούνται ταυτόχρονα υπολογισμοί και επικοινωνία, και εκτέλεση χωρίς επικάλυψη.Μετά την υλοποίηση εκτελούμε μια σειρά πειραμάτων και συγκρίνουμε τον χρόνο εκτέλεσης των σχημάτων χρονοδρομολόγησης για διαφορετικούς χώρους επαναλήψεων με στόχο να εκτιμήσουμε τη συμπεριφορά των αλγορίθμων χρονοδρομολόγησης και να προτείνουμε τον καταλληλότερο με βάση τον χώρο του προβλήματος και την διαθέσιμη αρχιτεκτονική. Τα πειραματικά αποτελέσματα θα δείξουν τα πλεονεκτήματα και μειονεκτήματα των σχημάτων, δίνοντας κίνητρο για περαιτέρω έρευνα. Τα προγράμματα δρομολόγησης μπορούν να χρησιμοποιηθούν για την παραλληλοποίηση πραγματικών αριθμητικών εφαρμογών, όπως αλγόριθμοι επεξεργασίας εικόνων και επαναληπτικές μέθοδοι επίλυσης διαφορικών εξισώσεων.