Επόμενο:2.8 Περίληψη Πάνω:Κεφάλαιο 2ο: Παραλληλισμός Δεδομένων Πίσω:2.6 Ο τελεστής FORK

2.7 Ο νόμος του AMDAHL.

2.7.1 Oι Επιδράσεις του Σειριακού Κώδικα στην Επιτάχυνση

Ένα στοιχείο που μπορεί να μειώσει αρκετά την επιτάχυνση που μπορεί να επιτευχθεί από ένα παράλληλο πρόγραμμα είναι τα τμήματα σειριακού κώδικα, ακόμα και αν αυτά είναι μικρά συγκριτικά με τα παράλληλα τμήματα. Το γεγονός αυτό εκφράζεται με ένα γνωστό τύπο που ονομάζεται νόμος του Amdahl. Υποθέστε ότι ένας υπολογισμός έχει συνολικά n τελεστές, που ο καθένας απαιτεί μια μονάδα χρόνου για να εκτελεστεί. Υποθέστε ακόμα ότι το κλάσμα f των τελεστών πρέπει να εκτελεστεί σειριακά(όπου το f είναι μεταξύ 0 και 1). Επομένως, fn τελεστές πρέπει να εκτελεστούν σειριακά, και το πολύ (1-f)n τελεστές παράλληλα. Αν αυτό το πρόγραμμα τρέξει σε παράλληλο σύστημα με p φυσικούς επεξεργαστές, ο συνολικός ελάχιστος χρόνος εκτέλεσης θα είναι fn+(1-f)n/p. Ο συνολικός χρόνος εκτέλεσης αυτού του προγράμματος σε σειριακό σύστημα είναι απλά n. Διαιρώντας τον σειριακό χρόνο με τον ελάχιστο παράλληλο χρόνο παίρνουμε την ελάχιστη επιτάχυνση που μπορεί να επιτευχθεί σε ένα παράλληλο σύστημα με p επεξεργαστές :

Μέγιστη Επιτάχυνση=

ΣΧΗΜΑ 2.6 Οι Επιδράσεις του Νόμου του Amdahl.

Αυτός είναι ο νόμος του Amdahl. Καθώς το p πλησιάζει το άπειρο, η τιμή αυτής της έκφρασης συγκλίνει στο 1/f. Αυτό σημαίνει ότι η αναλογία του σειριακού κώδικα σε οποιοδήποτε παράλληλο πρόγραμμα μπορεί να επιφέρει σοβαρούς περιορισμούς στην μέγιστη επιτάχυνση που μπορεί να επιτευχθεί. Αν, για παράδειγμα, μια φαινομενικά μικρό κλάσμα ας πούμε 5 τοις εκατό του κώδικα πρέπει να εκτελεστεί σειριακά, αυτό θα περιορίσει την μέγιστη επιτάχυνση σε 1/0.05=20, χωρίς να έχει σημασία πόσοι επεξεργαστές χρησιμοποιούνται. Στο Σχήμα 2.6 παρουσιάζεται το γράφημα της μέγιστης επιτάχυνσης καθώς ο αριθμός των επεξεργαστών αυξάνεται από 1 σε 100. Το γράφημα χρησιμοποιεί το νόμο του Amdahl, η αναλογία του σειριακού κώδικα είναι 5 τοις εκατό.

Σήμερα πολλά παράλληλα συστήματα αποτελούνται από 100 ή και περισσότερους επεξεργαστές, και η επόμενη γενιά παράλληλων συστημάτων μπορεί να περιέχει 1000 ή και περισσότερους επεξεργαστές. Σύμφωνα με τον νόμο του Amdahl για να χρησιμοποιήσουμε αυτά τα συστήματα αποδοτικά, η αναλογία του σειριακού κώδικα πρέπει να είναι πολύ μικρή στα παράλληλα προγράμματα. Έτσι, για να επιτευχθεί επιτάχυνση 100, ο σειριακός κώδικας πρέπει να είναι μικρότερος από 1 τοις εκατό συνολικά.

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

2.7.2 Υπερνικώντας την Σπατάλη Αρχικοποίησης.

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

Ένας παράγοντας που βοηθάει ιδιαίτερα να ξεπεραστεί το πρόβλήμα της αρχικοποίησης σε προγράμματα που εκτελούνται σε παράλληλα συστήματα είναι η υπολογιστική ένταση. Αυτό σημαίνει ότι το πλήθος των υπολογισμών σε ένα πρόγραμμα είναι συχνά ανάλογο της δύναμης του μεγέθους του προβλήματος δεδομένων-συνήθως της δύναμης του 2 αλλά μερικές φορές και ακόμα μεγαλύτερων δυνάμεων. Το πρόγραμμα Σειριακής Ταξινόμησης που παρουσιάστηκε σε αυτό το κεφάλαιο έχει υπολογισμούς ανάλογους με n², ενώ το πρόγραμμα Πολλαπλασιασμού Μητρών ανάλογους με n³. Από τη στιγμή που το τμήμα αρχικοποίησης του προγράμματος είναι πάντα ανάλογο με το μέγεθος των δεδομένων (n), το κλάσμα των συνολικών υπολογισμών που χρειάζονται για την αρχικοποίηση θα μειώνεται σημαντικά καθώς το n αυξάνει. Αυτό σημαίνει ότι ο νόμος του Amdahl μπορεί να ξεπεραστεί αν αυξήσουμε τη βάση δεδομένων.

Υποθέστε ότι το πλήθος των υπολογισμών που απαιτείται για την αρχικοποίηση είναι cn, και το πλήθος των υπολογισμών στο σώμα του κυρίως προγράμματος είναι dn². Υποθέστε ακόμα ότι ο κώδικας που ασχολείται με την αρχικοποίηση πρέπει να εκτελεστεί παράλληλα, αλλά το υπόλοιπο του προγράμματος παρουσιάζει υψηλό παραλληλισμό. Τότε το κλάσμα f του σειριακού κώδικα σύμφωνα με τον νόμο του Amdahl είναι:

Καθώς το μέγεθος της δομής δεδομένων n μεγαλώνει, το κλάσμα f μικραίνει. Επομένως καθώς το n πλησιάζει το άπειρο, η μέγιστη επιτάχυνση για το παράλληλο πρόγραμμα με p επεξεργαστές, σύμφωνα με το νόμο του Amdahl, πλησιάζει το p. Έτσι, τα προβλήματα απόδοσης που προκαλούνται από την αρχικοποίηση μπορούν να ελαχιστοποιηθούν με τη χρήση μεγάλων δομών δεδομένων. Αυτό παρουσιάζεται στο γράφημα το Σχήματος 2.7. Για συστήματα διαμοιραζόμενης μνήμης με p=100 φυσικούς επεξεργαστές, το γράφημα δείχνει τη μέγιστη επιτάχυνση σύμφωνα με το νόμο του Amdahl, καθώς το μέγεθος της βάσης δεδομένων n μεγαλώνει. Για μέγεθος δεδομένων n<200, όπως φαίνεται στο σχήμα, η σειριακή αρχικοποίηση περιορίζει την μέγιστη επιτάχυνση. Όμως, για μέγεθος δεδομένων n>500, οι απώλειες λόγω αρχικοποίησης είναι λιγότερο από 15 τοις εκατό. Από τη στιγμή που το σύστημα έχει μόνο 100 φυσικούς επεξεργαστές, είναι φυσικό η μέγιστη επιτάχυνση να περιορίζεται σε 100, ανεξάρτητα από το μέγεθος των δεδομένων. (Σημείωση: Το γράφημα στο σχήμα 2.7 υποθέτει c=d επομένως f=1/n).

ΣΧΗΜΑ 2.7 Αύξηση της μέγιστης επιτάχυνσης με το μέγεθος των δεδομένων

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

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

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

Επόμενο:2.8 Περίληψη Πάνω:Κεφάλαιο 2ο: Παραλληλισμός Δεδομένων Πίσω:2.6 Ο τελεστής FORK