Παράλληλος προγραμματισμός

Επισκόπηση

Η ανάπτυξη εφαρμογών σε συστήματα κοινής και κατανεμημένης κοινής μνήμης συνήθως γίνεται με τη βοήθεια λογισμικού συστήματος για κατασκευή, χειρισμό και συντονισμό πολλαπλών διεργασιών ή / και νημάτων, ή με API όπως το OpenMP, ένα υψηλού επιπέδου πρότυπο κατασκευής βιβλιοθηκών, επεκτάσεων μεταγλωττιστή και μεταβλητών περιβάλλοντος με υλοποιήσεις για διάφορους συνδυασμούς επεξεργαστή / λειτουργικού συστήματος / γλώσσας προγραμματισμού, το οποίο βασίζεται στην κοινή μνήμη του ενιαίου χώρου διευθύνσεων για τη διαδιεργασιακή / διανηματική επικοινωνία. Στην πλειονότητα των περιπτώσεων το OpenMP υλοποιείται εσωτερικά με τα συνήθη νήματα του προτύπου POSIX των λειτουργικών συστημάτων Unix, τα οποία (όπως και οι μέθοδοι χειρισμού διεργασιών και διαδιεργασιακής επικοινωνίας του POSIX) προγραμματίζονται με τον ίδιο τρόπο σε έναν σειριακό υπολογιστή και σε έναν πολυεπεξεργαστή για την κατασκευή εφαρμογών που εκμεταλλεύονται τον ταυτοχρονισμό. Στον πολυεπεξεργαστή ωστόσο ο πυρήνας αυτομάτως χρονοπρογραμματίζει καταλλήλως τα νήματα ή τις διεργασίες ώστε, αν είναι εφικτό, να εκτελούνται παράλληλα σε διαφορετικούς επεξεργαστές, ενώ στον σειριακό υπολογιστή όλα τα νήματα ή διεργασίες εκτελούνται σειριακά και ψευδοπαράλληλα στον ίδιο επεξεργαστή χωρίς να υπάρχει πραγματικός παραλληλισμός.
Στους πολυυπολογιστές από την άλλη βρίσκει εφαρμογή το MPI, ένα πρότυπο κατασκευής βιβλιοθηκών για την επικοινωνία παράλληλων διεργασιών μέσω ρητής ανταλλαγής μηνυμάτων. Εσωτερικά, στις περισσότερες υλοποιήσεις της, η βιβλιοθήκη του MPI καλεί το API δικτυακού προγραμματισμού των υποδοχών (sockets) αλλά είναι υψηλότερου επιπέδου από αυτό, προσανατολίζεται αποκλειστικά σε πολυυπολογιστικά κατανεμημένα συστήματα, παρέχει πιο εξελιγμένες δυνατότητες και διατίθεται σε διάφορες εκδόσεις βελτιστοποιημένες για πολυυπολογιστές με συγκεκριμένη τοπολογία δικτύου διασύνδεσης (Ethernet, υπερκύβος, πλέγμα κλπ, ή ακόμη και σε εκδόσεις για πολυεπεξεργαστές κοινής μνήμης). Με το MPI ο υπολογισμός κατανέμεται σε ένα σύνολο πανομοιότυπων διεργασιών, σειριακά αριθμημένων, που εκτελούνται σε διαφορετικούς κόμβους και ο κώδικάς τους διαφοροποιείται ρητά ανάλογα με τον σειριακό αριθμό τους. Το MPI είναι προσανατολισμένο στη μεγιστοποίηση των επιδόσεων και γι' αυτό συνήθως εξετάζεται στα πλαίσια της παράλληλης και όχι της κατανεμημένης επεξεργασίας.

Σχεδίαση παράλληλων προγραμμάτων

Ένα παράδειγμα αποτελεί ο προσεγγιστικός υπολογισμός της τιμής του αριθμού π μέσω μίας επαναληπτικής μεθόδου αριθμητικής ανάλυσης, όπου σε έναν βρόχο Ν επαναλήψεων εκτελείται μία αριθμητική πράξη το αποτέλεσμα της οποίας προστίθεται κάθε φορά σε μία μεταβλητή, αρχικοποιημένη σε 0. Μία διάσπαση πεδίου ορισμού, η οποία είναι η πιο φυσική για αυτό το πρόβλημα, διαμοιράζει τον βρόχο σε Κ υποβρόχους, μεγέθους Ν/Κ ο καθένας, και αναθέτει τον καθένα σε ξεχωριστή διεργασία ή νήμα. Αντίθετα σε ένα άλλο πρόβλημα μπορεί να ταιριάζει περισσότερο η λειτουργική διάσπαση, όπου κάθε επεξεργαστής αναλαμβάνει να εκτελέσει διαφορετική εργασία: π.χ. σε ένα πρόγραμμα συμπίεσης βίντεο μπορεί μία διεργασία / νήμα να επεξεργάζεται τα ηχητικά δεδομένα ενώ μία άλλη επενεργεί στα οπτικά δεδομένα.
Στο παράδειγμα παραλληλοποίησης του υπολογισμού του π με διάσπαση πεδίου ορισμού φαίνονται δύο πολύ σημαντικά ζητήματα του παράλληλου προγραμματισμού: ο αμοιβαίος αποκλεισμός και ο συγχρονισμός της εκτέλεσης. Ο πρώτος αφορά μόνο το μοντέλου κοινού χώρου διευθύνσεων, όπου ο πηγαίος κώδικας της i-οστής διεργασίας / νήματος θα ήταν περίπου έτσι σε γλώσσα προγραμματισμού C:
float localsum=0;for(j=i;j<i+(N/K);j++){
  localsum+=...//Κώδικας αριθμητικού υπολογισμού}
pi+=localsum;
Στην περίπτωση αυτή προκαλούνται συνθήκες συναγωνισμού λόγω της ταυτόχρονης, μη ατομικής προσπέλασης διαφορετικών επεξεργαστών στην κοινή μεταβλητή pi, με αποτέλεσμα να πρέπει να χρησιμοποιηθούν κάποιες προγραμματιστικές δομές αμοιβαίου αποκλεισμού (mutex, κλειδώματα, σημαφόροι κλπ) προκειμένου το τελικό αποτέλεσμα να είναι εγγυημένα ορθό. Ο σωστός κώδικας θα έπρεπε να είναι περίπου ως εξής:
float localsum=0;for(j=i;j<i+(N/K);j++){
  localsum+=...//Κώδικας αριθμητικού υπολογισμού}
mutex_lock(mutexVar); //Υποθετική συνάρτηση βιβλιοθήκης
pi+=localsum;
mutex_unlock(mutexVar); //Υποθετική συνάρτηση βιβλιοθήκης
Τόσο στο μοντέλου κοινού χώρου διευθύνσεων όσο και στο μοντέλο μεταβίβασης μηνυμάτων τίθεται το θέμα του συγχρονισμού, αφού η κύρια διεργασία / νήμα θα πρέπει να περιμένει η εκτέλεση όλων των άλλων να φτάσει σε ένα συγκεκριμένο σημείο του κώδικά τους (στο συγκεκριμένο παράδειγμα να ολοκληρώσουν τον υπολογισμό και τη λειτουργία τους) προτού συνεχίσει με τη δική της εκτέλεση (π.χ. στο συγκεκριμένο παράδειγμα προτού εκτυπώσει την τιμή του π που μόλις υπολογίστηκε). Για τον σκοπό αυτό είναι απαραίτητες προγραμματιστικές δομές συγχρονισμού μεταξύ των επεξεργαστών οι οποίες ονομάζονται φράγματα εκτέλεσης. Φυσικά στο μοντέλο μεταβίβασης μηνυμάτων τα φράγματα υλοποιούνται με ανταλλαγή μηνυμάτων.

Ζητήματα μοντέλου μεταβίβαση μηνυμάτων

Στο μοντέλο μεταβίβασης μηνυμάτων συνήθως είναι πιο αποδοτική (ταχύτερη) η από κοινού αποστολή πολλαπλών μικρών διαδοχικών μηνυμάτων σε ένα μεγάλο μήνυμα μέσω του δικτύου διασύνδεσης, προκειμένου να αποδυναμωθεί η χρονική επιβάρυνση της αποστολής μηνυμάτων και να μειωθεί έτσι ο χρόνος που δαπανούν οι επεξεργαστές για επικοινωνίες. Η επικοινωνία χαμηλού επιπέδου μεταξύ δύο υπολογιστών προγραμματιστικά επιτυγχάνεται μέσω κατάλληλων κλήσεων συστήματος (έστω send() και recv(), από το API των υποδοχών που παρέχει το λειτουργικό σύστημα για διαδιεργασιακή επικοινωνία μέσω δικτύου), οι οποίες μπορούν να λειτουργήσουν είτε ανασταλτικά είτε μη ανασταλτικά. Στην ανασταλτική επικοινωνία οι διεργασίες που λαμβάνουν ή αποστέλλουν στο δίκτυο τίθενται σε αναμονή μέχρι να ληφθούν ή να αποσταλλούν αντίστοιχα δεδομένα (π.χ. αφαιρούνται από την ουρά χρονοπρογραμματισμού). Αντιθέτως στη μη ανασταλτική επικοινωνία η send() μπορεί να επιστρέψει τον έλεγχο στη διεργασία που την κάλεσε προτού ολοκληρωθεί η αποστολή (π.χ. όσο το μεταδιδόμενο μήνυμα βρίσκεται ακόμα στην προσωρινή μνήμη του πυρήνα και αναμένει να εισέλθει στο δίκτυο), ενώ η recv() μπορεί επίσης να επιστρέψει προτού ληφθεί κάτι και όταν ληφθούν πραγματικά δεδομένα η διεργασία να ειδοποιηθεί ασύγχρονα (π.χ. με ένα σήμα). Η ανασταλτική επικοινωνία είναι ευκολότερη στον προγραμματισμό και οδηγεί σε ασφαλέστερες εφαρμογές αλλά μειονεκτεί σε ταχύτητα. Η μη ανασταλτική επικοινωνία προσφέρει παραλληλισμό (αφού μία διεργασία μπορεί να συνεχίσει να εκτελείται προτού ολοκληρωθεί η επικοινωνία) με αυξημένο κόστος προγραμματιστικής δυσκολίας.
Επίσης, στη μεταβίβαση μηνυμάτων, η επικοινωνία μπορεί να είναι αποθηκευόμενη, με τον πυρήνα του λειτουργικού συστήματος σε κάθε υπολογιστή να διατηρεί μία προσωρινή μνήμη για κάθε διεργασία (όπου αποθηκεύει δεδομένα που του εστάλησαν με προορισμό την αντίστοιχη διεργασία) και την εφαρμογή να αφαιρεί μηνύματα από αυτήν την προσωρινή μνήμη κάθε φορά που καλεί τη recv(), ή μη αποθηκευόμενη, όπου κάθε παραλήπτης θα πρέπει να καλέσει τη recv() με ειδικό όρισμα, το οποίο ορίζει μία προσωρινή μνήμη στον χώρο του χρήστη όπου θα αποθηκευτούν τα ληφθέντα δεδομένα, προτού κάποιος αποστολέας του αποστείλει τα τελευταία. Στο μοντέλο πελάτη-διακομιστή υπάρχει ακόμη και το ζήτημα της αξιοπιστίας, αφού οι αιτήσεις ή οι απαντήσεις μπορεί να χαθούν σε αναξιόπιστα κανάλια. Το πρόβλημα αντιμετωπίζεται συνήθως με επιβεβαιώσεις και ακολουθιακούς αριθμούς των μηνυμάτων / πακέτων στο επίπεδο μεταφοράς.
Πολύ σημαντική είναι και η διάκριση μεταξύ σύγχρονων και ασύγχρονων επικοινωνιών, με τις πρώτες να οδηγούν σε βήμα προς βήμα συγχρονισμό μεταξύ των εμπλεκόμενων διεργασιών κατά την ανταλλαγή μηνυμάτων (π.χ. η διεργασία 1 αποστέλλει μία αίτηση και αναστέλλει τη λειτουργία της μέχρι να λάβει απάντηση, η διεργασία 2 αναστέλλεται μέχρι να λάβει την αίτηση, επεξεργάζεται την τελευταία και αποστέλλει απάντηση, με αποτέλεσμα την επανενεργοποίηση της διεργασίας 1), ενώ στις ασύγχρονες κάθε οντότητα εκτέλεσης συνεχίζει τους υπολογισμούς της μετά την αποστολή μηνύματος, χωρίς να αναστέλλει τη λειτουργία της μέχρι να λάβει απάντηση. Οι σύγχρονες επικοινωνίες μπορούν να υλοποιηθούν με ειδικές κλήσεις αποστολής (πιο «περιοριστικές» από τις αντίστοιχες ανασταλτικές, αφού η σύγχρονη send() δεν επιστρέφει μέχρι να καλέσει ο παραλήπτης την αντίστοιχη recv()), ανασταλτικές κλήσεις λήψης και κατάλληλο σχεδιασμό του προγράμματος.
Τέλος, οι επικοινωνίες μπορούν να είναι είτε ιδιωτικές (από έναν επεξεργαστή σε έναν άλλον) είτε συλλογικές (από έναν επεξεργαστή σε πολλούς, από πολλούς σε πολλούς ή από πολλούς σε έναν). Όλα αυτά συνήθως, αλλά όχι πάντοτε, είναι υπό τον άμεσο έλεγχο του προγραμματιστή και το πώς θα αξιοποιηθούν εξαρτάται από τη φύση του εκάστοτε προβλήματος προς επίλυση.

Αυτόματη παραλληλοποίηση

Στις περισσότερες περιπτώσεις ένα παράλληλο πρόγραμμα έχει σχεδιαστεί κατάλληλα και ο πηγαίος κώδικας έχει γραφεί από τον προγραμματιστή έτσι ώστε να υποστηρίζει παραλληλισμό («ρητός παραλληλισμός»). Επειδή η διαδικασία αυτή είναι επίπονη, χρονοβόρα και απαιτεί ειδικές γνώσεις εκ μέρους του προγραμματιστή, έχουν υπάρξει πολλές προσπάθειες για την αυτόματη παραλληλοποίηση τμημάτων σειριακού πηγαίου κώδικα (συνήθως επαναληπτικών βρόχων) από κατάλληλους μεταγλωττιστές. Στην περίπτωση αυτή ο προγραμματιστής συγγράφει τυπικό σειριακό κώδικα, χωρίς κλήσεις σε κάποια υποστηρικτική βιβλιοθήκη όπως των νημάτων POSIX, του OpenMP ή του MPI, και κατά τη μεταγλώττιση εντοπίζονται αυτομάτως τα σημεία που επιδέχονται παραλληλισμό. Οι περισσότεροι μεταγλωττιστές σήμερα υποστηρίζουν ανάλογες μεθόδους (π.χ. στον gcc μπορεί να δοθεί από τη γραμμή εντολών η παράμετρος «-ftree-parallelize-loops=x», όπου το x ένας ακέραιος ο οποίος δηλώνει το πλήθος των επεξεργαστών), ωστόσο ο αντικειμενικός κώδικας ο οποίος προκύπτει συνήθως δεν εκτελείται εξίσου γρήγορα με έναν κώδικα ρητού παραλληλισμού −ίσως μάλιστα να εκτελείται πιο αργά και από τον σειριακό κώδικα− ή παράγει λανθασμένα αποτελέσματα.