9.2 Το Πρόβλημα των Ν-Σωμάτων στην Αστροφυσική

Επόμενο:9.3 Πολλαπλασιασμός Μήτρας Πάνω: Κεφάλαιο 9o : Επιμερισμός δεδομένων Πίσω: 9.1 Επιβάρυνση Επικοινωνίας

9.2 Το Πρόβλημα των Ν-Σωμάτων στην Αστροφυσική

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

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

9.2.1 Έκδοση διαμοιραζόμενης μνήμης.

Το πρόβλημα των Ν-Σωμάτων χρησιμοποιείται στην αστροφυσική για τον υπολογισμό των δυναμικών του ηλιακού συστήματος και των γαλαξιών. Κάθε μάζα σε αυτό το πρόβλημα δέχεται έλξη βαρύτητας από κάθε άλλη μάζα, σε αναλογία με το αντίστροφο τετράγωνο της απόστασης μεταξύ των αντικειμένων. Ο νόμος του Νεύτωνα για τη βαρύτητα δίνει τον τύπο της δύναμης μεταξύ δύο οποιονδήποτε αντικειμένων με μάζες m₁ και m₂ που βρίσκονται σε απόσταση d μεταξύ τους:

Δύναμη=

όπου G είναι η σταθερά της βαρύτητας.

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

Για να επικεντρώσουμε την προσοχή μας στη γενική οργάνωση του αλγορίθμου εξωτερικού γινομένου απλοποιούμε τους υπολογισμούς χρησιμοποιώντας μόνο δύο χωρικές διαστάσεις αντί για τρεις. Οι υπολογισμοί για κάθε ζεύγος αντικειμένων φαίνεται στο σχήμα 9.2. Η Μάζα 1 βρίσκεται στη θέση (x₁, y₁) και η Μάζα 2 στη θέση (x₂, y₂). Από αυτές τις συντεταγμένες δύο διαστάσεων τα xdist, ydist και dist υπολογίζονται εύκολα. Χρησιμοποιώντας την υπολογισμένη απόσταση μεταξύ των σωμάτων και το νόμο του Νεύτωνα το μέγεθος f της δύναμης της βαρύτητας μπορεί να υπολογιστεί απευθείας. Αυτή η δύναμη f μπορεί να αναχθεί στα x και y συστατικά της στοιχεία με τον ακόλουθο τρόπο:

δύναμη στη θέση x = f * xdist/dist

δύναμη στη θέση y = f * ydist/dist

ΣΧΗΜΑ 9.1 Δυνάμεις βαρύτητας

ΣΧΗΜΑ 9.2 Υπολογισμός δυνάμεων βαρύτητας

Το σχήμα 9.3 δείχνει το πρόγραμμα της Multi-Pacal για το πρόβλημα των Ν-Σωμάτων σε έναν πολυεπεξεργαστή διαμοιραζόμενης μνήμης. Το εξωτερικό γινόμενο όλων των ζευγών των σωμάτων δημιουργείται από δυο φωλιασμένους βρόχους. Η εξωτερική δήλωση FORALL εκτείνεται σε όλα τα σώματα i, και ο εσωτερικός βρόχος FOR μέσα σε κάθε διεργασία σε όλα τα σώματα j. Ο κώδικας μέσα στη διεργασία FindForce χρησιμοποιεί το νόμο του Νεύτωνα για τη βαρύτητα για τον υπολογισμό της δύναμης που ασκείται από το σώμα j στο σώμα i. Η μεταβλητή force[i] χρησιμοποιείται για να συσσωρεύει το άθροισμα των δυνάμεων στο σώμα i από όλα τα άλλα σώματα.

9.2.2 Επιμερισμός του πίνακα δεδομένων

Για τη δημιουργία αυτού ενός προγράμματος σε σύστημα κατανεμημένης μνήμης για το πρόβλημα των Ν-Σωμάτων ο πίνακας δεδομένων που περιέχει τη μάζα και τη θέση των σωμάτων μπορεί να επιμεριστεί στις τοπικές μνήμες των επεξεργαστών. Αν υπάρχουν n σώματα και p επεξεργαστές τότε σε κάθε επεξεργαστή ανατίθενται k=n/p σώματα. Όμως, για να υπολογίσει κάθε επεξεργαστής τη δύναμη στα σώματα που του έχουν ανατεθεί χρειάζεται να έχει πρόσβαση στις πληροφορίες όλων των άλλων σωμάτων. Μια προφανής λύση σε αυτό το πρόβλημα είναι η διατήρηση ενός αντίγραφου του αρχικού πίνακα σε κάθε τοπική μνήμη, έτσι ώστε κάθε επεξεργαστής να έχει το δικό του πλήρες αντίγραφο του πίνακα. Για έναν μεγάλο πίνακα όμως αυτό θα έχει ως αποτέλεσμα πολύ μεγάλο χρόνο αρχικοποίησης για την αντιγραφή όλου του πίνακα σε κάθε τοπική μνήμη.

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

PROGRAM Nbody;


CONST n=100; (*Αριθμός των σωμάτων*)


G=...; (*Σταθερά βαρύτητας*) 


TYPE bodytype=RECORD


              mass, x, y: REAL; (*Μάζα και θέση*)


              END;


    forcetype=RECORD


                x, y: REAL; (*Δύναμη στις κατευθύνσεις x και y*)


                END;


VAR body: ARRAY [1..n] OF bodytype; (*Αρχικός πίνακας δεδομένων*)


    force: ARRAY [1..n] OF forcetype; (*προκύπτουσες δυνάμεις*)


    i: INTEGER;


 


PROCEDURE FindForce(me: INTEGER);


VAR j: INTEGER;


    xdist, ydist, dist, distsq, pull: REAL;


BEGIN


    force[me].x:= 0; force[me].y:= 0;


    FOR j:= 1 TO n DO (*Εξέταση κάθε άλλου σώματος*)


        IF j ‹› me DO

        BEGIN

            xdist:= body[j].x - body[me].x;

            ydisst:= doby[j].y - body[me].y;

            distsq:= xdist*xdist + ydist*ydist;

            dist:= Sqrt(distsq); (*Απόσταση μεταξύ των σωμάτων*)

            pull:= G*body[me].mass * body[j].mass/distsq;

            force[me].x:= force[me].x + pull*xdist/dist; (*Η δύναμη x*)

            force[me].y:= force[me].y + pull*ydist/dist; (*Η δύναμη y*)

      END;

END;

 

BEGIN

 

    .... (*Αρχικοποίηση του πρωταρχικού πίνακα “body”*)

 

    FORALL i:= 1 TO n DO (*Δημιουργία των διεργασιών*)

        FindForce(i);

END.

ΣΧΗΜΑ 9.3 Το πρόβλημα των Ν-Σωμάτων για συστήματα κατανεμημένης μνήμης

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

Αρχικά ο πρωταρχικός πίνακας δεδομένων επιμερίζεται όμοια σε όλες τις διεργασίες του δακτυλίου. Αυτό σχηματίζει την μόνιμη επιμέριση κάθε διεργασίας. Στη συνέχεια κάθε διεργασία αντιγράφει το μόνιμο τμήμα της στο περιστρεφόμενο τμήμα της. Η ακόλουθη επαναληπτική διαδικασία εκτελείται από κάθε διεργασία:

For each body i in my “permanenet partition” do


    For each body j in the “circulating partition” do


        Compute force exerted by body j on body i;


Send circulating partition to the right-neighbor process;


Receive new circulating partition from left-neighbor process;

Η παραπάνω διαδικασία επαναλαμβάνεται από κάθε διεργασία μέχρι όλες οι διεργασίες να δουν ένα αντίγραφο από τα περιστρεφόμενα τμήματα. Για να γίνει κατανοητή αυτή η κίνηση των περιστρεφόμενων τμημάτων θεωρείστε έναν πρωταρχικό πίνακα δεδομένων με πέντε τμήματα: A, B, C, D, E. Ο παρακάτω πίνακας δείχνει τα τμήματα που κρατούνται από κάθε διεργασία κατά τη διάρκεια των διαδοχικών επαναλήψεων του αλγορίθμου. Αρχικά, σε κάθε διεργασία δίνεται το μόνιμο τμήμα της, το οποίο αντιγράφεται στο περιστρεφόμενο τμήμα της. Στον πίνακα αυτό για κάθε διεργασία το μόνιμο τμήμα της είναι στα αριστερά και το περιστρεφόμενο τμήμα της στα δεξιά:

*****πίνακας σελίδας 226*****

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

9.2.3 Το πρόγραμμα των Ν-Σωμάτων σε τοπολογία Δακτυλίου.

Το σχήμα 9.4 δείχνει το πλήρες πρόγραμμα των Ν-Σωμάτων για τοπολογία Δακτυλίου σε σύστημα κατανεμημένης μνήμης με 25 επεξεργαστές. Για λόγους προγραμματιστικής ευκολίας, ο πρωταρχικός πίνακας δεδομένων bodies οργανώνεται σαν πίνακας τμημάτων, καθένα από τα οποία περιέχει τέσσερα στοιχεία δεδομένων. Για την δια-διεργασιακή επικοινωνία υπάρχει ένας πίνακας καναλιών, inchan, με ένα κανάλι να έχει ανατεθεί σε καθεμία από τις 25 διεργασίες. Η διαδικασία FindForce τρέχει σε κάθε επεξεργαστή. Η καρδιά της διεργασίας είναι οι τρεις φωλιασμένοι βρόχοι. Ο εξωτερικός βρόχος με το δείκτη k ελέγχει την κυκλοφορία των τμημάτων σε κάθε επανάληψη τα τμήματα κυκλοφορούν κατά ένα βήμα γύρω από το δακτύλιο. Οι εσωτερικοί βρόχοι με τους δείκτες i, j συγκρίνουν κάθε στοιχείο του μόνιμου τμήματος (body) με κάθε στοιχείο του περιστρεφόμενου τμήματος (circ).

Μετά τη συμπλήρωση αυτών των δυο εσωτερικών βρόχων, κάθε διεργασία στέλνει ένα τμήμα στο δεξιό της γείτονα γράφοντας στο inchan που έχει ανατεθεί σε αυτή τη δεξιά γειτονική διεργασία. Κάθε διεργασία λαμβάνει το νέο περιστρεφόμενο τμήμα της διαβάζοντας το δικό της inchan και χρησιμοποιώντας τον αριθμό διεργασίας της me σαν δείκτη. Όταν οι τρεις αυτοί φωλιασμένοι FOR βρόχοι έχουν τελειώσει η διεργασία θα έχει υπολογίσει τις δυνάμεις σε όλα τα σώματα στο μόνιμο τμήμα της. Το τελευταίο βήμα στη διαδικασία FindForce είναι να γράψει η διεργασία την υπολογισμένη δύναμη για τα στοιχεία του τμήματός της πίσω στην πρωταρχική διεργασία, χρησιμοποιώντας την τεχνική των παραμέτρων διεύθυνσης που παρουσιάστηκε στο κεφάλαιο 8.

Ένα ενδιαφέρον χαρακτηριστικό αυτού του προγράμματος Ν-Σωμάτων είναι η μέθοδος που χρησιμοποιείται για την ανάθεση των διεργασιών στην αρχιτεκτονική δακτυλίου και η κατανομή σε κάθε διεργασία του αρχικού τμήματός της. Αυτό όλο γίνεται απλά μέσα στη δήλωση FORALL που δημιουργεί τις διεργασίες στο κυρίως πρόγραμμα. Η κλήση διαδικασίας στην FindForce δημιουργεί κάθε διεργασία. Αυτή η κλήση διαδικασίας περνά σε κάθε διεργασία το μόνιμο τμήμα της σαν μια παράμετρο bodies[i]. Εφόσον ο πίνακας bodies είναι οργανωμένος σαν ένας πίνακας τμημάτων είναι αρκετός ένας μόνο δείκτης για την επιλογή του κατάλληλου τμήματος για κάθε διεργασία που δημιουργείται.

PROGRAM Nbody;


ARCHITECTURE RING(25);


CONST n=100; (*Αριθμός των σωμάτων*)


    numproc=25; (*Αριθμός των διεργασιών*)


    partsize=4; (*Μέγεθος κάθε τμήματος*)


    G=...; (*Σταθερά βαρύτητας*)


TYPE bodytype= RECORD


                m, x, y: REAL; (*Μάζα και θέση*)


                END;


    forcetype= RECORD;


                x, y:REAL; (*Δύναμη στις κατευθύνσεις x και y*)


                END;


    parttype= ARRAY [1..partsize] OF bodytype;


    resulttype=ARRAY [1..partsize] OF forcetype;


VAR bodies: ARRAY [1..numproc] OF parttype; (*Αρχικός πίνακας δεδομένων*)


    finalforce: ARRAY [1..numproc] OF resulttype; (*Προκύπτουσες δυνάμεις*)


    i, j: INTEGER;


    inchan: ARRAY [1..numproc] OF CHANNEL OF parttype; (*Επικοινωνία*)

 


PROCEDURE FindForce(me: INTEGER;


body: parttype; (*Το μόνιμο τμήμα*)


VAR result: resulttype); (*Για να σταλούν πίσω τα αποτελέσματα*)


VAR i, j, k: INTEGER;


    circ: parttype; (*Περιστρεφόμενο τμήμα*)


    force: resulttype; (*Για την συσσωρευμένη δύναμη στα σώματα*)


    xdist, ydist, dist, sqdist, pull: REAL;


BEGIN


    circ:= body; (*Αντιγραφή του μόνιμου τμήματος στο περιστρεφόμενο*)


    FOR i:= 1 TO partsize DO


        BEGIN force[i].x:= 0; force[i].y:= 0; END;


            FOR k:= 1 TO numproc DO


            BEGIN


                FOR i:= 1 TO partsize DO


                    FOR j:= 1 TO partsize DO


                    BEGIN (*Υπολογισμός της δύναμης που ασκείται από το σώμα j στο σώμα i*)


                        xdist:= circ[j].x - body[i].x;


                        ydist:= circ[j].x - body[i].y;


                        distsq:= xdist*xdist + ydist*ydist;


                        dist:= Sqrt(distsq);


                        IF dist ‹› 0 THEN

                        BEGIN

                            pull:= G * body[i].m * circ[j].m / distsq;

                            force[i].x:= force[i].x + pull*xdist/dist;

                            force[i].y:= force[i].y + pull*ydist/dist;

                        END;

        END;

        inchan[me MOD numproc + 1]:= circ; (*Αποστολή στα δεξιά*)

        circ:= inchan[me]; (*Λήψη από τον αριστερό γείτονα*)

    END;

    result:= force; (*Τελική απάντηση στην πρωταρχική διεργασία*)

END;

 

BEGIN (* Κυρίως πρόγραμμα*)

 

    .... (*Αρχικοποίηση του πρωταρχικού πίνακα “bodies*)

 

    FORALL i:= 1 TO numproc DO (*Δημιουργία των διεργασιών*)

        (@i-1 PORT inchan[i]) FindForce(i, bodies[i], finalforce[i]);

 

END.

ΣΧΗΜΑ 9.4 Πρόβλημα των Ν-Σωμάτων σε σύστημα κατανεμημένης μνήμης δακτυλίου.

9.2.4 Ανάλυση Απόδοσης

Το πρόγραμμα των Ν-Σωμάτων υπακούει στις γενικές ιδιότητες που παρουσιάστηκαν στο πρώτο μέρος αυτού του κεφαλαίου: κάθε επανάληψη έχει μία φάση υπολογισμού και μια επικοινωνίας. Κατά τη διάρκεια της φάσης υπολογισμού κάθε διεργασία υπολογίζει τη δύναμη που ασκείται από το περιστρεφόμενο τμήμα του κάθε σώματος στο μόνιμο τμήμα του κάθε σώματος. Αν θεωρήσουμε ότι k είναι το μέγεθος του τμήματος τότε η συνολική διάρκεια της φάσης υπολογισμού κατά τη διάρκεια μιας επανάληψης είναι Sk².

Κατά τη διάρκεια της φάσης επικοινωνίας τα k αντικείμενα δεδομένων του περιστρεφόμενου τμήματος μεταδίδονται στο γειτονικό επεξεργαστή της τοπολογίας Δακτυλίου. Χρησιμοποιώντας το μοντέλο επικοινωνίας που περιγράψαμε στο κεφάλαιο 8 (παράγραφος 8.4.1) η καθυστέρηση επικοινωνίας υλικού για τη μετάδοση k πακέτων, υποθέτοντας ότι η βασική καθυστέρηση επικοινωνίας είναι D, είναι:

Σε αυτό το μοντέλο επικοινωνίας ο αριθμός των r πακέτων είναι μόλις k/3. Κάνοντας την αντικατάσταση στην παραπάνω έκφραση έχουμε:

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

Vk + F

Προσθέτοντας αυτόν τον χρόνο επικοινωνίας και το χρόνο υπολογισμού έχουμε τον τύπο που δώσαμε στην παράγραφο 9.1. Ο χρόνος εκτέλεσης κάθε επανάληψης είναι:

p(Sk² + Vk + F)

Αν θεωρήσουμε ότι n είναι ο συνολικός αριθμός όλων των σωμάτων, μπορούμε να αντικαταστήσουμε k=n/p στην παραπάνω έκφραση και να έχουμε:

Ο όρος n² στον παραπάνω χρόνο εκτέλεσης είναι αποτέλεσμα των βασικών ιδιοτήτων του ακολουθιακού αλγορίθμου των Ν-Σωμάτων, που είναι O(n²). Εφόσον έχουμε n επεξεργαστές που τρέχουν παράλληλα ο όρος n² διαιρείται με p. Ο δεύτερος όρος (Vn) στο χρόνο εκτέλεσης είναι η επιβάρυνση επικοινωνίας που απαιτείται για την κυκλοφορία των n σωμάτων γύρω από το Δακτύλιο. Ο τρίτος όρος Fp είναι αποτέλεσμα του γεγονότος ότι η επικοινωνία πραγματοποιείται σε n διακριτά βήματα, ένα βήμα κατά τη διάρκεια κάθε μιας από τις p επαναλήψεις.

Ενστικτωδώς, αναμένεται ότι μια αύξηση στον αριθμό των επεξεργαστών θα αυξήσει το συνολικό χρόνο εκτέλεσης για ένα παράλληλο πρόγραμμα. Αυτή η ιδιότητα εκφράζεται στον πρώτο όρο του χρόνου εκτέλεσης Sn²/p, που μειώνεται με τις αυξανόμενες τιμές του p. Όμως ο τρίτος όρος αυξάνεται με το p-η επιβάρυνση επικοινωνίας αυξάνεται αναλογικά με τον αριθμό των επεξεργαστών. Εφόσον υπάρχουν αυτές οι δυο αντικρουόμενες τάσεις καθώς αυξάνεται ο αριθμός των επεξεργαστών, θα υπάρχει ένας βέλτιστος αριθμός επεξεργαστών που θα παράγουν τον ελάχιστο χρόνο εκτέλεσης προγράμματος για μια δεδομένη τιμή n. Αυτός ο βέλτιστος αριθμός μπορεί να καθοριστεί παίρνοντας την παράγωγο ως προς p του χρόνου εκτέλεσης και θέτοντάς τη ίση με το 0 (υποθέτοντας ότι το n διατηρείται σταθερό):

Λύνοντας αυτή την εξίσωση έχουμε την ακόλουθη βέλτιστη τιμή για τον αριθμό των επεξεργαστών στον Δακτύλιο:

Βέλτιστο

Αυτή η ανάλυση απόδοσης φανέρωσε μια σημαντική ιδιότητα του παράλληλου προγράμματος των Ν-Σωμάτων: η βέλτιστη απόδοση δεν χρησιμοποιεί απαραίτητα όλους τους διαθέσιμους επεξεργαστές. Εξαιτίας της φύσης των επιβαρύνσεων επικοινωνίας, η απόδοση μπορεί να βελτιωθεί μειώνοντας τον αριθμό των επεξεργαστών και συνεπώς αυξάνοντας το μέγεθος του τμήματος και της κάθε διεργασίας. Από τον παραπάνω τύπο για το βέλτιστο p φαίνεται ότι αυξάνοντας την βασική καθυστέρηση επικοινωνίας D, που θα αυξήσει το F, θα πρέπει να μειωθεί ο βέλτιστος αριθμός των επεξεργαστών.

Το σχήμα 9.5 δείχνει ένα γράφημα του συνολικού χρόνου εκτέλεσης για το πρόγραμμα των Ν-Σωμάτων για διάφορες τιμές του k, που είναι το μέγεθος τμήματος. Ο κάθετος άξονας είναι ο χρόνος εκτέλεσης του προγράμματος των Ν-Σωμάτων και ο κάθετος άξονας είναι η βασική καθυστέρηση επικοινωνίας D. Ο συνολικός αριθμός n των σωμάτων διατηρείται σταθερός καθώς το k λαμβάνει ποικίλες τιμές. Φυσικά ο αριθμός των επεξεργαστών που χρησιμοποιούνται σε κάθε τιμή του k είναι p=n/k. Στο σχήμα 9.5 μπορεί κανείς να δει ότι η καλύτερη επιλογή του k εξαρτάται από την καθορισμένη τιμή του D. Για D135, k=1 και p=100 έχουμε την καλύτερη απόδοση. Για 135D230, k=2 και p=50 έχουμε την καλύτερη απόδοση. Οι τιμές D230, k=3 και p=34 είναι βέλτιστες. Παρόλο που δεν φαίνεται στο σχήμα, καθώς το D αυξάνεται ακόμα περισσότερο, τα k=4 και μετά k=5 τελικά θα υπερέχουν.

ΣΧΗΜΑ 9.5 Χρόνος εκτέλεσης του προγράμματος N-Body

9.2.5 Επικαλύπτοντας την Επικοινωνία με Υπολογισμό

Είναι δυνατή η βελτίωση της απόδοσης του προγράμματος των Ν-Σωμάτων του σχήματος 9.4 με μια απλή τροποποίηση που επιτρέπει να επικαλύπτονται οι υπολογισμοί και η επικοινωνία. Όπως είναι τώρα το πρόγραμμα κάθε διεργασία πραγματοποιεί την παρακάτω ακολουθία δραστηριοτήτων κατά τη διάρκεια κάθε επανάληψης:

1. Υπολογισμός της δύναμης που ασκείται από όλα τα σώματα του περιστρεφόμενου τμήματος σε όλα τα σώματα του μόνιμου τμήματος.

2. Αποστολή του τρέχοντος περιστρεφόμενου τμήματος στο δεξιό γείτονα

3. Λήψη του νέου περιστρεφόμενου τμήματος από τον αριστερό γείτονα.

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

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

9.2.6 Ιδεατή εναντίον Φυσικής τοπολογίας.

Κάθε αλγόριθμος έχει τη δική του φυσική τοπολογία επικοινωνίας διεργασιών. Στην περίπτωση του προγράμματος Ν-Σωμάτων, ο Δακτύλιος είναι η φυσική τοπολογία-κάθε διεργασία επικοινωνεί μόνο με τις διεργασίες που βρίσκονται αριστερά της ή δεξιά της στο Δακτύλιο. Εξαιτίας της τοπολογίας του ιδεατού Δακτυλίου στον αλγόριθμο επιλέχθηκε φυσική τοπολογία Δακτυλίου συστήματος κατανεμημένης μνήμης Δακτυλίου. Όμως, αυτός ο ιδεατός Δακτύλιος μπορεί να απεικονιστεί σε φυσικές τοπολογίες πιο υψηλής συνεκτικότητας, όπως είναι το Πλέγμα, ο Τόρος και ο Υπερκύβος. Οι επιπλέον φυσικοί σύνδεσμοι επικοινωνίας στις πιο συνεκτικές τοπολογίες δεν θα χρησιμοποιούνται κατά τη διάρκεια της επαναληπτικής εκτέλεσης των διεργασιών. Όμως, αυτές οι επιπλέον συνδέσεις βοηθούν στη μείωση του χρόνου για τη δημιουργία των διεργασιών και την κατανομή τους μαζί με τα αρχικά τμήματά τους στους επεξεργαστές. Η μικρότερη διάμετρος των υψηλά συνεκτικών τοπολογιών θα μειώσει το χρόνο για τη δημιουργία της διεργασίας και το βήμα αρχικοποίησης της όπως επίσης και το χρόνο για το βήμα τερματισμού της.

PROCEDURE FindForce(me: INTEGER;


body: parttype; (*Το μόνιμο τμήμα*)


VAR result: resulttype); (*Για την αποστολή των αποτελεσμάτων πίσω*)


VAR i, j, k: INTEGER;


    circ: parttype; (*Περιστρεφόμενο τμήμα*)


    force: resulttype; (*Για τη συσσώρευση της δύναμης στα σώματα*)


    xdist, ydist, dist, distsq, pull: REAL;


BEGIN


        circ:= body; (*Αντιγραφή του μόνιμου τμήματος στο περιστρεφόμενο*)


        FOR i:= 1 TO partsize DO


        BEGIN force[i].x:= 0; force[i].y:= 0; END;


        FOR k:= 1 TO numproc DO


        BEGIN

 

            inchan[me MOD numproc+1]:= circ; (*Αποστολή στα δεξιά**)

 


            (*Φάση Υπολογισμού*)


            FOR i:= 1 TO partsize DO 


                FOR j:= 1 TO partsize DO


                    BEGIN (*Υπολογισμός της δύναμης που ασκείται από το σώμα j στο σώμα i*)


                        xdist:= circ[j].x - doby[i].x;


                        ydist:= circ[j].y - body[i].y;


                        distsq:= xdist*xdist + ydist*ydist;


                        dist:= Sqrt(distsq);


                        IF dist ‹› 0 THEN 

                            BEGIN

                            pull:= G * body[i].m * circ[j].m/distsq;

                            force[i].x:= force[i].x + pull*xdist/dist;

                            force[i].y:= force[i].y + pull*ydist/dist;

                            END;

                    END;

                    circ:= inchan[me]; (*Λήψη από τον αριστερό γείτονα*)

        END;

        result:= force; (*Τελική απάντηση πίσω στην πρωταρχική διεργασία*)

END;

ΣΧΗΜΑ 9.6 Επικαλυπτόμενος υπολογισμός και επικοινωνία στο πρόγραμμα των Ν-Σωμάτων

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

1. Γραμμή

2. Δακτύλιος

3. Δι-διάστατο Πλέγμα

4. Τόρος

5. Τρισδιάστατο Πλέγμα

6. Υπερκύβος

7. Πλήρως Συνδεδεμένη

Γενικά, όλες οι τοπολογίες που βρίσκονται στην αρχή της παραπάνω λίστας μπορούν να απεικονιστούν από τις τοπολογίες που βρίσκονται προς το τέλος. Όμως, σε μερικές περιπτώσεις η απεικόνιση απαιτεί ότι κάποιοι από τους επεξεργαστές δεν θα χρησιμοποιηθούν. Για παράδειγμα, η απεικόνιση ενός Δακτυλίου 25 επεξεργαστών σε έναν Υπερκύβο απαιτεί έναν Υπερκύβο πέντε διαστάσεων με 32 επεξεργαστές. Φυσικά κάθε ιδεατή δομή επικοινωνίας μπορεί να εφαρμοστεί σε κάθε φυσική τοπολογία με την προϋπόθεση ότι είναι δυνατή η ανοχή των επιπλέον χρονικών καθυστερήσεων της επικοινωνίας μεταξύ επεξεργαστών που δεν συνδέονται με απευθείας φυσικό σύνδεσμο.

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

FORALL i:= 1 TO numproc DO (*Δημιουργία των διεργασιών*)

(@i-1 PORT inchan[i]) Findforce(i, bodies[i], finalforce[i]);

Η έκφραση “@i-1” αναθέτει κάθε διεργασία στον κατάλληλο φυσικό επεξεργαστή της στην υποκείμενη τοπολογία Δακτυλίου του συστήματος κατανεμημένης μνήμης. Για την εφαρμογή αυτού του προγράμματος σε σύστημα κατανεμημένης μνήμης Υπερκύβου χρειάζονται μόνο λίγες αλλαγές. Θυμηθείτε ότι στον Υπερκύβο κάθε επεξεργαστής έχει απευθείας συνδέσεις προς όλους τους επεξεργαστές των οποίων οι αριθμοί διαφέρουν από τον δικό του κατά ένα δυαδικό ψηφίο. Μια δομή επικοινωνίας ιδεατού δακτυλίου μπορεί να απεικονιστεί φυσική τοπολογία Υπερκύβου χρησιμοποιώντας τον Κώδικα Gray, όπως είδαμε και στο κεφάλαιο 7. Ο Κώδικας Gray είναι μια ακολουθία αριθμών τέτοια ώστε κάθε διαδοχικός αριθμός διαφέρει από τους προηγούμενους μόνο κατά ένα δυαδικό ψηφίο.

Στο πρόγραμμα πρέπει να δημιουργηθεί ένας πίνακας Gray που περιέχει την αρίθμηση του Κώδικα Gray για την απεικόνιση ενός ιδεατού Δακτυλίου σε Υπερκύβο. Η ακολουθία των αριθμών στον πίνακα Gray είναι απλώς η ακολουθία του Κώδικα Gray. Για παράδειγμα, να το πρόγραμμα δημιουργεί οκτώ διεργασίες (numproc=8) τότε ο πίνακας Gray πρέπει να περιέχει τους ακόλουθους αριθμούς:

Gray[1]=0 (δυαδικό 000)

Gray[2]=1 (δυαδικό 001)

Gray[3]=3 (δυαδικό 011)

Gray[4]=2 (δυαδικό 010)

Gray[5]=6 (δυαδικό 110)

Gray[6]=7 (δυαδικό 111)

Gray[7]=5 (δυαδικό 101)

Gray[8]=4 (δυαδικό 100)

Η ακολουθία των αριθμών στον πίνακα Gray δίνει τη φυσική ακολουθία των επεξεργαστών στον Υπερκύβο που σχηματίζουν έναν ιδεατό Δακτύλιο. Οι τιμές για αυτόν τον πίνακα μπορούν να αναγνωστούν από το πρόγραμμα ή να υπολογιστούν εσωτερικά, χρησιμοποιώντας τον ορισμό για τους Κώδικες Gray που παρουσιάστηκε στο κεφάλαιο 7. Η μόνη διαφορά στο αρχικό πρόγραμμα των Ν-Σωμάτων του σχήματος 9.4 είναι η τροποποίηση της έκφρασης που ακολουθεί ο τελεστής @ στη δήλωση δημιουργίας της διεργασίας, όπως φαίνεται παρακάτω:

FORALL i:= 1 TO numproc DO (*Δημιουργία των διεργασιών*)

(@Gray[i] PORT inchan[i]) FindForce(i, bodies[i],finalforce[i]);

Η έκφραση @Gray[i] αναθέτει τις διεργασίες στους κατάλληλους φυσικούς επεξεργαστές στον Υπερκύβο, έτσι ώστε οι διεργασίες που επικοινωνούν να έχουν πάντα έναν απευθείας φυσικό σύνδεσμο στον Υπερκύβο. Χρησιμοποιώντας μια παρόμοια προγραμματιστική τεχνική, το πρόγραμμα των Ν-Σωμάτων μπορεί να εκτελεστεί σε όλες τις τοπολογίες των συστημάτων κατανεμημένης μνήμης. Το μόνο που χρειάζεται είναι ένας πίνακας που να περιέχει την ακολουθία των φυσικών επεξεργαστών που είναι απαραίτητη για τη δημιουργία του ιδεατού Δακτυλίου από την υποκείμενη τοπολογία συστήματος κατανεμημένης μνήμης.