5.4 Αριθμητική Ολοκλήρωση

Επόμενο:5.5 Συγκρίνοντας το Κλείδωμα και τα Κανάλια Πάνω: Κεφάλαιο 5ο : Μοίρασμα Δεδομένων Πίσω: 5.3 Ανταγωνισμός για Διαμοιραζόμενα Δεδομένα

5.4 Αριθμητική Ολοκλήρωση

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

Μια εφαρμογή της αριθμητικής ολοκλήρωσης φαίνεται στο σχήμα 5.6. Η καμπύλη δείχνει την ταχύτητα ενός οχήματος σαν συνάρτηση του χρόνου. Για να καθοριστεί η συνολική απόσταση που καλύπτεται από ένα όχημα σε χρόνο από a ως b, πρέπει να υπολογιστεί όλη η περιοχή κάτω από την καμπύλη, όπως φαίνεται και στο σχήμα. Ο υπολογισμός αυτής της περιοχής μπορεί να γίνει με ένα αριθμητικό ολοκλήρωμα. Για κάθε συνάρτηση f(t) έχουμε το ολοκλήρωμα :

Αν η συνάρτηση f(t) δηλώνει την ταχύτητα του οχήματος τότε το παραπάνω ολοκλήρωμα δίνει τη συνολική απόσταση στο χρονικό διάστημα από a έως b που καλύπτεται από αυτό. Σε μια διαφορετική περιοχή εφαρμογών το f(t) μπορεί να δηλώνει το ρεύμα ενός πυκνωτή μέσα σε ένα ηλεκτρονικό κύκλωμα. Στην περίπτωση αυτή το ολοκλήρωμα θα έδινε τη συνολική αλλαγή τάσης στον πυκνωτή κατά τη διάρκεια του χρόνου μεταξύ a και b.

Αυτό το ολοκλήρωμα μπορεί να προσεγγιστεί με τη δειγματοληψία της συνάρτησης f μεταξύ των δυο οριακών σημείων a και b και n εσωτερικών σημείων που απέχουν μεταξύ τους κατά σταθερή απόσταση w. Χρησιμοποιώντας τον τυπικό κανόνα του τραπεζίου προκύπτει ο παρακάτω τύπος για το ολοκλήρωμα :

w[f(a)/2+f(a+w)+f(a+2w)+...+f(a+nw)+f(b)/2]

ΣΧΗΜΑ 5.6 Εφαρμογή της αριθμητικής ολοκλήρωσης

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

Sequential Numerical Integration:


sum := 0;
t := a;
For i := 1 to n do
  BEGIN
	t:=t+w;	      	(*Προχωρά στο επόμενο σημείο *)
	sum:=sum+f(t);	(*Προστίθεται το σημείο δείγματος στο άθροισμα*)
  END;
sum := sum + (f(a) + f(b)) / 2;
answer := w * sum;

Για την ανάπτυξη του παράλληλου προγράμματος αριθμητικής ολοκλήρωσης ένα τμήμα της καμπύλης που πρόκειται να ολοκληρωθεί εκχωρείται σε κάθε διεργασία. Ο πρώτος σκοπός μας θα είναι να προστεθούν όλες οι διεργασίες τα σημεία της δειγματοληψίας σε μια διαμοιραζόμενη μεταβλητή, την sum, χρησιμοποιώντας ένα κλείδωμα για την εγγύηση της ακεραιότητας της λειτουργίας της πρόσθεσης. Όμως, η συγκέντρωση του αθροίσματος οδηγεί σε πρόβλημα ανταγωνισμού που μπορεί να βλάψει την απόδοση. Μια καλύτερη λύση είναι η “αποκέντρωση” του αθροίσματος σε τοπικές μεταβλητές αθροίσματος, οι οποίες στη συνέχεια θα προσθέτονται σε μια καθολική μεταβλητή αθροίσματος. Όταν το πρόγραμμα εκτελείται παράλληλα, οι διεργασίες επεξεργάζονται και αθροίζουν τα σημεία δειγματοληψίας στο δικό τους τμήμα, χρησιμοποιώντας ένα δικό τους τοπικό αθροιστή. Στη συνέχεια τα τοπικά αθροίσματα προστίθενται σε έναν γενικό αθροιστή με μια ατομική λειτουργία. Η συνολική τεχνική φαίνεται στο σχήμα 5.7 :

ΣΧΗΜΑ 5.7 Παράλληλη μορφή αριθμητικής ολοκλήρωσης

Το συνολικό πρόγραμμα φαίνεται στο σχήμα 5.8. Το κεντρικό στοιχείο του προγράμματος είναι η διαδικασία Integrate που σχηματίζει το σώμα κάθε διεργασίας. Μετά τον καθορισμό του σημείου έναρξης η διαδικασία έχει ένα βρόχο FOR για την πρόσθεση όλων των σημείων δειγματοληψίας της συνάρτησης χρησιμοποιώντας μια τοπική μεταβλητή αθροιστή. Η σταθερά numpoints λαμβάνει ως τιμή τον αριθμό των σημείων δειγματοληψίας της περιοχής που αποδίδονται στην κάθε διεργασία. Εφόσον υπάρχουν συνολικά numproc διεργασίες ο συνολικός αριθμός των σημείων δειγματοληψίας θα είναι numproc*numpoints. Στο τέλος της διαδικασίας το localsum προστίθεται στο globalsum με μια ατομική λειτουργία. Για το συγκεκριμένο πρόγραμμα απαιτούνται 40 επεξεργαστές. Εκτελώντας το πρόγραμμα σε σύστημα αλληλεξάρτησης Multi-Pascal η τελική επιτάχυνση είναι τελικά 25. Με τη χρησιμοποίηση της μεταβλητής localsum για κάθε διεργασία η πιθανότητα εμφάνισης ανταγωνισμού ελαχιστοποιείται. Έτσι, το πρόγραμμα επιτυγχάνει μια καλή απόδοση

PROGRAM Numerical Integration;
CONST numproc = 40;    (*Πλήθος των διεργασιών*)
      numpoints = 30;  (*Πλήθος των στοιχείων ανά διεργασία*)


VAR  a, b, w, globalsum, answer: real;
     i: integer;
     L: spinlock;


Function f(t: real): Real;  (*Η συνάρτηση που θα ολοκληρωθεί*)
BEGIN
....... (*Υπολογισμός της τιμής της f(t)*)
 
END;


Procedure Integrate(myindex: Integer);
VAR  localsum, t: Real;
     j: Integer;

BEGIN
t:= a + myindex * (b-a)/numproc;	(*Η αρχική θέση*)
For j:= 1 to numpoints do
  BEGIN
	localsum:= localsum + f(t);  (*Πρόσθεση του επομένου στοιχείου της δειγματοληψίας*)
	
	t:= t + w;
  END;
localsum:= w*localsum;
Lock(L);
globalsum:= globalsum + localsum;  (*Ατομική αλλαγή*)
Unlock(L);
END;

BEGIN
.... (*Αρχικοποίηση των τιμών των ακράιών σημείων a και b*)

w:= (b-a) / (numproc*numpoints);  (*Η απόσταση μεταξύ των σημείων*)

Forall I:= 0 to numproc-1 do  (*Δημιουργία διεργασιών*)
Integrate(i);
answer:=globalsum+w/2*(f(b)-f(a)); (*Πρόσθεση των ακραίων σημείων*)
END.

ΣΧΗΜΑ 5.8 Πρόγραμμα παράλληλης αριθμητικής ολοκλήρωσης

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