1.5 Παράλληλος Προγραμματισμός

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

Ένα χρήσιμο εννοιολογικό εργαλείο, για την δημιουργία προγραμμάτων για παράλληλα συστήματα είναι η κατανόηση της έννοιας της διεργασίας, που είναι ουσιαστικά η σειρά (διαδοχή) των λειτουργιών που μπορούν να εκτελεστούν από έναν απλό επεξεργαστή. Η διεργασία μπορεί να χρησιμοποιηθεί σαν η βασική δομή για το χτίσιμο παράλληλων προγραμμάτων: κάθε επεξεργαστής εκτελεί μια συγκεκριμένη διεργασία σε οποιαδήποτε στιγμή. Άτυπα, η διεργασία μπορεί να νοηθεί σαν μια υπορουτίνα ή διαδικασία που εκτελείται από ένα συγκεκριμένο φυσικό επεξεργαστή. Η διαθεσιμότητα μεγάλου αριθμού φυσικών επεξεργαστών σημαίνει ότι ένας μεγάλος αριθμός διεργασιών λογισμικού μπορεί να εκτελείται παράλληλα από το υλικό του υπολογιστή. Υποθέτοντας, ότι η δραστηριότητα της κάθε διεργασίας συμβάλλει στην ολοκλήρωση ενός απλού υπολογισμού, τότε η εκτέλεση αυτού του υπολογισμού μπορεί να είναι πολύ πιο γρήγορη απ’ ότι σε ένα σύστημα ενός επεξεργαστή. Η έννοια της διεργασίας για να είναι χρήσιμη στη δημιουργία προγραμμάτων για παράλληλα συστήματα, πρέπει να προστεθεί σαν επιπλέον χαρακτηριστικό στις παράλληλες γλώσσες προγραμματισμού. Μετά ο προγραμματιστής μπορεί να σχεδιάσει και να κωδικοποιήσει τους παράλληλους αλγόριθμους που είναι ικανοί να εκμεταλλευτούν τη διαθεσιμότητα πολλών επεξεργαστών στο υλικό των παράλληλων συστημάτων κατανεμημένης και διαμοιραζόμενης μνήμης.

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

Κατά τη διάρκεια της δεκαετίας του 1970-80, είχε αναπτυχθεί ένας αριθμός γλωσσών προγραμματισμού που περιλάμβανε χαρακτηριστικά για τη δημιουργία και αλληλεπίδραση των παράλληλων διεργασιών, με εφαρμογή στην ανάπτυξη λογισμικού για λειτουργικά συστήματα. Σε αυτές περιλαμβάνονταν η Pascal [Brinch Hansen, 1975], Modula-2 [Wirth, 1977], Communication Sequential Processes [Hoare,1978], Distributed Procceses [Brinch Hansen, 1978], και η PLITS [Feldman, 1979] και η Occam [Inmos 1984]. Η έννοια της διεργασίας υπήρξε χρήσιμη και για τα ένθετα συστήματα πραγματικού χρόνου και έτσι περιλήφθηκε και στη γλώσσα ADA [U.S. Department of Defence, !981]. Η γλώσσα Argus [Liskov and Scheifler, 1982] χρησιμοποιεί παράλληλες διεργασίες για τη δημιουργία κατανεμημένων συστημάτων βάσεων δεδομένων για δίκτυα υπολογιστών.

Καθώς, τα παράλληλα συστήματα κατανεμημένης και διαμοιραζόμενης μνήμης έγιναν δημοφιλή στη δεκαετία του 1980, η έννοια της διεργασίας προστέθηκε σε έναν αριθμό εφαρμοσμένων γλωσσών προγραμματισμού ευρείας χρήσης όπως η Fortran, C, Pascal και Lisp. Για τα περισσότερα εμπορικά διαθέσιμα παράλληλα συστήματα, αυτό επιτεύχθηκε με το να επιτραπούν ειδικές κλήσεις συστήματος μέσα στη γλώσσα για την δημιουργία, επικοινωνία και συγχρονισμό των διεργασιών. Λόγω της απουσίας καθιερωμένων παράλληλων γλωσσών προγραμματισμού, ο κάθε κατασκευαστής συστήματος δημιουργούσε την δική του ποικιλία από τέτοιες κλήσεις λειτουργικού συστήματος. Δύο τέτοιες γλώσσες, που έχουν εφαρμογή σε πολλά εμπορικά συστήματα είναι η Linda [Ahuja, Carriero, and Gelernter, 1986] και Multilisp [Halstead,1985]. Παρότι, υπάρχει μεγάλη ποικιλία στην ακριβή σύνταξη και σημασιολογία των χαρακτηριστικών της παράλληλης γλώσσας στα σύγχρονα παράλληλα συστήματα κατανεμημένης και διαμοιραζόμενης μνήμης, όλα αυτά διαπερνούνται από μερικές απλές έννοιες, με κυριότερη αυτή της διεργασίας.

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

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

Για να γίνει πιο κατανοητός ο αλγόριθμος, δίδεται το παρακάτω παράδειγμα μιας μη ταξινομημένης λίστας και της σειράς κάθε στοιχείου εντός της λίστας:

(Μη ταξινομημένη)

------------------------------------------

LIST          RANK

------------------------------------------


15            4

10            3

39            7

 8            2

22            6

 4            0

19            5

 6            1


------------------------------------------

Προσέξτε ότι ο πίνακας Rank δίνει ακριβώς τη θέση των στοιχείων στην ταξινομημένη λίστα. Από την στιγμή που θα υπολογιστεί ο πίνακας που περιέχει τη σειρά των στοιχείων, ο αλγόριθμος μπορεί εύκολα να τοποθετήσει τα στοιχεία στις τελικές ταξινομημένες θέσεις, χρησιμοποιώντας την τιμή που περιέχει ο πίνακας RANK στη θέση i (RANK[i]) σαν δείκτης για την τοποθέτηση του στοιχείου που βρίσκεται στην i θέση του πίνακα LIST (LIST[i]).

O αλγόριθμος ταξινόμησης σειράς μπορεί εύκολα να λειτουργήσει παράλληλα γιατί η σειρά κάθε στοιχείου της λίστας μπορεί να υπολογιστεί ανεξάρτητα από διαφορετικούς επεξεργαστές. Ο επεξεργαστής 1 μπορεί να υπολογίσει την τιμή του στοιχείου της θέσης 1 του πίνακα RANK (RANK[1]) παίρνοντας την τιμή που υπάρχει στη θέση 1 του πίνακα LIST(LIST[1])και συγκρίνοντας την με οποιοδήποτε άλλο στοιχείο της λίστας. Όταν αυτός ο υπολογισμός γίνεται στον επεξεργαστή 1 ο επεξεργαστής 2 μπορεί ταυτόχρονα να υπολογίζει την τιμή της θέσης 2 του πίνακα RANK (RANK[2]) συγκρίνοντας την τιμή που βρίσκεται στη θέση 2 του πίνακα LIST(LIST[2]) με κάθε άλλο στοιχείο της λίστας. Αν υπάρχουν n στοιχεία στη LIST και n επεξεργαστές, τότε κάθε επεξεργαστής i μπορεί να αναλάβει τον υπολογισμό του RANK[i] χρησιμοποιώντας το στοιχείο LIST[i]. Αυτό επεξηγείται στο σχήμα 1.4 για ένα παράλληλο σύστημα διαμοιραζόμενης μνήμης. *****

Οι τρεις πίνακες LIST, RANK, και SORTED βρίσκονται στη διαμοιραζόμενη μνήμη, και έτσι είναι άμεσα προσπελάσιμοι απ’ όλους τους επεξεργαστές. Αρχικά, τα μη ταξινομημένα στοιχεία τοποθετούνται στον πίνακα LIST. Ο επεξεργαστής 1 διαβάζει το LIST[1] από τη διαμοιραζόμενη μνήμη και μετά συνεχίζει στον υπολογισμό του RANK[1] συγκρίνοντας το LIST[1] με όλα τα άλλα στοιχεία του πίνακα LIST. Όταν υπολογιστεί το RANK(1), ο επεξεργαστής 1 μπορεί να γράψει το LIST[1] άμεσα στην κατάλληλη τελική ταξινομημένη θέση του στον πίνακα SORTED. Από τη στιγμή που και οι n επεξεργαστές υπολογίζουν παράλληλα, και τα n στοιχεία της λίστας θα τοποθετηθούν στην τελική ταξινομημένη τους θέση.

Πολλές από τις σημαντικές ιδιότητες των παράλληλων προγραμμάτων επεξηγούνται από αυτό το παράδειγμα Ταξινόμησης Σειράς όπως φαίνεται στο σχήμα 1.4. Η υπολογιστική δραστηριότητα του κάθε επεξεργαστή καλείται διεργασία. Η διεργασία είναι κατά βάση διαφορετική από τον επεξεργαστή, ο επεξεργαστής είναι η φυσική συσκευή υλικού, που έχει την δυνατότητα προσπέλασης της μνήμης και υπολογισμού νέων τιμών δεδομένων, ενώ η διεργασία είναι πολύ πιο αφηρημένη: η διεργασία είναι μια υπολογιστική δραστηριότητα. Για να έχει ο φυσικός επεξεργαστής δικαίωμα να κάνει οτιδήποτε πρέπει να του έχουν ανατεθεί κάποιες διεργασίες - αυτό σημαίνει ότι ο επεξεργαστής πρέπει να έχει μερικές υπολογιστικές δραστηριότητες να εκτελέσει. Στο σχήμα 1.4 η διεργασία που εκτελείται από τον επεξεργαστή 1 είναι ‘’Να υπολογίσει το RANK(1)και να αντιγράψει το LIST(1) στο SORTED‘’. Η διεργασία που ο κάθε επεξεργαστής εκτελεί ορίζεται από το πρόγραμμα. Έτσι ο επεξεργαστής είναι συσκευή υλικού, ενώ η διεργασία μια γενική ιδέα λογισμικού. Προς το παρόν, η διεργασία μπορεί άτυπα να οριστεί σαν τον κώδικα του προγράμματος που εκτελείται από έναν επεξεργαστή (παρόλο που αργότερα θα γίνει ξεκάθαρο ότι αυτή η αντίληψη δεν είναι απόλυτα ορθή).

Η απόδοση των παράλληλων προγραμμάτων εκτιμάται κυρίως από δύο σημαντικούς παραμέτρους: τον Χρόνο Εκτέλεσης και την Επιτάχυνση. Ο Χρόνος Εκτέλεσης που καλείται και Παράλληλος Χρόνος Εκτέλεσης, είναι απλά ο χρόνος εκτέλεσης του παράλληλου προγράμματος στην αρχιτεκτονική του παράλληλου συστήματος που θέλουμε να προσομοιώσουμε. Ο Σειριακός Χρόνος Εκτέλεσης ορίζεται σαν ο χρόνος εκτέλεσης της σειριακής έκδοσης του ίδιου αλγορίθμου, που εκτελείται με έναν μόνο επεξεργαστή. Η Επιτάχυνση του παράλληλου προγράμματος είναι ο λόγος του Σειριακού Χρόνου Εκτέλεσης προς τον Παράλληλο Χρόνο Εκτέλεσης. Ένα άλλο σημαντικό μέτρο της απόδοσης του προγράμματος είναι η Απόδοση του Επεξεργαστή. Για κάθε επεξεργαστή, αυτό ορίζεται σαν το ποσοστό του χρόνου που ο επεξεργαστής πραγματικά λειτουργεί κατά τη διάρκεια εκτέλεσης του προγράμματος. Αν αναφερθούμε στο σύνολο του προγράμματος, η Απόδοση του Συστήματος για τον συγκεκριμένο αλγόριθμο ορίζεται σαν η μέση απόδοση όλων των επεξεργαστών.