Επόμενο:2.1 Εντολή FORALL Πάνω:Περιεχόμενα Πίσω:Ασκήσεις
ΚΕΦΑΛΑΙΟ 2ο: Παραλληλισμός Δεδομένων
Η πλέον ισχυρή και ευρέως διαδεδομένη τεχνική για την οργάνωση παράλληλων προγραμμάτων είναι ο παραλληλισμός δεδομένων, που σε γενικές γραμμές μπορεί να καθορισθεί ως την ταυτόχρονη εκτέλεση της ίδιας λειτουργίας σε κάθε συστατικό μιας δομής δεδομένων. Η μεγάλη εφαρμογή των παράλληλων υπολογισμών στα επιστημονικά προβλήματα βασίζεται στη χρήση μεγάλων πολυδιάστατων πινάκων και άλλων μεγάλων δομών δεδομένων. Ο κεντρικός πυρήνας των περισσοτέρων παραδοσιακών αλγορίθμων αποτελείται από σειρές φωλιασμένων βρόχων, που εκτελούν πολύπλοκους χειρισμούς πινάκων για να παράγουν κάποιο αριθμητικό αποτέλεσμα. Σήμερα ωστόσο, τα περισσότερα παράλληλα προγράμματα δημιουργούνται με την αναδιοργάνωση αυτών των σειριακών αλγόριθμων ώστε οι φωλιασμένοι βρόχοι να εκτελούνται παράλληλα. Συνήθως αυτό σημαίνει, ότι εξαιτίας της παράλληλης εφαρμογής της ίδιας λειτουργίας σε διαφορετικά τμήματα του πίνακα δεδομένων, υπάρχει ο παραλληλισμός και στην παραγωγή των αποτελεσμάτων του προγράμματος.
Ο παραλληλισμός δεδομένων με απλά λόγια σημαίνει ότι η δομή του παραλληλισμού ανταποκρίνεται στη δομή των δεδομένων. Σε ορισμένες περιπτώσεις, κάθε στοιχειώδης μονάδα δεδομένων υφίσταται παράλληλη επεξεργασία. Σε άλλες περιπτώσεις, η δομή των δεδομένων τμηματοποιείται σε ομάδες ανεξάρτητων μονάδων δεδομένων, όπου κάθε ομάδα υφίσταται παράλληλη επεξεργασία. Παραδείγματα που θα βρείτε παρακάτω, θα δείξουν ότι ο παραλληλισμός των δεδομένων όχι μόνο εφαρμόζεται σε επιστημονικούς αλγόριθμους με πολλές αριθμητικές πράξεις αλλά και σε μη αριθμητικά προβλήματα όπως είναι η ταξινόμηση, οι αλγόριθμοι γραφημάτων και η συνδυαστική αναζήτηση. Όλες αυτές οι περιοχές εφαρμογών χρησιμοποιούν δομές που περιέχουν μεγάλους αριθμούς παρόμοιων μονάδων δεδομένων. Στις περισσότερες περιπτώσεις, οι μονάδες δεδομένων αποθηκεύονται σε μεγάλους πίνακες αλλά μερικές φορές χρησιμοποιούνται και δομές με δείκτες όπως είναι οι συνδεδεμένες λίστες.
Οι παράλληλοι τύποι δεδομένων συνήθως κάνουν μεγάλη χρήση της εντολής FORALL, που είναι ένας παράλληλος τύπος του επαναληπτικού βρόχου, όπου όλες οι επαναλήψεις εκτελούνται παράλληλα. Είναι φυσικό το γεγονός ότι αυτό το είδος παραλληλισμού επικράτησε στα πρώτα στάδια της ανάπτυξης της παράλληλης επεξεργασίας. Οι προγραμματιστές έχουν ήδη εξοικειωθεί με τη χρήση φωλιασμένων βρόχων, στα προγράμματα τους. Είναι φυσικό να σκεφτείτε ως ένα πρώτο βήμα, τον παραλληλισμό των προς εκτέλεση βρόχων σε ένα σύστημα διαμοιραζόμενης μνήμης, όπου ο κάθε επεξεργαστής θα εκτελεί μια διαφορετική επαναληπτική διαδικασία. Ωστόσο, θα δούμε ότι οι επαναληπτικοί βρόχοι δεν είναι πάντοτε πρόθυμοι να λειτουργήσουν αμέσως παράλληλα. Συχνά, ορισμένες προσωρινές τιμές συσσωρεύονται και μεταφέρονται από την μία επανάληψη στην επόμενη, με αποτέλεσμα οι επαναλήψεις να εκτελούνται σειριακά. Σε αυτές τις περιπτώσεις, η σειριακή έκδοση του αλγόριθμου πρέπει να τροποποιηθεί σημαντικά προκειμένου να προκύψει η παράλληλη έκδοση, συχνά σε τέτοιο σημείο ώστε να πρόκειται ουσιαστικά για την δημιουργία ενός νέου αλγορίθμου.
Επίσης, με την παράλληλη εκτέλεση βρόχων προκύπτουν πολύπλοκα θέματα απόδοσης όπως ο χρόνος δημιουργίας των διεργασιών, ο ανταγωνισμός πρόσβασης στη μνήμη και οι καθυστερήσεις συγχρονισμού. Μέσα από μια σειρά από απλά παραδείγματα, το κεφάλαιο θα ξεκινήσει να ασχολείται με μερικά από τα οργανωτικά θέματα των προγραμμάτων που κάνουν χρήση του παραλληλισμού δεδομένων. Για παιδαγωγικούς λόγους, τα παραδείγματα του κεφαλαίου θα είναι απλοί αλγόριθμοι δίχως συγχρονισμό ανάμεσα στις παράλληλες διεργασίες. Το θέμα του συγχρονισμού των διεργασιών θα συζητηθεί αναλυτικότερα στο κεφάλαιο 4.
Το κεφάλαιο εξυπηρετεί ως μια εισαγωγή στη γλώσσα προγραμματισμού Multi-Pascal και την διαδικασία του παράλληλου προγραμματισμού. Είναι ενδιαφέρον, να προσέξει κανείς ότι μόλις παρουσιασθούν μερικές απλές εντολές στη Multi-Pascal, είναι δυνατόν να δημιουργήσει μια μεγάλη ποικιλία παράλληλων αλγόριθμων για εφαρμογές σε πολλά διαφορετικά γνωστικά πεδία. Από τη στιγμή που κατανοήσει κάποιος μερικές από τις πιο σημαντικές οργανωτικές τεχνικές για τα παράλληλα προγράμματα, η διαδικασία του παράλληλου προγραμματισμού είναι εξίσου απλή όσο και ο συμβατικός ακολουθιακός προγραμματισμός.
Επόμενο: 2.1 Εντολή FORALL Πάνω:Περιεχόμενα Πίσω:Ασκήσεις