el el el el el el el el el el el el el el el el el el el el el el el el el el el el el el el el el el el el el el el el el el el el el en el el el el el el el en el el el el el el el el el en el el en el el el el el el el el el el el el el el el el el el el el el el el el el el el el el en el el el el el el el el el el el el el el el el la el el el el el el el el el el el el
Το λήμμα δεν περιέχει πηγές ή αυτές που περιέχει δεν επαρκούν. Μπορείτε να βοηθήσετε προσθέτοντας την κατάλληλη τεκμηρίωση. Υλικό που είναι ατεκμηρίωτο μπορεί να αμφισβητηθεί και να αφαιρεθεί.
Στην πληροφορική, παράλληλα, κατανεμημένα ή ταυτόχρονα συστήματα ονομάζονται υπολογιστές οι οποίοι επιτρέπουν την ταυτόχρονη εκτέλεση πολλαπλών συνεργαζόμενων προγραμμάτων σε μία ή περισσότερες επεξεργαστικές μονάδες. Οι διαφορές μεταξύ αυτών των όρων είναι λεπτές, με την έμφαση να δίνεται άλλοτε στον σχεδιασμό και ανάλυση αλγορίθμων, άλλοτε στην κατασκευή υποστηρικτικού λογισμικού και άλλοτε στη σχεδίαση των υποδομών υλικού που απαιτούνται για την επίτευξη του ταυτοχρονισμού.
Ο Cray-2, ο ταχύτερος υπολογιστής του κόσμου από το 1985 έως το 1989. Μία παραδοσιακή χρήση του υπολογιστικού παραλληλισμού είναι στον τομέα της κατασκευής τέτοιων υπερυπολογιστών.
Κατά τη δεκαετία του 1960 η εμφάνιση πολυδιεργασιακών λειτουργικών συστημάτων και η τυποποίηση της έννοιας της διεργασίας έφεραν στην επιφάνεια τον ταυτοχρονισμό, μία ιδιότητα των υπολογιστικών συστημάτων η οποία αφορά την παράλληλη ή ψευδοπαράλληλη εκτέλεση διαφορετικών, συνεργαζόμενων διεργασιών, σε έναν ή περισσότερους υπολογιστές, για την εκτέλεση ενός υπολογισμού. Αρχικώς οι επιστήμονες της θεωρητικής πληροφορικής επιχείρησαν να δώσουν απαντήσεις σε αλγοριθμικά ζητήματα λογισμικού όπως ο αμοιβαίος αποκλεισμός, η εκλογή αρχηγού, ο συγχρονισμός και η ομοφωνία μεταξύ συνεργαζόμενων, ταυτοχρόνως εκτελούμενων διεργασιών (το πεδίο αυτό σήμερα προσδιορίζεται με τον όρο κατανεμημένος υπολογισμός), ενώ με τις μεθόδους πρακτικής υλοποίησης της πολυδιεργασίας (τον χρονοπρογραμματισμό) ασχολήθηκαν οι ερευνητές από τον χώρο των λειτουργικών συστημάτων.
Με την καθιέρωση υπολογιστών με πολλαπλούς επεξεργαστές, όπου οι διεργασίες μπορούσαν να εκτελούνται πραγματικά παράλληλα και όχι ψευδοπαράλληλα, προέκυψαν νέα ζητήματα υλικού με αποτέλεσμα να αναδυθεί η παράλληλη επεξεργασία, ένα επιστημονικό πεδίο το οποίο μελετά, τόσο από πλευράς υλικού όσο και λογισμικού, μόνο υπολογιστικά συστήματα με πολλαπλές επεξεργαστικές μονάδες. Τα συστήματα αυτά μπορούν να εκτελούν ορισμένες, κατάλληλα σχεδιασμένες εφαρμογές (συνήθως επιστημονικού σκοπού, π.χ. προσομοιώσεις) ταχύτερα απ' ό,τι οι συνηθισμένοι σειριακοί υπολογιστές αρχιτεκτονικής Φον Νόιμαν. Την ίδια περίοδο όμως εξελίσσονταν και τα δίκτυα υπολογιστών με αποτέλεσμα, καθώς η δικτύωση άρχισε να είναι πανταχού παρούσα προς τα τέλη της δεκαετίας του 1970, να εμφανιστούν δικτυακά προγράμματα που όχι μόνο αλληλεπιδρούσαν μεταξύ τους μέσω της υποκείμενης δικτυακής υποδομής αλλά εκτελούσαν από κοινού υπολογισμούς με διαφανή για τον χρήστη τρόπο, διασπώντας τους σε τμήματα και κατανέμοντάς τους μεταξύ τους, ενώ στο εξωτερικό περιβάλλον εμφανίζονταν ως ένα μοναδικό σύστημα. Καθώς αυτός ήταν ένας τύπος παραλληλισμού εμφανίστηκε ο όρος κατανεμημένη επεξεργασία για να τον περιγράψει.
2.1 Ο νόμος του Άμνταλ
3 Μη συνεκτικά κατανεμημένα συστήματα
Υπό το πρίσμα της παράλληλης επεξεργασίας υπάρχουν τέσσερα είδη υπολογιστικών συστημάτων (ταξινόμηση Φλυν, 1966), τα οποία διαχωρίζονται με βάση το πόσες ταυτόχρονες ροές επεξεργασίας εντολών και δεδομένων υποστηρίζουν:
Οι υπολογιστές SISD (Μία Εντολή - Ένα Δεδομένο): οι συνήθεις σειριακοί υπολογιστές Φον Νόιμαν, όπου κάθε στιγμή ένας μοναδικός επεξεργαστής εκτελεί μία εντολή σε ένα δεδομένο το οποίο έχει προσκομίσει από την κύρια μνήμη.
Οι υπολογιστές SIMD (Μία Εντολή - Πολλαπλά Δεδομένα): μία σπάνια κατηγορία, όπου κάθε στιγμή πολλαπλοί επεξεργαστές εκτελούν μία μόνο κοινή εντολή σε πολλαπλά διαφορετικά δεδομένα. Ο όρος σήμερα περιγράφει σε σημαντικό βαθμό τη λειτουργία των σύγχρονων επεξεργαστών γραφικών.
Οι υπολογιστές MISD (Πολλαπλές Εντολές - Ένα Δεδομένο): ασυνήθιστη αρχιτεκτονική, όπου κάθε στιγμή πολλαπλοί επεξεργαστές τροποποιούν με διαφορετικό τρόπο την ίδια ροή δεδομένων· συνήθως αξιοποιείται με γνώμονα την αύξηση της ανοχής σφαλμάτων μίας εφαρμογής και όχι την αύξηση των υπολογιστικών επιδόσεων.
Οι υπολογιστές MIMD (Πολλαπλές Εντολές - Πολλαπλά Δεδομένα): οι πλήρως παράλληλοι υπολογιστές, όπου πολλαπλοί αυτόνομοι επεξεργαστές εκτελούν ταυτοχρόνως πολλαπλές διαφορετικές ροές εντολών σε διαφορετικά δεδομένα.
Τα συστήματα MIMD διακρίνονται σε πολυεπεξεργαστές κοινής μνήμης, όπου πολλαπλοί επεξεργαστές επικοινωνούν με μία κοινή μνήμη ενιαίου χώρου διευθύνσεων, και σε πολυυπολογιστές κατανεμημένης μνήμης, όπου πολλαπλά πακέτα επεξεργαστή-ιδιωτικής μνήμης, με τον δικό του χώρο διευθύνσεων το καθένα, διασυνδέονται και επικοινωνούν μεταξύ τους --και στις δύο περιπτώσεις η επικοινωνία γίνεται μέσω ενός «δικτύου διασύνδεσης». Τα μοντέλα παράλληλου προγραμματισμού για πολυεπεξεργαστές και πολυυπολογιστές είναι το μοντέλο κοινού χώρου διευθύνσεων (π.χ. πολλαπλές διεργασίες ή νήματα, OpenMP) και το μοντέλο μεταβίβασης μηνυμάτων (π.χ. PVM, MPI), αντιστοίχως. Στο πρώτο οι επεξεργαστικές μονάδες ανταλλάσσουν πληροφορίες προσπελαύνοντας κοινόχρηστες μεταβλητές στην κοινή μνήμη, ενώ στο δεύτερο ανταλλάσσοντας μηνύματα. Κάθε προγραμματιστικό μοντέλο μπορεί να εφαρμοστεί και σε σύστημα μιας αρχιτεκτονικής που δεν είναι η φυσική του (π.χ. πολυνηματικό πρόγραμμα σε πολυυπολογιστή ή πρόγραμμα MPI σε πολυεπεξεργαστή) αλλά συνήθως με χαμηλότερες επιδόσεις.
Στους πολυεπεξεργαστές εκτελείται ένα μόνο λειτουργικό σύστημα, το οποίο αναλαμβάνει να αναθέσει την εκτέλεση παράλληλων διεργασιών σε διαφορετικούς επεξεργαστές, ενώ στους πολυυπολογιστές, οι οποίοι ουσιαστικά αποτελούν κατανεμημένα συστήματα εφόσον είναι εφοδιασμένοι με το κατάλληλο λογισμικό, κάθε κόμβος εκτελεί τον δικό του πυρήνα. Μία υβριδική αρχιτεκτονική, η οποία επιτρέπει εύκολη εκτέλεση προγραμμάτων κοινού χώρου διευθύνσεων σε πολυυπολογιστές, είναι η κατανεμημένη κοινή μνήμη, στην οποία εξειδικευμένο υλικό (ελεγκτές μνήμης) παρέχει διαφανώς την ψευδαίσθηση ενιαίου χώρου διευθύνσεων στο λογισμικό που εκτελείται σε κάθε κόμβο. Στα συστήματα αυτά, φυσικά κατανεμημένης αλλά λογικά ενιαίας μνήμης, ένας κόμβος προσπελαύνει πολύ γρηγορότερα τα δεδομένα που είναι αποθηκευμένα στην τοπική του μνήμη απ' ό,τι τα δεδομένα που βρίσκονται σε κάποιον απομακρυσμένο κόμβο και γι' αυτό λέγονται συστήματα Ανομοιόμορφης Πρόσβασης Μνήμης (NUMA). Στους υπολογιστές αυτούς συνήθως εκτελείται ένας μόνο πυρήνας λειτουργικού συστήματος ο οποίος γνωρίζει, για λόγους βελτιστοποίησης των επιδόσεων, τις λεπτομέρειες της υποκείμενης αρχιτεκτονικής NUMA.
Στους πολυεπεξεργαστές η μνήμη συνήθως διασπάται σε πολλαπλά τμήματα προκειμένου να επιτρέπονται ταυτόχρονες προσπελάσεις σε αυτά από διαφορετικούς επεξεργαστές (χωρίς αυτό να αναιρεί φυσικά την ύπαρξη ενιαίου χώρου διευθύνσεων), ενώ το δίκτυο διασύνδεσης είναι στην απλούστερη περίπτωση ένας δίαυλος, δηλαδή ένα κοινό μέσο μετάδοσης το οποίο κάθε δεδομένη στιγμή μόνο ένας επεξεργαστής μπορεί να χρησιμοποιεί για επικοινωνία με κάποιο τμήμα μνήμης. Ως εκ τούτου οι πολυεπεξεργαστές διαύλου δεν παρουσιάζουν επαρκή κλιμακωσιμότητα, καθώς ο δίαυλος δεν διαθέτει αρκετή χωρητικότητα ώστε να εξυπηρετεί ταυτόχρονα αιτήσεις από πολλούς διαφορετικούς επεξεργαστές. Αυτό συνεπάγεται ότι οι επιδόσεις δεν αυξάνονται αναλογικά με το πλήθος των επεξεργαστών, αφού με την προσθήκη νέων επεξεργαστών πολλαπλασιάζονται τα διαστήματα αναμονής του καθενός για κατάληψη του διαύλου. Η λύση του διαύλου πάντως είναι η απλούστερη καθώς οι συνήθεις σειριακοί υπολογιστές έτσι κι αλλιώς διαθέτουν έναν δίαυλο για την επικοινωνία του επεξεργαστή με τη μνήμη και τις μονάδες Εισόδου / Εξόδου. Αν ωστόσο χρειαζόμαστε ένα σύστημα με περισσότερες από 10-20 CPU πρέπει να καταφύγουμε σε δίκτυα μεταγωγής, όπου μεταξύ κάθε επεξεργαστή και κάθε τμήματος της μνήμης δημιουργείται μία μοναδική διαδρομή.
Ένας διπύρηνος μικροεπεξεργαστής Athlon 64 X2 6400+. Πρόκειται για έναν πολυεπεξεργαστή διαύλου υλοποιημένο σε ένα μόνο μικροτσίπ.
Ανεξάρτητα από το είδος της διασύνδεσης, για την αύξηση των επιδόσεων και την αποφυγή υπερφόρτωσης του δικτύου, κάθε CPU διαθέτει τη δική της τοπική κρυφή μνήμη. Στα παράλληλα συστήματα όμως παρουσιάζεται το λεγόμενο «πρόβλημα της συνεκτικότητας» (cache coherence): ένα κοινόχρηστο δεδομένο που έχει αντιγραφεί σε πολλές κρυφές μνήμες μπορεί να τροποποιηθεί ανεξάρτητα στην καθεμία χωρίς να το γνωρίζει η κύρια ή οι άλλες κρυφές μνήμες, με αποτέλεσμα να υπάρχει ασάφεια ως προς το ποια είναι η σωστή τιμή του κάθε στιγμή. Το πρόβλημα αυτό επιλύεται στην περίπτωση ύπαρξης διαύλου με «πρωτόκολλα παρακολούθησης», όπου το υλικό κάθε επεξεργαστή παρακολουθεί όλη την πληροφορία που διακινείται στο κοινό μέσο και δρα ανάλογα, ενώ στην περίπτωση δικτύου μεταγωγής με «πρωτόκολλα καταλόγων», στους οποίους κάθε τμήμα της μνήμης διατηρεί έναν πίνακα με πληροφορίες για το ποιοι επεξεργαστές έχουν κάθε δεδομένο στην κρυφή τους μνήμη ώστε όποτε χρειάζεται να γίνονται οι κατάλληλες ενημερώσεις. Σε κάθε περίπτωση πάντως τα πρωτόκολλα συνεκτικότητας επιβαρύνουν το σύστημα, αφού αυξάνουν την κίνηση στο δίκτυο διασύνδεσης, με το πρόβλημα να μειώνεται (όχι όμως να απαλείφεται) μόνο αν καταβληθεί προσπάθεια ώστε τα παράλληλα προγράμματα να μην τροποποιούν συχνά κοινόχρηστα δεδομένα. Τα παράλληλα συστήματα κοινής μνήμης με δίαυλο στα οποία όλες οι CPU είναι ισότιμες και μπορούν όλες να αναλάβουν την εκτέλεση του λειτουργικού συστήματος ονομάζονται «συμμετρικοί πολυεπεξεργαστές» (SMP). Πάντως ακόμη και οι πολυεπεξεργαστές μεταγωγής στην πράξη έχουν περιορισμένη κλιμακωσιμότητα λόγω τετραγωνικά αυξανόμενου ως προς το πλήθος των επεξεργαστών κόστους κατασκευής του δικτύου διασύνδεσης, με αποτέλεσμα αν χρειαζόμαστε ένα σύστημα με παραπάνω από 64 CPU συνήθως να καταφεύγουμε σε πολυυπολογιστές.
Οι πολυυπολογιστές εμφανίζονται σε διάφορες εκδοχές αλλά σε κάθε περίπτωση πρόκειται για μία συλλογή ανεξάρτητων υπολογιστών (είτε απλώς πακέτα επεξεργαστή / ιδιωτικής μνήμης, είτε πλήρη και αυτοτελή συστήματα) που επικοινωνούν μεταξύ τους μέσω ενός δικτύου διασύνδεσης (είτε δίκτυο διαύλου είτε δίκτυο μεταγωγής). Οι κόμβοι μπορούν μεταξύ τους να είναι είτε ίδιοι («ομοιογενείς πολυυπολογιστές»), είτε διαφορετικοί («ετερογενείς πολυυπολογιστές»). Το δίκτυο διασύνδεσης μπορεί να είναι:
Εξειδικευμένο και εμπορικά κατοχυρωμένο δίκτυο υψηλής απόδοσης. Στην περίπτωση αυτή υπάγονται συνήθως εμπορικά κατοχυρωμένοι, ολοκληρωμένοι ομοιογενείς πολυυπολογιστές εξειδικευμένης αρχιτεκτονικής υπερυψηλών επιδόσεων (συμπεριλαμβανομένων συστημάτων NUMA), όπου κάθε κόμβος συνίσταται σε ένα πακέτο επεξεργαστή / μνήμης. Οι πολυυπολογιστές αυτού του τύπου με δίκτυο διασύνδεσης μεταγωγής μπορούν να κλιμακωθούν ακόμη και σε αρκετές χιλιάδες επεξεργαστές στο ίδιο σύστημα («μαζικός παραλληλισμός»), γι' αυτό και σπανίως γίνεται χρήση διαύλου. Τα δίκτυα μεταγωγής τα οποία αξιοποιούν ωστόσο διαφέρουν συνήθως από τα αντίστοιχα των πολυεπεξεργαστών κοινής μνήμης, αφού εδώ υπάρχουν ιδιωτικές συνδέσεις μεταξύ ορισμένων μόνο κόμβων και η επικοινωνία μεταξύ δύο ασύνδετων επεξεργαστών γίνεται με δρομολόγηση του μηνύματος μέσω ενδιάμεσων σταθμών. Η χωρική διάταξη των επεξεργαστών και των συνδέσεων μεταξύ τους καθορίζει την τοπολογία του δικτύου.
Συνηθισμένο δίκτυο υπολογιστών (LAN ή και WAN, όπως το Διαδίκτυο). Εδώ συνήθως υπάγονται ανοιχτής αρχιτεκτονικής, ετερογενείς πολυυπολογιστές που προκύπτουν από τη δικτύωση αυτόνομων, συνηθισμένων υπολογιστών («υπολογιστικές συστάδες», clusters). Η λύση αυτή είναι χαμηλότερου κόστους, χαμηλότερων επιδόσεων και πολύ δημοφιλής, ενώ τα δίκτυα διασύνδεσης που συνήθως αξιοποιεί είναι συνηθισμένα και εύκολα προσπελάσιμα (π.χ. Ethernet LAN, Intranet, ή ακόμη και το Διαδίκτυο). Οι συστάδες με δίκτυο διασύνδεσης το Διαδίκτυο έχει επικρατήσει να ονομάζονται «υπολογιστικά πλέγματα» (computer grid) και υλοποιούνται κυρίως με εξειδικευμένο καταναμεμημένο λογισμικό το οποίο εκτελείται σε συνηθισμένους δικτυωμένους ηλεκτρονικούς υπολογιστές.
Σε κάθε περίπτωση, από τη στιγμή που το λογισμικό εξασφαλίζει για τους χρήστες συνεκτική εικόνα των πόρων του πολυυπολογιστή και την ψευδαίσθηση ενός μοναδικού συστήματος, έστω και στο πλαίσιο μίας μόνο εφαρμογής, κάνουμε λόγο για κατανεμημένο σύστημα.
Μία υπολογιστική συστάδα τύπου Beowulf: ένας συνεκτικός, ομοιογενής πολυυπολογιστής προσανατολισμένος στη μεγιστοποίηση των υπολογιστικών επιδόσεων
Στους εξειδικευμένους πολυυπολογιστές υψηλής απόδοσης κάθε κόμβος επικοινωνεί με το δίκτυο διασύνδεσης μέσω ενός δρομολογητή, ενός μικρού κυκλώματος μεταγωγής με το οποίο δρομολογούνται πακέτα δεδομένων (μηνύματα) από έναν κόμβο σε έναν άλλον (πιθανώς διερχόμενα από ενδιάμεσους σταθμούς σε περίπτωση δικτύου μεταγωγής). Το ίδιο το δίκτυο μπορεί να έχει διάφορες τοπολογίες (δίαυλος, πλέγμα, υπερκύβος κ.λπ.) ενώ η μορφή των μηνυμάτων καθορίζεται από εξειδικευμένα πρωτόκολλα (ανάλογα με τον κατασκευαστή). Ένας τέτοιος πολυυπολογιστής μοιάζει πολύ με ένα ιδιότυπο τοπικό δίκτυο υπολογιστών, στο οποίο η τοπολογία είναι αυστηρά στατική, οι αποστάσεις πολύ μικρές και η ανάγκη για ταχύτητα εξαιρετικά αυξημένη. Ως εκ τούτου οι δρομολογητές, οι οποίοι παίζουν ταυτόχρονα τον ρόλο των καρτών δικτύου ενός συνήθους LAN και των δρομολογητών ενός WAN, έχουν όλη τη λειτουργικότητά τους τυπωμένη σε κυκλώματα υλικού ώστε να ελαχιστοποιούνται οι καθυστερήσεις, ενώ οι αλγόριθμοι δρομολόγησης που υλοποιούν είναι εξαιρετικά απλοί και ταχείς.
Ένας άλλος τύπος πολυυπολογιστή είναι μία συστάδα, ένα πραγματικό LAN ή WAN στο οποίο κάθε κόμβος είναι ένας πλήρης υπολογιστής, το δίκτυο διασύνδεσης ταυτίζεται με ένα σύνηθες δίκτυο υπολογιστών και τα χρησιμοποιούμενα πρωτόκολλα είναι αυτά της τυπικής στοίβας TCP/IP. Τόσο στις συστάδες όσο και στα συστήματα κατανεμημένης κοινής μνήμης που προαναφέρθηκαν το σύνηθες είναι κάθε κόμβος να αποτελεί έναν πλήρη συμμετρικό πολυεπεξεργαστή, οπότε το δίκτυο διασύνδεσης μοιάζει κατά κάποιον τρόπο με WAN και κάθε κόμβος με αυτόνομο LAN που συμμετέχει στο ολικό δίκτυο μέσω του δρομολογητή του. Με αυτόν τον τρόπο η ικανότητα κλιμάκωσης του ολικού συστήματος αυξάνεται κατά πολύ. Σε πολυυπολογιστές κατανεμημένης κοινής μνήμης μπορούν να χρησιμοποιηθούν κρυφές μνήμες σε κάθε κόμβο για την αύξηση των επιδόσεων αλλά έτσι εμφανίζεται πάλι, σε διαφορετικό πλαίσιο, το προαναφερθέν πρόβλημα της συνεκτικότητας. Αντιμετωπίζεται με πρωτόκολλα καταλόγων, αφού συνήθως δεν υπάρχει κοινό μέσο, ενώ όταν κάθε σταθμός είναι συμμετρικός πολυεπεξεργαστής διαύλου χρησιμοποιείται ένα τέτοιο «εξωτερικό» πρωτόκολλο για το ολικό δίκτυο και ένα «εσωτερικό» πρωτόκολλο παρακολούθησης σε κάθε κόμβο.
Κύριο λήμμα: Παράλληλος προγραμματισμός
Η ανάπτυξη εφαρμογών σε συστήματα κοινής και κατανεμημένης κοινής μνήμης συνήθως γίνεται με τη βοήθεια λογισμικού συστήματος για κατασκευή, χειρισμό και συντονισμό πολλαπλών διεργασιών ή / και νημάτων, ή με API όπως το OpenMP, ένα υψηλού επιπέδου πρότυπο κατασκευής βιβλιοθηκών, επεκτάσεων μεταγλωττιστή και μεταβλητών περιβάλλοντος με υλοποιήσεις για διάφορους συνδυασμούς επεξεργαστή / λειτουργικού συστήματος / γλώσσας προγραμματισμού, το οποίο βασίζεται στην κοινή μνήμη του ενιαίου χώρου διευθύνσεων για τη διαδιεργασιακή / διανηματική επικοινωνία. Στην πλειονότητα των περιπτώσεων το OpenMP υλοποιείται εσωτερικά με τα συνήθη νήματα του προτύπου POSIX των λειτουργικών συστημάτων Unix, τα οποία (όπως και οι μέθοδοι χειρισμού διεργασιών και διαδιεργασιακής επικοινωνίας του POSIX) προγραμματίζονται με τον ίδιο τρόπο σε έναν σειριακό υπολογιστή και σε έναν πολυεπεξεργαστή για την κατασκευή εφαρμογών που εκμεταλλεύονται τον ταυτοχρονισμό. Στον πολυεπεξεργαστή ωστόσο ο πυρήνας αυτομάτως χρονοπρογραμματίζει καταλλήλως τα νήματα ή τις διεργασίες ώστε, αν είναι εφικτό, να εκτελούνται παράλληλα σε διαφορετικούς επεξεργαστές, ενώ στον σειριακό υπολογιστή όλα τα νήματα ή διεργασίες εκτελούνται σειριακά και ψευδοπαράλληλα στον ίδιο επεξεργαστή χωρίς να υπάρχει πραγματικός παραλληλισμός.
Στους πολυυπολογιστές από την άλλη βρίσκει εφαρμογή το MPI, ένα πρότυπο κατασκευής βιβλιοθηκών για την επικοινωνία παράλληλων διεργασιών μέσω ρητής ανταλλαγής μηνυμάτων. Εσωτερικά, στις περισσότερες υλοποιήσεις της, η βιβλιοθήκη του MPI καλεί το API δικτυακού προγραμματισμού των υποδοχών (sockets) αλλά είναι υψηλότερου επιπέδου από αυτό, προσανατολίζεται αποκλειστικά σε πολυυπολογιστικά κατανεμημένα συστήματα, παρέχει πιο εξελιγμένες δυνατότητες και διατίθεται σε διάφορες εκδόσεις βελτιστοποιημένες για πολυυπολογιστές με συγκεκριμένη τοπολογία δικτύου διασύνδεσης (Ethernet, υπερκύβος, πλέγμα κλπ, ή ακόμη και σε εκδόσεις για πολυεπεξεργαστές κοινής μνήμης). Με το MPI ο υπολογισμός κατανέμεται σε ένα σύνολο πανομοιότυπων διεργασιών, σειριακά αριθμημένων, που εκτελούνται σε διαφορετικούς κόμβους και ο κώδικάς τους διαφοροποιείται ρητά ανάλογα με τον σειριακό αριθμό τους. Το MPI είναι προσανατολισμένο στη μεγιστοποίηση των επιδόσεων και γι' αυτό συνήθως εξετάζεται στα πλαίσια της παράλληλης και όχι της κατανεμημένης επεξεργασίας.
Συνήθως ένας αλγόριθμος παραλληλοποιείται με διάσπασή του σε πολλαπλά τμήματα τα οποία ανατίθενται σε ξεχωριστά νήματα ή διεργασίες και έτσι εκτελούνται παράλληλα σε διαφορετικές επεξεργαστικές μονάδες. Στο μοντέλο κοινού χώρου διευθύνσεων μπορούν να ανακύψουν ζητήματα αμοιβαίου αποκλεισμού αλλά και συγχρονισμού, τα οποία πρέπει να αντιμετωπιστούν προγραμματιστικά. Εκ φύσεως στο μοντέλο μεταβίβασης μηνυμάτων ανακύπτουν μόνο αλγοριθμικά ζητήματα συγχρονισμού, αφού δεν υπάρχουν κοινόχρηστες μεταβλητές.
Ο νόμος του ΆμνταλΕπεξεργασία
Ο Τζιν Άμνταλ το 2008
Ο νόμος του Άμνταλ χρησιμοποιείται για να διαπιστωθεί η αναμενόμενη μείωση του χρόνου εκτέλεσης από την παραλληλοποίηση ενός σειριακού προγράμματος. Φέρει το όνομα του Τζιν Άμνταλ που τον πρωτοδιατύπωσε και δηλώνει ότι η επιτάχυνση ενός προγράμματος το οποίο αξιοποιεί πολλαπλούς επεξεργαστές περιορίζεται από τον χρόνο εκτέλεσης που απαιτεί το σειριακό μέρος του προγράμματος. Ο νόμος του Άμνταλ συνήθως ορίζεται με τη βοήθεια του παρακάτω μαθηματικού τύπου:
1 ( 1 − P ) + P N {\displaystyle {\frac {1}{(1-P)+{\frac {P}{N}}}}}
Στον τύπο αυτόν η μεταβλητή P δηλώνει το ποσοστό των συνολικών υπολογισμών του προγράμματος οι οποίοι μπορούν να παραλληλοποιηθούν και η μεταβλητή Ν το πλήθος των διαθέσιμων επεξεργαστών. Για παράδειγμα, αν το P είναι 90% (0,9), τότε το (1-P) είναι 10% και το ολικό πρόγραμμα (σύμφωνα με τον τύπο του Άμνταλ) μπορεί να επιταχυνθεί το πολύ 10 φορές, όσους επεξεργαστές και αν χρησιμοποιήσουμε. Γι' αυτόν τον λόγο η παράλληλη επεξεργασία είναι χρήσιμη μόνο για περιορισμένο πλήθος επεξεργαστών (μικρό N) ή για προβλήματα με πολύ μεγάλη τιμή P (π.χ. η πρόσθεση δύο ν-διάστατων διανυσμάτων έχει P 100%, αφού πρακτικώς δεν υπάρχει αποκλειστικά σειριακό τμήμα στον αλγόριθμο).
Στις περισσότερες περιπτώσεις ένα παράλληλο πρόγραμμα έχει σχεδιαστεί κατάλληλα και ο πηγαίος κώδικας έχει γραφεί από τον προγραμματιστή έτσι ώστε να υποστηρίζει παραλληλισμό («ρητός παραλληλισμός»). Επειδή η διαδικασία αυτή είναι επίπονη, χρονοβόρα και απαιτεί ειδικές γνώσεις εκ μέρους του προγραμματιστή, έχουν υπάρξει πολλές προσπάθειες για την αυτόματη παραλληλοποίηση τμημάτων σειριακού πηγαίου κώδικα (συνήθως επαναληπτικών βρόχων) από κατάλληλους μεταγλωττιστές. Στην περίπτωση αυτή ο προγραμματιστής συγγράφει τυπικό σειριακό κώδικα, χωρίς κλήσεις σε κάποια υποστηρικτική βιβλιοθήκη όπως των νημάτων POSIX, του OpenMP ή του MPI, και κατά τη μεταγλώττιση εντοπίζονται αυτομάτως τα σημεία που επιδέχονται παραλληλισμό.
Πέρα από τις, συμπληρωματικές μεταξύ τους, λύσεις της αυτόματης παραλληλοποίησης και της προσθήκης εξειδικευμένων βιβλιοθηκών και επεκτάσεων σε συνήθεις γλώσσες προγραμματισμού όπως η C ή η Fortran, κατά καιρούς έχουν εμφανιστεί και ορισμένες γλώσσες προγραμματισμού σχεδιασμένες από τη βάση τους με στόχο την εγγενή υποστήριξη ταυτοχρονισμού, είτε παράλληλου είτε ψευδοπαράλληλου. Ακόμη και συνηθισμένες γλώσσες γενικού σκοπού παρέχουν κάποια στοιχειώδη εγγενή υποστήριξη για ταυτοχρονισμό και αμοιβαίο αποκλεισμό (π.χ. η Java και η C#), αλλά οι εξειδικευμένες γλώσσες ταυτόχρονου προγραμματισμού είναι βελτιστοποιημένες συγκεκριμένα προς αυτή την κατεύθυνση.
Μη συνεκτικά κατανεμημένα συστήματαΕπεξεργασία
Τα μη συνεκτικά κατανεμημένα συστήματα εκτελούνται συνήθως σε ετερογενείς δικτυωμένους πολυυπολογιστές και βασίζονται σε λογισμικό το οποίο παρέχει υπηρεσίες σε χρήστες, αποκρύπτοντας όμως την ύπαρξη πολλαπλών υπολογιστών και τη χρήση του υποκείμενου δικτύου (διαφάνεια). Το δίκτυο διασύνδεσης ποικίλει, από την κλίμακα ενός τοπικού Ethernet (π.χ. για τις ανάγκες μίας επιχείρησης ή ενός πανεπιστημιακού τμήματος) μέχρι την κλίμακα του Διαδίκτυο. Στόχος αυτών των συστημάτων συνήθως είναι η διαφανής παροχή κάποιας υπηρεσίας (π.χ. διαμοιρασμός πόρων μεταξύ απομακρυσμένων χρηστών, αυτόματη μετάφραση κειμένου μέσω Διαδικτύου κλπ), αλλά σπανιότερα μπορούν να αξιοποιηθούν και για αύξηση των υπολογιστικών επιδόσεων κατά την επίλυση ενός προβλήματος (π.χ. υπολογιστικά πλέγματα, αν και γι' αυτόν τον σκοπό χρησιμοποιούνται κυρίως πολυεπεξεργαστές ή συνεκτικοί πολυυπολογιστές με τοπικά δίκτυα διασύνδεσης χαμηλής υστέρησης). Συνήθως η εργασία που επιτελεί ένα τέτοιο κατανεμημένο σύστημα μπορεί να γίνει και από ένα συγκεντρωτικό σύστημα (π.χ. έναν κεντρικό υπολογιστή στον οποίον συνδέονται οι πελάτες μέσω δικτύου). Ωστόσο τα κατανεμημένα συστήματα πλεονεκτούν έναντι των συγκεντρωτικών ως προς:
Την οικονομία, αφού ένας κεντρικός υπολογιστής μεγάλης ισχύος μπορεί να είναι πολύ ακριβότερος
Την ευελιξία, αφού ο φόρτος εργασίας μπορεί να διαμοιραστεί κατάλληλα στους κόμβους του συστήματος
Την αξιοπιστία, αφού αν ένας κόμβος καταρρεύσει δεν επηρεάζονται οι υπόλοιποι
Τη σταδιακή ανάπτυξη, αφού μπορεί να προστεθεί σταδιακά περισσότερη ισχύς με την προσθήκη νέων κόμβων
Την κοινοχρησία δεδομένων ή συσκευών μεταξύ απομακρυσμένων χρηστών
Με την εμφάνιση των κατανεμημένων συστημάτων προέκυψαν ζητήματα λογισμικού, αφού έπρεπε να γραφούν κατάλληλες γλώσσες προγραμματισμού, λειτουργικά συστήματα και εφαρμογές που να υποστηρίζουν αυτό το μοντέλο, ζητήματα δικτύωσης, αφού είναι αναγκαία η ύπαρξη δικτύου και αν το δίκτυο καταρρεύσει ή κορεστεί καταρρέει και το σύστημα, και ασφάλειας δεδομένων. Ένα κατανεμημένο σύστημα είναι ανοιχτό, παρέχει δηλαδή υπηρεσίες σύμφωνα με συγκεκριμένους γνωστούς κανόνες, έχει επαρκή κλιμακωσιμότητα και προσφέρει στους χρήστες του κάποιους ή όλους από τους παρακάτω τύπους διαφάνειας:
Διαφάνεια πρόσβασης, δηλαδή απόκρυψη των πιθανών διαφορών στην αναπαράσταση των δεδομένων και του πώς προσπελαύνονται μεταξύ των κόμβων του συστήματος
Διαφάνεια θέσης, δηλαδή απόκρυψη της πληροφορίας σχετικά με το σε ποιον κόμβο τοποθετείται ένας πόρος
Διαφάνεια μετανάστευσης, δηλαδή παροχή δυνατότητας στους πόρους να μετακινούνται κατά βούληση μεταξύ των κόμβων χωρίς να αλλάζουν ιδιότητες ή όνομα
Διαφάνεια επανατοποθέτησης, δηλαδή παροχή δυνατότητας κινητικότητας στους πόρους ενώ χρησιμοποιούνται
Διαφάνεια αντιγραφής, δηλαδή απόκρυψη του πλήθους αντιγράφων που μπορεί να έχει ένας πόρος για λόγους ασφάλειας ή αξιοπιστίας (ανοχής σφαλμάτων)
Διαφάνεια ταυτοχρονισμού, δηλαδή παροχή δυνατότητας αυτόματου και συνεπούς διαμοιρασμού των πόρων την ίδια στιγμή μεταξύ διαφορετικών χρηστών
Διαφάνεια βλαβών, δηλαδή απόκρυψη αστοχίας πόρων
Διαφάνεια διατήρησης, δηλαδή απόκρυψη της κατάστασης αποθήκευσης ενός πόρου (προσωρινός, σε μνήμη RAM, ή μόνιμος, σε δίσκο)
Διαφάνεια παραλληλισμού, δηλαδή απόκρυψη του αν μία εφαρμογή εκτελείται σε έναν ή πολλαπλούς επεξεργαστές
Προκειμένου να παρουσιάζει ένα κατανεμημένο σύστημα καλή κλιμακωσιμότητα ως προς το πλήθος των κόμβων, συνήθως αποφεύγονται κατά την κατασκευή του οι συγκεντρωτικοί αλγόριθμοι, οι συγκεντρωτικές δομικές μονάδες και οι συγκεντρωτικοί πίνακες. Προτιμώνται κατανεμημένοι αλγόριθμοι, χωρίς συγχρονισμένο καθολικό ρολόι και όπου οι κόμβοι είναι ισότιμοι και παίρνουν αποφάσεις στηριζόμενοι μόνο σε αποσπασματικές, τοπικά διαθέσιμες πληροφορίες για το σύστημα. Έτσι ο φόρτος εργασίας δεν αυξάνει ανάλογα με το πλήθος των κόμβων και αποφεύγεται η κατάρρευση του συστήματος όταν καταρρέει ένας κόμβος.
Όμως ζητήματα κλιμακωσιμότητας προκύπτουν και λόγω των περιορισμών του δικτύου ή των διακομιστών. Ένας κόμβος του συστήματος πρέπει να αποκρύπτει από τον χρήστη τις πιθανές καθυστερήσεις επικοινωνίας όσο μπορεί, π.χ. μεταφέροντας ένα μέρος των υπολογισμών από τον διακομιστή στον πελάτη ή επικαλύπτοντας επικοινωνία και υπολογισμό, ενώ επιτυχημένες μέθοδοι για την αντιμετώπιση του ζητήματος είναι η αντιγραφή (replication), δηλαδή η δημιουργία πολλαπλών αντιγράφων ενός πόρου και η διανομή τους σε ποικίλους κόμβους ώστε να αυξηθεί η διαθεσιμότητα (και επομένως η ανοχή σφαλμάτων ή οι υπολογιστικές επιδόσεις), και η διανομή, ο διαχωρισμός ενός συστατικού σε μικρότερα και η διαμοίρασή τους στο σύστημα.
Από τη σκοπιά της κατανεμημένης επεξεργασίας τα λειτουργικά συστήματα διακρίνονται σε συνεκτικά, στα οποία το λογισμικό διατηρεί και εμφανίζει στους χρήστες μία ενιαία καθολική εικόνα των πόρων, και μη συνεκτικά, στα οποία οι κόμβοι είναι θεμελιωδώς ανεξάρτητοι μεταξύ τους και επικοινωνούν σε κάποιον περιορισμένο βαθμό. Έτσι υπάρχουν οι εξής κατηγορίες ΛΣ:
Κατανεμημένα Λειτουργικά Συστήματα (DOS), τα οποία είναι συνεκτικά ΛΣ για πολυεπεξεργαστές και ομοιογενείς πολυυπολογιστές. Ένα DOS που εκτελείται σε έναν πολυυπολογιστή αποτελεί πραγματικό κατανεμημένο σύστημα.
Λειτουργικά Συστήματα Δικτύου (NOS), τα οποία είναι μη συνεκτικά ΛΣ για ετερογενείς πολυυπολογιστές σε LAN και WAN. Τα NOS (στην πράξη σχεδόν όλα τα σύγχρονα λειτουργικά συστήματα) δεν μπορούν να χαρακτηριστούν από μόνα τους κατανεμημένα συστήματα.
Ενδιάμεσο λογισμικό, το οποίο είναι ένα επίπεδο λογισμικού που μεσολαβεί μεταξύ ενός NOS και μιας εφαρμογής (συνήθως μεταξύ του επιπέδου μεταφοράς και του επιπέδου εφαρμογών του μοντέλου TCP/IP) παρέχοντας την ψευδαίσθηση ενός DOS και ενός εικονικού ομοιογενούς περιβάλλοντος. Με το ενδιάμεσο λογισμικό είναι εφικτός ο συνδυασμός των πλεονεκτημάτων των DOS και των NOS.
Το BOINC είναι μία πλατφόρμα ενδιάμεσου λογισμικού για υποστήριξη κατανεμημένων εφαρμογών υπολογιστικού πλέγματος, οι οποίες αξιοποιούν την πληθώρα υπολογιστών συνδεδεμένων στο Διαδίκτυο για να επιτύχουν εξαιρετικά υψηλές υπολογιστικές επιδόσεις
Με βάση τα προηγούμενα, ενδιάμεσο λογισμικό αποτελεί π.χ. μία βιβλιοθήκη η οποία υλοποιεί το MPI, λειτουργώντας έτσι ως «διαμεσολαβητής» για την εύκολη και διαφανή ανάπτυξη παράλληλων εφαρμογών μεταβίβασης μηνυμάτων σε πολυυπολογιστές. Ωστόσο το MPI, λόγω του ρόλου και της φύσης του, παραβιάζει θεμελιωδώς τη διαφάνεια θέσης με τη ρητή ανταλλαγή μηνυμάτων μεταξύ των συμμετεχόντων διεργασιών. Ακόμα, κάποιο ενδιάμεσο λογισμικό μπορεί να μην παρέχεται ως ξεχωριστή βιβλιοθήκη για την υποστήριξη πολλαπλών εφαρμογών, αλλά να είναι ενσωματωμένο σε μία μόνο κατανεμημένη δικτυακή εφαρμογή και βελτιστοποιημένο γι' αυτήν. Αυτό συμβαίνει π.χ. με τις περισσότερες ομότιμες εφαρμογές ανταλλαγής αρχείων μέσω Διαδικτύου.
Τα DOS παρουσιάζονται στους χρήστες ως συγκεντρωτικά και μονοεπεξεργαστικά. Ένα DOS σε πολυεπεξεργαστή έχει έναν μοναδικό πυρήνα κοινό για όλες τις CPU (όχι μονολιθικό στην πλειονότητα των περιπτώσεων, για λόγους ευελιξίας) ενώ, αντιθέτως, σ' ένα DOS σε πολυυπολογιστή κάθε κόμβος έχει τον δικό του πυρήνα (ο οποίος χρησιμοποιεί την τοπική μνήμη) αλλά παρέχεται κατάλληλη διασύνδεση που αποκρύπτει αυτό το γεγονός από τις εφαρμογές προσφέροντας, αν χρειάζεται, μέχρι και την ψευδαίσθηση κοινής εικονικής μνήμης: ο χώρος εικονικών διευθύνσεων διαμερίζεται σε σελίδες και σε κάθε κόμβο ανατίθενται κάποιες (κατανεμημένη κοινή μνήμη λογισμικού). Αυτό μοιάζει με ό,τι συμβαίνει στα συστήματα NUMA, όπου ο χώρος διευθύνσεων είναι έτσι κι αλλιώς κοινός από τη σκοπιά του λειτουργικού συστήματος, μόνο που οι επιδόσεις ενός πολυυπολογιστή με κατανεμημένη κοινή μνήμη λογισμικού είναι σαφώς χαμηλότερες απ' ό,τι αν η ψευδαίσθηση του εναίου χώρου διευθύνσεων υλοποιούνταν απευθείας στο υλικό, όπως στην αρχιτεκτονική NUMA.
Η διαδιεργασιακή επικοινωνία στα πολυυπολογιστικά συστήματα συνήθως υλοποιείται σε χαμηλό επίπεδο με το σύνηθες δικτυακό μοντέλο πελάτη-διακομιστή, όπου οι πελάτες αιτούνται μέσω του δικτύου υπηρεσίες που παρέχουν οι διακομιστές και αναμένουν απάντηση. Οι πελάτες θα πρέπει να γνωρίζουν πού να απευθυνθούν για μία υπηρεσία και υπάρχουν τρεις τρόποι για την αντιστοίχηση υπηρεσιών-διακομιστών: χρήση συγκεκριμένων διευθύνσεων τύπου υπηρεσία@μηχάνημα, η οποία όμως παραβιάζει τη διαφάνεια θέσης (π.χ. Παγκόσμιος Ιστός), επιλογή τυχαίας διεύθυνσης από την υπηρεσία και ανακοίνωσή της με πολυδιανεμόμενο μήνυμα, ή χρήση ενός διακομιστή ονομάτων ο οποίος συνδέει ASCII ονόματα υπηρεσιών με χαμηλού επιπέδου δικτυακές διευθύνσεις και τον οποίον συμβουλεύονται οι εφαρμογές. Η επικοινωνία χαμηλού επιπέδου μεταξύ δύο υπολογιστών προγραμματιστικά επιτυγχάνεται μέσω κατάλληλων κλήσεων συστήματος (π.χ. send() και recv(), από το API των υποδοχών που παρέχει το λειτουργικό σύστημα για διαδιεργασιακή επικοινωνία μέσω δικτύου).
Στο μοντέλο πελάτη-διακομιστή εμφανίζονται δύο ζητήματα που πρέπει να αντιμετωπιστούν: η αρχιτεκτονική εξυπηρέτησης που προσφέρουν και η κλιμακωσιμότητά τους. Η αρχιτεκτονική μπορεί να είναι είτε ακολουθιακή, όπου κάθε φορά εξυπηρετείται ένας πελάτης σειριακά, είτε παράλληλη, όπου ο διακομιστής δημιουργεί νέα διεργασία ή νέο νήμα για την εξυπηρέτηση κάθε πελάτη και ο χρονοπρογραμματιστής του λειτουργικού του συστήματος αναλαμβάνει την ταυτόχρονη εκτέλεσή τους. Η αύξηση της κλιμακωσιμότητας επιτυγχάνεται με προσθήκη κρυφής μνήμης, χρήση ισχυρότερου υπολογιστή (π.χ. με περισσότερους επεξεργαστές), κατανομή των δεδομένων ή / και των αλγορίθμων σε πολλαπλούς διακομιστές κλπ. Αντί για το μοντέλο πελάτη-διακομιστή όμως μπορεί να αξιοποιηθεί ένα μοντέλο ομότιμης επικοινωνίας, όπου όλοι οι κόμβοι είναι ισότιμοι και μπορούν να λειτουργούν τόσο ως πελάτες όσο και ως διακομιστές. Έτσι η προσθήκη περισσότερων κόμβων σε μία ομότιμη εφαρμογή ανταλλαγής και διαμοιρασμού αρχείων μέσω Διαδικτύου (π.χ. eMule) αυξάνει στην πραγματικότητα την κλιμακωσιμότητα του ολικού συστήματος (αφού με κάθε νέο κόμβο που συμμετέχει προστίθενται νέες συνδέσεις στο λογικό δίκτυο επικάλυψης της εφαρμογής, όπως και περισσότερος αποθηκευτικός χώρος), ενώ η προσθήκη περισσότερων πελατών που αναμένουν την εξυπηρέτησή τους από έναν διακομιστή μεταφοράς αρχείων (π.χ. FTP) οδηγεί σταδιακά στον κορεσμό του τελευταίου, αφού το σύστημα χαρακτηρίζεται από στατική κλιμακωσιμότητα.
Στα κατανεμημένα συστήματα πολλές φορές είναι επιθυμητή η κατασκευή πολλαπλών συνεργαζόμενων διεργασιών, που μπορεί να τοποθετούνται σε διαφορετικούς δικτυωμένους υπολογιστές, για την επίτευξη ενός στόχου. Αυτές οι ομάδες διεργασιών αποτελούν ένα μηχανισμό αφαίρεσης και μία κατανεμημένη εφαρμογή πρέπει να μπορεί να επικοινωνεί μαζί τους ατομικά χωρίς να γνωρίζει το ακριβές πλήθος ή τις διευθύνσεις των μελών. Αυτό επιτυγχάνεται είτε με υποστήριξη από το υλικό του δικτύου (πολυδιανομή, εκπομπή), είτε με χαμηλότερου επιπέδου αποστολή μηνυμάτων σε κάθε μέλος της ομάδας ξεχωριστά, διαφανώς για τον χρήστη. Οι ομάδες μπορούν να είναι είτε κλειστές, όπου επιτρέπεται επικοινωνία μόνο μεταξύ μελών της ομάδας, είτε ανοιχτές, όπου επιτρέπεται επιπλέον και η αμφίδρομη επικοινωνία των μελών της ομάδας με τον «έξω κόσμο», ενώ επίσης μπορούν να είναι ιεραρχικές, με εσωτερική δομή όπου υπάρχει ένας συντονιστής και οι υπόλοιπες διεργασίες θεωρούνται εργάτες, ή ομότιμες, όπου όλα τα μέλη είναι ισότιμα. Το πρόβλημα με τις ιεραρχικές ομάδες είναι ότι αν καταρρεύσει ο συντονιστής καταστρέφεται όλη η εργασία, ενώ το πρόβλημα με τις ομότιμες ομάδες είναι ότι προκειμένου να ληφθεί μία απόφαση πρέπει να διεξαχθεί «ψηφοφορία» όπου κάθε μέλος στέλνει ένα μήνυμα με την ψήφο του στα άλλα. Δύο άλλα ζητήματα, η λύση των οποίων εξαρτάται από την εκάστοτε εφαρμογή, είναι ο ταυτοχρονισμός (αν υπάρχουν δηλαδή περιορισμοί σχετικά με τη σειρά παραλαβής δύο μηνυμάτων σε κάθε μέλος) και τα σφάλματα (είναι αποδεκτή η λήψη ενός μηνύματος μόνο από ένα υποσύνολο των μελών;).