Επόμενο:Αναφορές Πάνω: Κεφάλαιο 4o : Επικοινωνία διεργασιών Πίσω: 4.6 Διτονική ταξινόμηση με συγχώνευση

4.7 Περίληψη

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

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

Ένας γνωστός αλγόριθμος διασωλήνωσης δόθηκε για την επίλυση του τριγωνικού συστήματος γραμμικών εξισώσεων, που βασίζεται στον ακολουθιακό αλγόριθμο ανάδρομης υποκατάστασης. Σε αυτή τη μέθοδο διασωλήνωσης, η κάθε διεργασία υπολογίζει την τιμή ενός αγνώστου και στέλνεται στην διασωλήνωση για να διαβαστεί από τις υπόλοιπες διεργασίες. Καθώς κάθε διεργασία λαμβάνει τιμές άγνωστες από αριστερά, αυτές περνούν από δεξιά και επεξεργάζονται από ένα εσωτερικό μηχανισμό. Όσο περνάει ο χρόνος όλο και περισσότερες διεργασίες ενεργοποιούνται. Η επιτάχυνση του παράλληλου αλγόριθμου με τη μέθοδο της σειριακής ανάδρομης υποκατάστασης είναι Ο(n). Αυτή η μέθοδος της παράλληλης διασωλήνωσης για γραμμικές εξισώσεις χρησιμοποιείται συχνά στην πράξη.

Σε αυτό το κεφάλαιο περιγράφτηκε η πλήρης σύνταξη και σημασιολογία των μεταβλητών καναλιών. Τα κανάλια συνθέτονται από άλλους τύπους δεδομένων της Pascal, συμπεριλαμβάνοντας και τους δομημένους τύπους. Επιτρέπεται η χρήση πίνακα που αποτελείται από κανάλια καθώς και κανάλι που τα στοιχεία του είναι τύπου πίνακα. Τα κανάλια μπορούν ακόμα να αποτελούνται από δεδομένα τύπου εγγραφής. Ο Διτονικός αλγόριθμος ταξινόμησης με συγχώνευση παρουσιάστηκε για να περιγράψει την χρήση του διδιάστατου πίνακα από κανάλια για την επικοινωνία των διεργασιών. Οι μεταβλητές καναλιών χρησιμοποιούνται εκτενώς στα παραδείγματα που ακολουθούν αυτό το κεφάλαιο.

Επόμενο:Αναφορές Πάνω: Κεφάλαιο 4o : Επικοινωνία διεργασιών Πίσω: 4.6 Διτονική ταξινόμηση με συγχώνευση