8.4 Καθυστέρηση Επικοινωνίας

Επόμενο:8.5 Επικοινωνίες Πολλαπλών Θυρών Πάνω: Κεφάλαιο 8o: Προγράμματα περάσματος μηνυμάτων Πίσω: 8.3 Προγράμματα Διασωλήνωσης σε Συστήματα Κατανεμημένης Μνήμης

8.4 Καθυστέρηση Επικοινωνίας

Υπάρχουν τέσσερις τύποι γεγονότων κατά την εκτέλεση ενός προγράμματος Multi-Pascal που προκαλούν την αποστολή ενός μηνύματος κατά μήκους του δικτύου επικοινωνίας:

Εγγραφή σε ένα κανάλι επικοινωνίας

Δημιουργία μιας νέας διεργασίας

Εγγραφή σε μια παράμετρο απομακρυσμένης διεύθυνσης

Τερματισμός διεργασίας

Η εγγραφή σε ένα κανάλι επικοινωνίας έχει ήδη περιγραφεί εκτενώς σε αυτό το κεφάλαιο. Το γεγονός αυτό προκαλεί την αποστολή ενός μηνύματος από τη διεργασία εγγραφής στη διεργασία που κατέχει το κανάλι επικοινωνίας. Αν υποθέσουμε ότι αυτές οι διεργασίες εκτελούνται σε διαφορετικούς επεξεργαστές, θα έχουμε ως αποτέλεσμα την αποστολή του μηνύματος κατά μήκους του δικτύου επικοινωνίας του συστήματος κατανεμημένης μνήμης. Η εκτέλεση μιας δήλωσης δημιουργίας διεργασίας θα δημιουργήσει επίσηςένα μήνυμα “δημιουργίας διεργασίας” θα σταλεί στον επεξεργαστή στον οποίο θα εκτελεστεί η νέα διεργασία. Αυτό το μήνυμα “δημιουργίας διεργασίας” θα περιέχει επίσης τα αρχικά δεδομένα από τις παραμέτρους της διαδικασίας δημιουργίας διεργασίας, όπως αναφέραμε προηγουμένως.

Όταν οποιαδήποτε διεργασία γράφει σε μια παράμετρο απομακρυσμένης διεύθυνσης για την επιστροφή κάποιων δεδομένων στο κυρίως πρόγραμμα, τότε αυτή η λειτουργία προκαλεί την αποστολή των δεδομένων σε ένα μήνυμα διαμέσου του δικτύου επικοινωνίας στον επεξεργαστή όπου βρίσκεται το κυρίως πρόγραμμα. Όταν κάθε διεργασία τελικά τερματίζεται, η γονική διεργασία πρέπει να ειδοποιηθεί, γιατί περιμένει τον τερματισμό του παιδιού της. Αυτή η ειδοποίηση γίνεται με ένα μήνυμα “ειδοποίησης” που στέλνεται κατά μήκους του δικτύου επικοινωνίας από τη διεργασία παιδί στη διεργασία γονέα.

Στην Multi-Pascal για κάθε μια από τις παραπάνω κατηγορίες μηνυμάτων καθορίζεται μια καθυστέρηση επικοινωνίας. Η καθυστέρηση αυτή βασίζεται στη τοπολογία του συστήματος κατανεμημένης μνήμης που έχει επιλεγεί, τα φυσικά χαρακτηριστικά του δικτύου επικοινωνίας και την τρέχουσα κυκλοφορία μηνυμάτων στο δίκτυο. Η καθυστέρηση επικοινωνίας λαμβάνεται υπόψη στην προσομοίωση του προγράμματος εκτέλεσης και στα στατιστικά της αναφερόμενης απόδοσης. Ο σκοπός αυτής της παραγράφου είναι να εξηγήσει το μοντέλο επικοινωνίας που χρησιμοποιείται στο λογισμικό προσομοίωσης για να καθορίσει την καθυστέρηση της επικοινωνίας. Το μοντέλο επικοινωνίας χρησιμοποιείται και στην ανάλυση απόδοσης προγραμμάτων των συστημάτων κατανεμημένης μνήμης στα κεφάλαια που ακολουθούν.

8.4.1 Βασικό μοντέλο επικοινωνίας

Κάθε μήνυμα όταν δημιουργείται χωρίζεται σε πακέτα. Οι τιμές των δεδομένων ομαδοποιούνται σε πακέτα με τρεις τιμές ανά πακέτο. Στην προκειμένη περίπτωση μια τιμή δεδομένων μπορεί να είναι σε οποιοδήποτε από τους βασικούς τύπους δεδομένων της Pascal: Integer, Real, Char ή Boolean. Αν ο συνολικός αριθμός των τιμών δεδομένων στο μήνυμα δεν διαιρείται ακριβώς με το τρία τότε το τελευταίο πακέτο περιέχει δύο ή μόνο μια τιμή. Για παράδειγμα, ένας πίνακας με 10 τιμές θα δημιουργήσει ένα μήνυμα των 4 πακέτων. Υποτίθεται ότι ένα μήνυμα τερματισμού διεργασίας αποτελεί ένα πακέτο. Όμοια, ένα μήνυμα δημιουργίας διεργασίας αποτελείται από ένα πακέτο και προστίθεται ένας επιπλέον, οποιοσδήποτε, αριθμός πακέτων που χρειάζονται για να περιέχουν τις αρχικές παραμέτρους για τη διεργασία. Το μήνυμα δημιουργίας της διεργασίας δεν περιέχει τον κώδικα του προγράμματος για τη διεργασία-υποτίθεται ότι ο κώδικας έχει ήδη αποθηκευτεί στην τοπική μνήμη του κάθε επεξεργαστή. Τα περισσότερα συστήματα κατανεμημένης μνήμης έχουν ένα ειδικό μηχανισμό υψηλής ταχύτητας για τη διάδοση του κώδικα του προγράμματος στον κάθε επεξεργαστή πριν αρχίσει η εκτέλεση του προγράμματος.

Μια σημαντική παράμετρος που καθορίζει την ταχύτητα των επικοινωνιών σε ένα σύστημα κατανεμημένης μνήμης είναι ο χρόνος T που απαιτείται για την μετάδοση ενός πακέτου διαμέσου ενός μόνο φυσικού συνδέσμου επικοινωνίας. Μία άλλη σημαντική παράμετρος είναι ο χρόνος επεξεργασίας P για κάθε πακέτο στη διεπαφή επικοινωνίας. Αν υποθέσουμε ότι ο χρόνος επεξεργασίας είναι αμελητέος στο προηγούμενο κεφάλαιο αναπτύξαμε τον παρακάτω τύπο για το χρόνο επικοινωνίας ενός μηνύματος με k πακέτα κατά μήκους ενός μονοπατιού με m συνδέσμους επικοινωνίας:

Καθυστέρηση Επικοινωνίας: (m+k-1)T

Αυτός ο τύπος υπολογίζεται προσθέτοντας δύο παράγοντες: το χρόνο που χρειάζεται το αρχικό πακέτο να φτάσει στον προορισμό (mT) και το χρόνο που χρειάζεται για τα υπόλοιπα πακέτα να ακολουθήσουν ([k-1]T). Αν ο χρόνος επεξεργασίας P δεν είναι αμελητέος τότε μπορεί να επηρεάσει αυτά τα δύο στοιχεία. Έχουμε υποθέσει ότι η επεξεργασία σε κάθε διεπαφή επικοινωνίας μπορεί να επικαλυφθεί πλήρως με τη μετάδοση στους συνδετικούς συνδέσμους επικοινωνίας. Έτσι, κάθε διεπαφή επικοινωνίας μπορεί να επεξεργάζεται ένα πακέτο ενώ άλλα πακέτα αποστέλλονται ή λαμβάνονται από τους συνδέσμους. Με αυτή την υπόθεση ο χρόνος που απαιτείται για να φτάσει τον προορισμό του το αρχικό πακέτο θα είναι m(T+P). Στην περίπτωση αυτή τα υπόλοιπα πακέτα θα ακολουθήσουν σε κανονικά διαστήματα, των οποίων η διάρκεια καθορίζεται από το μέγιστο των (T, P). Συνεπώς, η συνολική καθυστέρηση επικοινωνίας για ένα μήνυμα είναι:

Καθυστέρηση Επικοινωνίας: m(T+P)+(k-1)max(T,P)

Στην Multi-Pascal ο χρήστης πρέπει να καθορίσει τη βασική καθυστέρηση επικοινωνίας που είναι το άθροισμα T+P. Για λόγους απλότητας, υποθέτουμε ότι T=P. Θεωρώντας ότι η βασική καθυστέρηση επικοινωνίας είναι D, έχουμε ότι T=P=D/2. Τότε ο παραπάνω τύπος απλοποιείται στον ακόλουθο:

Καθυστέρηση Επικονωνίας:

Για ένα μήνυμα με ένα μόνο πακέτο αυτός ο τύπος δίνει καθυστέρηση επικοινωνίας ίση με mD. Έτσι, η παράμετρος D μπορεί να γίνει αντιληπτή ως ο βασικός χρόνος που απαιτείται για την επικοινωνία ένός απλού πακέτου ανάμεσα σε δυο επεξεργαστές με απευθείας φυσικό σύνδεσμο επικοινωνίας. Η καθυστέρηση επικοινωνίας που έχουμε κατά την αποστολή ενός πακέτου κατά μήκους ενός μονοπατιού με m συνδέσμους είναι mD. Η εφαρμογή αυτού του τύπου φαίνεται στο σχήμα 8.7, όπου φαίνονται τα διαδοχικά βήματα στην μετάδοση ενός μηνύματος τριών πακέτων (k=3) κατά μήκους ενός μονοπατιού με τρεις συνδέσμους επικοινωνίας (m=3). Σε αυτή την περίπτωση ο τύπος προβλέπει χρόνο επικοινωνίας ίσο με 4D.

ΣΧΗΜΑ 8.7 Αποστολή μηνύματος με πολλά πακέτα

Το σχήμα 8.7 δείχνει ένα στιγμιότυπο της κατάστασης μετά από κάθε D/2 μονάδες χρόνου και με τον χρόνο να απεικονίζεται κάθετα από την κορυφή προς το κάτω μέρος του σχήματος. Οι κύκλοι απεικονίζουν τους επεξεργαστές, καθένας από τους οποίους έχει τη δική του διεπαφή επικοινωνίας και οι συνδετικές γραμμές αναπαριστούν τους συνδέσμους επικοινωνίας. Τα τρία πακέτα του μηνύματος αναπαρίστανται από τα τρία μικρά τετράγωνα, που είναι αριθμημένα από το 1 ως το 3. Όταν ένα πακέτο μηνύματος στο σχήμα είναι πάνω σε ένα σύνδεσμο επικοινωνίας τότε μεταδίδεται από αυτόν τον σύνδεσμο. Ένα πακέτο μηνύματος μέσα σε έναν κύκλο επεξεργαστή σημαίνει η διεπαφή επικοινωνίας αυτού του επεξεργαστή επεξεργάζεται το πακέτο. Εφόσον ο χρόνος επεξεργασίας σε κάθε διεπαφή είναι ίσος με το χρόνο μετάδοσης κατά μήκος κάθε συνδέσμου (D/2) τα πακέτα του μηνύματος κινούνται το ένα πίσω από το άλλο κατά μήκος του μονοπατιού επικοινωνίας, όπως φαίνεται στο σχήμα.

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

Κάποια προγράμματα έχουν πιο συχνή κυκλοφορία μηνυμάτων που εκτείνεται σε μεγαλύτερα μονοπάτια κατά μήκους του δικτύου.Αυτό έχει ως αποτέλεσμα την ενδεχόμενη σύγκρουση των μηνυμάτων και συνεπώς καθυστερήσεις που μπορεί να μειώσουν την απόδοση του προγράμματος. Για την προσομοίωση της εκτέλεσης τέτοιων προγραμμάτων η Multi-Pascal έχει μια επιλογή “συμφόρησης” κατά την οποία κάθε ξεχωριστό πακέτο μηνύματος ακολουθείται καθώς κινείται στο δίκτυο επικοινωνίας. Το σύστημα παρακολουθεί κατά καιρούς τους συνδέσμους επικοινωνίας και τις διεπαφές που είναι απασχολημένες. Όταν ένα πακέτο απαιτεί τη χρήση ενός συνδέσμου ή μιας διεπαφής που την τρέχουσα χρονική στιγμή είναι απασχολημένη τότε καθυστερείται τη μετακίνησή του. Λεπτομέρειες πάνω στο θέμα της επιλογής συμφόρησης μπορούν να βρεθούν στο τμήμα 10.2 του Παραρτήματος.

8.4.2 Επιβάρυνση λογισμικού

Η προηγούμενη αναφορά στην καθυστέρηση επικοινωνίας είχε σχέση με το χρόνο που κάνει ένα μήνυμα να ταξιδεύσει από την αφετηρία στον προορισμό του. Θα ήταν πολύ χρήσιμο να σκεφτούμε το ρόλο του επεξεργαστή σε αυτή την επικοινωνία. Όλη η επικοινωνία αρχικοποιείται από κάποιες λειτουργίες στο πρόγραμμα της Multi-Pascal, όπως είναι η λειτουργία εγγραφής σε μια θύρα επικοινωνίας. Η Multi-Pascal θα χρεώσει με μια μικρή επιβάρυνση λογισμικού για το χρόνο εκτέλεσης αυτών των λειτουργιών, όπως και στην περίπτωση όλων των εντολών του προγράμματος. Επίσης, ο εκάστοτε προορισμός θα έχει κάποια επιπλέον επιβάρυνση λογισμικού, εφόσον μια εντολή της Multi-Pascal εκτελείται για τη λήψη ενός μηνύματος, όπως για παράδειγμα η ανάγνωση από μια θύρα επικοινωνίας. Συνεπώς, ο συνολικός χρόνος επικοινωνίας θα είναι το άθροισμα αυτής της καθορισμένης επιβάρυνσης στον επεξεργαστή αφετηρίας και τον αντίστοιχο προορισμού, συν την καθυστέρηση στο δίκτυο επικοινωνίας, που υπολογίστηκε παραπάνω.

Η επιβάρυνση λογισμικού στην αφετηρία και τον προορισμό έχουν συνήθως την ίδια τιμή των 10 μονάδων χρόνου. Εξαρτάται βέβαια από την πολυπλοκότητα των εντολών που προκαλούν την επικοινωνία. Εκτός από τον χρόνο που απαιτείται για την εκτέλεση αυτών των εντολών στους επεξεργαστές αφετηρίας και προορισμού, δεν προκαλείται από την επικοινωνία επιπλέον επιβάρυνση του επεξεργαστή. Υποθέτουμε ότι το δίκτυο επικοινωνίας μπορεί να λειτουργήσει ανεξάρτητα από τη στιγμή που το μήνυμα έχει σταλεί από τον επεξεργαστή προορισμού. Ακόμα και όταν το μήνυμα κινείται κατά μήκος του δικτύου οι επεξεργαστές μπορούν συνεχίσουν την εκτέλεσή τους κανονικά χωρίς μείωση της απόδοσής τους. Παρά το ότι αυτή η περίπτωση δεν είναι αντιπροσωπευτική όλων των συστημάτων κατανεμημένης μνήμης, συμβαίνει στα πιο σύγχρονα μοντέλα που έχουν περίπλοκο δίκτυο επικοινωνίας. Αυτή η σημαντική ιδιότητα του δικτύου επικοινωνίας οδηγεί στην πιθανότητα επικάλυψης επικοινωνίας και υπολογισμών - το θέμα αυτό αναλύεται περισσότερο στο κεφάλαιο 9.

Για να δείξουμε τη χρήση της Multi-Pascal στην ανάλυση της απόδοσης των προγραμμάτων συστημάτων κατανεμημένης μνήμης θεωρείστε το πρόγραμμα διασωλήνωσης που παρουσιάσαμε στην προηγούμενη παράγραφο. Η Ταξινόμηση με Εισαγωγή εκτελέστηκε σε Πλήρως Συνδεδεμένη τοπολογία και σε τοπολογία Γραμμής, η κάθε μια με 101 επεξεργαστές. Τα αποτελέσματα φαίνονται στο σχήμα 8.8. Ο κάθετος άξονας είναι ο χρόνος εκτέλεσης του προγράμματος και ο οριζόντιος δίνει την τιμή της βασικής καθυστέρησης επικοινωνίας. Στην Multi-Pascal υπάρχει μιε εντολή που επιτρέπει στον χρήστη να δίνει διαφορετικές τιμές στην βασική καθυστέρηση επικοινωνίας (η παράμετρος D στον τύπο που αναλύθηκε προηγουμένως), με σκοπό τον υπολογισμό την επίδρασης των καθυστερήσεων επικοινωνίας στην απόδοση του προγράμματος.

Στο σχήμα 8.8 οι καμπύλες απόδοσης δίνονται για τις παρακάτω τρεις τοπολογίες: Πλήρως Συνδεδεμένη τοπολογία, τοπολογία Γραμμής με ανενεργή την επιλογή συμφόρησης και τοπολογία Γραμμής με ενεργή την επιλογή συμφόρησης. Για την Πλήρως Συνδεδεμένη τοπολογία ο χρόνος εκτέλεσης αυξάνεται γραμμικά σε σχέση με την βασική καθυστέρηση επικοινωνίας. Αυτό το πρότυπο απόδοσης είναι τυπικό των προγραμμάτων διασωλήνωσης. Οι δυο καμπύλες των τοπολογιών Γραμμής δείχνουν ότι η συμφόρηση αρχίζει να γίνεται πρόβλημα όταν η βασική καθυστέρηση επικοινωνίας είναι μεγαλύτερη από 40 μονάδες χρόνου-και σε αυτή την περίπτωση όμως δεν αποτελεί σοβαρό πρόβλημα.

ΣΧΗΜΑ 8.8 Απόδοση της Ταξινόμησης με Εισαγωγή