Επόμενο:4.1 Κανάλια Επικοινωνίας Διεργασιών Πάνω: Περιεχόμενα Πίσω: Ασκήσεις
Κεφάλαιο 4o : Επικοινωνία διεργασιών
Οι παράλληλοι αλγόριθμοι που έχουν παρουσιασθεί μέχρι τώρα στο κείμενο ήταν ασύγχρονοι: κάθε παράλληλη διεργασία λειτουργούσε ανεξάρτητα χωρίς να απαιτείται αλληλεπίδραση με τις υπόλοιπες διεργασίες. Σε ορισμένες μόνο περιπτώσεις, οι διεργασίες μοιράζονταν τμήματα των δεδομένων αλλά και σε αυτές τις περιπτώσεις τα δεδομένα χρησιμοποιούνταν μόνο για ανάγνωση και όχι για εγγραφή. Σε ένα ασύγχρονο παράλληλο αλγόριθμο, καμιά διεργασία δεν γράφει μια τιμή που προορίζεται για χρήση από μια άλλη παράλληλη διεργασία. Αυτοί οι τύποι αλγόριθμων μελετήθηκαν στην αρχή γιατί είναι απλοί και παράγουν πολύ καλές επιταχύνσεις σε μια μεγάλη ποικιλία από παράλληλες αρχιτεκτονικές.
Σε αυτό το κεφάλαιο θα ξεκινήσουμε την ανάλυση των θεμάτων που αφορούν την επικοινωνία και την αλληλεπίδραση των διεργασιών. Θα περιγράψουμε ένα ειδικό χαρακτηριστικό της γλώσσας προγραμματισμού Multi-Pascal που ονομάζεται μεταβλητή καναλιού και χρησιμοποιείται για την επικοινωνία και τον συγχρονισμό των διεργασιών. Η μεταβλητή καναλιού, όπως υπονοεί το όνομα της, συλλέγει δεδομένα από τις διεργασίες που γράφουν και τις διοχετεύει σε διεργασίες που διαβάζουν δεδομένα. Οι μεταβλητές καναλιών επιτρέπουν στις παράλληλες διεργασίες να ανταλλάσσουν και να μοιράζονται δεδομένα με ένα ελεγχόμενο τρόπο που εμποδίζει την πιθανότητα σφαλμάτων χρονικής εξάρτησης. Το κεφάλαιο περιγράφει την σημασιολογία και το πλήρες συντακτικό των μεταβλητών καναλιών στη Multi-Pascal.
Η ύπαρξη καναλιών για την αλληλεπίδραση διεργασιών θα επιτρέψει την παρουσίαση, σε αυτό το κεφάλαιο και στα επόμενα, νέων και πολύ σημαντικών κλάσεων παράλληλων αλγόριθμων. Το κεφάλαιο αυτό εισάγει την έννοια των αλγόριθμων διασωλήνωσης, μέσα στους οποίους μια σειρά από παράλληλες διεργασίες, συνδεδεμένες με κανάλια, σχηματίζουν μια διασωλήνωση μεγάλου μήκους που επιτρέπει τη ροή και τον μετασχηματισμό των δεδομένων. Κάθε διεργασία αντιπροσωπεύει ένα στάδιο στην επεξεργασία των δεδομένων. Τα αρχικά δεδομένα εισάγονται μέσα στη διασωλήνωση από το ένα άκρο της και κατόπιν επεξεργασίας, τα τελικά αποτελέσματα εξέρχονται από το άλλο άκρο. Εάν η διασωλήνωση είναι γεμάτη με δεδομένα τότε κάθε διεργασία μπορεί να συνεχίσει να λειτουργεί παράλληλα, δεχόμενη νέα δεδομένα από τη μια γειτονική της διεργασία και στέλνοντας δεδομένα στην άλλη γειτονική διεργασία της.
Ένα σημαντικό παράδειγμα αλγόριθμου διασωλήνωσης είναι το παρακάτω: μια πρακτική μέθοδος για την επίλυση ενός τριγωνικού συστήματος γραμμικών εξισώσεων είναι η προς τα πίσω αντικατάσταση (back substitution). Σε αυτόν τον αλγόριθμο, κάθε εξίσωση ανατίθεται σε μια διεργασία της διασωλήνωσης και οι εκτιμημένες τιμές των αγνώστων, ρέουν μέσα στη διασωλήνωση από τη μια διεργασία στην επόμενη. Η προαναφερθείσα μέθοδος διασωλήνωσης πετυχαίνει επιτάχυνση O(n) σε σχέση με τη σειριακή μορφή της προς τα πίσω αντικατάστασης. Προκειμένου να επεξηγηθούν πιο πολύπλοκα πρότυπα επικοινωνίας μεταξύ των διεργασιών, παρακάτω περιγράφεται εν συντομία ο διτονικός (bitonic) αλγόριθμος ταξινόμησης με συγχώνευση. Αυτός ο αποδοτικός παράλληλος αλγόριθμος ταξινόμησης έχει χρόνο εκτέλεσης της τάξεως O(log2n) και αποτελεί τη βάση για πολλούς αλγόριθμους ταξινόμησης που χρησιμοποιούνται σε παράλληλα συστήματα.
Επόμενο:4.1 Κανάλια Επικοινωνίας Διεργασιών Πάνω: Περιεχόμενα Πίσω: Ασκήσεις