Algorithms design for the parallelization of nested loops

Abstract

The need for parallel processing arises from the existence of time consuming applications in different areas, such as weather forecasting, nuclear fusion simulations, DNA and protein analysis, computational fluid dynamics, etc. Parallel processing comprises algorithms, computer architecture, parallel programming and performance analysis. In optimizing the performance of scientific and engineering sequential programs, the most gain comes from optimizing nested loops or recursive procedures, where major chunks of computation are performed repeatedly. Nested loops without dependencies are called DOALL, while those with dependencies are called DOACROSS loops. Parallelizing DOACROSS loops is much more challenging than parallelizing DOALL loops, because the existing dependencies between iterations of the loop nest much be satisfied. The challenges that must be addressed for the parallelization of time consuming applications are: minimizing the total execution time, minimizing the communication time between the processors (especially in the case of DOACROSS loops), load balancing the computational load among the processors, dealing with and recovering from failures that may occur either in the program or the system, meeting deadlines, or a combination of these. This doctoral dissertation focuses on parallelizing applications that contain nested DOACROSS loops, while trying to address some of the aforementioned challenges. In particular, it proposes and presents four static methods and three dynamic methods for scheduling nested DOACROSS loops on various architectures. The static scheduling methods were devised for homogeneous systems, while the dynamic scheduling methods were devised for heterogeneous systems or systems with rapidly varying loads. One of the dynamic approaches was bibliographically the first attempt towards the parallelization of nested DOACROSS loops using a coarse grain approach and dynamic scheduling, on heterogeneous systems. The proposed algorithms were implemented, verified and evaluated through extensive experiments on various computer systems architectures.

Η ανάγκη για παράλληλη επεξεργασία προκύπτει από την ύπαρξη χρονοβόρων εφαρμογών σε διάφορους τομείς, όπως η πρόβλεψη καιρού, οι εξομοιώσεις πυρηνικής ένωσης, η ανάλυση του DNA και των πρωτεϊνών, η υπολογιστική προσέγγιση της δύναμης των ρευστών, κ.α. Η παράλληλη επεξεργασία συμπεριλαμβάνει αλγόριθμους, αρχιτεκτονική υπολογιστών, παράλληλο προγραμματισμό και ανάλυση της αποδοτικότητας. Κατά τη βελτιστοποίηση της απόδοσης των ακολουθιακών επιστημονικών και τεχνολογικών προγραμμάτων, το μέγιστο κέρδος προέρχεται από την παραλληλοποίηση των φωλιασμένων βρόχων ή των επαναληπτικών διαδικασιών, όπου μεγάλα κομμάτια υπολογισμού εκτελούνται επανειλημμένα. Οι φωλιασμένοι βρόχοι χωρίς εξαρτήσεις ονομάζονται DOALL, ενώ αυτοί με εξαρτήσεις ονομάζονται DOACROSS. Η παραλληλοποίηση των DOACROSS βρόχων είναι πολύ πιο δύσκολη από την περίπτωση των DOALL βρόχων, διότι πρέπει να ικανοποιηθούν οι υπάρχουσες ανάμεσα στις επαναλήψεις εξαρτήσεις. Οι προκλήσεις που πρέπει να αντιμετωπιστούν για την παραλληλοποίηση χρονοβόρων προβλημάτων είναι: η ελαχιστοποίηση του συνολικού χρόνου επεξεργασίας, η ελαχιστοποίηση του χρόνου επικοινωνίας μεταξύ επεξεργαστών (ιδιαίτερα στην περίπτωση των DOACROSS βρόχων), η εξισορρόπηση του υπολογιστικού φόρτου ανάμεσα στους επεξεργαστές, η αντιμετώπιση και η ανάκτηση από σφάλματα που μπορούν να προκύπτουν στο πρόγραμμα ή στο σύστημα, η διατήρηση των χρονικών περιορισμών, ή ένας συνδυασμός των παραπάνω. Η παρούσα διδακτορική διατριβή εστιάζεται στη παραλληλοποίηση εφαρμογών που περιέχουν DOACROSS βρόχους, αντιμετωπίζοντας μερικές από τις παραπάνω προκλήσεις. Συγκεκριμένα, προτάθηκαν και παρουσιάζονται τέσσερεις στατικές μέθοδοι και τρεις δυναμικές μέθοδοι δρομολόγησης, για διάφορες αρχιτεκτονικές υπολογιστών. Οι στατικές μέθοδοι σχεδιάστηκαν για ομογενή συστήματα, ενώ για ετερογενή συστήματα ή συστήματα με γρήγορο μεταβαλλόμενο φορτίο, σχεδιάστηκαν οι δυναμικές μέθοδοι. Μια από αυτές τις δυναμικές προσεγγίσεις ήταν βιβλιογραφικά η πρώτη προσπάθεια προς την παραλληλοποίηση των DOACROSS φωλιασμένων βρόχων, χρησιμοποιώντας μια χονδρόκοκκη (coarse grain) προσέγγιση και δυναμική δρομολόγηση, σε ετερογενή συστήματα υπολογιστών. Οι προτεινόμενοι αλγόριθμοι υλοποιήθηκαν, επαληθεύτηκαν και αξιολογήθηκαν με εξαντλητικά πειράματα σε διάφορες αρχιτεκτονικές υπολογιστικών συστημάτων.