7.1 Επικοινωνία μεταξύ Επεξεργαστών

Επόμενο:7.2 Τοπολογίες Συστημάτων Κατανεμημένης Μνήμης Πάνω: Κεφάλαιο 7o : Αρχιτεκτονική συστημάτων κατανεμημένης μνήμης Πίσω: Κεφάλαιο 7o : Αρχιτεκτονική συστημάτων κατανεμημένης μνήμης

7.1 Επικοινωνία μεταξύ Επεξεργαστών

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

7.1.1 Σύνδεσμος επικοινωνίας

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

ΣΧΗΜΑ 7.1 Σύνδεσμος επικοινωνίας επεξεργαστών

Η λειτουργία της διεπαφής επικοινωνίας όσον αφορά τον επεξεργαστή είναι όμοια με τη διεπαφή εισόδου-εξόδου (Ε/Ε) σε ένα συνηθισμένο υπολογιστή. Η διεπαφή Ε/Ε λαμβάνει εντολές εισόδου ή εξόδου από τον επεξεργαστή και στη συνέχεια τις μεταφέρει σε μια συγκεκριμένη συσκευή, όπως είναι ο εκτυπωτής ή ο οδηγός δισκέτας, για να εκτελεστούν και να σταλούν ή να ληφθούν δεδομένα. Η διεπαφή Ε/Ε απελευθερώνει τον επεξεργαστή από λεπτομέρειες χαμηλού επιπέδου που αφορούν τον έλεγχο υλικού των συσκευών εισόδου-εξόδου, έτσι ώστε να ασχοληθεί με τη συνέχιση των υπολογισμών όσο πραγματοποιείται η είσοδος ή η έξοδος. Συνήθως η διεπαφή Ε/Ε έχει Απευθείας Προσπέλαση της Μνήμης (Direct Memory Access - DMA), που επιτρέπει την εγγραφή ή την ανάγνωση δεδομένων απευθείας από τη μνήμη χωρίς να χρειάζεται να παρεμβληθεί ο επεξεργαστής. Η λειτουργία της διεπαφής επικοινωνίας σε ένα παράλληλο σύστημα κατανεμημένης μνήμης είναι παρόμοια με τη διεπαφή Ε/Ε - είναι απλά ένας νέος τύπος. Η μόνη διαφορά είναι ότι τα δεδομένα μεταφέρονται διαμέσου ενός συνδέσμου επικοινωνίας και όχι μιας συσκευής Ε/Ε.

Όπως φαίνεται και στο σχήμα 7.1, ο σύνδεσμος επικοινωνίας είναι διπλής κατεύθυνσης, πράγμα που σημαίνει ότι τα δεδομένα μπορούν να μετακινηθούν και προς τις δυο κατευθύνσεις. Κάθε διεπαφή επικοινωνίας έχει τη δυνατότητα αποστολής αλλά και λήψης μηνυμάτων. Ο σύνδεσμος επικοινωνίας είναι απλά μια ηλεκτρική σύνδεση που μπορεί να μεταφέρει ακολουθίες bits από τη μια διεπαφή επικοινωνίας στην άλλη. Κάποιος μπορεί να θεωρήσει αυτή τη διεπαφή επικοινωνίας ως ένα σωλήνα - τα bits εισάγονται ένα κάθε φορά στο ένα άκρο του σωλήνα, κινούνται κατά μήκος αυτού και τελικά φτάνουν στο άλλο άκρο. Σε κάθε δεδομένη στιγμή, μια από τις διεπαφές επικοινωνίας θα είναι ο παραλήπτης και η άλλη θα είναι ο αποστολέας. Η βασική μονάδα επικοινωνίας είναι ένα πακέτο ή ένα μήνυμα που αποτελείται από πολλά bits δεδομένων. Ο αποστολέας στέλνει διαμέσου του συνδέσμου επικοινωνίας τα bits του μηνύματος, ένα κάθε φορά, μέχρι όλα να ληφθούν από το άλλο άκρο.

Είναι προφανές ότι δαπανάται κάποιος χρόνος στη μετάδοση κάθε μηνύματος. Ο σύνδεσμος δεδομένων έχει ένα συγκεκριμένο μέγιστο εύρος ζώνης, που συνήθως μετράται σε bits ανά δευτερόλεπτο. Ένα συνηθισμένο εύρος ζώνης για ένα τέτοιο σύνδεσμο επικοινωνίας είναι είναι 10 megabits ανά δευτερόλεπτο. Αν ένα πακέτο μηνύματος περιλαμβάνει 50 bytes, τότε απαιτούνται 40 microseconds για τη μετάδοση. Αυτός ο χρόνος είναι σημαντικός όταν συγκρίνεται με την ταχύτητα του επεξεργαστή, που μπορεί να απαιτεί 1 ως 10 microseconds για την εκτέλεση μιας εντολής.

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

7.1.2 Δρομολόγηση και Συμφόρηση

Κάθε διεπαφή επικοινωνίας μπορεί να έχει πολλούς συνδέσμους που να τη συνδέουν σε πολλούς διαφορετικούς επεξεργαστές όπως φαίνεται και στο σχήμα 7.2. Ο επεξεργαστής στο κέντρο του σχήματος έχει τέσσερις απευθείας συνδέσμους επικοινωνίας προς τους άλλους επεξεργαστές. Αυτοί οι άλλοι επεξεργαστές έχουν με τη σειρά τους απευθείας συνδέσμους σε άλλους επεξεργαστές. Αυτά τα εννιά ζευγάρια επεξεργαστή-μνήμης με όλους τους συνδέσμους επικοινωνίας που τα συνδέουν αποτελούν ένα δίκτυο επικοινωνίας. Κάθε επεξεργαστής μπορεί να επικοινωνεί απευθείας με τους άμεσους γείτονες του χρησιμοποιώντας τους άμεσους συνδέσμους επικοινωνίας Επίσης επεξεργαστές που δεν έχουν άμεσες συνδέσεις μπορούν να επικοινωνούν με την προώθηση μηνυμάτων από ενδιάμεσες διεπαφές επικοινωνίας. Για παράδειγμα, ο επεξεργαστής 0 μπορεί να μεταδώσει ένα

alt

ΣΧΗΜΑ 7.2 Δίκτυο επικοινωνίας

μήνυμα στον επεξεργαστή 2 στέλνοντάς το απευθείας στη διεπαφή επικοινωνίας του επεξεργαστή 1, που θα το προωθήσει στη διεπαφή επικοινωνίας του επεξεργαστή 2. Έτσι, αν ο χρόνος μετάδοσης με ένα μονό σύνδεσμο επικοινωνίας είναι Τ μονάδες χρόνου, τότε ο συνολικός χρόνος που απαιτείται για τη μετάδοση ενός μηνύματος από τον επεξεργαστή 0 στον επεξεργαστή 2 είναι 2Τ μονάδες.

Για κάποια ζευγάρια επεξεργαστών υπάρχουν εναλλακτικά μονοπάτια στο δίκτυο. Ο P0 μπορεί να στείλει ένα μήνυμα στον P5 ακολουθώντας κάποιο από τα παρακάτω μονοπάτια: P0-P1-P2-P5, P0-P1-P4-P5, P0-P3-P4-P5. Και τα τρία αυτά πιθανά μονοπάτια απαιτούν τη μετακίνηση του μηνύματος μεταξύ τριών συνδέσμων επικοινωνίας. Συνεπώς, η συνολική καθυστέρηση της επικοινωνίας από τον P0 στον P5 είναι 3Τ. Για να είναι δυνατή η σωστή δρομολόγηση κάθε μηνύματος προς τον προορισμό του, κάθε πακέτο μηνύματος περιέχει ως τμήμα της επικεφαλίδας του τον αριθμό του επεξεργαστή στον οποίο κατευθύνεται. Η γενική μορφή ενός πακέτου μηνύματος φαίνεται στο σχήμα 7.3

ΣΧΗΜΑ 7.3 Μορφή πακέτου επικοινωνίας

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

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

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

Αν σε κάποια δεδομένη χρονική στιγμή κυκλοφορούν αρκετά μηνύματα μέσα στο δίκτυο, υπάρχει πιθανότητα επιπλέον καθυστερήσεων αν δύο μηνύματα προσεγγίσουν την ίδια διεπαφή με μικρή διαφορά το ένα από το άλλο. Κάθε διεπαφή έχει ένα όριο στον ρυθμό με τον οποίο μπορεί να χειριστεί τα μηνύματα. Αν ο ρυθμός άφιξης των μηνυμάτων υπερβεί αυτό το όριο, τότε θα έχουμε ως αποτέλεσμα κάποιες καθυστερήσεις. Για παράδειγμα, έστω ότι στο σχήμα 7.2 ο επεξεργαστής P1 στέλνει μια σειρά μηνυμάτων στον επεξεργαστή P7 που βρίσκεται στην αντίθετη πλευρά του δικτύου. Το πιο σύντομο μονοπάτι για αυτή την επικοινωνία είναι το P1-P4-P7. Όμως, έστω ότι την ίδια στιγμή ο επεξεργαστής P3 στέλνει μια σειρά μηνυμάτων στον επεξεργαστή P5. Για αυτήν την επικοινωνία το πιο σύντομο μονοπάτι είναι το P3-P4-P5. Βλέπουμε ότι και οι δύο επικοινωνίες περνούν από τον επεξεργαστή P4. Αυτό το σενάριο επικοινωνίας φαίνεται καλύτερα στο σχήμα 7.4.

ΣΧΗΜΑ 7.4 Συμφόρηση σε δίκτυο επικοινωνίας

Αν και από τις δύο αφετηρίες των διεπαφών επικοινωνίας 1 και 3 στέλνονται μηνύματα με το μέγιστο ρυθμό επικοινωνίας, τότε η διεπαφή 4 δεν θα είναι σε θέση να χειριστεί όλη την κυκλοφορία των μηνυμάτων. Αν κάθε διεπαφή μπορείνα χειριστεί r μηνύματα το δευτερόλεπτο, τότε τα μηνύματα θα συγκλίνουν στη διεπαφή 4 με ρυθμό 2r το δευτερόλεπτο. Έτσι, οι διεπαφές 1 και 3 θα βρουν την διεπαφή 4 απασχολημένη το μισό χρόνο. Το αποτέλεσμα είναι ότι τα μηνύματα πρέπει να τεθούν σε μια ουρά στις αφετηρίες των διεπαφών 1 και 3 για να μεταδοθούν στη διεπαφή 4. Έτσι, κάθε διεπαφή πρέπει να έχει κάποιο χώρο αποθήκευσης όπου θα τοποθετούνται τα μηνύματα που πρόκειται να μεταδοθούν. Η περίπτωση στην οποία τα μηνύματα δημιουργούνται και καθυστερούνται ονομάζεται κυκλοφοριακή συμφόρηση.

Η κυκλοφοριακή συμφόρηση μιας διεπαφής ενός δικτύου επικοινωνίας μπορεί γρήγορα να διαδοθεί και στις γειτονικές διεπαφές. Η κατάσταση είναι όμοια με τη ροή της κίνησης των αυτοκινήτων σε ένα δίκτυο δρόμων μιας πόλης. Κάθε διασταύρωση είναι ανάλογη με τις διεπαφές και κάθε δρόμος της διασταύρωσης είναι ανάλογος με το σύνδεσμο επικοινωνίας. Κάθε διασταύρωση έχει μια μέγιστη δυνατότητα χειρισμού της κυκλοφοριακής κίνησης. Αν η ροή των αυτοκινήτων υπερβεί αυτή την δυνατότητα, τότε το αποτέλεσμα είναι συμφόρηση: η κίνηση θα μεταδοθεί σε όλους τους γύρω δρόμους. Τελικά, η κίνηση μπορεί να διαδοθεί τόσο που να επηρεαστούν και οι γειτονικές διασταυρώσεις, προκαλώντας περισσότερη συμφόρηση. Μια λύση στο πρόβλημα αυτό είναι να αρχίσει η τροχαία, που γνωρίζει ίσως τις μπλοκαρισμένες διασταυρώσεις, να διοχετεύει την κίνηση σε διαφορετικούς δρόμους. Η λύση αυτή μπορεί επίσης να εφαρμοστεί και σε ένα δίκτυο επικοινωνίας παράλληλου συστήματος κατανεμημένης μνήμης. Ο αλγόριθμος δρομολόγησης που χρησιμοποιείται από κάθε διεπαφή επικοινωνίας μπορεί να λάβει υπόψη του το πρόβλημα της συμφόρησης. Μια πιο λεπτομερής ανάλυση τέτοιων αλγορίθμων δρομολόγησης είναι πέρα από τον στόχο του συγκεκριμένου βιβλίου. Περισσότερο εκτενής αναφορά αυτού του θέματος γίνεται στον Tanenbaum [1989].

Το αν θα εμφανιστεί συμφόρηση ή όχι εξαρτάται τόσο από την επικοινωνία του δικτύου όσο και από την συμπεριφορά του παράλληλου αλγορίθμου που εκτελείται στην δεδομένη χρονική στιγμή. Κάποιοι αλγόριθμοι έχουν σχετικά αραιή επικοινωνία και έτσι δεν προκαλείται συμφόρηση. Κάποιοι άλλοι μπορεί να έχουν μερικές χρονικές στιγμές κατά την διάρκεια των οποίων δημιουργούνται πολλά μηνύματα από διαφορετικούς επεξεργαστές και έτσι μπορεί προσωρινά να προκληθεί συμφόρηση σε κάποια τμήματα του δικτύου. Εξαιτίας των καθυστερήσεων που απαιτούνται για την επικοινωνία, οι αλγόριθμοι σχεδιάζονται πάντα με βάση τον στόχο της ελαχιστοποίησης της ποσότητας της επικοινωνίας. Ένας τρόπος για την μείωση του κόστους του επιπλέον χρόνου εκτέλεσης, που συνδέεται με την επικοινωνία, είναι η βελτίωση των χαρακτηριστικών της επικοινωνίας του δικτύου. Αυτό μπορεί να επιτευχθεί προσθέτοντας περισσότερους απευθείας συνδέσμους και αυξάνοντας το εύρος ζώνης τους και επιπλέον αυξάνοντας την ταχύτητα των διεπαφών επικοινωνίας. Μια άλλη μέθοδος είναι να σχεδιάσουμε τον αλγόριθμο με τέτοιο τρόπο ώστε να ταιριάζει με την τοπολογία του δεδομένου δικτύου στο οποίο εκτελείται και με το στόχο της ελαχιστοποίησης της συχνότητας της επικοινωνίας και την απόσταση που διανύεται από κάθε μήνυμα.

7.1.3 Καθυστέρηση της επικοινωνίας.

Ο χρόνος επικοινωνίας που χρειάζεται ένα μήνυμα για να κινηθεί κατά μήκος ενός δικτύου έχει τρία συστατικά στοιχεία: το χρόνο μετάδοσης, το χρόνο επεξεργασίας και το χρόνο αναμονής. Ο χρόνος αναμονής είναι αποτέλεσμα των καθυστερήσεων που προκαλούνται από συμφόρηση στο δίκτυο επικοινωνίας. Ο χρόνος μετάδοσης είναι ο χρόνος που απαιτείται για τη φυσική διάδοση των bits του μηνύματος διαμέσου των συνδέσμων επικοινωνίας. Αν το μήνυμα μαζί με την επικεφαλίδα είναι συνολικά L bits και κάθε σύνδεσμος επικοινωνίας έχει εύρος ζώνης B τότε ο χρόνος μετάδοσης ανά σύνδεσμο είναι L/B.Το τμήμα καθυστέρησης επικοινωνίας που αναφέρεται στο χρόνο επεξεργασίας είναι αποτέλεσμα της αναγκαιότητας να πραγματοποιηθούν κάποιοι υπολογισμοί μέσα σε κάθε διεπαφή για κάθε μήνυμα. Αυτοί οι υπολογισμοί περιλαμβάνουν ανίχνευση λάθους χρησιμοποιώντας έλεγχο αθροίσματος και αποφάσεις δρομολόγησης που βασίζονται στους αριθμούς αφετηρίας και προορισμού των επεξεργαστών. Ας χρησιμοποιήσουμε το L για να δηλώσουμε το μέσο χρόνο επεξεργασίας που απαιτείται ανά μήνυμα σε κάθε διεπαφή. Αν το μήνυμα έχει να διασχίσει m συνδέσμους από την αφετηρία του ως τον προορισμό του, τότε το άθροισμα του χρόνου μετάδοσης και του χρόνου επεξεργασίας είναι m(L/B+P).

Στα περισσότερα παράλληλα συστήματα κατανεμημένης μνήμης, η επικοινωνία γίνεται με ένα καθορισμένο μέγεθος πακέτου. Τα μηνύματα που υπερβαίνουν αυτό το προκαθορισμένο μέγεθος χωρίζονται σε διάφορα πακέτα, που μεταδίδονται ακολουθιακά. Αυτό το καθορισμένο μέγεθος πακέτου επιτρέπει τη χρησιμοποίηση χώρων αποθήκευσης καθορισμένου μεγέθους στις διεπαφές επικοινωνίας και γενικά τείνει να απλοποιεί την εσωτερικά επεξεργασία της διεπαφής επικοινωνίας. Έχει επίσης το πλεονέκτημα της μείωσης του χρόνου μετάδοσης για μεγάλα μηνύματα. Για την κατανόηση αυτού του φαινομένου έστω ότι ο χρόνος επεξεργασίας είναι αμελητέος σε σχέση με το χρόνο μετάδοση, ο οποίος είναι ούτως ή άλλος ο κυρίαρχος όρος στην καθυστέρηση της επικοινωνίας. Αν ένα μήνυμα που περιέχει L bits χωρίζεται σε k πακέτα, τότε κάθε πακέτο περιλαμβάνει L/k bits. Ο χρόνος μετάδοσης ενός μόνο πακέτου σε έναν σύνδεσμο επικοινωνίας με εύρος ζώνης B είναι L/(kB). Η μετάδοση ολόκληρου του μηνύματος διαμέσου ενός μόνο συνδέσμου επικοινωνίας απαιτεί την μετάδοση και των k πακέτων και συνεπώς απαιτεί L/B συνολικό χρόνο, που είναι ακριβώς ο ίδιος με τον χρόνο μετάδοσης του ίδιου μηνύματος χωρίς να έχει χωριστεί σε τμήματα.

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

Έστω ότι T είναι ο χρόνος L/(kB) που θέλει κάθε μήνυμα για να διασχίσει ένα σύνδεσμο επικοινωνίας. Τότε ο συνολικός χρόνος που απαιτείται για τη δρομολόγηση των πακέτων είναι (k-1)T. Από τη στιγμή που ο συρμός έχει δημιουργηθεί εντελώς, το πακέτο που αποτελεί την ουρά του έχει να διασχίσει όλους τους m συνδέσμους μεταξύ των επεξεργαστών της αφετηρίας και του προορισμού. Ο συνολικός χρόνος για αυτή τη διάσχιση είναι mT. Εφόσον η ουρά είναι το τελευταίο πακέτο που θα φτάσει στον προορισμό, ο συνολικός χρόνος επικοινωνίας είναι απλώς το άθροισμα του χρόνου δημιουργίας του συρμού και του χρόνου που κάνει η ουρά να διασχίσει το μονοπάτι: (k-1)T+mT=(m+k-1)T. Ο χρόνος που απαιτείται για την επικοινωνία ενός μηνύματος που δεν έχει τμηματοποιηθεί έχει υπολογιστεί: mL/B=mkT. Έτσι, η επιτάχυνση που είναι αποτέλεσμα της τμηματοποίησης είναι: mk/(m+k-1). Για παράδειγμα, αν το μήκος του μονοπατιού m είναι 12 και το πλήθος των k πακέτων είναι 5, τότε επιτυγχάνεται ένας παράγοντας επιτάχυνσης της επικοινωνίας ίσος με 3.75 ως αποτέλεσμα της τμηματοποίησης.

Χρησιμοποιώντας αυτόν τον τύπο κάποιος μπορεί να θεωρήσει ότι αν συνεχίσει η αύξηση του k θα συνεχιστεί και η αύξηση της επιτάχυνσης. Το ακραίο σε αυτή την κατεύθυνση είναι ένα πακέτο μεγέθους 1 bit, που σύμφωνα με τους υπολογισμούς που προηγήθηκαν θα ελαχιστοποιήσει την καθυστέρηση της επικοινωνίας. Αυτό έχει προταθεί σαν βιώσιμη μέθοδος επικοινωνίας και ονομάζεται cut-through δρομολόγηση. Σε αυτή την μέθοδο, κάθε bit του μηνύματος μεταβιβάζεται στη διεπαφή επικοινωνίας αμέσως μόλις ληφθεί. Οι Athas και Seitz [1988] έχουν αναπτύξει μια εναλλακτική δρομολόγηση που ονομάζεται worm-hole δρομολόγηση, η οποία χρησιμοποιεί πακέτα πολύ μικρού μεγέθους.

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

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