Δρομολόγηση φωλιασμένων βρόχων με τη χρήση μεθόδων υπολογιστικής γεωμετρίας

Abstract

One of the major problems in the area of parallel processing, is scheduling nested loops. This thesis studies the problem of scheduling nested loops with uniform dependencies, focusing onto the geometric properties of the index space and the dependence vectors of the problem. Initially, a new algorithm for mapping onto distributed memory architectures is presented. The followed technique is based on mapping onto systolic arrays. After the index space transformation is performed, the transformed index space needs to be partitioned and mapped to the given architecture. The partitioning is made along the directions of the transformed index space boundaries. This method achieves optimal load balancing between processors, although scheduling complexity is not optimal. After that, the geometric properties of the index space considered in the uniform nested loop problems are studied. The formal expressions that give the execution wavefront of any time instance are presented. Although they can only be solved by integer linear programming techniques, it is the first time they are computed in closed form. Some special cases are also noted. In these cases, certain inequalities between the algorithm dependence vectors hold and the complexity of computing the execution wavefront decreases dramatically: it can be computed in polynomial or even linear time. Based on the above geometric properties, a technique for scheduling any nested loop problem that follows the unit execution - zero communication time model - UET is presented. This scheduling method is nearly optimal. In addition to the above, we introduce a method of reducing problems that consider the unit execution - unit communication time model - UET-UCT to pure UET equivalent ones. This is one of the main contributions of our work, as it enables any scheduling technique of the bibliography for the UET cases, to apply to any problem that considers unit communication cost. During the scheduling algorithms presented in this thesis, a new method of computing the hyperplane vector Π is concerned. This method is explicitly based on the algorithm dependence vectors and on how these vectors allow the execution of the index space points. Actually, it is a revision of the convex hull computing method, called QuickHull. It should be noted that, in comparison with all other methods of the bibliography, it achieves quite a small complexity. Finally, the generalization of the above scheduling techniques for n-dimensional problems is presented. Certain simulation programs have been implemented, in order to testify the scheduling methods of this thesis. The proposed geometric method is compared with the hyperplane one, as well as with the exhaustive scheduling procedure, also called optimal. The comparison results are analytically presented.

Πρωταρχικό πρόβλημα στο χώρο της παράλληλης επεξεργασίας, αποτελεί η δρομολόγηση φωλιασμένων βρόχων. Η παρούσα διατριβή μελετά τη δρομολόγηση φωλιασμένων βρόχων με ομοιόμορφες εξαρτήσεις, εστιάζοντας στις γεωμετρικές ιδιότητες των εξαρτήσεων και του χώρου δεικτών. Παρουσιάζεται αρχικά, ένας νέος αλγόριθμος απεικόνισης σε αρχιτεκτονικός κατανεμημένης μνήμης. Η τεχνική που ακολουθεί βασίζεται στην απεικόνιση σε συστολικές διατάξεις. Μετά τον κατάλληλο μετασχηματισμό του χώρου δεικτών, απαιτείται η διαμέριση και η απεικόνισή του στη δεδομένη αρχιτεκτονική. Η μέθοδος διαμέρισης που προτείνεται, αξιοποιεί τις διευθύνσεις των συνόρων του μετασχηματισμένου χώρου. Παρότι δεν παρουσιάζει τη βέλτιστη πολυπλοκότητα, επιτυγχάνει αποδοτική απεικόνιση σε επεξεργαστές, ισοκατανέμοντας τον φόρτο εργασίας.Μελετώνται κατόπιν, οι γεωμετρικές ιδιότητες του χώρου δεικτών, για τα προβλήματα φωλιασμένων βρόχων με ομοιόμορφες εξαρτήσεις. Σχηματίζονται οι εξισώσεις που δίνουν την κυματομορφή εκτέλεσης για κάθε χρονική στιγμή. Παρά το γεγονός ότι απαιτείται ακέραιος γραμμικός προγραμματισμός για τη λύση των εξισώσεων αυτών, είναι η πρώτη φορά που παρουσιάζονται σε κλειστή μορφή. Σημειώνονται επιπλέον ειδικές περιπτώσεις, κατά τις οποίες οι κυματομορφές εκτέλεσης είναι απολύτως ομοιόμορφες και επαναλαμβανόμενες. Στις περιπτώσεις αυτές, τα διανύσματα εξάρτησης του αλγορίθμου επαληθεύουν κάποιες ανισότητες και η πολυπλοκότητα υπολογισμού των κυματομορφών εκτέλεσης μειώνεται δραματικά: υπολογίζονται με πολυωνυμικό ή ακόμα και γραμμικό κόστος. Με βάση την ανάλυση των γεωμετρικών ιδιοτήτων, αναδεικνύεται η χρησιμότητα και η εφαρμογή τους στα προβλήματα δρομολόγησης φωλιασμένων βρόχων. Παρουσιάζεται, αρχικά, ένας αλγόριθμος δρομολόγησης, ο οποίος αφορά τα προβλήματα που ακολουθούν το μοντέλο μοναδιαίου κόστους υπολογισμού - μηδενικού κόστους επικοινωνίας - UET. Η δρομολόγηση που προτείνεται είναι ασυμπτωτικά βέλτιστη και εμφανίζει μικρότερο κόστος ανά επανάληψη από τις ήδη υπάρχουσες μεθόδους. Στη συνέχεια, παρουσιάζεται μια μέθοδος αναγωγής των προβλημάτων που ακολουθούν το μοντέλο μοναδιαίου κόστους υπολογισμού - μοναδιαίου κόστους επικοινωνίας - UET-UCT, σε ισοδύναμα προβλήματα μηδενικού κόστους επικοινωνίας -έννοια ισοδυνάμου UET προβλήματος. Επιτυγχάνεται έτσι, η δρομολόγηση των προβλημάτων που εμπεριέχουν κόστος επικοινωνίας, τόσο από τη μέθοδο που προτείνουμε, όσο και από οποιαδήποτε μέθοδο της βιβλιογραφίας που αναφέρεται σε προβλήματα UET. Στις μεθόδους δρομολόγησης που παρουσιάζονται, ακολουθείται μια εναλλακτική μέθοδος υπολογισμού του διανύσματος δρομολόγησης Π. Η μέθοδος αυτή βασίζεται αποκλειστικά στις σχέσεις που συνδέουν τα διανύσματα εξάρτησης και τον τρόπο που αυτά επιτρέπουν την εκτέλεση των στιγμιοτύπων του χώρου δεικτών. Αποτελεί μια παραλλαγή της μεθόδου υπολογισμού του κυρτού περιγράμματος συνόλου σημείων στο n-διάστατο χώρο, ο οποίος ακούει στο όνομα QuickHull. Το ιδιαίτερο χαρακτηριστικό αυτής της εναλλακτικής μεθόδου υπολογισμού του διανύσματος δρομολόγησης, είναι ότι παρουσιάζει εξαιρετικά χαμηλή πολυπλοκότητα, σε σύγκριση με τις υπάρχουσες μεθόδους της βιβλιογραφίας. Προτείνεται τέλος, η βασική ιδέα για τη γενίκευση των παραπάνω γεωμετρικών μεθόδων δρομολόγησης στις η διαστάσεις. Για την αξιολόγηση των μεθόδων δρομολόγησης της παρούσας διατριβής, πραγματοποιήθηκε μια σειρά υλοποιήσεων. Με τη βοήθεια των υλοποιήσεων αυτών, συγκρίνεται η προτεινόμενη γεωμετρική μέθοδος δρομολόγησης τόσο με τη μέθοδο των υπερεπιπέδων, όσο και με την εξαντλητική μέθοδο δρομολόγησης, την επικαλούμενη βέλτιστη. Τα αποτελέσματα που εξάγονται παρατίθενται με τη μορφή πινάκων και διαγραμμάτων.