Δρομολόγηση φωλιασμένων βρόχων με τη χρήση μεθόδων υπολογιστικής γεωμετρίας
Authors: Δροσίτης Ιωάννης 
Published: August 2021

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