Θεωρητικά θέματα των Παράλληλων Μηχανών

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

- Κάθε μονάδα επεξεργασίας (Μ.Ε.) λειτουργεί κάτω από τοπικό (και όχι ολικό) έλεγχο. Αυτό σημαίνει ότι κάθε Μ.Ε. εκτελεί το πρόγραμμά της ανεξάρτητα από τις άλλες Μ.Ε. και άρα σε κάθε Μ.Ε. υπάρχει αποθηκευμένο τοπικά το πρόγραμμα που εκτελεί. Άμεσα συνδεδεμένο με την ιδιότητα αυτή είναι το γεγονός ότι κάθε λειτουργία που εκτελείται σε κάθε Μ.Ε. εξαρτάται μόνο από τα δεδομένα που είναι αποθηκευμένα τοπικά και από τα δεδομένα που δέχεται η Μ.Ε. από τις "γειτονικές" Μ.Ε.

- Οι Μ.Ε. λειτουργούν σε επίπεδο λέξης (και όχι σε επίπεδο bit). Το μέγεθος της λέξης μπορεί να είναι 8 ή 16 Bits (ή και περισσότερο μέσω λογισμικού). Στις περισσότερες περιπτώσεις δεν συσχετίζουμε το μέγεθος της λέξης με το πλήθος των Μ.Ε. Σε ορισμένες πάντως περιπτώσεις πρέπει να λάβουμε υπ' όψιν μας και το πλήθος των Μ.Ε., όπως για παράδειγμα όταν πρέπει να αθροίσουμε Ν ακεραίους, όπου το άθροισμα χρειάζεται log₂N επιπλέον bits. Εναλλακτικά μπορούμε να περιορίσουμε το πλήθος των Μ.Ε. με βάση το μέγεθος της λέξης.

- Κατά την ανάπτυξη αλγορίθμων για παράλληλες μηχανές, κάθε μονάδα επεξεργασίας μπορεί ή όχι να ξέρει την τοπολογία του δικτύου, το μέγεθός του καθώς και τη θέση της μέσα σε αυτό. Η "γνώση" της τοπολογίας και του μεγέθους του δικτύου επηρεάζει τη μορφή του αλγορίθμου. Σε όλα τα παραδείγματα που περιγράφονται στις ιστοσελίδες αυτές θεωρούμε ότι κάθε πρόγραμμα έχει αναπτυχθεί για συγκεκριμένη τοπολογία και μέγεθος δικτύου. Όσον αφορά στη γνώση της "διεύθυνσης" (ID) κάθε μονάδας επεξεργασίας, υπάρχουν αλγόριθμοι που θεωρούν ότι κάθε μονάδα επεξεργασίας έχει ξεχωριστή και γνωστή διεύθυνση, και άλλοι που θεωρούν ότι οι μονάδες επεξεργασίας δεν έχουν τέτοια γνώση. Ας σημειωθεί εδώ ότι η γνώση της διεύθυνσης απαιτεί ειδικού χειρισμό όταν προγραμματίζεται η κάθε μονάδα επεξεργασίας. Τα εργαλεία που έχουν αναπτυχθεί μέχρι τώρα δεν διευκολύνουν τέτοιον κώδικα.

- Οι μονάδες επεξεργασίας (Μ.Ε.) επικοινωνούν μεταξύ τους μέσω ενός σταθερού δικτύου διασύνδεσης (fixed interconnection network). Αυτό σημαίνει ότι κάθε Μ.Ε. μπορεί να ανταλλάσσει δεδομένα με έναν σταθερό και προκαθορισμένο αριθμό άλλων επεξεργαστικών μονάδων (αυτοί είναι και οι γείτονές της). Σημ. τα reconfigurable networks αποτελούν μελλοντικό στόχο.

Βασικά δίκτυα διασύνδεσης είναι το linear array και το δυαδικό δέντρο.

- linear array

Ένα παράδειγμα δίνεται στο παρακάτω σχήμα:

Linear array με 5 μονάδες επεξεργασίας.

Κάθε μία από τις εσωτερικές μονάδες επεξεργασίας συνδέεται με δικατευθυντήριες συνδέσεις με τον αριστερό γείτονα και τον δεξιό γείτονα. Οι δύο εξωτερικές μονάδες επεξεργασίες έχουν μόνο μία διασύνδεση η κάθε μία. Οι δύο εξωτερικές μονάδες μπορούν να γίνουν τα σημεία εισόδου-εξόδου για όλο το δίκτυο.

- Δυαδικό δένδρο

Ένα παράδειγμα δίνεται στο παρακάτω σχήμα:

Κάθε κόμβος συνδέεται με τρεις άλλους κόμβους: δύο "προς τα κάτω" και έναν "προς τα πάνω". Ο "πάνω" κόμβος λέγεται "μπαμπάς" και οι δύο "κάτω" κόμβοι λέγονται "παιδιά".

Ο κόμβος που είναι πιο πάνω από όλους ονομάζεται "ρίζα" του δένδρου και συνδέεται μόνο με δύο κόμβους (τα παιδιά του) καθώς δεν υπάρχει άλλος κόμβος πιο πάνω (δεν υπάρχει ο "μπαμπάς" του). Αντίστοιχα οι κόμβοι που είναι στο κατώτερο επίπεδο ονομάζονται "φύλλα" του δένδρου. Κάθε φύλλο συνδέεται μόνο με έναν άλλο κόμβο (τον μπαμπά του) καθώς δεν υπάρχουν άλλοι κόμβοι πιο κάτω (δεν υπάρχουν "παιδιά").

Το δένδρο του σχήματος έχει 7 κόμβους (Ν=7) που βρίσκονται σε 3 επίπεδα (κ=3). Γενικά σε κάθε δυαδικό δένδρο ισχύει η σχέση Ν=2^κ-1.

Η επικοινωνία μεταξύ των κόμβων μπορεί να είναι μίας κατεύθυνσης ή και δικατευθυντήρια. Η είσοδος και η έξοδος των δεδομένων γίνεται από τα φύλλα ή/και τη ρίζα του δένδρου.

Αρχική σελίδα Παράλληλης Επεξεργασίας