2.2 Παράδειγμα: Παράλληλη Ταξινόμηση

Επόμενο:2.3 Φωλιασμένοι Βρόχοι Πάνω:Κεφάλαιο 2ο: Παραλληλισμός Δεδομένων Πίσω:2.1 Εντολή FORALL

2.2 Παράδειγμα: Παράλληλη Ταξινόμηση

Για να επεξηγηθεί η χρήση της εντολής FORALL στον παραλληλισμό των δεδομένων, θα χρησιμοποιηθεί ο αλγόριθμος Ταξινόμησης Σειράς και που είχε παρουσιασθεί και στο κεφάλαιο 1. Στην ταξινόμηση σειράς, κάθε στοιχείο ενός πίνακα συγκρίνεται με καθένα από τα υπόλοιπα στοιχεία για να βρεθεί ποιο στοιχείο από κάθε ζεύγος σύγκρισης είναι μεγαλύτερο. Για το στοιχείο e, το Rank(e) ορίζεται ως ο συνολικός αριθμός των στοιχείων του πίνακα που είναι μικρότερα από το e. Είναι φανερό ότι η τελική θέση του στοιχείου e στην ταξινομημένη έκδοση του δοθέντος πίνακα είναι Rank(e). Η ταξινόμηση σειράς μπορεί να επιτευχθεί με δύο φωλιασμένους βρόχους: ο εξωτερικός βρόχος σε κάθε επανάληψη κρατά το εκάστοτε προς εξέταση στοιχείο e και ο εσωτερικός βρόχος παίρνει όλες τις υπόλοιπες τιμές του πίνακα, εξετάζοντας τες μία προς μία με το στοιχείο e και κρατάει ένα αθροιστή για τη σειρά του e:

RANK SORT;
  FOR    κάθε στοιχείο e του πίνακα
  BEGIN
		rank := 0;
  		FOR   κάθε στοιχείο t του πίνακα
				IF e >= t THEN rank := rank+1;
				τοποθέτησε το e στη θέση του ταξινομημένου πίνακα;
  END;

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

FORALL i   :=   1 TO n DO
BEGIN
		e := values[i];
		rank := 0;
  		FOR   κάθε στοιχείο t της λίστας
				IF e >= t THEN rank := rank+1;(*τοποθέτησε το e στη θέση του ταξινομημένου πίνακα;*)
END;

Το σώμα αυτής της διατύπωσης της FORALL μπορεί να μετατραπεί σε μια διαδικασία με το όνομα ‘’PutinPlace’’. Το πρόγραμμα σε Multi-Pascal που προκύπτει, παρουσιάζεται στο σχεδιάγραμμα 2.3. Το πρόγραμμα ξεκινά από τις γραμμές 18-19 όπου διαβάζονται οι αρχικές τιμές που είναι προς ταξινόμηση. Έπειτα η διατύπωση της FORALL στη γραμμή 20 δημιουργεί μια παράλληλη διεργασία για κάθε στοιχείο του πίνακα values, καλώντας τη διαδικασία PutinPlace. Αυτό φαίνεται στο σχέδιο 2.4 .

1   PROGRAM RankSort;
2    CONST n = 100;
3    VAR   values,final : ARRAY [1..n] OF INTEGER;
4          i: INTEGER;
5    PROCEDURE PutinPlace(src : INTEGER);
6     VAR  testval,j,rank : INTEGER;
7      BEGIN
8        testval := values[src];
9        j := src;   (* το j θα κινηθεί σειριακά  σε όλο τον πίνακα *)
10       rank := 0;
11       REPEAT
12             j := j MOD n+1;
13               IF testval >= values[j] THEN rank := rank+1;
14       UNTIL  j=src;
15      final[rank]:=testval; (*βάλε την τιμή στην ταξινομημένη της θέση *)
16     END;
17     BEGIN	(* Κυρίως πρόγραμμα *)
18     FOR i := 1 TO n DO
19        READLN(values[i]); (*αρχικοποίηση των τιμών προς ταξινόμηση *)
20     FORALL i := 1 TO n DO
21      PutinPlace(i); (*Εύρεση της σειράς των values[i] και τοποθέτηση τους*)  
22	 END.

ΣΧHMA 2.3 Παράλληλη Ταξινόμηση Σειράς

Αφού οι πίνακες values και final δηλώνονται στο κυρίως πρόγραμμα, είναι και οι δύο προσβάσιμοι από την διαδικασία PutinPlace, σύμφωνα πάντα με τους κανόνες της κοινής Pascal. Οι πίνακες είναι αποθηκευμένοι στη διαμοιραζόμενη μνήμη και είναι προσβάσιμοι από όλους τους επεξεργαστές. Στη Multi-Pascal, όποια μεταβλητή δηλωθεί στην αρχή του κυρίως προγράμματος θεωρείται διαμοιραζόμενη μεταβλητή και μπορεί να χρησιμοποιηθεί απευθείας από οποιοδήποτε διεργασία. Η παρουσία εντολών δημιουργίας διεργασιών στη Multi-Pascal δεν μεταβάλλει τα όρια των κανόνων για την μετάφραση των ονομάτων των μεταβλητών που εμφανίζονται στο πρόγραμμα.

Σε καθένα από τους 100 φυσικούς επεξεργαστές ανατίθεται, μέσω του βρόχου FORALL, μια τιμή του πίνακα διεργασιών, κάτι που φαίνεται στο σχεδιάγραμμα 2.4. Το αποτέλεσμα είναι μια ξεχωριστή κλήση της διαδικασία PutinPlace από κάθε επεξεργαστή. Αν κοιτάξουμε μια ματιά στον κώδικα της διαδικασίας Putinplace θα παρατηρήσουμε ότι υπάρχουν 3 τοπικές μεταβλητές: η testval, η j και η rank. Στην Pascal κάθε κλήση σε οποιαδήποτε διαδικασία θα δημιουργήσει ένα νέο αντίγραφο όλων των τοπικών μεταβλητών. Το ίδιο ακριβώς συμβαίνει και στην Multi-Pascal. Καθώς κάθε επεξεργαστής καλεί την διαδικασία PutinPlace, λαμβάνει το δικό του αντίγραφο τοπικών μεταβλητών. Για αυτό, οι 100 παράλληλες κλήσεις της διαδικασίας PutinPlace θα δημιουργήσουν 100 αντίγραφα των τοπικών μεταβλητών της διαδικασίας. Έτσι επιτρέπεται σε όλους τους επεξεργαστές να λειτουργήσουν παράλληλα χωρίς καμιά παρενόχληση. Παρακάτω στο κεφάλαιο θα συζητηθεί αναλυτικότερα το θέμα των διαμοιραζόμενων και των τοπικών μεταβλητών.

Η διαδικασία PutinPlace βρίσκει την σειρά του κάθε στοιχείου, ερευνώντας ολόκληρο τον πίνακα values. Μετά τον υπολογισμό της σειράς του στοιχείου, η διαδικασία τοποθετεί το στοιχείο στην τελική του θέση, μέσα στον ταξινομημένο πίνακα final. Η διαδικασία PutinPlace έχει ένα βρόχο στις γραμμές 11-14 που μετακινεί τον δείκτη j μέσα στον πίνακα και συγκρίνει κάθε στοιχείο με το στοιχείο σύγκρισης (testval) για να υπολογίσει την σειρά. Έπειτα η τιμή της μεταβλητής rank χρησιμοποιείται ως δείκτης για να τοποθετηθεί το testval στη σωστή θέση μέσα στον πίνακα final ( γραμμή 15 ).

shareMemoryIamge

ΣΧHMA 2.4 Εκτέλεση παράλληλου αλγόριθμου ταξινόμησης σειράς

Το πρόγραμμα ταξινόμησης σειράς που παρουσιάζεται στο σχεδιάγραμμα 2.3, παράγει 100 διεργασίες που μπορούν να εκτελεστούν σε διαφορετικούς επεξεργαστές παράλληλα, πετυχαίνοντας πολύ μεγάλη επιτάχυνση. Εάν όμως υπάρχουν λιγότεροι από 100 επεξεργαστές στο σύστημα διαμοιραζόμενης μνήμης τότε ο προγραμματιστής μπορεί να χρησιμοποιήσει την επιλογή GROUPING στη διατύπωση της εντολής FORALL στη γραμμή 20, ώστε να μειωθεί ο αριθμός των διεργασιών που θα δημιουργηθούν και να ταιριάξει ο αριθμός τους με τον αριθμό των επεξεργαστών. Για παράδειγμα, η παρακάτω διατύπωση της FORALL θα δημιουργήσει μόνο 25 διεργασίες-παιδιά:

FORALL i := 1 TO 100 GROUPING 4 DO
	PutinPlace(i);

Η ανάλυση του σειριακού προγράμματος ταξινόμησης σειράς δείχνει ότι ο χρόνος εκτέλεσης του είναι O(n²), γιατί έχει δύο φωλιασμένους βρόχους που ο καθένας εκτελείται n φορές. Για το χαρακτηρισμό της γενικής εκτέλεσης των προγραμμάτων, το κείμενο χρησιμοποιεί μερικές φορές αυτό την προκαθορισμένη σημειογραφία, που προτάθηκε από τον Knuth[1976]. Για τους αναγνώστες που δεν είναι εξοικειωμένοι με αυτή τη σημειογραφία, το O(n²) απλά σημαίνει ότι ο συνολικός χρόνος εκτέλεσης του προγράμματος είναι ανάλογος του n²θεωρώντας ότι το n είναι αρκετά μεγάλο. Ο τυπικός ορισμός έχει ως εξής:

Για οποιαδήποτε από τις δύο συναρτήσεις f και g με πεδίο ορισμού τους φυσικούς αριθμούς, το Ο(f(n)) δηλώνει το σύνολο των g(n), για το οποίο υπάρχουν θετικές τιμές των σταθερών τιμών c και n_o έτσι ώστε |g(n)|<cf για κάθε n>n_o.

Για παράδειγμα, 50n³ ισούται με Ο(n³) και 35 n² ισούται με Ο(n²). Επίσης 50 n³+60 n² ισούται με Ο(n³), και 30 n²+20 n ισούται με Ο (n²).

Aς θεωρήσουμε τώρα την εκτέλεση του προγράμματος της Παράλληλης Ταξινόμησης Σειράς. Χρησιμοποιώντας τουλάχιστον n επεξεργαστές σε σύστημα διαμοιραζόμενης μνήμης όπως φαίνεται στο σχήμα 2.4, όλες οι κλήσεις στην διαδικασία PutinPlace θα εκτελούνται παράλληλα σε διαφορετικούς επεξεργαστές. Η καρδιά αυτής της διαδικασίας είναι ένας απλός βρόχος που υλοποιείται με την εντολή repeat και επαναλαμβάνεται n φορές. Επομένως, ο συνολικός χρόνος εκτέλεσης για κάθε κλήση της PutinPlace είναι Ο(n). Εφόσον όλες αυτές οι κλήσεις εκτελούνται παράλληλα, ο συνολικός χρόνος εκτέλεσης ολόκληρου του παράλληλου προγράμματος είναι επίσης Ο(n). Αυτός είναι ανώτερος από τους ταχύτερους γνωστούς αλγόριθμους σειριακής ταξινόμησης, που όλοι τους είναι Ο(n log n). (Σημείωση: Θεωρούμε ότι όλοι οι λογάριθμοι έχουν βάση 2 εκτός εάν ορίζεται διαφορετικά).

Εάν ο αριθμός των φυσικών επεξεργαστών p είναι μικρότερος από τον αριθμό των στοιχείων του πίνακα n τότε η επιλογή GROUPING μπορεί να χρησιμοποιηθεί για να εκχωρήσει n/p στοιχεία σε κάθε επεξεργαστή. Σε αυτή την περίπτωση, ο συνολικός χρόνος εκτέλεσης είναι O(n²/p). Εάν ο αριθμός των διαθέσιμων επεξεργαστών είναι p=n, τότε αυτή η έκφραση καταλήγει στην Ο(n), η οποία υπολογίστηκε παραπάνω. Το πρόβλημα της παράλληλης ταξινόμησης μελετήθηκε πολύ κατά την διάρκεια των προηγούμενων 10 χρόνων, και πολλοί χρήσιμοι αλγόριθμοι αναπτύχθηκαν, οι οποίοι ελαχιστοποιούν το συνολικό ποσό των υπολογισμών και προσφέρουν δυνατότητα για μεγάλες επιταχύνσεις. Σαν παράδειγμα αναφέρουμε τον Bitonic Αλγόριθμο Συγχώνευσης, ο οποίος έχει χρόνο εκτέλεσης O(log²n). Aυτό παρουσιάζεται στο κεφάλαιο 4 μέσα στο πλαίσιο των τεχνικών για την επικοινωνία των διεργασιών. Η Ταξινόμηση Σειράς επιλέχθηκε εδώ σαν παράδειγμα κυρίως για την απλότητα και όχι για την αποδοτικότητα της.

Επόμενο:2.3 Φωλιασμένοι ΒρόχοιΠάνω:Κεφάλαιο 2ο: Παραλληλισμός Δεδομένων Πίσω:2.1 Εντολή FORALL