.
Στην πληροφορική, παράλληλος προγραμματισμός λέγεται η ανάπτυξη εφαρμογών οι οποίες εκμεταλλεύονται την ύπαρξη πολλαπλών επεξεργαστικών μονάδων σε έναν πολυεπεξεργαστή ή πολυυπολογιστή για να επιτύχουν αύξηση των υπολογιστικών επιδόσεων και μείωση του απαιτούμενου χρόνου εκτέλεσης της εφαρμογής. Επομένως ο παράλληλος προγραμματισμός μπορεί να ιδωθεί ως ειδική περίπτωση ταυτόχρονου προγραμματισμού, όπου η εκτέλεση γίνεται πραγματικά παράλληλα και όχι ψευδοπαράλληλα.
Τα παράλληλα συστήματα διακρίνονται σε πολυεπεξεργαστές κοινής μνήμης, όπου πολλαπλοί επεξεργαστές επικοινωνούν με μία κοινή μνήμη ενιαίου χώρου διευθύνσεων, και σε πολυυπολογιστές κατανεμημένης μνήμης, όπου πολλαπλά πακέτα επεξεργαστή-ιδιωτικής μνήμης, με τον δικό του χώρο διευθύνσεων το καθένα, διασυνδέονται και επικοινωνούν μεταξύ τους· και στις δύο περιπτώσεις η επικοινωνία γίνεται μέσω ενός «δικτύου διασύνδεσης». Τα μοντέλα παράλληλου προγραμματισμού για πολυεπεξεργαστές και πολυυπολογιστές είναι το μοντέλο κοινού χώρου διευθύνσεων (π.χ. πολλαπλές διεργασίες ή νήματα, OpenMP) και το μοντέλο μεταβίβασης μηνυμάτων (π.χ. PVM, MPI), αντιστοίχως. Στο πρώτο οι επεξεργαστικές μονάδες ανταλλάσσουν πληροφορίες προσπελαύνοντας κοινόχρηστες μεταβλητές στην κοινή μνήμη, ενώ στο δεύτερο ανταλλάσσοντας μηνύματα. Κάθε προγραμματιστικό μοντέλο μπορεί να εφαρμοστεί και σε σύστημα μιας αρχιτεκτονικής που δεν είναι η φυσική του (π.χ. πολυνηματικό πρόγραμμα σε πολυυπολογιστή ή πρόγραμμα MPI σε πολυεπεξεργαστή) αλλά συνήθως με χαμηλότερες επιδόσεις.
Επισκόπηση
Η ανάπτυξη εφαρμογών σε συστήματα κοινής και κατανεμημένης κοινής μνήμης συνήθως γίνεται με τη βοήθεια λογισμικού συστήματος για κατασκευή, χειρισμό και συντονισμό πολλαπλών διεργασιών ή / και νημάτων, ή με 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()), ανασταλτικές κλήσεις λήψης και κατάλληλο σχεδιασμό του προγράμματος.
Τέλος, οι επικοινωνίες μπορούν να είναι είτε ιδιωτικές (από έναν επεξεργαστή σε έναν άλλον) είτε συλλογικές (από έναν επεξεργαστή σε πολλούς, από πολλούς σε πολλούς ή από πολλούς σε έναν). Όλα αυτά συνήθως, αλλά όχι πάντοτε, είναι υπό τον άμεσο έλεγχο του προγραμματιστή και το πώς θα αξιοποιηθούν εξαρτάται από τη φύση του εκάστοτε προβλήματος προς επίλυση.
Ο νόμος του Άμνταλ
Ο Τζιν Άμνταλ το 2008
Ο νόμος του Άμνταλ χρησιμοποιείται για να διαπιστωθεί η αναμενόμενη μείωση του χρόνου εκτέλεσης από την παραλληλοποίηση ενός σειριακού προγράμματος. Φέρει το όνομα του Τζιν Άμνταλ που τον πρωτοδιατύπωσε και δηλώνει ότι η επιτάχυνση ενός προγράμματος το οποίο αξιοποιεί πολλαπλούς επεξεργαστές περιορίζεται από τον χρόνο εκτέλεσης που απαιτεί το σειριακό μέρος του προγράμματος. Ο νόμος του Άμνταλ συνήθως ορίζεται με τη βοήθεια του παρακάτω μαθηματικού τύπου:
\( \frac{1}{(1-P) + \frac{P}{N}} \)
Στον τύπο αυτόν η μεταβλητή P δηλώνει το ποσοστό των συνολικών υπολογισμών του προγράμματος οι οποίοι μπορούν να παραλληλοποιηθούν και η μεταβλητή Ν το πλήθος των διαθέσιμων επεξεργαστών. Για παράδειγμα, αν το P είναι 90% (0,9), τότε το (1-P) είναι 10% και το ολικό πρόγραμμα (σύμφωνα με τον τύπο του Άμνταλ) μπορεί να επιταχυνθεί το πολύ 10 φορές, όσους επεξεργαστές και αν χρησιμοποιήσουμε. Γι' αυτόν τον λόγο η παράλληλη επεξεργασία είναι χρήσιμη μόνο για περιορισμένο πλήθος επεξεργαστών (μικρό N) ή για προβλήματα με πολύ μεγάλη τιμή P (π.χ. η πρόσθεση δύο ν-διάστατων διανυσμάτων έχει P 100%, αφού πρακτικώς δεν υπάρχει αποκλειστικά σειριακό τμήμα στον αλγόριθμο).
Αυτόματη παραλληλοποίηση
Στις περισσότερες περιπτώσεις ένα παράλληλο πρόγραμμα έχει σχεδιαστεί κατάλληλα και ο πηγαίος κώδικας έχει γραφεί από τον προγραμματιστή έτσι ώστε να υποστηρίζει παραλληλισμό («ρητός παραλληλισμός»). Επειδή η διαδικασία αυτή είναι επίπονη, χρονοβόρα και απαιτεί ειδικές γνώσεις εκ μέρους του προγραμματιστή, έχουν υπάρξει πολλές προσπάθειες για την αυτόματη παραλληλοποίηση τμημάτων σειριακού πηγαίου κώδικα (συνήθως επαναληπτικών βρόχων) από κατάλληλους μεταγλωττιστές. Στην περίπτωση αυτή ο προγραμματιστής συγγράφει τυπικό σειριακό κώδικα, χωρίς κλήσεις σε κάποια υποστηρικτική βιβλιοθήκη όπως των νημάτων POSIX, του OpenMP ή του MPI, και κατά τη μεταγλώττιση εντοπίζονται αυτομάτως τα σημεία που επιδέχονται παραλληλισμό. Οι περισσότεροι μεταγλωττιστές σήμερα υποστηρίζουν ανάλογες μεθόδους (π.χ. στον gcc μπορεί να δοθεί από τη γραμμή εντολών η παράμετρος «-ftree-parallelize-loops=x», όπου το x ένας ακέραιος ο οποίος δηλώνει το πλήθος των επεξεργαστών), ωστόσο ο αντικειμενικός κώδικας ο οποίος προκύπτει συνήθως δεν εκτελείται εξίσου γρήγορα με έναν κώδικα ρητού παραλληλισμού −ίσως μάλιστα να εκτελείται πιο αργά και από τον σειριακό κώδικα− ή παράγει λανθασμένα αποτελέσματα.
Γλώσσες ταυτόχρονου προγραμματισμού
Πέρα από τις, συμπληρωματικές μεταξύ τους, λύσεις της αυτόματης παραλληλοποίησης και της προσθήκης εξειδικευμένων βιβλιοθηκών και επεκτάσεων σε συνήθεις γλώσσες προγραμματισμού όπως η C ή η Fortran, κατά καιρούς έχουν εμφανιστεί και ορισμένες γλώσσες προγραμματισμού σχεδιασμένες από τη βάση τους με στόχο την εγγενή υποστήριξη ταυτοχρονισμού, είτε παράλληλου είτε ψευδοπαράλληλου. Ακόμη και συνηθισμένες γλώσσες γενικού σκοπού παρέχουν κάποια στοιχειώδη εγγενή υποστήριξη για ταυτοχρονισμό και αμοιβαίο αποκλεισμό (π.χ. η Java και η C#), αλλά οι εξειδικευμένες γλώσσες ταυτόχρονου προγραμματισμού είναι βελτιστοποιημένες συγκεκριμένα προς αυτή την κατεύθυνση.
Έτσι π.χ. η Cilk αποτελεί μία ελαφρώς τροποποιημένη εκδοχή της C, για παράλληλο προγραμματισμό στο μοντέλο κοινού χώρου διευθύνσεων, με επιπρόσθετες λέξεις-κλειδιά οι οποίες αποτελούν σύντομες οδηγίες πολυνημάτωσης και συγχρονισμού του προγραμματιστή προς τον μεταγλωττιστή. Με το μεταγλωττιζόμενο πρόγραμμα συνδέεται η βιβλιοθήκη χρόνου εκτέλεσης της Cilk η οποία, όταν το πρόγραμμα εκτελείται, αναλαμβάνει να διαμοιράσει αυτομάτως τον φόρτο, να δημιουργήσει, να χρονοπρογραμματίσει και να συντονίσει νήματα κλπ, ανάλογα με τις τρέχουσες συνθήκες. Η υλοποίηση της βιβλιοθήκης περιέχει μία ενσωματωμένη διασύνδεση νημάτων επιπέδου χρήστη χαμηλής χρονικής επιβάρυνσης και χαμηλού κόστους διαχείρισης, εκτελούμενων σε τόσα νήματα πυρήνα όσοι είναι οι διαθέσιμοι επεξεργαστές κατά τον χρόνο εκτέλεσης, επιτρέποντας έτσι την σχεδόν αυτοματοποιημένη κατασκευή γρήγορων παράλληλων προγραμμάτων με εκατοντάδες νήματα.
Ωστόσο οι εξειδικευμένες αυτές γλώσσες προγραμματισμού δεν χρησιμοποιούνται ευρέως καθώς έχει επικρατήσει η λύση των συνηθισμένων μεταγλωττιστών / γλωσσών με την προσθήκη τυποποιημένων βιβλιοθηκών επέκτασης (π.χ. νήματα POSIX, OpenMP, MPI κλπ).
Νεότερες γλώσσες προγραμματισμού, όπως η Haskell, η Scala και η Erlang, προσφέρουν υψηλότερου επιπέδου τρόπους προγραμματισμού, χωρίς να απαιτείται ο προγραμματιστής να ασχολείται με έννοιες όπως τα νήματα και ο συντονισμός μεταξύ τους. Ειδικότερα, η Scala και η Erlang βασίζονται στο μοντέλο Actor.
Hellenica World - Scientific Library
Από τη ελληνική Βικιπαίδεια http://el.wikipedia.org . Όλα τα κείμενα είναι διαθέσιμα υπό την GNU Free Documentation License
