4.3 Παραλληλισμός Διασωλήνωσης

Επόμενο: 4.4 Επίλυση Γραμμικών Εξισώσεων Πάνω: Κεφάλαιο 4o : Επικοινωνία διεργασιών Πίσω: 4.2 Μεταβλητές Καναλιών

4.3 Παραλληλισμός Διασωλήνωσης

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

ΣΧΗΜΑ 4.5 Διασωλήνωση Διεργασιών

Το Σχήμα 4.5 επεξηγεί τη γενική δομή της διασωλήνωσης διεργασιών. Κάθε διεργασία ενεργεί ταυτόχρονα και σαν παραγωγός αλλά και σαν καταναλωτής. Η διεργασία καταναλώνει από τα αριστερά της στο κανάλι και παράγει προς το δεξιό της στο κανάλι. Για να διευκολυνθεί ο προγραμματισμός των αλγόριθμων διασωλήνωσης, χρησιμοποιείται ένας πίνακας που αποτελείται από κανάλια. Η Multi-Pascal επιτρέπει την ομαδοποίηση πολλών καναλιών σε πίνακες όπως ακριβώς απλές μεταβλητές ομαδοποιούνται σε πίνακες. Για παράδειγμα, πολλά κανάλια ακέραιων αριθμών μπορούν να ομαδοποιηθούν ως εξής:

VAR chan: ARRAY [1..20] OF CHANNEL OF INTEGER;

Η αναφορά οποιουδήποτε στοιχείου του πίνακα καναλιών γίνεται ακριβώς όπως η αναφορά στα στοιχεία ενός οποιουδήποτε κοινού πίνακα. Το chan[1] είναι το πρώτο κανάλι του πίνακα ενώ το chan[2] είναι το δεύτερο κανάλι του πίνακα και ούτω καθεξής. Για παράδειγμα,η παρακάτω πρόταση θα γράψει την τιμή 10 στο κανάλι chan[1] :

chan[1]:=10; (* Γράφει μέσα στο κανάλι chan[1]  *)

Παρόμοια, η παρακάτω πρόταση θα διαβάσει μια τιμή από chan[1] και θα την τοποθετήσει στην ακέραια μεταβλητή x:

x:=chan[1];

Επίσης αυθαίρετες εκφράσεις επιτρέπονται κατά την αναφορά του πίνακα καναλιών όπως συμβαίνει και με τους απλούς πίνακες. Το επόμενο παράδειγμα διαβάζει μια τιμή από το κανάλι chan[5] και την τοποθετεί στη μεταβλητή x:

i:=5;


x:=chan[i]; (* Διαβάζει από chan[i]  *)

Η χρήση του πίνακα καναλιών είναι ιδιαίτερα χρήσιμη στον προγραμματισμό της διασωλήνωσης διεργασιών, όπως φαίνεται και στο Σχήμα 4.5. Οι διεργασίες είναι αριθμημένες σειριακά, ξεκινώντας από τα αριστερά προς τα δεξιά. Η διεργασία 1 διαβάζει από το κανάλι chan[1] που βρίσκεται από τα αριστερά της και γράφει στο chan[2] που βρίσκεται στα δεξιά της. Ομοίως, η διεργασία 2 διαβάζει από το chan[2] και γράφει στο chan[3]. Γενικά ισχύει, η διεργασία k διαβάζει από το κανάλι chan[k] και γράφει στο κανάλι chan[k+1]. Η παρακάτω διαδικασία μπορεί να χρησιμοποιηθεί ως τη βάση για κάθε διεργασία της διασωλήνωσης. Υπάρχει μόνο μία διεργασία που διαβάζει m τιμές από το αριστερό κανάλι και κατόπιν επεξεργασίας γράφει m τιμές στο δεξιό κανάλι:

PROCEDURE PipeProcess( mynumber : INTEGER );


VAR inval,outval,i:INTEGER;


BEGIN


    FOR i:=1 TO m DO


        BEGIN


            inval:=chan[mynumber]; (* Διαβάζει από το αριστερό κανάλι *)


           ...(* Χρήση της inval για να υπολογιστεί η outval *)


           chan[mynumber+1]:=outval; (* Γράφει στο δεξιό κανάλι *)


        END;


END;

Όταν κληθεί η παραπάνω διεργασία για τη δημιουργία των διεργασιών της διασωλήνωσης, θα δεχθεί τον αριθμό της διεργασίας μέσω της παραμέτρου εισόδου mynumber. Η mynumber θα δείξει στη διεργασία, ποια κανάλια πρέπει να χρησιμοποιήσει για είσοδο και έξοδο μέσα στη διασωλήνωση. Η είσοδος των δεδομένων γίνεται από το κανάλι chan[mynumber] ενώ η έξοδος των αποτελεσμάτων γίνεται από το κανάλι chan[mynumber+1].

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