Επόμενο:3.6 Θερμά Σημεία Μνήμης (Memory Hot Spots) Πάνω: Κεφάλαιο 3ο :Αρχιτεκτονική συστημάτων διαμοιραζόμενης μνήμης. Πίσω:3.4 Δίκτυα διασύνδεσης Επεξεργαστή-Μνήμης
3.5 Η Επίδραση του Αλγορίθμου.
Θεωρείστε τους αλγορίθμους Παράλληλης Ταξινόμησης Σειράς και Πολλαπλασιασμού Μητρών του 2ου Κεφαλαίου, υπό το φως της συζήτησης για την αρχιτεκτονική των συστημάτων διαμοιραζόμενης μνήμης και του ανταγωνισμού πρόσβασης στη μνήμη. Και στους δύο αλγορίθμους, υπάρχουν μεγάλοι πίνακες διαμοιραζόμενων δεδομένων, που διαβάζονται απ’ όλες τις παράλληλες διεργασίες. Οι τοπικές κρυφές μνήμες θα βοηθήσουν να μειωθεί ο ανταγωνισμός που παρουσιάζεται κατά την προσπάθεια ανάγνωσης από τους διαμοιραζόμενους πίνακες. Σε αυτούς τους αλγόριθμους, γίνονται και μερικές εγγραφές στους διαμοιραζόμενους πίνακες, αλλά οι εγγραφές είναι σχετικά σπάνιες, και ποτέ δύο διαφορετικές διεργασίες δεν εγγράφουν στην ίδια θέση μνήμης, μειώνοντας έτσι την πιθανότητα να εμφανιστεί ανταγωνισμός κατά την εγγραφή.
3.5.1 Ταξινόμηση Σειράς.
Αναφερόμαστε πάλι στο σχήμα 2.4 της βασικής δομής του Παράλληλου προγράμματος Ταξινόμησης Σειράς. Οι δύο βασικές δομές δεδομένων είναι, ο πίνακας values που περιέχει την αρχική μη ταξινομημένη λίστα και ο πίνακας final όπου θα δημιουργηθεί η ταξινομημένη λίστα. Κάθε επεξεργαστής παίρνει μια μοναδική τιμή από τον πίνακα values και υπολογίζει την σειρά συγκρίνοντας αυτήν την τιμή με όλα τα άλλα στοιχεία του πίνακα values. Έτσι ο κάθε επεξεργαστής πρέπει να σαρώσει όλο τον πίνακα values, διαβάζοντας κάθε στοιχείο. Το πρόγραμμα παρουσιάζεται στο Σχήμα 2.3. Η Διαδικασία PutinPlace περιέχει ένα βρόχο Repeat με ένα δείκτη j, που κινείται σειριακά στον πίνακα values. Αυτό σημαίνει ότι κάθε επεξεργαστής διαβάζει όλα τα στοιχεία του πίνακα values σειριακά. Συνήθως ένας μονοδιάστατος πίνακας όπως ο values αποθηκεύεται στην φυσική μνήμη και σε διαδοχικές θέσεις μνήμης. Επομένως, ο κάθε επεξεργαστής θα διαβάζει σειριακά διαμέσου των διαδοχικών θέσεων μνήμης.
Αυτή είναι η ίδια περίπτωση με αυτή που είχαμε συζητήσει για τα πολλαπλά τμήματα μνήμης. Αν η αρχιτεκτονική του συστήματος διαμοιραζόμενης μνήμης έχει πολλαπλά τμήματα μνήμης με τις διευθύνσεις να κατανέμονται όπως φαίνεται στο Σχήμα 3.3, τότε η ανάγνωση του πίνακα values, απ’ όλους τους επεξεργαστές δεν θα προκαλέσει ανταγωνισμό πρόσβασης στη μνήμη. Αφού όλοι οι επεξεργαστές εκτελούν την ίδια Διαδικασία “PutinPlace” (δες Σχήμα 2.4), μπορούμε να υποθέσουμε ότι θα κινηθούν σειριακά στον πίνακα values με τον ίδιο περίπου ρυθμό. Επομένως, όλες οι απαραίτητες συνθήκες για την εξάλειψη του ανταγωνισμού κατά την λειτουργία ανάγνωσης του πίνακα ικανοποιούνται, σύμφωνα με αυτά που συζητήσαμε στο τμήμα 3.3.
Εκτός από τον πίνακα values, υπάρχει και ένας άλλος διαμοιραζόμενος πίνακας ο final. Όμως κάθε διεργασία αναφέρεται σε αυτό τον πίνακα μόνο μια φορά στο τέλος της Διαδικασίας Putinplace, και η κάθε διεργασία αναφέρεται σε διαφορετικό στοιχείο του πίνακα. Έτσι, αναφερόμενοι στον πίνακα final δεν αναμένεται καθόλου ανταγωνισμός πρόσβασης στη μνήμη. Εκτός από τους δύο διαμοιραζόμενους πίνακες, ο κάθε επεξεργαστής έχει φυσικά και μερικές από τις δικές του τοπικές, ιδιωτικές μεταβλητές, που είναι οι τοπικές μεταβλητές της Διαδικασίας PutinPlace. Ο κάθε επεξεργαστής αναφέρεται στις τοπικές μεταβλητές του σε κάθε επανάληψη του βρόχου. Από τη στιγμή που αυτές οι μεταβλητές δεν διαμοιράζονται σε άλλους επεξεργαστές θα καταλήξουν στην κρυφή μνήμη του επεξεργαστή που τις χρησιμοποιεί. Επομένως, δεν απαιτείται καθόλου πρόσβαση στην διαμοιραζόμενη μνήμη για την ανάγνωση αυτών των τοπικών μεταβλητών, με αυτό τον τρόπο μειώνεται η πιθανότητα ανταγωνισμού. Όμως, οι εγγραφές στις τοπικές μεταβλητές της κρυφής μνήμης αποτελούν ένα ξεχωριστό θέμα. Όπως συζητήσαμε προηγουμένως, η συνοχή της κρυφής μνήμης απαιτεί κάποιο είδος τακτικής απευθείας εγγραφής στην διαμοιραζόμενη μνήμη.
Με το σύστημα πολυτμηματικής μνήμης, ο κύριος παράγοντας που προσδιορίζει την εμφάνιση ανταγωνισμού, είναι ο μεγάλος αριθμός από παράλληλες αιτήσεις που απευθύνονται στο ίδιο τμήμα μνήμης. Από αυτή τη συνοπτική ανάλυση του προγράμματος Παράλληλης Ταξινόμησης Σειράς φαίνεται ότι μια τέτοια συμπεριφορά δεν είναι αναμενόμενη. Όμως, για ένα σύστημα βασισμένο σε διαύλους απαιτείται ένα διαφορετικό είδος ανάλυσης του προγράμματος. Στο βασισμένο σε διαύλους σύστημα που φαίνεται στο Σχήμα 3.2, ο ανταγωνισμός μνήμης εξαρτάται από την συχνότητα με την οποία οι επεξεργαστές αναφέρονται στην διαμοιραζόμενη μνήμη, και την ταχύτητα με την οποία ο δίαυλος είναι ικανός να χειρίζεται τις αιτήσεις χωρίς να καθυστερεί τους επεξεργαστές. Μπορούμε να αναμένουμε ότι το σύστημα έχει καλό σχεδιασμό, έτσι ώστε ο δίαυλος να έχει αρκετή χωρητικότητα, για να χειρίζεται κανονικά πρότυπα προσπέλασης μνήμης από τους επεξεργαστές.
Ένα από τα πιο σημαντικά ζητήματα στην εκτέλεση ενός προγράμματος σε σύστημα διαύλων, είναι η έκταση στην οποία οι κρυφές μνήμες θα είναι αποδοτικές στην μείωση της κυκλοφορίας στην διαμοιραζόμενη μνήμη. Οι κρυφές μνήμες είναι ιδιαίτερα αποδοτικές, εάν κάθε επεξεργαστής εξακολουθεί να διαβάζει από την ίδια θέση μνήμης πολλές φορές. Μετά το πρώτο διάβασμα, ένα αντίγραφο τοποθετείται στην τοπική κρυφή μνήμη, απ’ όπου μπορεί να προσπελαστεί με υψηλή ταχύτητα χωρίς να επιβαρύνεται η διαμοιραζόμενη μνήμη. Αν μια λειτουργία εγγραφής εκτελείται σε ένα τμήμα της κρυφής μνήμης, τότε απαιτείται μια άμεση απευθείας - εγγραφή στην διαμοιραζόμενη μνήμη με την χρήση του διαύλου. Αναφερόμενη στο πρόγραμμα Ταξινόμησης του Σχήματος 2.3, η κύρια δραστηριότητα κάθε παράλληλης διεργασίας είναι να εκτελέσει τον βρόχο ‘’Repeat’’ στις γραμμές 11-14 όπως φαίνεται παρακάτω.
11 REPEAT 12 j := j MOD n+1; 13 IF testval >=values[j] THEN rank := rank+1; 14 UNTILL j := src;
Σε κάθε επανάληψη του βρόχου, υπάρχουν εννέα αναφορές στις μεταβλητές του προγράμματος : τέσσερις αναφορές στο j, δύο αναφορές στο rank, μια στο testval, μια στο src και μια στο values. Επτά από τις εννιά αναφορές είναι λειτουργίες ανάγνωσης, και έξι από τις επτά διαβάζουν μεταβλητές που είναι ήδη αποθηκευμένες στην κρυφή μνήμη. Η λειτουργία ανάγνωσης του πίνακα values είναι η μόνη που χρειάζεται να πάει στην διαμοιραζόμενη μνήμη, επειδή αναφέρεται πάντα σε ένα στοιχείο του πίνακα, που δεν έχει προηγουμένος αναφερθεί από αυτόν τον επεξεργαστή. Οι δύο λειτουργίες εγγραφής των τοπικών μεταβλητών j και rank θα προκαλέσουν στην κρυφή μνήμη μια απευθείας - εγγραφή πίσω στην διαμοιραζόμενη μνήμη. Έτσι, από τις εννιά αναφορές μνήμης σε κάθε επανάληψη του βρόχου, οι έξι θα εξυπηρετηθούν από την κρυφή μνήμη. Κατά μέσο όρο αυτό σημαίνει ότι το ένα τρίτο από τις αναφορές μνήμης θα πρέπει να προσπελάσουν την διαμοιραζόμενη μνήμη.
Κατά πόσο, αυτή η Ταξινόμηση Σειράς παρουσιάζει ανταγωνισμό πρόσβασης στη μνήμη, εξαρτάται απλά από το αν το εύρος ζώνης του διαύλου είναι ικανό να χειριστεί την κυκλοφορία της διαμοιραζόμενης μνήμης. Η χρήση της διαμοιραζόμενης μνήμης στην Ταξινόμησης Σειράς δεν είναι ασυνήθιστα υψηλή, και επομένως αναμένεται ότι ένα καλά ισορροπημένο σύστημα βασισμένο σε διαύλους μπορεί να εκτελέσει το πρόγραμμα χωρίς σημαντικές υποβαθμίσεις εξαιτίας του ανταγωνισμού πρόσβασης στη μνήμη.
3.5.2 Πολλαπλασιασμός Μητρών.
Ο πολλαπλασιασμός μητρών είναι ένα από τα μετροπρογράμματα (benchmark programs) για τα παράλληλα συστήματα. Όπως μπορούμε να δούμε στο παράλληλο πρόγραμμα πολλαπλασιασμού μητρών του Κεφαλαίου 2, παρουσιάζεται μια ευκαιρία για ένα μεγάλο αριθμό από παράλληλες διεργασίες. Για λόγους εποπτικούς η βασική δομή του προγράμματος επαναλαμβάνεται:
Parallel Matrix Multiply C = A * B; FORALL i := 1 TO n DO FORALL j := 1 TO n DO υπολόγισε το C[i, j] σαν το εσωτερικό γινόμενο της γραμμής i της Α με την στήλη j της Β;
Η ανάγνωση των δύο μητρών από τις διεργασίες, σκόπιμα πραγματοποιείται διαμέσου των ανυσμάτων. Κάθε διεργασία διαβάζει μια γραμμή της μήτρας Α και μια στήλη της μήτρας Β. Όταν αυτό το πρόγραμμα εφαρμόζεται σε μήτρες με διαστάσεις nxn, θα υπάρχουν n2 παράλληλες διεργασίες. Κάθε γραμμή της Α θα διαβάζεται από n διεργασίες και κάθε στήλη της Β θα διαβάζεται από n διεργασίες. Αυτός ο τρόπος ανάγνωσης βοηθάει να μειωθεί η πιθανότητα ανταγωνισμού πρόσβασης στη μνήμη. Γενικά, τα περισσότερα παράλληλα συστήματα αποδίδουν πολύ καλά κατά την εκτέλεση του προγράμματος πολλαπλασιασμού μητρών.
Το διάβασμα των μητρών από κάθε επεξεργαστή ακολουθεί επίσης το “διαδοχικό - σειριακό” πρότυπο όπως είδαμε στην ταξινόμηση σειράς, το οποίο λειτουργεί ικανοποιητικά στα συστήματα διαμοιραζόμενης μνήμης με πολλαπλά τμήματα μνήμης. Αυτό σημαίνει ότι μια διεργασία μπορεί αρχικά να αντιμετωπίσει κάποια καθυστέρηση όταν αρχίζει να διαβάζει τις καταχωρήσεις της μήτρας, αλλά μετά την πρώτη καταχώρηση που διαβάζεται οι διεργασίες θα έχουν ήδη εγκαταστήσει το πρότυπο πρόσβασης χρονομετάθεσης που εμφανίζεται στο Σχήμα 3.5. Επομένως δεν θα υπάρξει επιπρόσθετος ανταγωνισμός. Από τη στιγμή που υπάρχουν n διεργασίες που διαβάζουν κάθε γραμμή του Α, μια διεργασία μπορεί να καθυστερήσει για n προσπελάσεις μνήμης από τις υπόλοιπες διεργασίες, ενώ διαβάζει το πρώτο στοιχείο από την γραμμή της Α που της έχει ανατεθεί. Όμως δεν θα υπάρξουν επιπρόσθετες καθυστερήσεις για το υπόλοιπο της γραμμής. Όταν η διεργασία διαβάζει την στήλη της από την μήτρα Β, άλλη μια καθυστέρηση διάρκειας n προσπελάσεων είναι πιθανή.
Αυτή η αρχική καθυστέρηση λόγω ανταγωνισμού παρουσιάστηκε σχηματικά στο Σχήμα 3.5: από τη στιγμή που υπάρχουν τέσσερις επεξεργαστές που ξεκινούν από την ίδια διεύθυνση μνήμης 0, απαιτούνται τέσσερις προσπελάσεις μνήμης πριν να εγκατασταθεί το πρότυπο χρονομετάθεσης. Γενικά, με n επεξεργαστές απαιτούνται n προσπελάσεις μνήμης για να εγκατασταθεί το πρότυπο πρόσβασης χρονομετάθεσης. Έτσι η μέγιστη καθυστέρηση λόγω ανταγωνισμού πρόσβασης στη μνήμη θα είναι n. Στο παράλληλο πρόγραμμα Πολλαπλασιασμού Μητρών, η κάθε διεργασία υπολογίζει ένα άνυσμα που παράγεται από την γραμμή της μήτρας Α με την στήλη της μήτρας Β. Το παραγόμενο αυτό άνυσμα απαιτεί n πολλαπλασιασμούς και n προσθέσεις. Μια μοναδική πρόσθεση ή πολλαπλασιασμός πραγματικών αριθμών απαιτεί γενικά το λιγότερο δέκα φορές περισσότερο χρόνο απ’ ότι μια μοναδική πρόσβαση στη μνήμη. Επομένως, οι καθυστερήσεις λόγω ανταγωνισμού για n προσπελάσεις είναι αποδεκτές από τις διεργασίες, χωρίς να δημιουργούν σημαντική υποβάθμιση στην απόδοση.
Επόμενο:3.6 Θερμά Σημεία Μνήμης (Memory Hot Spots) Πάνω: Κεφάλαιο 3ο : Αρχιτεκτονική συστημάτων διαμοιραζόμενης μνήμης. Πίσω:3.4 Δίκτυα διασύνδεσης Επεξεργαστή-Μνήμης