Επόμενο:Κεφάλαιο 8o: Προγράμματα περάσματος μηνυμάτων Πάνω: Κεφάλαιο 7o : Αρχιτεκτονική συστημάτων κατανεμημένης μνήμης Πίσω: Αναφορές
ΑΣΚΗΣΕΙΣ
1. Υποθέστε ότι σε ένα δίκτυο επικοινωνίας υπάρχουν δυο επεξεργαστές X και Y που χωρίζονται από m συνδέσμους επικοινωνίας. Αυτό σημαίνει ότι ένα μήνυμα που ταξιδεύει από τον επεξεργαστή X στον Y πρέπει να διασχίσει συνολικά m συνδέσμους. Επίσης έστω ότι ο χρόνος που απαιτείται για την μετάδοση ενός δεδομένου μηνύματος κατά μήκος μόνο ενός συνδέσμου είναι Τ μονάδες χρόνου. Όμως, κάποιες φορές κατά τη διάρκεια εκτέλεσης του προγράμματος ο πραγματικός χρόνος επικοινωνίας είναι πολύ περισσότερος από αυτό το ελάχιστο. Εξηγείστε όλες τις πιθανές αιτίες αυτού του επιπλέον χρόνου.
2. Θεωρείστε μια τεχνική δρομολόγησης η οποία βοηθάει στην μείωση της κυκλοφοριακής συμφόρησης σε ένα δίκτυο επικοινωνίας. Σε αυτή την τεχνική μια δοσμένη διεπαφή επικοινωνίας επιλέγει πρώτα όλους τους συνδέσμους που έχουν τις παρακάτω ιδιότητες:
(α) Το μήνυμα πλησιάζει στο στόχο του.
(β) Η διεπαφή επικοινωνίας στο άλλο άκρο του συνδέσμου δεν έχει μεγάλη ουρά μηνυμάτων που περιμένουν να σταλούν.
Αν υπάρχουν περισσότεροι από ένας τέτοιοι σύνδεσμοι, τότε πραγματοποιείται μια τυχαία επιλογή μεταξύ αυτών. Αν δεν υπάρχουν σύνδεσμοι που έχουν τις παραπάνω ιδιότητες, τότε γίνεται μια τυχαία επιλογή μεταξύ αυτών που φαίνεται ότι έχουν την ιδιότητα (β). Αν δεν υπάρχουν σύνδεσμοι που έχουν την ιδιότητα (α), τότε γίνεται μια τυχαία επιλογή μεταξύ των συνδέσμων που φαίνεται ότι έχουν την ιδιότητα (α).
Αυτός ο αλγόριθμος δρομολόγησης όντως βοηθάει στην μείωση και την αποφυγή της κυκλοφοριακής συμφόρησης μέσα στο δίκτυο. Όμως, έχει και την ανεπιθύμητη ιδιότητα κατά την οποία μπορούν να συμβούν αυθαίρετα μεγάλες καθυστερήσεις κατά τη διάρκεια της επικοινωνίας. Δεν υπάρχει περιορισμός σχετικά με το πόσους συνδέσμους θα διασχίσει ένα μήνυμα από την αφετηρία μέχρι τον προορισμό του. Εξηγείστε με λεπτομέρειες τους λόγους αυτής της ιδιότητας των αυθαίρετα μεγάλων καθυστερήσεων. Περιγράψτε ένα απλό σενάριο που να δείχνει πως το μήνυμα μπορεί να έχει να διασχίσει έναν μεγάλο αριθμό συνδέσμων πριν να φτάσει στον προορισμό του.
3. Μια απλή τεχνική δρομολόγησης για την αποφυγή της κυκλοφοριακής συμφόρησης και της εξισορρόπησης της ροής των μηνυμάτων σε ένα δίκτυο επικοινωνίας είναι η χρήση της τυχαίας επιλογής. Σε κάθε διεπαφή επικοινωνίας είναι καθορισμένοι οι σύνδεσμοι που θα μεταφέρουν το μήνυμα πιο κοντά στο στόχο του. Αν υπάρχουν περισσότεροι από ένας τέτοιοι σύνδεσμοι, τότε γίνεται μια τυχαία επιλογή μεταξύ τους. Όμως, η τεχνική αυτή έχει ως αποτέλεσμα τη δημιουργία της ανεπιθύμητης ιδιότητας: τα μηνύματα που στέλνονται από την ίδια αφετηρία προς τον ίδιο προορισμό μπορεί να φτάσουν με διαφορετική σειρά από αυτή με την οποία στάλθηκαν. Εξηγείστε με λεπτομέρειες τους λόγους για τους οποίους προκύπτει αυτή η ιδιότητα. Περιγράψτε ένα απλό σενάριο το οποίο να δείχνει πως αυτό συμβαίνει.
4. Ένα δίκτυο επικοινωνίας ενός συστήματος κατανεμημένης μνήμης έχει εύρος ζώνης Β. Η επικοινωνία πραγματοποιείται με την κατάτμηση κάθε μηνύματος σε πακέτα μεγέθους S. Ο χρόνος επεξεργασίας ανά πακέτο σε κάθε διεπαφή επικοινωνίας είναι P. Η επεξεργασία σε κάθε διεπαφή μπορεί να γίνει παράλληλα με φυσική επικοινωνία καθενός από τους συνδέσμους.
(α) Δώστε μια αλγεβρική έκφραση του συνολικού χρόνου που απαιτείται για την επικοινωνία ενός μηνύματος μεγέθους L ανάμεσα σε δυο επεξεργαστές που χωρίζονται από m συνδέσμους.(Υποθέστε ότι δεν υπάρχουν καθυστερήσεις συμφόρησης).
(β) Χρησιμοποιήστε την παραπάνω έκφραση για να υπολογίσετε το βέλτιστο μέγεθος πακέτου που θα ελαχιστοποιήσει την καθυστέρηση της επικοινωνίας. Για λόγους απλότητας, υποθέστε ότι το L είναι ακριβές πολλαπλάσιο του S.
(γ) Επαναλάβετε το τμήμα (α), υποθέτοντας ότι απαιτείται πλήρης προσοχή από τη διεπαφή επικοινωνίας κατά τη διάρκεια της λήψης ή της αποστολής οποιουδήποτε πακέτου μηνύματος. Με αυτόν τον τρόπο, η επεξεργασία στη διεπαφή δεν μπορεί να γίνει παράλληλα ούτε κατά την λήψη ούτε κατά την αποστολή.
5. Ένας κατασκευαστής υπολογιστών έχει μόλις δει ένα νέο μοντέλο του συστήματος κατανεμημένης μνήμης, στο οποίο έχει προστεθεί σε κάθε διεπαφή επικοινωνίας ένας συνεπεξεργαστής επικοινωνίας για να βοηθάει στην επικοινωνία. Σχετικά με την απόδοση αυτού του νέου μοντέλου έχουμε τα δυο παρακάτω δεδομένα:
(α) Οι καθυστερήσεις της επικοινωνίας είναι ίδιες με του προηγούμενου μοντέλου.
(β) Η απόδοση των προγραμμάτων που πραγματοποιούν την περισσότερη επικοινωνία είναι καλύτερη σε αυτό το νέο μοντέλο.
Δώστε μια ενδεχόμενη εξήγηση αυτών των δυο δεδομένων.
6. (α) Σύμφωνα με όσα αναθέρθηκαν στο κεφάλαιο η διάμετρος της τοπολογίας του τρισδιάστατου Πλέγματος με n επεξεργαστές είναι 3(n1/3-1). Δείξτε με λεπτομέρειες ότι αυτό είναι σωστό.
(β) Όπως το διδιάστατο Πλέγμα μπορεί να αυξηθεί με την πρόσθεση επιπλέον συνδέσμων μεταξύ των επεξεργαστών που βρίσκονται σε αντίθετες οριακές θέσεις στα έτσι μπορεί να αυξηθεί και το τρισδιάστατο Πλέγμα. Οι επεξεργαστές που βρίσκονται στις έξι οριακές θέσεις του Πλέγματος συνδέονται με τα αντίστοιχα ζεύγη τους που βρίσκονται απέναντί τους. Με τον τρόπο αυτό η συνδεσιμότητα κάθε επεξεργαστή είναι ακριβώς έξι. Ποια είναι η νέα διάμετρος του τρισδιάστατου Πλέγματος; Εξηγήστε την απάντησή σας.
7. Σε μια τοπολογία Δένδρου οι επεξεργαστές συνδέονται μεταξύ τους σύμφωνα με το πρότυπο του δυαδικού δένδρου και ο κύριος επεξεργαστής βρίσκεται στην κορυφή του δένδρου.
(α) Ποια είναι η συνδεσιμότητα της τοπολογίας του Δένδρου;
(β) Για μια τοπολογία Δένδρου με n επεξεργαστές ποια είναι η διάμετρος;
(γ) Φαίνεται ότι αυτή η τοπολογία επιτυγχάνει χαμηλή συνδεσιμότητα και διάμετρο. Όμως, για αλγορίθμους που έχουν συχνή επικοινωνία η τοπολογία του Δένδρου παρουσιάζει ένα σοβαρό πρόβλημα που μειώνει σημαντικά την απόδοση. Περιγράψτε τη φύση και την αιτία αυτής της μείωσης της απόδοσης.
8. Υποθέστε ότι ο χρόνος μετάδοσης ενός μηνύματος διαμέσου ενός μόνο συνδέσμου είναι πάντα ίσος με T μονάδες χρόνου. Στην τοπολογία Γραμμής ο χρόνος επικοινωνίας που απαιτείται για την αποστολή ενός μηνύματος από τον επεξεργαστή i στον επεξεργαστή j είναι T|i-j|. Περιγράψτε έναν παρόμοιο τύπο για τον χρόνο επικοινωνίας μεταξύ δύο οποιονδήποτε επεξεργαστών των παρακάτω τοπολογιών:
(α) Ένα διδιάστατο Πλέγμα mxm.
(β) Ένα τρισδιάστατο Πλέγμα mxmxm.
9. Το σχήμα 7.11 δείχνει τη δομή του Υπερκύβου με διάσταση 4. Συμπληρώστε το διάγραμμα γράφοντας για τον καθένα από τους 16 επεξεργαστές έναν αριθμό με 4 bit.
10. Για την τοπολογία Τόρου του σχήματος 7.8 περιγράψτε έναν βέλτιστο αλγόριθμο μετάδοσης, έτσι ώστε ο επεξεργαστής 0 να διανέμει σε όλους τους υπόλοιπους επεξεργαστές δεδομένα. Σχεδιάστε το πρότυπο της μετάδοσης προσθέτοντας στο σχήμα 7.8 βέλη, όπως έχει γίνει και για τις υπόλοιπες τοπολογίες στα σχήματα 7.13-7.17.
11. Σε μια πολυκομβική σύνδεση, κάθε επεξεργαστής διαδίδει τα δεδομένα που έχει σε όλους τους άλλους επεξεργαστές. Θεωρήστε το πρόβλημα της πολυκομβικής διάδοσης σε μια τοπολογία Γραμμής.
(α) Υποθέστε ότι κάθε σύνδεσμος μπορεί να χειριστεί μόνο ένα μήνυμα κάθε φορά και περιγράψτε έναν αποτελεσματικό αλγόριθμο πολυκομβικής διάδοσης. Ποιος είναι ο συνολικός χρόνος εκτέλεσης για αυτόν τον αλγόριθμο;
(β) Επαναλάβετε το τμήμα (α), υποθέτοντας ότι κάθε σύνδεσμος μπορεί να στέλνει μηνύματα προς τις αντίθετες κατευθύνσεις ταυτόχρονα.
12. Γράψτε μια συνάρτηση σε Pascal που θα ονομάζεται Delay(Source, Dfestination) και θα λαμβάνει τους αριθμούς δυο επεξεργαστών μιας τοπολογίας Υπερκύβου ως παραμέτρους εισόδου. Η συνάρτηση θα υπολογίζει τον αριθμό των συνδέσμων από τους οποίους θα πρέπει να περάσει ένα μήνυμα που θα κινηθεί μεταξύ δυο επεξεργαστών του Υπερκύβου. Υποθέστε ότι η διάσταση του Υπερκύβου είναι d.
13. Οι τοπολογίες του διδιάστατου και τρισδιάστατου Πλέγματος μπορούν να γενικευτούν και να συμπεριλάβουν πλέγματα μεγαλύτερων διαστάσεων. Για λόγους απλότητας υποθέστε ότι το μέγεθος κάθε δοσμένου πλέγματος είναι ίσο με τη διάστασή του. Αυτό σημαίνει ότι ένα τετραδιάστατο Πλέγμα θα είναι mxmxmxm. Απαντήστε τις παρακάτω ερωτήσεις λαμβάνοντας υπόψη ότι έχουμε ένα αυθαίρετο πλέγμα με διάσταση d και n επεξεργαστές:
(α) Ποια είναι η συνδεσιμότητα;
(β) Ποια είναι η διάμετρος;
(γ) Υποθέτοντας ότι ο βασικός χρόνος επικοινωνίας για κάθε σύνδεσμο είναι πάντα T μονάδες χρόνου, πόσος χρόνος απαιτείται για μια βέλτιστη διάδοση;
(δ) Περιγράψτε τη δομή ενός βέλτιστου αλγόριθμου μετάδοσης.
14. Στο σχήμα 7.21 φαίνεται η απεικόνιση ενός τρισδιάστατου Πλέγματος σε έναν Υπερκύβο χρησιμοποιώντας τη σιγμοειδή διάταξη της ακολουθίας του κώδικα Gray. Ορίστε το δυαδικό αριθμό κάθε επεξεργαστή σε αυτό το σχήμα και επιβεβαιώστε ότι όντως υπάρχουν όλοι οι απαιτούμενοι σύνδεσμοι για την απεικόνιση του τρισδιάστατου Πλέγματος.
15. Γράψτε έναν κώδικα Gray με 5 bits, που να αποτελεί την ακολουθία 32 αριθμών με 5 bit.
16. Γράψτε μια διαδικασία σε Pascal που θα ονομάζεται ComputeGray(n: Integer), που θα υπολογίζει τις τιμές για έναν κώδικα Gray με n bit και θα αποθηκεύει τα αποτελέσματα στον πίνακα GrayCode. Κάθε αριθμός μπορεί να αναπαρασταθεί στον πίνακα ως μία συνηθισμένη ακέραια τιμή, αλλά η ακολουθία των αριθμών πρέπει να ανταποκρίνεται στην ακολουθία του κώδικα Gray. Για παράδειγμα, η ακολουθία 2 bit του κώδικα Gray είναι 0, 1, 3, 2. Εκτελέστε και ελέγξτε το πρόγραμμα χρησιμοποιώντας το σύστημα της Multi-Pascal. Προσπαθήστε να κάνετε το πρόγραμμα όσο το περισσότερο αποδοτικό.
17. Σε αυτό το κεφάλαιο περιγράφηκε ένας αλγόριθμος διάδοσης του Υπερκύβου. Γράψτε μια απλή επαναληπτική διαδικασία σε Pascal, την Broadcast(i), που θα μπορεί να εκτελείται σε κάθε επεξεργαστή i και να πραγματοποιεί αυτή την διάδοση. Για να πραγματοποιήσετε την επικοινωνία χρησιμοποιήστε τις παρακάτω λειτουργίες:
Send(M,j) στέλνει την τιμή δεδομένων M στον αριθμό επεξεργαστή j.
Receive(M) λαμβάνει την επόμενη τιμή δεδομένων και την αποθηκεύει στην μεταβλητή M.
Για λόγους απλότητας υποθέστε ότι μία μόνο ακέραια τιμή δεδομένων διαδίδεται από τον επεξεργαστή 0 προς όλους τους άλλους επεξεργαστές του Υπερκύβου.
18. Η τεχνική του τουρνουά που περιγράφηκε στο κεφάλαιο 6 πραγματοποιεί μία συλλογή που ακολουθείται από μια διάδοση. Σε αυτή την τεχνική κάθε ζεύγος των διεργασιών που επικοινωνούν διαφέρει πάντα στον αριθμό επεξεργαστή κατά ένα ακριβώς bit. Έτσι, η μέθοδος αυτή μπορεί να υιοθετηθεί για την πραγματοποίηση συλλογής ή διάδοσης σε μια τοπολογία Υπερκύβου.
(α) Περιγράψτε έναν απλό αλγόριθμο διάδοσης για τον Υπερκύβο που να βασίζεται στην μέθοδο του τουρνουά. Σχεδιάστε τη δομή της διάδοσης πάνω στον Υπερκύβο του σχήματος 7.11. (Αυτή η μέθοδος είναι σχεδόν η ίδια με τον αλγόριθμο διάδοσης που αναφέρθηκε σε αυτό το κεφάλαιο. Διαφέρει μόνο η ακολουθία των ζευγών επικοινωνίας κάθε επεξεργαστή)
(β) Συγκρίνετε την μέθοδο διάδοσης του τουρνουά με τον αλγόριθμο διάδοσης του Υπερκύβου που παρουσιάστηκε σε αυτό το κεφάλαιο. Εξηγείστε τις διαφορές.
ΠΡΟΤΕΙΝΟΜΕΝΕΣ ΛΥΣΕΙΣ
14. Σιγμοειδής διάταξη κώδικα GRAY
000000---> 000001---> 000011---> 000010 /---------- 010010 <----010011<------ 010001<----- 010000
\/ | /\
000110 <--- 000111<--- 000101<--- 000100 | 010110 ----> 010111----> 010101----> 010100
\/ | /\
001100 ---> 001101---> 001111---> 001110 | 011110<---- 011111 <----- 011101<----- 011100
\/ | /\
001010<--- 001011<--- 001001<--- 001000 | 011010---> 011011----> 011001-----> 011000
\--------------------------------------------------------------------|------------------/\
\/ ---------------------------------------------------------------|
110000---->110001----> 110011----> 110010 100000 <----100001<----- 100011<----- 100010
\/ /\
110100<---- 110101<-----110111<---- 110110 100100-----> 100101-----> 100111-----> 100110
\/ /\
111100----->111101---> 111111----> 111110 101100 <----- 101101<----- 101111<---- 101110
\/ /\
111000<---- 111001<---- 111011<----- 111010 101000 ----> 101001---> 101011 ----> 101010
\-----------------------------------------------------------------------------------------/\
17. Διάδοση σε υπερκύβο με την Broadcast
Program Broadcast;
const n=8;
var i,m:integer;
Procedure Broadcast(i:integer);
begin
Receive(M);
z:=round(logi); /* Στρογγυλοποίηση προς τα πάνω */
for k:=z+1 to logn /* Λογάριθμος με βάση το 2 */
begin
bitnumber(i,k)=1;
j:=bitnumber(i,k);
Send(M,j);
end;
end;
begin
M:=2; /* Τυχαίο δεδομένο */
forall i:=1 to n do
Broadcast(i);
end.
Σχόλιο για την Broadcast
Η κάθε διεργασία, λογαριθμεί τον αριθμό της ( I , από 1 έως Ν) για να βρεί πόσες επαναλήψεις διάδοσης θα κάνει. Ο αριθμός των επαναλήψεων προκύπτει από τη στρογγυλοποίηση προς τα πάνω. `Ετσι π.χ. για n=8, η πρώτη διεργασία θα κάνει τρείς επαναλήψεις (επειδή log1 με βάση το 2 είναι 0), η δεύτερη δύο, η τρίτη μία, η τέταρτη μία και οι υπόλοιπες καμία. `Ετσι για n=8 η διάδοση του δεδομένου στον υπερκύβο θα γίνει όπως φαίνεται στο σχήμα. Η bitnumber χρησιμοποιήται για την αντιστροφή του k bit κάθε φορά. Κάθε διεργασία αναμένει να πάρει το M με την Receive και λογαριθμώντας βρίσκει πόσες επαναλήψεις θα κάνει. Θέτει το αντίστοιχο bit σε 1 και βρίσκει τη διεργασία παραλήπτη.
Διάδοση στον υπερκύβο με την Broadcast
18.
α. Τεχνική Τουρνουά για Υπερκύβο
Program HyperCubeTourn;
const n=16;
var i:integer;
Procedure Diadosi(i:integer);
Var position:integer;
begin
position:=1;
While position‹n do
begin
position:=position*2;
LosingPartner:=Setbit(mynumber,position);
Send message to LosingPartner;
end;
end;
begin
forall i:=1 to n do
diadosi(i);
end.
Δομή της διάδοσης
1.
2.
3.
4.
β. Η διαφορά της τεχνικής Τουρνουά από του Υπερκύβου είναι ότι η κάθε διεργασία για να βρεί τη σύντροφό της, αντιστρέφει τα bits της ξεκινώντας από δεξιά, ενώ αντίθετα στον Υπερκύβο η αντιστροφή ξεκινά από αριστερά και πάει προς τα δεξιά.
Επόμενο:Κεφάλαιο 8o: Προγράμματα περάσματος μηνυμάτων Πάνω: Κεφάλαιο 7o : Αρχιτεκτονική συστημάτων κατανεμημένης μνήμης Πίσω: Αναφορές