Επόμενο:4.7 Περίληψη Πάνω: Κεφάλαιο 4o : Επικοινωνία διεργασιών Πίσω: 4.5 Κανάλια και δομημένοι τύποι
4.6 Διτονική ταξινόμηση με συγχώνευση
Ως ένα παράδειγμα της εφαρμογής πολυδιάστατων πινάκων καναλιών, παρουσιάζεται η διτονική ταξινόμηση με συγχώνευση που είναι ένας αποδοτικός παράλληλος αλγόριθμος ταξινόμησης με χρόνο εκτέλεσης της τάξεως του O(log2n). Ο αλγόριθμος απαιτεί μια προγραμματιστική τεχνική που ονομάζεται ¨επικοινωνίες πινάκων κατά φάσεις" (phased-array communications), στην οποία κάθε διεργασία περνάει από πολλές υπολογιστικές φάσεις, χρησιμοποιώντας διαφορετικό κανάλι σε κάθε φάση. Στα προγράμματα διασωλήνωσης που παρουσιάσθηκαν παραπάνω, κάθε διεργασία έχει δύο προκαθορισμένους σύντροφους επικοινωνίας, την αριστερή γειτονική διεργασία από την οποία παραλαμβάνει δεδομένα και τη δεξιά γειτονική διεργασία στην οποία στέλνει δεδομένα. Στη διτονική ταξινόμηση με συγχώνευση, κάθε διεργασία έχει μια ολόκληρη σειρά από διαφορετικούς σύντροφους επικοινωνίας, με την σειρά των συντρόφων να αποτελεί κρίσιμο παράγοντα για την ορθότητα του προγράμματος. Για να διατηρηθεί η σωστή σειρά, κάθε διεργασία χρειάζεται να έχει το δικό της πίνακα καναλιών, ένα χωριστά για κάθε σύντροφο επικοινωνίας.
Η διτονική ταξινόμηση με συγχώνευση βασίζεται σε μια οργανωτική αρχή που είναι πανομοιότυπη με την κλασσική ταξινόμηση με συγχώνευση που μπορεί να είναι γνωστή στον αναγνώστη. Κατά τη διάρκεια κάθε βήματος της ταξινόμησης με συγχώνευση, μικρές και ταξινομημένες υπολίστες συγχωνεύονται ανά δύο και σχηματίζονται νέες λίστες που το πλήθος τους έχει υποδιπλασιασθεί αλλά το μήκος (δηλαδή ο αριθμός στοιχείων) τους έχει διπλασιασθεί. Για μια λίστα μήκους n, η επανάληψη αυτού του βήματος συγχώνευσης κατά log n φορές επιστρέφει ταξινομημένη τη λίστα. Η διτονική ταξινόμηση με συγχώνευση είναι πανομοιότυπη, μόνο που αντί για πλήρως ταξινομημένες υπολίστες χρησιμοποιούνται μερικώς ταξινομημένες υπολίστες που ονομάζονται διτονικές λίστες. Μια μη ταξινομημένη λίστα πρέπει να έχει ένα ορισμένο αριθμό από τοπικά μέγιστα και ελάχιστα. Ένα τοπικό μέγιστο ορίζεται ως ένα στοιχείο της λίστας που οι τιμές των γειτονικών του στοιχείων είναι μικρότερες. Παρόμοια, ένα τοπικό ελάχιστο έχει γείτονες με μεγαλύτερη τιμή. Τα ακραία στοιχεία της λίστας δεν θεωρούνται ως τοπικά μέγιστα ή ελάχιστα αφού έχουν μόνο ένα γείτονα. Μια διτονική λίστα ορίζεται ως μια λίστα που δεν έχει πάνω από ένα τοπικό μέγιστο και ένα τοπικό ελάχιστο.
Ένας σημαντικός τύπος διτονικής λίστας έχει το πρώτο μισό της λίστας ταξινομημένο με αύξουσα σειρά και το δεύτερο μισό ταξινομημένο με φθίνουσα σειρά. Αυτός ο τύπος λίστας έχει ένα τοπικό μέγιστο που βρίσκεται στο κέντρο της λίστας και κανένα τοπικό ελάχιστο. Η καρδιά της διτονικής ταξινόμησης με συγχώνευση είναι μια λειτουργία της διτονικής λίστας που ονομάζεται δυαδική διάσπαση. Με την ανάθεση μιας διεργασίας σε κάθε στοιχείο της λίστας, η δυαδική διάσπαση μπορεί να εκτελεσθεί παράλληλα με μερικά μόνο υπολογιστικά βήματα από κάθε διεργασία ανεξάρτητα από το μέγεθος της λίστας. Για την διευκόλυνση του υπόλοιπου τμήματος της συζήτησης, υποθέτουμε ότι το μήκος n της λίστας είναι μια δύναμη του 2. Τα στοιχεία της λίστας και οι διεργασίες που τους έχουν ανατεθεί είναι αριθμημένα από 0...n-1. Η δυαδική διάσπαση ορίζεται ως εξής:
1. Σε κάθε διεργασία του πρώτου μισού της λίστας ανατίθεται ως σύντροφος μια διεργασία που βρίσκεται στην ίδια σχετική θέση του δεύτερου μισού της λίστας. Αυτό απλά σημαίνει ότι σε κάθε διεργασία i του πρώτου μισού της λίστας ανατίθεται η διεργασία i+n/2 που ανήκει στο δεύτερο μισό της λίστας.
Κάθε ζευγάρι διεργασιών-συντρόφων συγκρίνει τις τιμές της λίστας που τις έχει ανατεθεί. Αν το στοιχείο της διεργασίας από το πρώτο μισό της λίστας είναι μεγαλύτερο από το στοιχείο της διεργασίας του δεύτερου μισού της λίστας, τότε οι διεργασίες ανταλλάσσουν τα στοιχεία τους ενώ σε αντίθετη περίπτωση δεν συμβαίνει καμιά ενέργεια.
Είναι φανερό ότι η δυαδική διάσπαση τείνει να αναδιοργανώσει τα στοιχεία της λίστας με τέτοιο τρόπο ώστε τα μικρότερα στοιχεία να κινούνται προς την αρχή της λίστας και τα μεγαλύτερα προς το τέλος της λίστας. Όταν δυαδική διάσπαση εφαρμόζεται σε μια διτονική λίστα, το αποτέλεσμα είναι μια νέα λίστα με αξιοσημείωτες ιδιότητες που θα αναφερθούν αλλά δεν θα αποδειχθούν:
1. Κάθε στοιχείο του πρώτου μισού της λίστας είναι μικρότερο από κάθε στοιχείο του δεύτερου μισού της λίστας.
2. Καθένα από τα δύο μισά της λίστας είναι από μόνα τους μια διτονική λίστα με μήκος n/2.
Για παράδειγμα, υπάρχει παρακάτω μια διτονική λίστα που έχει ένα τοπικό μέγιστο στο κέντρο της λίστας:
10 20 30 40 50 60 70 80 75 65 55 45 35 25 15 5
Εφαρμόζοντας τη δυαδική διάσπαση στο πιο πάνω παράδειγμα, προκύπτει η παρακάτω λίστα:
10 20 30 40 35 25 15 5 75 65 55 45 50 60 70 80
Προσέξτε ότι η λίστα ικανοποιεί ιδιότητα 2 αφού το πρώτο μισό της λίστας είναι μια διτονική λίστα με τοπικό μέγιστο την τιμή 40 αλλά και το δεύτερο μισό της λίστας είναι μια διτονική λίστα με τοπικό ελάχιστο την τιμή 45. Επίσης και η ιδίοτητα 1 ικανοποιείται από τη νέα λίστα.
Τι θα συμβεί όμως αν η δυαδική διάσπαση εφαρμοσθεί επανελειμένα στα δύο μισά της λίστας; Η απάντηση είναι ότι μετά από log n επαναλήψεις, η λίστα θα έχει ταξινομηθεί πλήρως. Αυτό το γεγονός οδηγεί στην προοπτική ενός παράλληλου αλγόριθμου που να ταξινομεί οποιαδήποτε διτονική λίστα μέσα από επαναλαμβανόμενες εφαρμογές της δυαδικής διάσπασης σε υπολίστες που ολοένα και μικραίνουν. Το μόνο που απαιτείται για την υλοποίηση του αλγόριθμου είναι μια μέθοδος που θα χρησιμοποιείται από κάθε διεργασία ώστε να επιλέγει, σε κάθε στάδιο, τη διεργασία-σύντροφο της. Αυτό μπορεί να επιτευχθεί με τη χρησιμοποίηση της δυαδικής μορφής του αριθμού αναγνώρισης της κάθε διεργασίας. Εάν υπάρχουν n διεργασίες τότε ο αριθμός αναγνώρισης κάθε διεργασίας έχει d=log n bits. Εξετάζοντας τα bits από τα αριστερά προς τα δεξιά, η διεργασία-σύντροφος σε κάθε στάδιο καθορίζεται με την αντιστροφή του εξεταζόμενου bit. Υποθέτουμε ότι οι θέσεις των bits είναι αριθμημένες από 0 ... d-1, ξεκινώντας από τα δεξιά προς τα αριστερά. Η επόμενη διαδικασία πρέπει να εκτελείται από κάθε διεργασία:
( Αύξουσα ) Ταξινόμηση της διτονικής λίστας:
(* Ο αριθμός αναγνώρισης της διεργασίας είναι το myid *)
FOR j:=d-1 DOWNTO 0 DO (* Χρήση του j bit του myid *)
BEGIN (* Δυαδική διάσπαση *)
Καθορισμός της διεργασίας-συντρόφου αντιστρέφοντας το j bit του myid;
Αποστολή αντιγράφου του στοιχείου της διεργασίας προς τη διεργασία-σύντροφο
Παραλαβή αντίγραφου του στοιχείου της διεργασίας-συντρόφου
IF (το j bit του myid)=0 THEN
κράτησε το μικρότερο από τα δυο στοιχεία
ELSE κράτησε το μεγαλύτερο από τα δυο στοιχεία;
END;
Αυτός ο παράλληλος αλγόριθμος ταξινομεί σε αύξουσα σειρά, οποιαδήποτε διτονική λίστα. Μετατρέποντας το 0 σε 1 στην πρόταση IF, ο αλγόριθμος ταξινομεί σε φθίνουσα σειρά. Ο αλγόριθμος μπορεί να χρησιμοποιηθεί για την συγχώνευση οποιοδήποτε ζεύγους διτονικών λιστών σε μια νέα διτονική λίστα, εάν εφαρμοσθεί η αύξουσα ταξινόμηση στην πρώτη λίστα και η φθίνουσα ταξινόμηση στη δεύτερη λίστα. Ο συγκεκριμένος αλγόριθμος συγχώνευσης με χρόνο εκτέλεσης της τάξεως O(log n), απαιτεί μια διεργασία για κάθε στοιχείο των λιστών και αποτελεί τη βάση για τον αλγόριθμο διτονικής ταξινόμησης με συγχώνευση. Με την εφαρμογή του αλγόριθμου σε παρακείμενα ζευγάρια διτονικών λιστών, ο αριθμός των διτονικών υπολιστών που προκύπτουν είναι μειωμένος κατά το ήμισυ ενώ το μέγεθος τους έχει διπλασιασθεί.
Οποιαδήποτε λίστα που περιέχει μόνο 2 στοιχεία, αποτελεί μια διτονική λίστα. Φανταστείτε τώρα ότι έχουμε μια μη ταξινομημένη λίστα με n στοιχεία, όπου σε κάθε στοιχείο ανατίθεται και μια διεργασία. Η μη ταξινομημένη λίστα περιέχει n/2 διτονικές λίστες που κάθε μία έχει 2 στοιχεία. Εφαρμόζοντας την παράλληλη ταξινόμηση σε ζεύγη παρακείμενων λιστών, το αποτέλεσμα είναι n/4 διτονικές λίστες με την κάθε λίστα να έχει μήκος ίσο με 4. Έπειτα από log n επαναλήψεις της παράλληλης συγχώνευσης, η λίστα θα έχει ταξινομηθεί πλήρως. Για την υλοποίηση του αλγόριθμου ταξινόμησης χρησιμοποιείται μια απλή αλλά ενδιαφέρουσα μέθοδος που βασίζεται στην εξέταση και την σύγκριση των d=log n bits του αριθμού αναγνώρισης των διεργασιών. Για να ολοκληρωθεί ο αλγόριθμος διτονικής ταξινόμησης με συγχώνευση, χρησιμοποιείται ο παρακάτω αλγόριθμος ταξινόμησης διτονικών λιστών που εσωκλείεται μέσα σε έναν εξωτερικό βρόχο που ανιχνεύει τα bits του αριθμού αναγνώρισης των διεργασιών από τα δεξιά προς τα αριστερά:
Διτονική ταξινόμηση με συγχώνευση:
(* Ο κώδικας εκτελείται από κάθε διεργασία myid *)
FOR i:=1 TO d DO (* Χρήση του i bit του myid *)
(* Εκτέλεση της παράλληλης συγχώνευσης για παρακείμενες βιοτονικές υπολίστες *)
FOR j:=i-1 DOWNTO 0 DO
BEGIN
Καθορισμός της διεργασίας-συντρόφου αντιστρέφοντας το j bit του myid;
Αποστολή αντιγράφου του στοιχείου της διεργασίας προς τη διεργασία-σύντροφο
Παραλαβή αντίγραφου του στοιχείου της διεργασίας-συντρόφου
IF (το j bit του myid) = (το i bit του myid) THEN
κράτησε το μικρότερο από τα δυο στοιχεία
ELSE κράτησε το μεγαλύτερο από τα δυο στοιχεία;
END;
Ο αλγόριθμος πραγματοποιεί d(d+1)/2 επαναλήψεις της δυαδικής διάσπασης, που έχει σταθερό χρόνο εκτέλεσης. Επομένως, ο συνολικός χρόνος εκτέλεσης αυτού του αλγόριθμου διτονικής ταξινόμησης με συγχώνευση είναι της τάξεως του O(log2n) και είναι ανώτερος του χρόνου εκτέλεσης O(n) του αλγόριθμου ταξινόμησης σειράς που παρουσιάσθηκε στο κεφάλαιο 2. Η υλοποίηση στη Multi-Pascal αυτού του αλγόριθμου διτονικής ταξινόμησης με συγχώνευση, παρουσιάζει ενδιαφέρον γιατί απαιτεί κάθε διεργασία να έχει το δικό της πίνακα καναλιών για την επικοινωνία με όλες τις διεργασίες-συντρόφους που θα προκύψουν στα διάφορα στάδια του αλγόριθμου. Όπως θα δείτε, το θέμα αναλύεται στην προγραμματιστική εργασία 2.
Επόμενο:4.7 Περίληψη Πάνω: Κεφάλαιο 4o : Επικοινωνία διεργασιών Πίσω: 4.5 Κανάλια και δομημένοι τύποι