Συστήματα παράλληλης επεξεργασίας
Authors: Θεοδωρόπουλος Παναγιώτης 
Published: August 2021

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