5.3 Ανταγωνισμός για Διαμοιραζόμενα Δεδομένα

Επόμενο:5.4 Αριθμητική Ολοκλήρωση Πάνω: Κεφάλαιο 5ο : Μοίρασμα Δεδομένων Πίσω: 5.2 Κλειδώματα

5.3 Ανταγωνισμός για Διαμοιραζόμενα Δεδομένα

Για την πρόληψη των λανθασμένων αλληλεπιδράσεων μεταξύ παράλληλων διεργασιών κατά την πρόσβαση σε διαμοιραζόμενα δεδομένα είναι απαραίτητη η δημιουργία ατομικών λειτουργιών χρησιμοποιώντας κλειδώματα. Όμως, σε μερικά προγράμματα οι ατομικές λειτουργίες είναι δυνατόν να αυξήσουν το συνολικό χρόνο εκτέλεσής τους μέσα από την αναμονή των διεργασιών για πρόσβαση σε διαμοιραζόμενα δεδομένα. Κατά τη διάρκεια μιας ατομικής λειτουργίας από μια διεργασία, έστω Α, όλες οι άλλες διεργασίες δεν μπορούν να έχουν πρόσβαση στα ίδια διαμοιραζόμενα δεδομένα. Αυτό μπορεί να μειώσει δραστικά την παράλληλη λειτουργία του προγράμματος και συνεπώς και την συνολική ταχύτητα εκτέλεσής του. Ακόμα και μια σχετικά σύντομη ατομική λειτουργία μπορεί να προκαλέσει την καθυστέρηση ενός προγράμματος αν αυτή η λειτουργία πραγματοποιείται συχνά από μεγάλο αριθμό παράλληλων διεργασιών. Για παράδειγμα, έστω ότι μια ατομική λειτουργία απαιτεί 10 μονάδες χρόνου. Αν υπάρχουν 50 παράλληλες διεργασίες καθεμία από τις οποίες πραγματοποιεί αυτή την ατομική λειτουργία, τότε απαιτούνται 500 μονάδες χρόνου.

5.3.1 Ιστόγραμμα μιας εικόνας

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

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

PROGRAM Histogram;
CONST n=20;	  (*Μέγεθος της εικόνας*)
      max=10; (*Μέγιστη ένταση του εικονοστοιχείου*)


VAR Image: Array [1..n,1..n] of integer;
    hist: Array [0..max] of integer;
    i,j,intensity: integer;

BEGIN
FOR i := 1 to n do (*Εισαγωγή του πίνακα της εικόνας*)
  BEGIN
  	For j := 1 to n do 
	Read((image[i,j]);
	Readln;
  END;
FOR i := 1 to max do (*Αρχικοποίηση του ιστογράμματος*)
  hist[i] := o;
FOR i := 1 to n do
FOR j := 1 to n do
  BEGIN
	intensity := image[i,j];
	hist[intensity] := hist[intensity]+1;
  END;
END.

ΣΧΗΜΑ 5.3 Ακολουθιακό πρόγραμμα για το ιστόγραμμα

Το πρόγραμμα του ιστογράμματος μπορεί να γίνει παράλληλο αλλάζοντας τον ακολουθιακό βρόχο For με μια δήλωση FORALL. Με τον τρόπο αυτό θα δημιουργηθεί μια παράλληλη διεργασία για κάθε γραμμή του πίνακα. Το νέο παράλληλο πρόγραμμα είναι αυτό που φαίνεται στο σχήμα 5.4. Πρέπει επίσης να σημειώσουμε ότι οι μεταβλητές intensity και j έχουν εισαχθεί σε κάθε διεργασία ως τοπικές μεταβλητές δήλωσης. Αυτό είναι απαραίτητο γιατί όλες οι διεργασίες αναφέρονται σε αυτές τις μεταβλητές.

PROGRAM ParallelHistogram;
CONST n=20;  (*Μέγεθος της εικόνας*)
      max=10;  (*Μέγιστη ένταση του εικονοστοιχείου*)


VAR  Image: Array [1..n,1..n] of integer;
     hist: Array [0..max] of integer;
     L: Array [0..max] of spinlock;
     i: integer;

BEGIN
... (*Αρχικοποίηση του πίνακα εικόνας*)


For I := 0 to max do 
  hist[i] := 0;
Forall i := 1 to n do
  VAR j, intensity : Integer;
   BEGIN
     For j := 1 to n do
	 BEGIN
		intensity := image[i,j];
		Lock(L[intensity]);
		hist[intensity] := hist[intensity]+1;
		Unlock(L[intensity]);
	 END;
   END;
END.

ΣΧΗΜΑ 5.4 Παράλληλο πρόγραμμα ιστογράμματος

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

BEGIN
  Intensity := image[i,j];
  Lock(L);
  hist[intensity] := hist[intensity]+1;
  Unlock(L);
END;

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

5.3.2 Επίδραση του ανταγωνισμού στην απόδοση

Στο πρόγραμμα του παράλληλου ιστογράμματος ο L δηλώνεται ως ένας πίνακας που έχει στοιχεία τύπου SPINLOCK και με τις ίδιες διαστάσεις που έχει και ο πίνακας hist. Μετά την εξέταση ενός εικονοστοιχείου από κάθε διεργασία, χρησιμοποιείται η ένταση για την επιλογή του κατάλληλου στοιχείου του hist που θα αλλαχθεί. Πριν την πραγματοποίηση της αλλαγής θα κλειδωθεί το συγκεκριμένο στοιχείο με την εντολή Lock(L[intensity]). Δύο διεργασίες μπορεί να βρουν την ίδια ένταση εικονοστοιχείου σε διαφορετικά τμήματα της εικόνας και να έτσι να προσπαθήσουν να αλλάξουν αυτό το στοιχείο του ιστογράμματος παράλληλα. Με τον τρόπο αυτό θα δημιουργηθεί ένας ανταγωνισμός και η μια διεργασία θα αναγκαστεί να περιμένει το πέρας της άλλης. Στο συγκεκριμένο πρόγραμμα δημιουργούνται n παράλληλες διεργασίες και υπάρχουν max διαφορετικά στοιχεία του πίνακα ιστογράμματος. Η πιθανότητα ανταγωνισμού που προκύπτει από το πρόγραμμα εξαρτάται από το λόγο n/max.

Κάθε διεργασία αποτελείται από έναν βρόχο FOR που προσπελαύνει ένα στοιχείο του πίνακα ιστογράμματος σε κάθε διάσχιση του βρόχου. Ένας σημαντικός παράγοντας που επηρεάζει τον ανταγωνισμό είναι το κλάσμα του χρόνου f που αντιστοιχεί στο χρόνο επανάληψης του βρόχου και κατά τη διάρκεια του οποίου μια διεργασία διενεργεί μια ατομική λειτουργία. Ο συντελεστής load, που καθορίζεται ως fn/max, δίνει το λόγο της ζήτησης για ατομικές λειτουργίες προς την παρεχόμενη προσφορά. Όσο μεγαλώνει ο συντελεστής load το πρόβλημα του ανταγωνισμού επιδεινώνεται. Χρησιμοποιώντας τον προσομοιωτή της Multi-Pascal το πρόγραμμα ιστογράμματος εκτελείται με 60 διεργασίες που δουλεύουν σε έναν πίνακα εικόνας διαστάσεων 60x60 που δημιουργείται από μια γεννήτρια τυχαίων αριθμών. Ο συντελεστής load ποικίλει ανάλογα με την αλλαγή της τιμής max. Το αποτέλεσμα φαίνεται στο σχήμα 5.5. Ο κάθετος άξονας είναι ο χρόνος εκτέλεσης του παράλληλου τμήματος του προγράμματος, αγνοώντας το χρόνο που απαιτείται για αρχικοποίηση και για τη δημιουργία της διεργασίας. Ο οριζόντιος άξονας είναι ο παράγοντας load. Ο αριθμός των διεργασιών και το μέγεθος του πίνακα εικόνας διατηρούνται σταθερά κατά μήκος του διαγράμματος. Έτσι, η αύξηση στο χρόνο εκτέλεσης είναι αποτέλεσμα μόνο του ανταγωνισμού για την πρόσβαση στον πίνακα hist.

Με το συντελεστή load ίσο με 1 η συνολική ζήτηση για πρόσβαση στον πίνακα ιστογράμματος από τις 60 διεργασίες είναι ακριβώς ίση με τη δυνατότητα ικανοποίησης αυτής της ζήτησης από την ατομική λειτουργία. Όμως, εξαιτίας της τυχαίας φύσης της πρόσβασης του επεξεργαστή στον πίνακα ιστογράμματος είναι πολύ πιθανό να συμβεί κάποιος ανταγωνισμός. Στο σχήμα 5.5 φαίνεται ότι ο ανταγωνισμός στο επίπεδο 1 του παράγοντα load έχει αυξήσει το χρόνο εκτέλεσης περίπου κατά 28%. Με τον συντελεστή load ίσο με 2 η ζήτηση είναι δυο φορές μεγαλύτερη από την προσφορά - έτσι ο ανταγωνισμός αναμέται ως ένα μεγάλο πρόβλημα. Στο σχήμα φαίνεται ότι ο χρόνος εκτέλεσης έχει ουσιαστικά διπλασιαστεί όταν ο παράγοντας load φτάνει το 2.

ΣΧΗΜΑ 5.5 Ανταγωνισμός στο πρόγραμμα ιστογράμματος

Επόμενο:5.4 Αριθμητική Ολοκλήρωση Πάνω: Κεφάλαιο 5ο : Μοίρασμα Δεδομένων Πίσω: 5.2 Κλειδώματα