Επόμενο:Aσκήσεις Πάνω: Κεφάλαιο 11o : Κατανεμημένη Ανίχνευση Τερματισμού Πίσω: Αναφορές

ΠΡΟΓΡΑΜΜΑΤΙΣΤΙΚΕΣ ΕΡΓΑΣΙΕΣ

1. Ασύγχρονη επίλυση γραμμικών εξισώσεων

Η τρίτη εργασία προγραμματισμού του κεφαλαίου 8 παρουσιάζει μια σύγχρονη μέθοδο παράλληλης επίλυσης ενός συστήματος γραμμικών εξισώσεων. Η παρούσα εργασία αφορά το γράψιμο ενός προγράμματος που χρησιμοποιεί ασύγχρονη επανάληψη για την επίλυση ενός συστήματος γραμμικών εξισώσεων. Για να υλοποιήσετε την ασύγχρονη επανάληψη χρησιμοποιήστε το υπόδειγμα των Κατανεμημένων Εργαζομένων και την συμπίεση εργασίας που παρουσιάσαμε στην παράγραφο 11.5. Η συνθήκη της κυριαρχίας του διαγώνιου στοιχείου που περιγράφτηκε στο κεφάλαιο 8 εγγυάται ότι το δείγμα του συστήματος των εξισώσεων πράγματι συγκλίνει με τη χρήση της ασύγχρονης μεθόδου.

Χρησιμοποιώντας τοπολογία Υπερκύβου εκτελέστε το πρόγραμμα σας για μια ποικιλία τιμών της βασικής καθυστέρησης επικοινωνίας. Προσδιορίστε πώς η καθυστέρηση επικοινωνίας επηρεάζει τα τρία κύρια μέρη του προγράμματός σας: τη δημιουργία της διεργασίας και την κατανομή των δεδομένων, τον επαναληπτικό υπολογισμό και τον τερματισμό. Αν έχετε κάνει την τρίτη εργασία προγραμματισμού του κεφαλαίου 8 θα ήταν ενδιαφέρον να συγκρίνετε την απόδοση της ασύγχρονης και της σύγχρονης μεθόδου.

2. Το πρόβλημα του Περιοδεύοντος Παραγωγού

Σε αυτή την εργασία πρέπει να γράψετε ένα πρόγραμμα Κατανεμημένων Εργαζομένων για το πρόβλημα του Περιοδεύοντος Παραγωγού σε ένα σύστημα κατανεμημένης μνήμης. Ο αλγόριθμος που χρησιμοποιείται είναι ίδιος με αυτόν που περιγράψαμε για τα Αντίγραφα Εργαζομένων σε σύστημα διαμοιραζόμενης μνήμης (δες κεφάλαιο 10, 2η εργασία προγραμματισμού). Επιτρέποντας σε κάθε εργαζόμενο να έχει το δικό του πλήρες αντίγραφο του πίνακα distance αποτρέπεται η ανάγκη για επιμερισμό δεδομένων. Το αποτέλεσμα είναι μια κατάσταση στην οποία οι εργαζόμενοι είναι μη-διακριτοί. Συνεπώς, κάθε αντικείμενο εργασίας μπορεί ελεύθερα να κατανεμηθεί σε οποιονδήποτε εργαζόμενο και να μειωθεί έτσι η πιθανότητα ανισορροπίας φορτίου.

Η βασική διαφορά με το πρόγραμμα του Περιοδεύοντος Παραγωγού σε σύστημα διαμοιραζόμενης μνήμης βρίσκεται στην υλοποίηση του τοπικά ελάχιστου ταξιδιού. Στο πρόγραμμα του συστήματος διαμοιραζόμενης μνήμης το τοπικό ελάχιστο διαμοιράζεται σε όλους τους εργαζόμενους και μπορεί εύκολα να προσπελαστεί από αυτούς (παρά την πιθανότητα συμφόρησης, η οποία πρέπει να αποφεύγεται). Όμως, αυτό παρουσιάζει πρόβλημα στο σύστημα κατανεμημένης μνήμης: πού θα αποθηκεύουμε το τοπικό ελάχιστο; Δεν είναι καθόλου αποδοτικό κάθε εργαζόμενος να διαβάζει το τοπικό ελάχιστο από μια απομακρυσμένη μνήμη. Η λύση είναι να κρατά κάθε εργαζόμενος ένα τοπικό αντίγραφο και να το χρησιμοποιεί για τον έλεγχο των δικών του ταξιδιών. Αν βρεθεί κάποιο ελάχιστο, τότε ο εργαζόμενος θα το στείλει σε μια κεντρική διεργασία επόπτη, η οποία στην συνέχεια θα διαδώσει αυτό το νέο τοπικό ελάχιστο σε όλους τους εργαζόμενους, έτσι ώστε να ενημερώσουν τα δικά τους τοπικά αντίγραφα.

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

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

Επόμενο:Aσκήσεις Πάνω: Κεφάλαιο 11o : Κατανεμημένη Ανίχνευση Τερματισμού Πίσω: Αναφορές