Επόμενο:1.8 Ο Σφαλματοθήρας και ο Ελεγκτής απόδοσης της Multi-Pascal Πάνω: Κεφάλαιο 1ο: Γιατί Παράλληλος Προγραμματισμός;  Πίσω:1.6 Η γλώσσα Multi-Pascal

1.7 Παράλληλοι Αλγόριθμοι

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

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

1Παραλληλισμός Δεδομένων (Data Parallelism).Ένας μεγάλος αριθμός δεδομένων υπόκεινται στην ίδια ή παρόμοια επεξεργασία παράλληλα. Αυτός ο τύπος παραλληλισμού είναι ιδιαίτερα χρήσιμος στους αριθμητικούς αλγορίθμους που ασχολούνται με μεγάλους πίνακες και ανύσματα.

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

2. Κατάτμηση Δεδομένων (Data Partitioning). Αυτός είναι ένας ιδιαίτερος τύπος παραλληλισμού δεδομένων στον οποίο ο χώρος αποθήκευσης των δεδομένων είναι φυσικά διαχωρισμένος σε παρακείμενες περιοχές, κάθε μία από τις οποίες υφίστανται επεξεργασία παράλληλα μέσω διαφορετικού επεξεργαστή. Μπορεί να υπάρξει σποραδική ανταλλαγή τιμών δεδομένων διαμέσου των ορίων της κάθε περιοχής. Αυτός ο τύπος αλγορίθμου είναι ιδιαίτερα κατάλληλος για παράλληλα συστήματα κατανεμημένης μνήμης γιατί η υπολογιστική δραστηριότητα του κάθε επεξεργαστή αφορά κυρίως την δική του περιοχή τοπικών δεδομένων και έτσι η επικοινωνία των αυτόνομων ενιαίων συστημάτων επεξεργαστών είναι σχετικά σπάνια.

Για παράδειγμα ένας επαναληπτικός αριθμητικός αλγόριθμος που χρησιμοποιεί ένα διδιάστατο πίνακα δεδομένων 80x80 θέσεων μπορεί να έχει εφαρμογή σε ένα παράλληλο σύστημα κατανεμημένης μνήμης, τμηματοποιώντας τα δεδομένα του πίνακα σε 64 μη επικαλυπτόμενες περιοχές, που η κάθε μία αποτελείται από ένα πίνακα αριθμών 10x10 θέσεων. Σε ένα παράλληλο σύστημα κατανεμημένης μνήμης με 64 επεξεργαστές, η κάθε μία από τις 64 περιοχές μπορεί να αποθηκευτεί στην τοπική μνήμη ενός από τους επεξεργαστές. Στη συνέχεια οι επεξεργαστές μπορούν να συγκεντρώσουν την υπολογιστική τους δραστηριότητα στην δική τους περιοχή τοπικών δεδομένων, ενώ σποραδικά ανταλλάσσουν πληροφορίες με άλλους επεξεργαστές με τον μηχανισμό περάσματος μηνυμάτων. Η χρήση της κατάτμησης δεδομένων στα παράλληλα συστήματα κατανεμημένης μνήμης παρουσιάζεται στο κεφάλαιο 9.

3.Ασύγχρονος Αλγόριθμος (Asychronous Algorithm).Κάθε παράλληλη διεργασία λειτουργεί αυτόνομα, χωρίς καθόλου συγχρονισμό ή επικοινωνία με τις άλλες διεργασίες. Οι ασύγχρονοι αλγόριθμοι αποδίδουν τόσο στα συστήματα διαμοιραζόμενης μνήμης όσο και στα συστήματα κατανεμημένης μνήμης και μπορεί να έχουν σαν αποτέλεσμα πολύ μεγάλες επιταχύνσεις. Η παράλληλη ταξινόμηση σειράς του σχήματος 1.4 είναι ένα παράδειγμα ασύγχρονου αλγόριθμου. Παρατηρούμε ότι παρότι που οι επεξεργαστές προσπελαύνουν μερικά κοινά δεδομένα, ο κάθε επεξεργαστής μπορεί να υπολογίσει με ένα απόλυτα αυτόνομο τρόπο, χωρίς καμιά βοήθεια, τις ενδιάμεσες τιμές δεδομένων που παράγονται από άλλους επεξεργαστές. Αυτή η απόλυτη αυτονομία του κάθε επεξεργαστή είναι ένα από τα γνωρίσματα-κλειδιά των ασύγχρονων αλγορίθμων που καθιστά εύκολο τον προγραμματισμό τους. Το κεφάλαιο 2 ασχολείται με τον προγραμματισμό ασύγχρονων παράλληλων αλγορίθμων.

4.Σύγχρονη Επανάληψη (Synchonous Iteration). Ο κάθε επεξεργαστής εκτελεί την ίδια επαναληπτική λειτουργία σε διαφορετικό τμήμα δεδομένων. Όμως, οι επεξεργαστές πρέπει να συγχρονίζονται στο τέλος κάθε επανάληψης. Αυτό εξασφαλίζει ότι δεν επιτρέπεται σε κανένα επεξεργαστή να αρχίσει την επόμενη επανάληψη, προτού ολοκληρώσουν και οι υπόλοιποι την τρέχουσα επανάληψη. Ο συγχρονισμός της κάθε επανάληψης είναι απαραίτητος επειδή τα δεδομένα που παράγονται από ένα συγκεκριμένο επεξεργαστή κατά τη διάρκεια της επανάληψης i χρησιμοποιούνται από πολλούς επεξεργαστές κατά την επανάληψη i+1. Έτσι, είναι απαραίτητο όλοι οι επεξεργαστές να ολοκληρώσουν την επανάληψη i, πριν κάποιους από αυτούς ξεκινήσει την επανάληψη i+1.

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

5.Πολλαπλοί Εργαζόμενοι (Multiple Workers). Εδώ διατηρείται μια κεντρική δεξαμενή παρόμοιων υπολογιστικών εργασιών. Υπάρχει ένας μεγάλος αριθμός από διεργασίες-εργαζόμενοι που ανακτούν εργασίες από την παραπάνω δεξαμενή, εκτελούν τους απαιτούμενους υπολογισμούς και πιθανώς προσθέτουν νέες εργασίες στην δεξαμενή. Όλη η υπολογιστική λειτουργία τερματίζει όταν η κεντρική δεξαμενή αδειάσει εντελώς. Αυτή η τεχνική των πολλαπλών εργαζομένων είναι χρήσιμη με προβλήματα εκθετικής πολυπλοκότητας, όπως είναι η αναζήτηση σε δένδρο ή σε γράφημα. Σε τέτοια προβλήματα, ένας μεγάλος αριθμός από μικρές υπολογιστικές εργασίες παράγεται δυναμικά ως αποτέλεσμα της συνολικής υπολογιστικής διαδικασίας. Από την στιγμή που δεν γνωρίζουμε εκ των προτέρων πότε ή πόσες τέτοιες εργασίες θα παραχθούν, είναι βολικό να οργανώσουμε το παράλληλο πρόγραμμα με μια δεξαμενή εργασίας (work-pool). Έτσι, όποτε μια καινούρια εργασία παράγεται, απλά προστίθεται στη δεξαμενή εργασίας, απ΄ όπου μπορεί αργότερα να ανακτηθεί από οποιαδήποτε από τις πανομοιότυπες διεργασίες-εργάτες. Αυτή η σημαντική τεχνική παράλληλου προγραμματισμού αναπτύσσεται στο κεφάλαιο 10 για τα παράλληλα συστήματα διαμοιραζόμενης μνήμης και στο κεφάλαιο 11 για τα παράλληλα συστήματα κατανεμημένης μνήμης.

6. Υπολογιστική Διαδικασία Διασωλήνωσης (Pipeline Computation). Οι διεργασίες οργανώνονται σε μερικές κανονικές δομές όπως είναι αυτή του δακτυλίου ή του διδιάστατου πλέγματος. Διαμέσου αυτής της κανονικής δομής τα δεδομένα, μετακινούνται μέσα στη δομή, με κάθε διεργασία να εκτελεί ένα συγκεκριμένο τμήμα της συνολικής υπολογιστικής διαδικασίας. Αυτοί οι αλγόριθμοι έχουν καλή εφαρμογή στα παράλληλα συστήματα κατανεμημένης μνήμης, λόγω του μεθοδικού τρόπου ροής των δεδομένων και της μη αναγκαιότητας για γενική προσπέλαση των διαμοιραζόμενων δεδομένων. Η υπολογιστική διαδικασία διασωλήνωσης παρουσιάζεται στο κεφάλαιο 4 για τα παράλληλα συστήματα διαμοιραζόμενης μνήμης και στο κεφάλαιο 8 για τα παράλληλα συστήματα κατανεμημένης μνήμης.

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

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

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

1 Ο ανταγωνισμός μνήμης (Memory Contention). . Η εκτέλεση του σε ένα επεξεργαστή καθυστερεί όταν αυτός περιμένει για να αποκτήσει πρόσβαση σ΄ ένα μια θέση μνήμης που χρησιμοποιείται εκείνη τη χρονική στιγμή από κάποιον άλλο επεξεργαστή. Το πρόβλημα μπορεί να παρουσιαστεί όταν δεδομένα διαμοιράζονται σε ένα μεγάλο αριθμό παράλληλων επεξεργαστών. Ο ανταγωνισμός της μνήμης τυπικά είναι ένα πρόβλημα που παρουσιάζεται μόνο όταν υπάρχει διαμοιραζόμενη μνήμη.

2. Εκτεταμένος Σειριακός Κώδικας (Extensive Sequencial Code). Σε οποιοδήποτε παράλληλο αλγόριθμο, θα υπάρχουν πάντα τμήματα που να περιέχουν καθαρά σειριακό κώδικα στα οποία εκτελούνται συγκεκριμένα είδη κεντρικών λειτουργιών όπως είναι η αρχικοποίηση των μεταβλητών. Το αποτέλεσμα του σειριακού κώδικα είναι να στερεί από μερικούς αλγόριθμους αρκετό ποσοστό από τη μέγιστη συνολική επιτάχυνση που μπορούν να πετύχουν.

3. Χρόνος δημιουργίας των διεργασιών (Process Creation Time)..Σε οποιοδήποτε πραγματικό σύστημα, η δημιουργία των παράλληλων διεργασιών απαιτεί ένα συγκεκριμένο τμήμα του συνολικού χρόνου εκτέλεσης. Αν οι διεργασίες είναι σχετικά μικρής διάρκειας είναι δυνατόν σε μερικούς αλγόριθμους, ο χρόνος δημιουργίας τους να ξεπεράσει το χρόνο που εξοικονομείται από τον παραλληλισμό. Συχνά αυτός ο παράγοντας αγνοείται στα εγχειρίδια και τα βιβλία για παράλληλους αλγόριθμους.

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

5. Καθυστέρηση Συγχρονισμού (Sychronization Delay). Όταν οι παράλληλες διεργασίες συγχρονίζονται, αυτό σημαίνει ότι μια διεργασία μπορεί να αναγκαστεί να περιμένει μια άλλη. Σε μερικά παράλληλα προγράμματα, οι επακόλουθες καθυστερήσεις μπορεί να προκαλέσουν ‘λειτουργική συμφόρηση’ και μείωση στη συνολική επιτάχυνση.

6. Ανισορροπία Φορτίου (Load Imballance). Σε ορισμένα παράλληλα προγράμματα, οι υπολογιστικές εργασίες παράγονται δυναμικά και με απρόβλεπτο τρόπο και πρέπει να μεταβιβάζονται στους επεξεργαστές αμέσως μόλις παράγονται. Έτσι όμως είναι δυνατόν, ορισμένοι επεξεργαστές να παραμένουν αδρανείς ενώ άλλοι να έχουν περισσότερες υπολογιστικές εργασίες από αυτές που μπορούν να χειριστούν. Η ανισορροπία φορτίου είναι ιδιαίτερα κοινή στα προγράμματα ‘πολλαπλών εργαζομένων’ που όπως αναφέραμε, αναλύονται στα κεφάλαια 10 και 11.

Επόμενο:1.8 Ο Σφαλματοθήρας και ο Ελεγκτής απόδοσης της Multi-Pascal Πάνω:Κεφάλαιο 1ο: Γιατί Παράλληλος Προγραμματισμός;  Πίσω:1.6 Η γλώσσα Multi-Pascal