Επόμενο:7.1 Επικοινωνία μεταξύ Επεξεργαστών Πάνω: Περιεχόμενα Πίσω: Ασκήσεις
Κεφάλαιο 7o : Αρχιτεκτονική συστημάτων κατανεμημένης μνήμης
Οι παράλληλοι υπολογιστές συνήθως χωρίζονται σε δύο μεγάλες κατηγορίες: τα συστήματα πολυεπεξεργαστών και τα συστήματα κατανεμημένης μνήμης. Ένας πολυεπεξεργαστής χαρακτηρίζεται από μια διαμοιραζόμενη μνήμη - ένας ενιαίος χώρος διευθύνσεων μνήμης που χρησιμοποιείται από όλους τους επεξεργαστές. Σε ένα παράλληλο σύστημα κατανεμημένης μνήμης κάθε επεξεργαστής έχει τη δική του τοπική μνήμη και η αλληλεπίδραση μεταξύ των επεξεργαστών γίνεται με μηνύματα. Σε ένα πολυεπεξεργαστή όλα τα δεδομένα που χρησιμοποιούνται από το πρόγραμμα είναι αποθηκευμένα στη διαμοιραζόμενη μνήμη και είναι προσβάσιμα από όλους τους επεξεργαστές. Όμως, σε ένα παράλληλο σύστημα κατανεμημένης μνήμης τα δεδομένα πρέπει να κατανεμηθούν στις τοπικές μνήμες των επεξεργαστών. Ένας επεξεργαστής δεν μπορεί άμεσα να έχει πρόσβαση στην τοπική μνήμη άλλου επεξεργαστή, αλλά μπορεί να λάβει ή να στείλει μπλοκ δεδομένων από άλλους επεξεργαστές μέσω του δικτύου διασύνδεσης. Εφόσον η πρόσβαση στην τοπική μνήμη ενός επεξεργαστή θα είναι σημαντικά γρηγορότερη από την καθυστέρηση του δικτύου, η απόδοση ενός προγράμματος εξαρτάται κυρίως από την τοποθέτηση των δεδομένων στις διάφορες τοπικές μνήμες.
Για να προγραμματίσουμε αποδοτικά ένα παράλληλο σύστημα κατανεμημένης μνήμης πρέπει να έχουμε μια γενική γνώση της αρχιτεκτονικής του. Παίρνοντας απλά ένα πρόγραμμα συστήματος μοιραζόμενης μνήμης και εκτελώντας το σε ένα σύστημα κατανεμημένης μνήμης θα έχουμε ως αποτέλεσμα μια μάλλον φτωχή απόδοση. Οι προγραμματιστικές τεχνικές που χρησιμοποιούνται στα συστήματα μοιραζόμενης μνήμης μπορούν να προσαρμοστούν και στον προγραμματισμό συστημάτων κατανεμημένης μνήμης. Όμως, αυτό απαιτεί τη γνώση της γενικής οργάνωσης του υλικού του παράλληλου συστήματος που τώρα είναι διαφορετική. Το κεφάλαιο αυτό αναφέρεται σε τέτοια θέματα αρχιτεκτονικής συστημάτων κατανεμημένης μνήμης που επηρεάζουν την απόδοση του προγράμματος και γι’ αυτό το λόγο πρέπει να είναι γνωστά στον προγραμματιστή. Στη βάση αυτής της γνώσης το επόμενο κεφάλαιο αρχίζει την ανάλυση των τεχνικών προγραμματισμού σε ένα σύστημα κατανεμημένης μνήμης.
Σε ένα σύστημα κατανεμημένης μνήμης κάθε επεξεργαστής έχει το δικό του τοπικό τμήμα μνήμης για την αποθήκευση και την ανάκτηση δεδομένων κατά τη διάρκεια των υπολογισμών. Επιπλέον, κάθε επεξεργαστής έχει μια ή περισσότερες άμεσες συνδέσεις με άλλους επεξεργαστές, διαμέσου των οποίων μπορεί να γίνει μεταβίβαση δεδομένων. Αν δυο επεξεργαστές δεν έχουν άμεση σύνδεση μεταξύ τους, μπορούν επίσης να επικοινωνούν έχοντας τους ενδιάμεσους επεξεργαστές να προωθούν τα δεδομένα. Η μετάδοση δεδομένων μεταξύ των επεξεργαστών απαιτεί ένα σημαντικό χρονικό διάστημα και η προώθηση των δεδομένων μεταξύ απομακρυσμένων επεξεργαστών απαιτεί ακόμα περισσότερο χρόνο. Έτσι, αν η επικοινωνία μεταξύ επεξεργαστών κατά τη διάρκεια εκτέλεσης του προγράμματος είναι συχνή, η καθυστέρηση που προκύπτει μπορεί να αυξήσει σημαντικά το χρόνο εκτέλεσης του προγράμματος.
Το όλο πρότυπο της άμεσης σύνδεσης των επεξεργαστών συνήθως ονομάζεται τοπολογία παράλληλου συστήματος κατανεμημένης μνήμης. Για ένα συγκεκριμένο αλγόριθμο οι καθυστερήσεις στην εκτέλεση που προκύπτουν από την επικοινωνία εξαρτώνται από την καθορισμένη τοπολογία. Σε αυτό το κεφάλαιο αναφέρονται αρκετές από τις πιο σημαντικές τοπολογίες παράλληλων συστημάτων κατανεμημένης μνήμης που περιλαμβάνουν τις τοπολογίες της γραμμής, του δακτυλίου, του πλέγματος, του τόρου και του υπερκύβου. Οι σχέσεις μεταξύ των διάφορων τοπολογιών καθώς και η σχετική τους καταλληλότητα στις διαφορετικές κατηγορίες αλγορίθμων περιγράφονται στο παρόν κεφάλαιο. Δυο σημαντικές παράμετροι που χαρακτηρίζουν κάθε τοπολογία είναι η συνδεσιμότητα, που είναι ο αριθμός των άμεσων συνδέσεων ανά επεξεργαστή και η διάμετρος, δηλαδή ο μέγιστος αριθμός των ενδιάμεσων συνδέσεων που απαιτούνται για την επικοινωνία των πλέον απομακρυσμένων επεξεργαστών. Η σύνδεση είναι σημαντική γιατί επηρεάζει το κόστος του υλικού και η διάμετρος είναι επίσης σημαντική γιατί επηρεάζει την απόδοση του προγράμματος.
Το κεφάλαιο αποτελείται από τρεις ενότητες. Η πρώτη ενότητα αφορά την επικοινωνία επεξεργαστή -προς- επεξεργαστή και τις διάφορες πηγές καθυστέρησης της επικοινωνίας. Η επόμενη περιγράφει τις ιδιότητες των διαφόρων τοπολογιών των παράλληλων συστημάτων κατανεμημένης μνήμης. Η τελευταία ενότητα ασχολείται με τις σχέσεις μεταξύ των τοπολογιών των παράλληλων συστημάτων κατανεμημένης μνήμης και των προτύπων επικοινωνίας που χρησιμοποιούνται σε διαφορετικές μορφές αλγορίθμων.
Επόμενο:7.1 Επικοινωνία μεταξύ Επεξεργαστών Πάνω: Περιεχόμενα Πίσω: Ασκήσεις