Επόμενο:Κεφάλαιο 10o: Αντίγραφα Εργαζομένων Πάνω: Κεφάλαιο 9o : Επιμερισμός δεδομένων Πίσω: Προγραμματιστικές Εργασίες

ΑΣΚΗΣΕΙΣ

1. Η ανάλυση απόδοσης του προγράμματος των Ν-Σωμάτων του σχήματος 9.4 έγινε με την υπόθεση ότι δεν υπάρχει επικαλυπτόμενη επικοινωνία και υπολογισμός. Τροποποιήστε την ανάλυση, έτσι ώστε να λαμβάνεται υπόψη η περίπτωση της επικαλυπτόμενης επικοινωνίας και του υπολογισμού, όπως φαίνεται στο σχήμα 9.6. Σε αυτή την ανάλυση μπορείτε να αγνοήσετε το χρόνο δημιουργίας της διεργασίας και της κατανομής των δεδομένων.

(α)Διατυπώστε μια γενική έκφραση για το χρόνο εκτέλεσης του προγράμματος των Ν-Σωμάτων του σχήματος 9.6

(β)Αντλήστε μια έκφραση που να δίνει το σημείο αλλαγής της βασικής καθυστέρησης επικοινωνίας D. Αν το D είναι μικρότερο από αυτό το σημείο αλλαγής, τότε η καθυστέρηση επικοινωνίας δεν επηρεάζει το χρόνο εκτέλεσης.

2. Η ανάλυση απόδοσης του προγράμματος των Ν-Σωμάτων του σχήματος 9.4 αγνοεί το χρόνο δημιουργίας των διεργασιών και κατανομής των τμημάτων των αρχικών δεδομένων στους επεξεργαστές. Τροποποιήστε τη γενική ανάλυση έτσι ώστε να περιλαμβάνει αυτό το χρόνο.

3 Τροποποιήστε κατάλληλα το πρόγραμμα των Ν-Σωμάτων του σχήματος 9.4 ώστε να εφαρμόζεται το πρόγραμμα αποδοτικά σε τοπολογία TORUS(5).

4. Γράψτε τη διαδικασία “ComputeGray(n: INTEGER)” σε Multi-Pascal που θα υπολογίζει τις τιμές για έναν Κώδικα Gray με n bits και θα αποθηκεύει τα αποτελέσματα στον πίνακα GrayCode. Εκτελέστε και ελέγξτε το πρόγραμμα χρησιμοποιώντας την Multi-Pascal. Προσπαθήστε να κάνετε το πρόγραμμα όσο περισσότερο αποδοτικό γίνεται.

5. Περιγράψτε τη γενική οργάνωση του προγράμματος Ταξινόμησης Σειράς συστήματος κατανεμημένης μνήμης. Πώς επιμερίζονται τα δεδομένα; Ποια είναι η γενική μορφή της ροής της επικοινωνίας και των δεδομένων;

6. Υπολογίστε το γινόμενο μητρών που προκύπτει από τα ακόλουθα:

1   1   1  1                                  4    4    4   4

2   2  2   2                                  3   3    3   3

Α=     3  3  3   3                          Β=    2   2    2    2

4  4  4   4                                   1   1   1    1

Επιμερίστε κάθε μήτρα σε τέσσερα 2x2 τμήματα όπως φαίνεται παρακάτω:

       A₁₁ A₁₂                                      B₁₁ B₁₂

A=                                         B=

       A₂₁ A₂₂                                      B₂₁ B₂₂

όπου κάθε A_ij και B_ij είναι μια 2x2 μήτρα.

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

7. Θεωρείστε τον πολλαπλασιασμό των 3x3 μητρών . Δηλώστε τα στοιχεία των μητρών χρησιμοποιώντας τη γενική αρίθμηση γραμμής και στήλης A_ij, B_ij, C_ij.

(α) Για το πρόγραμμα του Πολλαπλασιασμού Μήτρας του σχήματος 9.9 δείξτε την αρχική εκχώρηση των στοιχείων της μήτρας στους επεξεργαστές του Τόρου.

(β) Μετά το πρώτο βήμα επικοινωνίας δείξτε τη νέα θέση των στοιχείων της μήτρας στον Τόρο.

(γ) Μετά το δεύτερο βήμα επικοινωνίας δείξτε τη νέα θέση των στοιχείων της μήτρας στον Τόρο.

(δ)Επιβεβαιώστε ότι σε κάθε βήμα όλοι οι επεξεργαστές μπορούν να πολλαπλασιάσουν τις τρέχουσες τιμές τους A_ij, B_ij και να τις προσθέσουν στην C_ij. Δείξτε ότι το σωστό τελικό αποτέλεσμα υπολογίζεται για κάθε C_ij του Τόρου.

8. Δείξτε τι τροποποιήσεις χρειάζονται στο πρόγραμμα του Πολλαπλασιασμού Μήτρας του σχήματος 9.10 για να εκτελείται αποδοτικά σε έναν Υπερκύβο με διάσταση 6. Για λόγους απλότητας υποθέστε ότι στο πρόγραμμα είναι m=8.

9. Η ανάλυση απόδοσης του προγράμματος Πολλαπλασιασμού Μήτρας του σχήματος 9.10 δεν περιλαμβάνει τον τερματισμό διεργασίας και την επικοινωνία των τελικών αποτελεσμάτων με την πρωταρχική διεργασία. Αναπτύξτε μια γενική αλγεβρική έκφραση για τη διάρκεια αυτής της τελικής φάσης του προγράμματος.

10. Δώστε μια γενική αλγεβρική έκφραση για την επιτάχυνση στο πρόγραμμα του Πολλαπλασιασμού Μήτρας του σχήματος 9.10

11. Υποθέστε μια νέα έκδοση του προγράμματος του Πολλαπλασιασμού Μήτρας του σχήματος 9.10 δεν περιλαμβάνει επικάλυψη μεταξύ της επικοινωνίας και του υπολογισμού. Αναπτύξτε μια γενική αλγεβρική έκφραση για το χρόνο εκτέλεσης αυτού του προγράμματος.

12. Στο σχήμα 9.11 η επιτάχυνση αυξάνεται καθώς αυξάνεται η παράμετρος k. Όμως, αυτές οι αυξήσεις στην επιτάχυνση του αυξανόμενου k είναι πολύ μεγαλύτερες στην αριστερή πλευρά του γραφήματος σε σχέση με τη δεξιά πλευρά. Χρησιμοποιώντας την ανάλυση απόδοσης της παραγράφου 9.3.5 εξηγείστε τους λόγους για αυτή την ιδιότητα.

13. Δηλώστε τις τροποποιήσεις που χρειάζονται για να τρέξει το πρόγραμμα του αλγόριθμου Jacobi του σχήματος 9.13 σε Δακτύλιο συστήματος κατανεμημένης μνήμης παρά σε Υπερκύβο. Δείξτε τις απαιτούμενες αλλαγές στην γενική ανάλυση απόδοσης για αυτό το πρόγραμμα. Δημιουργήστε μια γενική έκφραση για το χρόνο εκτέλεσης του προγράμματος.

14. Στα προγράμματα του αλγόριθμου Jacobi του κεφαλαίου 6 το κύριο θέμα ήταν η εφαρμογή των φραγμάτων για το συγχρονισμό των επαναλήψεων. Εξηγείστε γιατί αυτό το θέμα του συγχρονισμού φράγματος δεν προκύπτει στην έκδοση του προγράμματος για σύστημα κατανεμημένης μνήμης.

15. Στο πρόγραμμα της Χαλάρωσης Jacobi του σχήματος 9.13 κάθε διεργασία i ανατίθεται στο inchan(GrayCode[i]) ως θύρα επικοινωνίας. Υποθέστε ότι κάνουμε την αλλαγή inchan[i]. Τι λάθη ή προβλήματα απόδοσης θα προκύψουν όταν θα εκτελεστεί το πρόγραμμα;

16. Χρησιμοποιώντας τη δι-διάστατη μέθοδο επιμερισμού για το πρόγραμμα του αλγόριθμου Jacobi εξηγείστε γιατί μόνο τα οριακά σημεία χρειάζεται να επικοινωνούν με τους γειτονικούς επεξεργαστές.

17. Η δι-διάστατη μέθοδος επιμερισμού για το πρόγραμμα του αλγόριθμου Jacobi μειώνει την ποσότητα των δεδομένων που κινούνται, με την προϋπόθεση ότι το n είναι αρκετά μεγάλο. Όμως, αυξάνει επίσης και τα βήματα επικοινωνίας για κάθε διεργασία από δύο σε τέσσερα. Αναλύστε την απόδοση και των δύο μεθόδων επιμερισμού και καθορίστε κάτω από ποιες προϋποθέσεις είναι ανώτερη η δι-διάστατη μέθοδος.

Επόμενο:Κεφάλαιο 10o: Αντίγραφα Εργαζομένων Πάνω: Κεφάλαιο 9o : Επιμερισμός δεδομένων Πίσω: Προγραμματιστικές Εργασίες