Αλγοριθμοι Δυναμικης Δρομολογησης Εφαρμογων Που Περιεχουν Φωλιασμενους Βροχους Σε Ετερογενη Δυκτια Υπολογιστων

Abstract

Ο στόχος της έρευνας ήταν η ανεύρεση αποδοτικών αλγορίθμων για την παραλληλοποίηση φωλιασμένων βρόχων που περιέχουν εξαρτήσεις σε κατανεμημένα συστήματα (δίκτυα υπολογιστών). Τα κατανεμημένα συστήματα είναι ένα ελκυστικό περιβάλλον εκτέλεσης παράλληλων εφαρμογών λόγω του χαμηλού κόστους συγκρότησης, σε σχέση με τα παραδοσιακά παράλληλα μηχανήματα. Ωστόσο, πολλές φορές χαρακτηρίζονται από ανομοιογένεια (heterogeneity) σε διάφορα επίπεδα, όπως ανομοιογένεια στους τύπους των υπολογιστών και στο δίκτυο που τα συνδέει και ανομοιογένεια και μεταβλητότητα στο φόρτο εργασίας (workload variation). Τα ιδιαίτερα αυτά χαρακτηριστικά κάνουν επιτακτική την ανάγκη ανάπτυξης νέων αλγορίθμων δρομολόγησης. Η έρευνα επικεντρώνεται στους δυναμικούς αλγόριθμους γιατί έχουν την δυνατότητα να προσαρμόζονται στις συνθήκες που επικρατούν στο περιβάλλον που εκτελούνται, δίνοντας έτσι την δυνατότητα να αντιμετωπίσουμε την ανομοιογένεια των πόρων και την διακύμανση του φόρτου εργασίας. Με την ολοκλήρωση της διατριβής παρουσιάστηκε μια σειρά νέων αλγορίθμων για την δυναμική δρομολόγηση εφαρμογών που περιέχουν φωλιασμένους βρόχους σε αρχιτεκτονικές κατανεμημένης μνήμης. Οι προτεινόμενοι αλγόριθμοι υλοποιήθηκαν, επαληθεύτηκαν και αξιολογήθηκαν με εξαντλητικά πειράματα.