Τεχνικές Βελτιστοποίησης Για Παράλληλο Λογισμικό Μεγάλης Κλίμακας

Abstract

Ένα από τα πιο δύσκολα προβλήματα στα συστήματα παράλληλης επεξεργασίας είναι η ανάπτυξη παράλληλου λογισμικού το οποίο κλιμακώνει αποδοτικά. Αρκετές εφαρμογές δεν κλιμακώνουν έπειτα από έναν αριθμό επεξεργαστών επειδή το κόστος επικοινωνίας γίνεται συγκρίσιμο με την ωφέλιμη υπολογιστική εργασία. Σκοπός αυτής της διπλωματικής εργασίας είναι η υλοποίηση ενός σχήματος παράλληλης εκτέλεσης που επικαλύπτει υπολογισμούς με επικοινωνία ώστε τελικά να μειώνεται ο συνολικός χρόνος εκτέλεσης της εφαρμογής. Χρησιμοποιούμε την επικαλυπτόμενη δρομολόγηση σε τέσσερις αντιπροσωπευτικές εφαρμογές: (α)Τον αλγόριθμο Floyd-Warshall που χρησιμοποιεί συλλογική επικοινωνία, (β)τον αλγόριθμο Smith-Waterman που είναι μία τυπική εφαρμογή δυναμικού προγραμματισμού, (γ)την εξίσωση μεταφοράς τριών διαστάσεων που απαιτεί επικοινωνία των διεργασιών μόνο προς ορισμένη κατεύθυνση και (δ)την εξίσωση διάδοσης θερμότητας τριών διαστάσεων, όπου κάθε διεργασία ανταλλάζει δεδομένα με όλες τις γειτονικές της διεργασίες. Υλοποιούμε αυτήν την τεχνική με δύο τρόπους, αρχικά χρησιμοποιώντας ασύγχρονη επικοινωνία και έπειτα αναθέτοντας το υπολογιστικό κομμάτι και την επικοινωνία σε διαφορετικά νήματα. Η τελευταία υλοποίηση βασίζεται σε υβριδικό προγραμματισμό με MPI και OpenMP. Η πλατφόρμα εκτέλεσης είναι μία συστοιχία από κόμβους πολυεπεξεργαστών με μοιραζόμενη μνήμη (SMP) και τα διαθέσιμα δίκτυα διασύνδεσης είναι Gigabit Ethernet και Myrinet. Εξετάζουμε την βιωσιμότητα αυτής της τεχνικής και στα δύο δίκτυα διασύνδεσης και παρατηρούμε βελτίωση στην επίδοση έως 40% σε σχέση με τις απλές παράλληλες εφαρμογές.