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

Abstract

The evolution of computer technology has been rapid over the past two decades. Equally striking, however, is the increase of needs in computing power. To meet the demanding and lengthy algorithms we introduce parallel processing. Parallel processing has been used for many years, mainly in the field of high performance computing, but interest in it has become even greater in recent years due to physical constraints that prevent further escalation of processors' frequency. Thus, it has recently become the dominant standard in computer architecture, mainly in the form of multicore processors. The coding of parallel programs is nonetheless significantly more difficult than that of the corresponding sequential, as the parallelism in the execution introduces several new categories of software errors. In addition, synchronization and communication costs between the parallel processes are usually the greatest obstacles in order to achieve good performance and decent acceleration from parallel programs. Finally, despite decades of work by researchers in the field of compilers, automatic parallelization of sequential programs had only limited success. The main parallel programming languages are explicitly parallel or, at best, partially driven, with the developer giving the compiler instructions for the parallelization of the code. The purpose of this thesis is the introduction and presentation to the developer of ways to facilitate programming in parallel processing systems and the efficient implementation of the respective mechanisms. The problem is approached from two different angles, giving the developer maximum flexibility in order to achieve the best results from the parallel program. The first approach is from the system level, in order to give the developer options for handwriting parallel code more easily and led to the implementation of the global semaphores mechanism. This mechanism has been implemented and ported to several different parallel programming environments, with the main being the parallel platforms PVM and MPI and is available as a C language library (runtime library) and some additional definitions files (include files). By using it, the parallel applications developer can address the problems of synchronizing parallel processes, mutual exclusion of critical sections and system resource allocation. The second approach is from the perspective of the compiler, so that a category of sequential algorithms can be automatically translated into equivalent parallel code and led to the implementation of the tool CRONUS. The CRONUS platform is an automated tool for the parallelization of general nested loops and is based on methods of computational geometry. Nested loops include complex loop bodies (assignments, conditionals, repetitions) and exhibit uniform dependencies through the body of the loop. The novelty of the CRONUS tool is twofold: firstly, it determines the optimal scheduling hyperplane using the QuickHull algorithm, which is more efficient than previously used methods and secondly, it implements a simple and efficient dynamic rule we call Successive Dynamic Scheduling (SDS), for the runtime scheduling of the loop iterations along the optimal hyperplane. This scheduling policy enhances data locality and improves the overall execution time. CRONUS provides an efficient runtime library, specifically designed to minimize the cost of communication and works both on shared memory and distributed memory systems. It uses two different models for data exchange and synchronization, with the first to rely solely on message passing calls, while the second combines the mechanism of global semaphores for synchronization and asynchronous message passing for data exchange. Finally, in real examples, it achieves significant speedups and performs much better than other similar tools of the literature.

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