Επόμενο:Αναφορές Πάνω:Κεφάλαιο 2ο: Παραλληλισμός Δεδομένων Πίσω:2.7 Ο νόμος του AMDAHL

2.8 Περίληψη

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

Ένας από τους κύριους σκοπούς αυτού του κεφαλαίου ήταν να παρουσιάσει την έννοια των παράλληλων διεργασιών στην Multi-Pascal, και να εξηγήσει την σύνταξη και σημασιολογία των εντολών δημιουργίας διεργασιών: FORALL και FORK. Η FORALL είναι η παράλληλη μορφή του βρόχου FOR, στην οποία οι επαναλήψεις του βρόχου εκτελούνται παράλληλα και όχι σειριακά. Ο τελεστής FORK μπορεί να μετατρέψει οποιαδήποτε γραμμή εντολών σε ανεξάρτητη παράλληλη διεργασία που τρέχει ταυτόχρονα με τον γονέα. Οι διεργασίες στην Multi-Pascal μπορούν να διαμοιράζονται δεδομένα με τη χρήση κοινών δηλώσεων μεταβλητών που εμφανίζονται στην αρχή του προγράμματος. Αυτές οι διαμοιραζόμενες μεταβλητές μπορούν να προσπελαστούν από πολλές διεργασίες παράλληλα. Οι διεργασίες μπορούν επίσης, καλώντας διαδικασίες ή συναρτήσεις με τοπικές δηλώσεις μεταβλητών, να αποκτήσουν τα δικά τους ιδιωτικά, τοπικά αντίγραφα μεταβλητών. Τα ομάδες εντολών με τοπικές δηλώσεις μπορούν επίσης να χρησιμοποιηθούν γι’ αυτό τον σκοπό. Έτσι, οι παράλληλες διεργασίες μπορεί να έχουν τόσο διαμοιραζόμενα όσο και τοπικά δεδομένα.

Χρησιμοποιώντας αυτές τις δύο πολύ σημαντικές δεσμευμένες λέξεις για την δημιουργία παράλληλων διεργασιών στη Multi-Pascal, παρουσιάστηκαν μερικοί απλοί παράλληλοι αλγόριθμοι, όπως ο αλγόριθμος Ταξινόμησης Σειράς και ο αλγόριθμος Πολλαπλασιασμού Μητρών, που και οι δύο επιτυγχάνουν υψηλό βαθμό παραλληλισμού και μεγάλη επιτάχυνση σε σχέση με τους σειριακούς αλγόριθμους. Και οι δύο αυτοί αλγόριθμοι προήλθαν από σειριακούς αλγόριθμους, με τον απλό παραλληλισμό των επαναληπτικών βρόχων με τις εντολές FORALL. Έγινε ξεκάθαρο, ότι αυτός ο παραλληλισμός πρέπει να γίνει προσεκτικά, έτσι ώστε να αποφευχθούν οι παρεμβολές ανάμεσα στις διεργασίες, που αφορούν την τροποποίηση των διαμοιραζόμενων μεταβλητών. Οι κλήσεις διαδικασιών και οι ομάδες εντολών με τοπικές δηλώσεις χρησιμοποιήθηκαν για να επιτρέψουν στις διεργασίες να έχουν τις δικές τους μη διαμοιραζόμενες μεταβλητές.

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

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

Επόμενο:Αναφορές Πάνω:Κεφάλαιο 2ο: Παραλληλισμός Δεδομένων Πίσω:2.7 Ο νόμος του AMDAHL