Συστήματα Παράλληλης Επεξεργασίας

Abstract

Η εξέλιξη της τεχνολογίας των υπολογιστών ήταν αλματώδης τις τελευταίες δύοδεκαετίες. Εξίσου θεαματική είναι ωστόσο η αύξηση των απαιτήσεων σε υπολογιστικήισχύ. Για την αντιμετώπιση των απαιτητικών και χρονοβόρων αλγορίθμων εισάγουμε τηνπαράλληλη επεξεργασία. Η παράλληλη επεξεργασία έχει χρησιμοποιηθεί για πολλάχρόνια, κυρίως στους υπολογισμούς υψηλών επιδόσεων (high performance computing), αλλάτο ενδιαφέρον για αυτήν έχει γίνει ακόμα μεγαλύτερο τα τελευταία χρόνια, λόγω τωνφυσικών περιορισμών που εμποδίζουν την παραπέρα κλιμάκωση της συχνότητας τωνεπεξεργαστών. Έτσι, έχει πρόσφατα καταστεί το κυρίαρχο πρότυπο στην αρχιτεκτονικήυπολογιστών, κυρίως με τη μορφή πολυπύρηνων επεξεργαστών (multicore processors).Η συγγραφή παράλληλων προγραμμάτων είναι όμως σημαντικά δυσκολότερη από εκείνητων αντίστοιχων ακολουθιακών, επειδή η παραλληλία στην εκτέλεση εισάγει αρκετές νέεςκατηγορίες πιθανών σφαλμάτων του λογισμικού. Επιπλέον, ο συγχρονισμός και το κόστοςεπικοινωνίας μεταξύ των παραλλήλων διεργασιών είναι συνήθως τα μεγαλύτερα εμπόδιαγια να έχουμε καλές επιδόσεις και ικανοποιητικές επιταχύνσεις από τα παράλληλαπρογράμματα. Τέλος, παρά την εργασία δεκαετιών από ερευνητές στον τομέα τωνμεταγλωττιστών, η αυτόματη παραλληλοποίηση ακολουθιακών προγραμμάτων είχεπεριορισμένη μόνο επιτυχία. Οι βασικές γλώσσες παράλληλου προγραμματισμούπαραμένουν είτε ρητά παράλληλες ή, στην καλύτερη περίπτωση, εν μέρεικατευθυνόμενες, με τον προγραμματιστή να δίνει οδηγίες στο μεταγλωττιστή για τηνπαραλληλοποίηση του κώδικα.Αντικείμενο της διατριβής είναι η εισαγωγή και παρουσίαση στον προγραμματιστήτρόπων διευκόλυνσης του προγραμματισμού σε συστήματα παράλληλης επεξεργασίας,καθώς και η αποδοτική υλοποίηση των αντίστοιχων μηχανισμών. Το πρόβλημαπροσεγγίζεται από δύο διαφορετικές οπτικές γωνίες, δίνοντας στον προγραμματιστή τημέγιστη ευελιξία για να επιτύχει τα βέλτιστα αποτελέσματα από το παράλληλοπρόγραμμα.Η πρώτη προσέγγιση είναι από την πλευρά του συστήματος, ώστε να δοθούν στονπρογραμματιστή παραλλήλων εφαρμογών επιλογές για ευκολότερη χειρόγραφησυγγραφή παράλληλου κώδικα και οδήγησε στην υλοποίηση του μηχανισμού τωνκαθολικών σηματοφορέων. Ο μηχανισμός αυτός έχει υλοποιηθεί και μεταφερθεί σεδιάφορα παράλληλα περιβάλλοντα, με κυριότερα τις πλατφόρμες παράλληλου προγραμματισμού PVM και MPI και είναι διαθέσιμος σαν μια βιβλιοθήκη της γλώσσας C(runtime library) και μερικά επιπρόσθετα αρχεία ορισμών (include files). Με τη χρήση του οπρογραμματιστής των παραλλήλων εφαρμογών μπορεί να αντιμετωπίσει τα προβλήματασυγχρονισμού παραλλήλων διεργασιών, αμοιβαίου αποκλεισμού κρισίμων τμημάτων καιδιάθεσης πόρων του συστήματος.Η δεύτερη προσέγγιση είναι από την πλευρά του μεταγλωττιστή, ώστε μια κατηγορίαακολουθιακών αλγορίθμων να μπορούν να μεταφράζονται αυτόματα σε ισοδύναμοπαράλληλο κώδικα και οδήγησε στην υλοποίηση του εργαλείου CRONUS. Η πλατφόρμαCRONUS αποτελεί ένα αυτοματοποιημένο εργαλείο για την παραλληλοποίησηγενικευμένων φωλιασμένων βρόχων που βασίζεται σε μεθόδους υπολογιστικήςγεωμετρίας. Οι φωλιασμένοι βρόχοι περιλαμβάνουν σύνθετα σώματα βρόχων (αναθέσεις,συνθήκες, επαναλήψεις) και επιδεικνύουν ομοιόμορφες εξαρτήσεις μέσω του σώματος τουβρόχου. Ο νεωτερισμός του εργαλείου CRONUS είναι διπλός: πρώτον, προσδιορίζει τοιδανικό υπερ-επίπεδο δρομολόγησης χρησιμοποιώντας τον αλγόριθμο QuickHull, ο οποίοςείναι πιο αποδοτικός από προηγούμενα χρησιμοποιηθείσες μεθόδους και δεύτερον,υλοποιεί έναν απλό και γρήγορο δυναμικό κανόνα, που ονομάζουμε Διαδοχική ΔυναμικήΔρομολόγηση (SDS), για τη δρομολόγηση κατά το χρόνο εκτέλεσης των επαναλήψεων τουβρόχου κατά μήκος του ιδανικού υπερ-επιπέδου. Αυτή η πολιτική δρομολόγησης ενισχύειτην τοπικότητα των δεδομένων και βελτιώνει το συνολικό χρόνο εκτέλεσης. Το CRONUSπαρέχει μια αποτελεσματική προγραμματιστική βιβλιοθήκη για το χρόνο εκτέλεσης(runtime library), ειδικά σχεδιασμένη για να ελαχιστοποιεί το κόστος επικοινωνίας καιλειτουργεί τόσο σε συστήματα μοιραζόμενης μνήμης όσο και σε συστήματακατανεμημένης μνήμης. Χρησιμοποιεί για συγχρονισμό και ανταλλαγή δεδομένων δύοδιαφορετικά μοντέλα, με το πρώτο να βασίζεται αποκλειστικά και μόνο σε κλήσειςανταλλαγής μηνυμάτων, ενώ το δεύτερο συνδυάζει το μηχανισμό των καθολικώνσηματοφορέων για συγχρονισμό και ασύγχρονων μηνυμάτων για ανταλλαγή δεδομένων.Τέλος, σε πραγματικά παραδείγματα επιτυγχάνει σημαντικές επιταχύνσεις και αποδίδειπολύ καλύτερα από άλλα ανάλογα εργαλεία της βιβλιογραφίας.