Next              Up                Back                Contents    

Επόμενο:4.5 Κανάλια και δομημένοι τύποι Πάνω: Κεφάλαιο 4o : Επικοινωνία διεργασιών Πίσω: 4.3 Παραλληλισμός Διασωλήνωσης


 

4.4 Επίλυση Γραμμικών Εξισώσεων

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

 

4.4.1 Προς τα πίσω Αντικατάσταση

Ένα σύστημα γραμμικών εξισώσεων ορίζει μια σχέση ανάμεσα σε μια ομάδα αγνώστων, συνήθως συμβολίζονται x1,x2,...,xn. Η γενική μορφή ενός συστήματος εξισώσεων είναι η ακόλουθη:

a11x1 + a12x2 + a13x3 + ... + a1nxn = b1

a21x1 + a22x2 + a23x3 + ... + a2nxn = b2

a31x1 + a32x2 + a33x3 + ... + a3nxn = b3

. . . . .

. . . . .

an1x1 + an2x2 + an3x3 + ... + annxn = bn

Οι τιμές των όρων a και b είναι γνωστές και ο Η/Υ καλείται να προσδιορίσει την αριθμητική τιμή των αγνώστων (x1,x2,...,xn) που θα κάνουν όλες τις εξισώσεις να ισχύουν ταυτόχρονα. Μια ειδική μορφή αυτού του συστήματος εξισώσεων, που είναι και εύκολη για να λυθεί, είναι το κάτω τριγωνικό σύστημα (απαλοιφή Gauss). Ένα κάτω τριγωνικό σύστημα έχει όλες τις τιμές των a ίσες με μηδέν στο άνω δεξιό τμήμα των εξισώσεων, συγκεκριμένα ισχύειaij=0 εάν ισχύει j>i μορφή του κάτω τριγωνικού συστήματος, αφού αφαιρεθούν όλοι οι μηδενικοί όροι του συστήματος:

 

a11x1                                                  = b1

a21x1 + a22x2                                             = b2

a31x1 + a32x2 + a33x3                                        = b3

a41x1 + a42x2 + a43x3 + a44x4                                  = b4

. . . . .

. . . . .

. . . . .

an1x1 + an2x2 + an3x3 + an4x4 + ... + annxn                        = bn

Στο αρχικό σύστημα, οι εξισώσεις έχουν ορθογώνια σχήμα. Όμως, με την απάλειψη των άνω δεξιών όρων, το σύστημα έχει τριγωνικό σχήμα και για αυτό και ονομάζεται κάτω τριγωνικό σύστημα εξισώσεων. Προσέξτε ότι στην εξίσωση i, υπάρχουν μόνο οι όροι από x1,x2,...,xi (οι υπόλοιποι είναι μηδέν). Κάθε διαδοχική εξίσωση προσθέτει έναν ακόμα άγνωστο, μέχρι που η τελευταία εξίσωση περιλαμβάνει και τις n εξισώσεις. Όταν ένα σύστημα βρίσκεται στην κάτω τριγωνική μορφή, είναι εύκολο να επιλυθεί, λύνοντας μια εξίσωση τη φορά ξεκινώντας από την κορυφή. Η εξίσωση 1 λύνεται εύκολα και προσδιορίζει την αριθμητική τιμή του αγνώστου x1:

 

image

Η δεύτερη εξίσωση μπορεί να λυθεί ως προς τον άγνωστο x2 ως εξής:

 

imageimage

Όλες οι τιμές που βρίσκονται στο δεξιό μέρος, είναι γνωστές, επομένως από την εξίσωση μπορεί να βρεθεί η αριθμητική τιμή του αγνώστου x2. Από τη στιγμή που έχουν βρεθεί οι τιμές των x1 και x2 , μπορεί πλέον να επιλυθεί και η τρίτη εξίσωση ώστε να βρεθεί και η τιμή του αγνώστου x3:

image

Εάν η μέθοδος επαναληφθεί σε κάθε μια εξίσωση του συστήματος, τότε θα υπολογισθούν οι τιμές και των n αγνώστων. Γενικά ισχύει ότι, όταν έρθει η σειρά της εξίσωσης i για να επιλυθεί, είναι ήδη γνωστές των αγνώστων x1, x2, ..., xi-1. Με αυτά τα στοιχεία μπορεί να λυθεί η εξίσωση i και να υπολογισθεί ο άγνωστος x3. Η γενική μορφή της εξίσωσης i είναι η ακόλουθη :

 

image

Επομένως, η τιμή του xi μπορεί να προσδιορισθεί ως εξής:

image

Η μέθοδος επίλυσης ενός κάτω τριγωνικού συστήματος, που μόλις περιγράφηκε, ονομάζεται προς τα πίσω αντικατάσταση και η μετατροπή του σε σειριακό πρόγραμμα είναι πολύ απλή. Οι aij μπορούν να αποθηκευθούν σε ένα διδιάστατο πίνακα Α, οι όροι bi θα αποθηκευθούν σε ένα μονοδιάστατο πίνακα Β και τέλος για τους αγνώστους θα χρησιμοποιηθεί ο μονοδιάστατος πίνακας X. Παρακάτω δίδεται ο σειριακός αλγόριθμος:

Sequential Back Substitution:

FOR i:=1 TO n DO

    BEGIN (* Επίλυση της εξίσωσης i για την τιμή του x1 *)

        sum:=0;

        FOR j:=1 TO i-1 DO

           sum:=sum+A[i,j]*x[j];

        x[i]:=(B[i]-sum)/A[i,i];

    END;

Ο παραπάνω σειριακός αλγόριθμος μπορεί να μετατραπεί σε παράλληλο αλλά χρειάζεται προσοχή κατά την μετατροπή. Ο εξωτερικός βρόχος FOR δεν γίνεται απλά να μετατραπεί σε FORALL. Ο εσωτερικός βρόχος υπολογίζει την τιμή τουx[i] με βάση τις τιμές των x[1],x[2],...,x[i-1] που βρέθηκαν σε προηγούμενες επαναλήψεις. Επομένως, οι τιμές του i δεν μπορούν να χρησιμοποιηθούν παράλληλα. Οι εξισώσεις δεν μπορούν να εξετασθούν παράλληλα άρα και ούτε να επιλυθούν παράλληλα. Ωστόσο, υπάρχει δυνατότητα να χρησιμοποιηθεί παραλληλισμός στην μέθοδο της προς τα πίσω αντικατάστασης.

 

4.4.2 Αλγόριθμος διασωλήνωσης στη μέθοδο της προς τα πίσω Αντικατάστασης

Για να δομηθεί ο παράλληλος αλγόριθμος, πρέπει να ανατεθεί κάθε εξίσωση σε μια διαφορετική διεργασία. Στην διεργασία i ανατίθεται η εξίσωση i και θα υπολογίσει την τιμή του x[i]. Για να το πετύχει αυτό, η διεργασία i χρειάζεται να έχει τις τιμές των x[1],x[2],...,x[i-1], που υπολογίζονται από τις διεργασίες 1, 2, ... , i-1. Εάν οι διεργασίες τοποθετηθούν σε μια διασωλήνωση και η αρίθμηση τους ξεκινήσει από τα αριστερά προς τα δεξιά, τότε η διεργασία i θα χρειαστεί όλες τις τιμές που υπολογίζονται από διεργασίες που βρίσκονται αριστερά της στη διασωλήνωση. Το παραπάνω φαίνεται καθαρά στο Σχήμα 4.6. Όταν η διεργασία 1, που βρίσκεται στην αρχή της διασωλήνωσης, υπολογίσει την τιμή του x[1], θα ξέρει ότι η τιμή είναι απαραίτητη για όλες τις άλλες διεργασίες που βρίσκονται στα δεξιά της. Στέλνοντας την τιμή x[1] προς τα δεξιά μέσα στη διασωλήνωση, θα φτάσει βαθμιαία σε όλες τις υπόλοιπες διεργασίες. Ομοίως, όταν η διεργασία 2 τελειώσει τους υπολογισμούς για την τιμή x[2], θα γνωρίζει ότι η τιμή χρειάζεται σε όλες τις διεργασίες που βρίσκονται στα δεξιά της και για αυτό θα την στείλει προς τα δεξιά μέσα στη διασωλήνωση.

 

image

ΣΧΗΜΑ 4.6 Η διασωλήνωση διεργασιών στη προς τα πίσω αντικατάσταση

Υποθέστε τώρα ότι κάθε διεργασία i της διασωλήνωσης θα στείλει την τιμή του x[i] που υπολόγισε, προς τα δεξιά της διασωλήνωσης. Κάθε διεργασία μπορεί να περιμένει ότι θα δεχθεί όλες τις αναγκαίες τιμές που θα έρχονται από τα αριστερά της. Μια παραπομπή στο Σχήμα 4.6 δείχνει φανερά ότι οπουδήποτε και αν βρίσκεται η διεργασία i θα παραλάβει από δεξιά της, τις τιμές x[1],x[2],...,x[i-1]. Ωστόσο για να λειτουργήσει σωστά ο αλγόριθμος, είναι απαραίτητο οι απαιτούμενες τιμές που έρχονται από τη διασωλήνωση, να καταφθάνουν με τη σωστή σειρά. Για να εξασφαλιστεί αυτό, κάθε διεργασία στέλνει πρώτα όλες τις προηγούμενες τιμές και στο τέλος στέλνει τη δική της τιμή. Αφού η διεργασία i παραλάβει τις τιμές x[1],x[2],...,x[i-1] που χρειάζεται, θα τις στείλει στη διεργασία i+1 και μετά θα στείλει την τιμή x[i] που υπολόγισε. Έτσι κάθε πετυχημένη διεργασία θα προσθέτει μια νέα τιμή στη σειρά των x που θα ρέει μέσα στη διασωλήνωση.

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

Pipeline Process i:

    sum:=0;

    FOR j:=1 TO i-1 DO

            BEGIN

            Διαβάζει την τιμή του x[j] από αριστερά;

            Στέλνει την τιμή του x[j] προς τα δεξιά;

            sum:=sum+A[i,j]*x[j];        

            END;

    x[i]:=(B[i]-sum)/A[i,i]; (* Υπολογίζει την τιμή του x[i] *)

    Στέλνει το x[i] προς τα δεξιά;

Προσέξτε ότι ο κώδικας για τη διεργασία i είναι σχεδόν όμοιος με τον εσωτερικό βρόχο FOR του σειριακού προγράμματος της προς τα πίσω αντικατάστασης που παρουσιάσθηκε παραπάνω. Η μόνη διαφορά είναι η χρήση της διασωλήνωσης για την ανάγνωση των x[1],x[2],...,x[i-1]. Προσέξτε επίσης ότι η διεργασία χρησιμοποιεί κάθε μία από τις τιμές, απευθείας μόλις την παραλάβει από τα αριστερά. Αμέσως μόλις παραληφθεί κάποιο x[j], πολλαπλασιάζεται με το A[i,j] και προστίθεται στο μερικό άθροισμα. Τέλος, το μερικό άθροισμα χρησιμοποιείται στον υπολογισμό της τελικής τιμής του x[i], το οποίο στέλνεται μέσα από τη διασωλήνωση σε άλλες διεργασίες.

Το ολοκληρωμένο πρόγραμμα σε Multi-Pascal παρουσιάζεται στο Σχήμα 4.7. Οι διεργασίες δημιουργούνται μέσα στη διαδικασία PipeProcess. Η κάθε διεργασία λαμβάνει, με μια παράμετρο τιμής, έναν δείκτη και μετά υπολογίζει τον άγνωστο x[i] χρησιμοποιώντας την i εξίσωση του αρχικού συστήματος γραμμικών εξισώσεων. Το πρόγραμμα χρησιμοποιεί n επεξεργαστές για να επιλύσει ένα σύστημα n εξισώσεων. Ο συνολικός χρόνος εκτέλεσης είναι O(n), σε αντίθεση με το σειριακό πρόγραμμα που έχει χρόνο εκτέλεσης O(n2). Η επιτάχυνση που πετυχαίνεται από το παράλληλο πρόγραμμα είναι O(n). Ο αλγόριθμος της προς τα πίσω αντικατάστασης με διασωλήνωση είναι μια χρήσιμη και πρακτική μέθοδος για την επίλυση κάτω τριγωνικών συστημάτων με γραμμικές εξισώσεις και χρησιμοποιείται πολύ συχνά στην πράξη σε μια ευρεία ποικιλία συστημάτων κατανεμημένης και διαμοιραζόμενης μνήμης.

Μπορούμε να πάρουμε μια εικόνα για τη δυναμική του προγράμματος από το διάγραμμα απόδοσης, που παρουσιάζεται στο Σχήμα 4.8, που δημιουργείται με την εντολή profile που υπάρχει στο διαλογικό σύστημα της Multi-Pascal (βλέπε παράρτημα). Προκειμένου να χωρέσει το πορτραίτο απόδοσης στο πλάτος της σελίδας, χρησιμοποιήθηκε ένα σύστημα 30 εξισώσεων και όχι 50 όπως ορίζει το πρόγραμμα, έτσι ώστε να απαιτώνται 31 επεξεργαστές. Κάθε οριζόντια γραμμή του πορτραίτου αντιστοιχεί σε 60 χρονικές μονάδες. Η κενή περιοχή που υπάρχει στο πάνω δεξιό τμήμα του πορτραίτου παριστάνει το χρόνο δημιουργίας των διεργασιών. Πριν ανατεθεί κάποιος επεξεργαστής σε μια διεργασία, το πορτραίτο παρουσιάζει κενό για εκείνο τον επεξεργαστή. Προσέξτε ότι ακόμα και μετά από τη δημιουργία της, η κάθε διεργασία πρέπει να περιμένει λίγο μέχρι να μπει σε πλήρη λειτουργία. Αυτό συμβαίνει γιατί κάθε διεργασία (πλην της διεργασίας 1) πρέπει να περιμένει να παραλάβει την τιμή του x[1] από τον αριστερό γείτονα πριν ξεκινήσει τους υπολογισμούς. Αφού λοιπόν η τιμή του x[1] προέρχεται από τη διεργασία 1 και κινείται βαθμιαία προς τα δεξιά μέσα στη διασωλήνωση, κάθε πετυχημένη διεργασία της διασωλήνωσης πρέπει να περιμένει ένα μικρό πρόσθετο χρονικό διάστημα πριν ξεκινήσει.

PROGRAM BackSubstitution;

    CONST n=50;

    VAR A:ARRAY [1.. n,1.. n] OF REAL;

        B,x:ARRAY [1.. n] OF REAL;

        pipechan : ARRAY [1.. n+1] OF CHANNEL OF REAL;

        i : INTEGER;

PROCEDURE PipeProcess(i:INTEGER);

    (* Επιλύει την εξίσωση i για να υπολογίσει το x[i] *)

    VAR j:INTEGER; sum,xvalue:REAL;

    BEGIN

        sum:=0;

        FOR j:=1 TO i-1 DO

            BEGIN

               xvalue:=pipechan[i]; (* Διαβάζει το x[j] από τα αριστερά *)

               pipechan[i+1]:=xvalue; (* Στέλνει το x[j] προς τα δεξιά *)

               sum := sum + A[i,j]*xvalue;

            END;

        x[i]:=(B[i]-sum)/A[i,i];(* Υπολογίζει την τιμή για το x[i] *)

        pipechan[i+1]:=x[i]; (*Στέλνει το x[i] προς τα δεξιά *)

    END;

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

    .... (* Αρχικοποίηση των πινάκων Α και Β *)

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

     pipeProcess(i);

END.

ΣΧΗΜΑ 4.7 Παράλληλη προς τα πίσω αντικατάσταση

Προσέξτε επίσης ότι οι διεργασίες με μεγαλύτερο δείκτη στο διάγραμμα πραγματοποιούν περισσότερους υπολογισμούς. Αυτό συμβαίνει εξαιτίας του τριγωνικού σχήματος του συστήματος εξισώσεων, όπου οι εξισώσεις με τη μεγαλύτερη αρίθμηση περιέχουν περισσότερους όρους. Το τριγωνικό σχήμα των εξισώσεων αντικατοπτρίζεται στο τριγωνικό σχήμα της υπολογιστικής περιοχής που βρίσκεται στο δεξιό τμήμα του πορτραίτου. Η μεγάλη περιοχή που καλύπτεται από κουκίδες αντιστοιχεί στο χρόνο που παραμένουν αδρανείς οι διεργασίες. Η μέση χρησιμοποίηση των επεξεργαστών είναι 37%. Ωστόσο, το πρόγραμμα πετυχαίνει μια ικανοποιητική συνολική επιτάχυνση ίση με 11.

**** ΣΧΗΜΑ 4.8 Πορτραίτο απόδοσης της προς τα πίσω αντικατάστασης

Ο χρόνος εκτέλεσης της τάξεως του O(n) φαίνεται επίσης και από το πορτραίτο απόδοσης. Ο χρόνος εκτέλεσης εξαρτάται από τον μεγαλύτερο σε αρίθμηση επεξεργαστή n που πρέπει να υπολογίσει την τιμή του x[n], χρησιμοποιώντας τις τιμές των x[1], x[2], ... , x[n-1]. Αυτό προϋποθέτει n αθροίσεις και n πολλαπλασιασμούς και επομένως είναι της τάξεως του O(n). Ο χρόνος που απαιτείται για να φθάσει η πρώτη τιμή δηλαδή το x[1] στον επεξεργαστή n, είναι επίσης O(n), επομένως ο συνολικός χρόνος εκτέλεσης του προγράμματος είναι O(n). Η παραπάνω ανάλυση επιβεβαιώνεται από το γράφημα απόδοσης που υπάρχει στο Σχήμα 4.9 και που δείχνει την επιτάχυνση του προγράμματος για αυξανόμενες τιμές του n που καθορίζονται με την εκτέλεση του προγράμματος από το πακέτο λογισμικού της Multi-Pascal. Το γράφημα δείχνει ότι η πραγματική επιτάχυνση του προγράμματος είναι κατά προσέγγιση 37n.

 

 

image

ΣΧΗΜΑ 4.9 Επιτάχυνση της προς τα πίσω αντικατάστασης

 


     Next              Up                Back                Contents   

Επόμενο:4.5 Κανάλια και δομημένοι τύποι Πάνω: Κεφάλαιο 4o : Επικοινωνία διεργασιών Πίσω: 4.3 Παραλληλισμός Διασωλήνωσης