Εισαγωγή στη Παράλληλη Επεξεργασία

Η εισαγωγή αυτή είναι βασισμένη στο tutorial "Introduction to Parallel Computing" του Blaise Barney, Lawrence Livermore Laboratory, USA. Επίσης έχει προστεθεί υλικό από το βιβλίο του A.S. Tanenbaum "Structured Computer Organization", τη Wikipedia, καθώς και από αρκετές πηγές του Διαδικτύου. Μετάφραση και προσαρμογή: Κ.Γ. Μαργαρίτης, Εργαστήριο Παράλληλης Κατανεμημένης Επεξεργασίας, Τμήμα Εφαρμοσμένης Πληροφορικής, Πανεπιστήμιο Μακεδονίας.

Περιεχόμενα

  1. Περίληψη
  2. Επισκόπηση
  3. 'Εννοιες και Ορολογία
  4. Αρχιτεκτονικές Παράλληλων Υπολογιστών
  5. Υποστήριξη Παράλληλου Προγραμματισμού
  6. Μοντέλα Παράλληλου Προγραμματισμού
  7. Ανάπτυξη Παράλληλων Προγραμμάτων
  8. Σχεδιασμός Παράλληλων Προγραμμάτων
  9. Απόδοση Παράλληλων Προγραμμάτων
  10. Παραδείγματα Παράλληλης Επεξεργασίας
  11. Αναφορές και Περισσότερες Πληροφορίες
Περίληψη


Αυτή η εισαγωγική παρουσίαση καλύπτει τα βασικά της παράλληλης επεξεργασίας. Αρχίζει με μια σύντομη επισκόπιση, ορισμένες βασικές έννοιες και ορολογία, και συνεχίζει με τα θέματα των παράλληλων αρχιτεκτονικών και των μοντέλων παράλληλου προγραμματισμού. Ακολουθεί μια συζήτηση για ζητήματα σχεδιασμού παραλλήλων προγραμμάτων.  Η τελευταία ενότητα εξετάζει μερικά παραδείγματα παράλληλης επεξεργασίας.
Επισκόπιση

Τι είναι Παράλληλη Επεξεργασία;

arch
Η Συντρέχουσα (Concurrent) Επεξεργασία δίνει έμφαση στο διαμοιρασμό ενός ή περιορισμένων πόρων μεταξύ πολλών ανεξάρτητων εργασιών που εκτελούνται ταυτόχρονα. Οι εργασίες είναι συνήθως σχετικά λίγες και ανόμοιες, και η επικοινωία μεταξύ τους είναι μη-προκαθορισμένη (μη-ντετερμινιστική) και βασίζεται σε συμβάντα (events). Χαρακτηριστικό πεδίο η ανάπτυξη λειτουργικών συστημάτων και πολυνηματικών εφαρμογών σε ένα υπολογιστή.

Η Παράλληλη (Parallel) Επεξεργασία δίνει έμφαση στην ταυτόχρονη εκτέλεση πολλών αλληλοεξαρτώμενων εργασιών σε πολλούς όμοιους πόρους για την επίλυση ενός προβλήματος. Οι εργασίες είναι συνήθως σχετικά πολλές, σχετικά όμοιες μεταξύ τους, και η επικοινωνία ακολουθεί συνήθως κάποιο προκαθορισμένο ή κανονικό πρότυπο. Χαρακτηριστικό πεδίο η ανάπτυξη επιστημονικών και βιομηχανικών εφαρμογών για την επεξεργασία πολλών δεδομένων / εκτέλεση πολλών υπολογισμών.

Η Κατανεμημένη (Distributed) Επεξεργασία δίνει έμφαση στην επικοινωνία πολλών ανεξάρτητων και ανόμοιων διεργασιών που εκτελούνται ταυτόχρονα σε ξεχωριστά σύνολα πόρων και όπου η επικοινωνία είναι μη-ντετερμινιστική, ίσως αναξιόπιστη και προκαλεί σημαντική επιβάρυνση. Χαρακτηριστικό πεδίο η ανάπτυξη διαδικτυακών εφαρμογών μεγάλης κλίμακας, με χρήση πολλαπλών εξειδικευμένων διακομιστών ή και ομότιμης τεχνολογίας.

Υπάρχουν σημαντικές αλληλεπικαλύψεις αλλά  και διαφορές. Σταδιακά όμως τα τρία μοντέλα υπολογισμού οδηγούνται σε σύγκλιση, όπως αυτό γίνεται φανερό στις τεχνολογίες Πλέγματος (Grid) και Νέφους (Cloud).


Επισκόπιση

Γιατί Παράλληλη Επεξεργασία;


hyper

mem1
mem2
power intel

Έννοιες και Ορολογία

Αρχιτεκτονική von Neumann



Έννοιες και Ορολογία

Κλασσική Ταξινόμηση Flynn

Απλή Εντολή, Απλό Δεδομένο (ΑΕΑΔ, SISD):
  • Ο τυπικός σειραικός (μη-παράλληλος) υπολογιστής
  • Απλή εντολή: μόνο μια ροή εντολών εκτελείται από τη CPU σε κάθε χρονική στιγμή (δε λαμβάνεται υπ' όψη ο Παραλληλισμός Επιπέδου Εντολής,  ILP)
  • Απλό δεδομένο: μόνο μια ροή δεδομένων υφίσταται επεξεργασία σε κάθε χρονική στιγμή
  • Προσδιοριστική (Deterministic) εκτέλεση
  • Το παλαιότερο και, μέχρι πρόσφατα, το επικρατέστερο μοντέλο
  • Παραδείγματα: τα περισσότερα PCs, σταθμοί εργασίας και κεντρικοί υπολογιστές
SISD
Απλή Εντολή, Πολλαπλά Δεδομένα (ΑΕΠΔ, SIMD):
  • Συνήθως υπάρχει μια κεντρική μονάδα ελέγχου (CU), πολλαπλές μονάδες επεξεργασίας (PUs) σχετικά μικρής ισχύος που  συνδέονται με τη μνήμη και μεταξύ τους με εσωτερικό δίκτυο διασύνδεσης
  • Δύο βασικές εκδοχές: Επεξεργαστές Πινάκων (Array Processors) και Ανυσματικοί Επεξεργαστές (Vector Processors)
  • Απλή εντολή: όλες οι μονάδες επεξεργασίας (Processing Units, PUs) εκτελούν την ίδια εντολή σε κάθε χρονική στιγμή
  • Πολλαπλά δεδομένα: κάθε PU επεξεργάζεται διαφορετική ροή δεδομένων
  • Σύγχρονη (κεντρικά συγχρονιζόμενη) και προσδιοριστική εκτέλεση
  • Συστήματα ειδικού σκοπού (και συν-επεξεργαστές) για προβλήματα με μεγάλο βαθμό κανονικότητας (πχ επεξεργασία εικόνας, πράξεις πινάκων).
  • Πρόκειται για εξειδικευμένη μορφή παραλληλισμού, η οποία βασίζεται κυρίως σε επεμβάσεις στο υλικό και την αρχιτεκτονική. Επίσης μπορεί να ειδωθεί ως ειδική περίπτωση της κατηγορίας MIMD.
  • Βρίσκει σημαντικές εφαρμογές στην επαναλαμβανόμενη  'ομαλή' επεξεργασία πινακοποιημένων δεδομένων (συμβολοσειρές, εικόνες, αλφαριθμητικά, βιολογικά δεδομένα) καθώς και ροών δεδομένων (ήχος, πακέτα δικτύου, σήμα, video).
  • Οι Μονάδες Επξεργασίας Γραφικών (Graphic Processing Units, GPUs) είναι το πιο πετυχημένο παράδειγμα SIMD αρχιτεκτονικής σήμερα. Παρακάτω φαίνεται ένα τέτοιο παράδειγμα.


SIMD

Πολλαπλές Εντολές, Απλό Δεδομένο (ΠΕΑΔ, MISD):
  • Μια ροή δεδομένων τροφοδοτεί πολλαπλές PUs
  • Κάθε PU επεξεργάζεται τα δεδομένα ανεξάρτητα μέσω ανεξάτρητων ροών εντολών
  • Ελάχιστα πρακτικά παραδείγματα, όπως ο πειραματικός υπολογιστήC.mmp του  πανεπιστημίου Carnegie-Mellon C.mmp (1971)
  • Μερικές πιθανές χρήσεις:
    • πολλαπλά φίλτρα συχνοτήτων που επενεργούν σε ένα σήμα
    • πολλαπλοί αλγόριθμοι κρυπτογραφίας που επενεργούν σε ένα κρυπτογραφημένο κείμενο


MISD

Πολλαπλές Εντολές, Πολλαπλά Δεδομένα (ΠΕΠΔ, MIMD):
  • Ο πλέον διαδεδομένος τύπος παράλληλου υπολογιστή. Σταδιακά, με την  έλευση των πολυ-πύρηνων συστημάτων, τείνει να καταστεί ο πλέον διαδεδομένος τύπος υπολογιστή. Συνήθως υπάρχουν πολλαπλούς επεξεργαστές (CPUs) που  συνδέονται μεταξύ τους είτε με δίαυλο και μοιραζόμενη μνήμη είτε με εσωτερικό δίκτυο και κατανεμημένη μνήμη είτε πρόκειται για κοινούς υπολογιστές συνδεδεμένους μέσω δικτύου.
  • Δύο βασικές εκδοχές: Μοιραζόμενης Μνήμης ή Πολυ-επεξεργαστές (Shared Memory, Multi-processors) και Κατανεμημένης Μνήμης ή Πολυ-υπολογιστές (Distributed Memory, Multi-computers)
  • Πολλαπλές εντολές: κάθε CPU μπορεί να εκτελεί διαφορετική ροή εντολών ή διαφορετική εντολή από την ίδια ροή εντολών 
  • Πολλαπλά δεδομένα: κάθε CPU μπορεί να επεξεργάζεται διαφορετική ροή δεδομένων ή διαφορετικό δεδομένο από την ίδια ροή
  • Η εκτέλεση συνήθως είναι ασύγχρονη (ένα ρολόι ανά επεξεργαστή) και ίσως μη-προσδιοριστική (αν δεν προβλεφθεί επαρκής συντονισμός)
  • Η συντριπτική πλειονότητα των παράλληλων συστημάτων εμπίπτει σε αυτή τη κατηγορία, με την οποία ασχολούμαστε στο υπόλοιπο κείμενο. Διαγράμματα και παραδείγματα θα δούμε στις επόμενες ενότητες
  • Παραδείγματα:
    • Αρχιτεκτονικές Μοιραζόμενης Μνήμης (Shared Memory): Πολυ-πύρηνα συστήματα (Multi-core), Συμμετρικοί Πολυ-Επεξεργαστές (Symmetric Multi-Processors)
    • Αρχιτεκτονικές Κατανεμημένης Μνήμης (Distributed Memory): Networks of Workstations (NOWs), Συστοιχίες (Clusters), Κατανεμημένοι Υπολογιστές (τύπου BOINC).
    • Υβριδικά Συστήματα: Αποτελούν τη μεγάλη πλειοψηφία των σύγχρονων υπερυπολογιστών και συνδυάζουν τις παραπάνω κατηγορίες. Θα αναλυθούν παρακάτω.


MIMD



Έννοιες και Ορολογία

Γενική Ορολογία

Παρακάτω εμφανίζονται μερικοί συχνά εμφανιζόμενοι όροι της παράλληλης επεξεργασίας. Μερικοί έχουν ήδη εμφανιστεί, οι περισσότεροι αναλύονται αργότερα στο κείμενο:
Κόμβος (Node)
Ένας αυτόνομος υπολογιστής (που θα μπορούσε να λειτουργήσει αυτόνομα, αν δεν ανήκε σε ένα παράλληλο σύστημα). Συνήθως περιέχει πολλαπλούς πυρήνες ή συνεπεξεργαστές (GPUs).
Κεντρική Μονάδα Επεξεργασίας (Central Processing Unit, CPU) / Πυρήνας (Core)
Μέχρι πριν μερικά χρόνια η CPU είχε τη μορφή που ορίζεται στο Μοντέλο Von Neuman (SISD), με τις εσωτερικές επεκτάσεις των τεχνολογιών Παραλληλισμού Επιπέδου Εντολής (Instruction Level Parallelism), που παρουσιάστηκαν σύντομα παραπάνω. Όμως πλέον η CPU έχει ταυτιστεί με την έννοια του Πυρήνα (Core), ενώ ένα ολοκληρωμένο κύκλωμα CPU πλέον περιλαμβλανει 4, 6 ή και παραπάνω Πυρήνες (άρα πλήρεις CPUs). Αυτές διασυνδέονται με εσωτερικό δίαυλο και μοιράζονται τα υψηλότερα επίπεδα της Ιεραχίας Κρυφής Μνήμης. Κάθε Κόμβος (Node) ενός Παράλληλου συστήματος συνήθως περιέχει 1 ή περισσότερα ολοκληρωμένα κυκλώματα CPUs, άρα αρκετούς Πυρήνες. Η εικόνα που ακολουθεί δείχνει μια τυπική συστοιχία με πολυπύρηνους κόμβους.

node


Μονάδα Επεξεργασίας (Processing Unit, PU)
Ένας συνδυασμός ALU και Τοπικής Μνήμης. Συνήθως χρησιμοποιείται σε συστήματα SIMD όπου μια μεγάλη ομάδα PEs ελέγχονται από μια Μονάδα Ελέγχουυ και εκτελούν τους ίδιους υπολογισμούς σε διαφορετικά δεδομένα. Τυπικό παράδειγμα οι επεξεργαστές των GPUs.
Μονάδα Επεξεργασίας Γραφικών (Graphics Processing Unit, GPU)
Συν-επεξεργαστές τύπου SIMD που διαθέτουν αρκετές εκατοντάδες PUs οργανωμένα σε ομάδες (blocks) με κοινή μνήμη. Τα PUs μπορούν να προσπελάσουν τα δεδομένα στη μνήμη τους σε μορφή ανύσματος ή πολυδιάστατου πίνακα. Οι GPUs επιτυγχάνουν εντυπωσιακές αποδόσεις στην ομαλή (χωρίς σημαντικές διακλαδώσεις ή πρόσβαση σε ανώτερα επίπεδα της ιεραρχίας μνήμης) επεξεργασία μεγάλου όγκου πινακοποιημενων δεδομένων. Χρησιμοποιούνται ως συνεπεξεργαστές σε σύγχρονα υβριδικά παράλληλα συστήματα. Παρακάτω φαίνεται το  διάγραμμα μιας τυπικής GPU (αριστερά) και ενός block PUs (δεξιά).


gpu01
gpu02

Δίκτυο Διασύνδεσης (Interconnection Network)
Tα εξαρτήματα του παράλληλου υπολογιστή που είναι υπεύθυνα για την υλοποίηση της επικοινωνίας μεταξύ επεξεργαστών ή επεξεργαστών και μνήμης ή ολόκληρων υπολογιστών. Το δίκτυο διασύνδεσης συνήθως μπορεί να είναι ένας απλός δίαυλος (bus) ή μια τυπική υποδομή τοπικού δικτύου. Όμως σε μεγαλύτερα παράλληλα συστήματα το δίκτυο διασύνδεσης είναι αρκετά περίπλοκες κατασκευές όπως crossbar switches, διακοπτικά συστήματα πολλαπλών σταδίων, πλέγματα, δακτύλιοι, δένδρα, υπερκύβοι διαφόρων διαστάσεων κλπ.
Εργασία (Task)
Μια λογικά διακριτή ενότητα υπολοιστικής εργασίας η που εκτελείται από ένα επεξεργαστή. Λογικά εμφανίζεται ως πρόγραμμα, υπο-πρόγραμμα (sub-routine), διαδικασία (procedure), συνάρτηση (function) ή μέθοδος (method).  Συνήθως υλοποιείται σαν διεργασία (process) ή νήμα (thread)
Παράλληλη Εργασία (Parallel Task)
Μια εργασία γραμμένη έτσι ώστε να μπορεί να εκτελεστεί ορθά από πολλαπλούς επεξεργαστές
Σειραική - Ακολουθιακή Εκτέλεση (Serial - Sequential Execution)
Συμβατική εκτέλεση ενός προγράμματος, μια εντολή κάθε φορά, όπως συμβαίνει σε συστήματα ενός επεξεργαστή (δε λαμβάνεται υπ' όψη ο Παραλληλισμός Επιπέδου Εντολής, ILP). Όμως, σχεδόν όλα τα παράλληλα προγράμματα έχουν κάποιο τμήμα που απαιτεί ακολουθιακή εκτέλεση
Παράλληλη Εκτέλεση (Parallel Execution)
Εκτέλεση ενός προγράμματος με χρήση πολλαπλών (παράλληλων) εργασιών, έτσι ώστεοι εργασίες μπορούν την ίδια χρονική στιγμή να εκτελούν ίδιο ή διαφορετικό τμήμα του προγράμματος
Μοιραζόμενη Μνήμα (Shared Memory)
Από πλευράς υλικού, πρόκειται για παράλληλη αρχιτεκτονική, υποκατηγορία MIMD, όπου όλοι οι επεξεργαστές έχουν άμεση (συνήθως μέσω διαύλου) και ισότιμη πρόσβαση σε κοινή φυσική μνήμη. Από πλευράς προγραμματιστικού μοντέλου, ο όρος περιγράφει ένα σύστημα όπου όλες οι παράλληλες εργασίες έχουν ενιαίο χώρο φυσικών διευθύνσεων ("βλέπουν" λογικά την ίδια μνήμη) ανεξάρτητα από τη φυσική θέση της μνήμης (συνήθως η προσπέλαση στις θέσεις μνήμης δεν είναι ακριβώς ισότιμη)
Κατανεμημένη Μνήμη (Distributed Memory)
Από πλευράς υλικού, πρόκειται για παράλληλη αρχιτεκτονική, υποκατηγορία ΜIMD, όπου ο κάθε επεξεργαστής έχει άμεση πρόσβαση σε ιδιωτική τοπική μνήμη, ενώ η πρόσβαση στη μνήμη άλλων επεξεργαστών επιτυγχλανεται συνήθως μέσω δικτύου (ειδικού ή γενικού). Από πλευράς προγραμματιστικού μοντέλου, ο όρος περιγράφει ένα σύστημα όπου οι παράλληλες διεργασίες έχουν διαφορετικό χώρο φυσικών διευθύνσεων ("βλέπουν" λογικά  ξεχωριστή μνήμη) και πρέπει να χρησιμοποιήσουν ειδικές προγραμματιστικές δομές για να προσπελάσουν δεδομένα που "βλέπουν" άλλες εργασίες
Επικοινωνία (Communication)
Συνήθως οι παράλληλες διεργασίες πρέπει να ανταλλάξουν δεδομένα. Υπάρχουν δύο βασικοί τρόποι επικοινωνίας δεδομένων: είτε έμμεσα, μέσω κοινών θέσεων μνήμης (μοιραζόμενη μνήμη) ή άμεσα, μέσω μεταβίβασης ων δεδομένων μέσω δικτύου. Ο όρος επικοινωνία εργασιών ή δεδομένων χρησιμοποιείται και στις δύο περιπτώσεις. Συνήθως η επικοινωνία επιφέρει σχετικές καθυστερήσεις καθώς κατά την ανταλλαγή δεδομένων πιθανώς κάποια παράλληλη εργασία να πρέπει να αναμένει δεδομένα για να συνεχίσει την εκτέλεσή της
Συγχρονισμός (Synchronization)
Συντονισμός της εκτέλεσης των (ασύγχρονων) παραλλήλων εργασιών σε πραγματικό χρόνο, που συνήθως επιτυγχάνεται μέσω επικοινωνίας (αρχιτεκτονικές MIMD). Συνήθως η κάθε παράλληλη εργασία περιέχει στο κώδικά της δομές συγχρονισμού, οι οποίες απαιτούν την επικοινωνία με άλλες εργασίες πριν η εργασία συνεχίσει την εκτέλεσή της. Ο συχγρονισμός υπονοεί οτι τουλάχιστο μια εργασία θα αναμένει, άρα ο αντίστοιχος επεξεργαστής θα είναι άεργος. Στις αρχιτεκτονικές SIMD η εκτέλεση των εντολών στις μονάδες επεξεργασίας είναι εξ' ορισμού σύγχρονη
Κοκκιότητα (Granularity)
Στη παράλληλη επεξεργασία, η κοκκιότητα είναι ένα μέτρο του λόγου υπολογισμού προς επικοινωνία (computation to communication rate) Από πλευράς υλικού ο υπολογιστικός φόρτος  και η επικοινωνία εξαρτώνται από την ισχύ του επεξεργαστή και τη ταχύτητα του δικτύου ή διαύλου. Επομένως, με εξαίρεση εξειδικευμένα συστήματα, τυπικά η επικοινωνία είναι πολύ πιο δαπανηρή από τον υπολογισμό, ιδιαίτερα στα συσήματα κατανεμημένης μνήμης
Σύνδεση (Coupling)
Στη παράλληλη επεξεργασία, η σύνδεση είναι ένα μέτρο της εγγύτητας των υπολογιστικών μονάδων
Μαζικά Παράλληλος Επεξεργαστής  (Massively Parallel Processor)
Αναφέρεται σε ειδικά παράλληλα συστήματα με πολύ μεγάλο αριθμό επεξεργαστών - για τη συγκεκριμένη τεχνολογία (συντομογραφία ΜPP). Συνήθως εννοούμε χιλιάδες επεξεργαστές. Τα δικτυα διασύνδεσης των MPPs προφανώς δεν μπορεί να είναι ούτε συμβατικοί δίαυλοι ούτε και τοπικά δίκτυα διαχωρισμός από συστοιχίες, clusters). Συνήθως χρησιμοποιούνται ιεραρχικά συνδεδεμένα συστήματα μεταγωγής ή ειδικά διασυνδετικά δίκτυα.

Πράξεις Κινητής Υποδιαστολής Ανά δευτερόλεπτο (Floating Poinf Operations Per Second, FLOPS)
Συνηθισμένο μέτρο σύγκρισης της απόδοσης παράλληλων υπολογιστών. Το μέτρο προκύπτει ως μέσος όρος εκτέλεσης μιας συγκεκριμένης ομάδας μετρο-προγραμμάτων (benchmarks) και αποτελεί το βασικό κριτήριο κατάταξης στο Top500. Ακολουθεί σχετικός πίνακας.

flops

Επιτάχυνση (Speedup)
Η επιτάχυνση ενός παραλληλοποιημένου προγράμματος ορίζεται ως ο λόγος:

χρόνος ακολουθιακής εκτέλεσης
χρόνος παράλληλης εκτέλεσης

Εννοείται οτι η επιτάχυνση ορίζεται για εκτέλεση μιας εφαρμογής συγκεκριμένου μεγέθους προβλήματος με συγκεκριμένο αριθμό επεξεργαστών και ίδιο αλγόριθμο και δεδομένα όπως η ακολουθιακή. Είναι ένας από τους απλούστερους και ευρύτερα χρησιμοποιούμενους δείκτες απόδοσης στη παράλλη επεξεργασία. Γραμμική (Linear) ονομάζεται η επιτάχυνση όταν αυξάνεται ανάλογα με τον αριθμό των χρησιμοποιούμενων επεξεργαστών, και αποτελεί μέτρο ιδανικής παραλληλοποίησης.

Επιβάρυνση (Overhead)
Ο χρόνος παράλληλης εκτέλεσης που δαπανάται για το συντονισμό των παραλλήλων εργασιών σε αντίθεση με τον χρόνο ωφέλιμου υπολογισμού (δηλαδή αυτόν που εκτελεί το πρόγραμμα και στην ακολουθιακή του μορφή). Η επιβάρυνση εξαρτάται από παράγοντες όπως:

Κόστος και Ωφελιμότητα (Cost and Utilization)
Το κόστος ορίζεται ως το γινόμενο: 
χρόνος (παράλληλης ή ακολουθιακής) εκτέλεσης * αριθμός επεξεργαστών (1 για ακολουθιακή εκτέλεση)
Η ωφελιμότητα ορίζεται ως [ακολουθιακό κόστος / παράλληλο κόστος]% ή αλλιώς

[επιτάχυνση / αριθμός επεξεργαστών]%

και δίνει ένα ποσοτικό μέτρο της συνολικής επιβάρυνσης της παράλληλης εκτέλεσης. Ωφελιμότητα 100% σημαίνει μηδενική επιβάρυνση, δηλαδή ιδανική παραλληλοποίηση.

Μεγέθυνση (Sizeup)
Αναφέρεται στη μεταβολή της επιτάχυνσης μιας παράλληλης εφαρμογής όταν αυξάνεται το μέγεθος του προβλήματος αλλά διατηρείται σταθερός ο αριθμός των επεξεργαστών (ή το μέγεθος του προβλήματος διατηρείται σταθερό και μειώνεται ο αριθμός των επεξεργαστών).  Σταδιακά η ωφελιμότητα προσγεγγίζει ένα μέγιστο, δηλαδή οι δυνατότητες παραλληλισμού της συγκεκριμένης λύσης τείνουν να εξαντληθούν. Στη συνέχεια η παραπέρα αύξηση του μεγέθους του προβλήματος (ή μείωση του αριθμού των επεξεργαστών) οδηγεί σε αύξηση του χρόνου εκτέλσης.
Κλιμάκωση (Scaleup)
Αναφέρεται στη δυνατότητα μιας παράλληλης εφαρμογής να διατηρήσει σταθερή επιτάχυνση με την αύξηση του μεγέθους του επιλυόμενου προβλήματος και αντίστοιχη αύξηση του αριθμού των επεξεργαστών.

Οι παράγοντες που συνεισφέρουν σε ικανοποιητική μεγέθυνση και κλιμάκωση σχετίζονται με το υλικό και το λογισμικό: 


Αρχιτεκτονικές Παράλληλων Υπολογιστών

Υπολογιστές Μοιραζόμενης Μνήμης ή Πολυ-Επεξεργαστές

Γενικά Χαρακτηριστικά:
Shared memory architecture shmem
Shared Memory

Πλεονεκτήματα:

Μειονεκτήματα:

Ομοιόμορφη και Ανομοιόμορφη Προσπέλαση Μνήμης (Uniform and Non-Uniform Memory Access, UMA):

numa
Shared Memory NUMA

Συνοχή Κρυφής Μνήμης (Cache Cohernece)

Στα σύγχρονα πολυπύρηνα συστήματα, σε κάθε CPU (core) εννοείται η ύπαρξη μνήμης Cache, με στόχο την απρόσκοπτη τροφοδοσία της CPU με δεδομένα και τη μείωση της κυκλοφορίας στο δαυλο μνήμης. O όρος συνοχή κρυφής μνήμης σημαίνει οτι όταν ένας επεξεργαστής ενημερώνει μια θέση της κρυφής του μνήμης, τότε όλοι οι άλλοι επεξεργαστές - και η κύρια μνήμη - ενημεώνονται έγκαιρα γι' αυτή τη τροποποίηση. Για τα συστήματα Shared memory UMA η συνοχή κρυφής μνήμης είναι δεδομένη και  επιτυγχάνεται σε επίπεδο υλικού, διαφανώς για το προγραμματιστή. Υπάρχουν δύο βασικο αλγόριθμοι. O write-through αλγόριθμος Snooping Cache, ο οποίος είναι απλός αλλά δαπανηρός, ειδικά όσο ο αριθμός των CPUs αυξάνει. O write-back αλγόριθμος MESI (Modified, Exclusive, Shared, Invalid) είναι ο πιο δημοφιλής αλγόριθμος. Για τα συστήματα Shared Memory NUMA η συνοχή κρυφής μνήμης δεν είναι δεδομένη, αλλά σταδιακά γίνεται απαραίτητη. Το πιο συνηθισμένο πρωτόκολλο στηρίζεται σε καταλόγους (Directory Based).

Αρχιτεκτονικές Παράλληλων Υπολογιστών 

Υπολογιστές Κατανεμημένης Μνήμης ή Πολυ-Υπολογιστές

Γενικά Χαρακτηριστικά:

Distributed memory architecture

distmem

Πλεονεκτήματα:

Μειονεκτήματα:

Κατανεμημένη Μοιραζόμενη Μνήμη (Distributed Shared Memory)

Από αρχιτεκτονική άποψη, αν το κόστος επικοινωνίας δεν είναι πολύ μεγαλύτερο από αυτό της πρόσβασης στη μοιραζόμενη μνήμη, ένα σύστημα Κατανεμημένης  Μνήμης μπορεί να αντιμετωπιστεί ως σύστημα Μοιραζόμενης Μνήμης NUMA. Γίνονται προσπάθειες για την ανάπτυξη τεχνικών σε επίπεδο υλικού αλλά και λογισμικού για την ανάπτυξης  ενός ενοποιημένου συστήματος (πχ Κατανεμημένης Μοιραζόμενης Μνήμης, Distributed Shared Memory, DSM) αλλά ακόμη η επιβάρυνση του υλικού, του λειτουργικού συστήματος ή του συστήματος εκτέλεσης είναι σημαντική.



Αρχιτεκτονικές Παράλληλων Υπολογιστών

Υβριδικοί Παράλληλοι Υπολογιστές

Hybrid memory architecture

hybrid2

hybrid03

google
bluegene
         top500

Υποστήριξη Παράλληλου Προγραμματισμού


Μοντέλα Παράλληλου Προγραμματισμού

Επισκόπιση

Μοντέλα Παράλληλου Προγραμματισμού

Μοντέλο Διεργασιών


Μοντέλα Παράλληλου Προγραμματισμού

Μοντέλο Νημάτων

Υλοποιήσεις:

Και στις δύο περιπτώσεις ο προγραμματιστής είναι υπεύθυνος για τον καθορισμό του παραλληλισμού. Το σύστημα εκτέλεσης της εφαρμογής μπορεί να συμμετέχει στη διαχείριση (User Level Threads) ή εναλλακτικά η διαχείριση γίνεται εξ' ολοκλήρου από το λειτουργικό σύστημα (Kernel Level Threads). Στη περίπτωση των User Level Threads, μπορεί απλά να έχουμε τυπική συντρέχουσα επεξεργασία σε επίπεδο εικονικής ή φυσικής μηχανής. Στη περίπτωση των Kernel Level Threads, η εφαρμογή μπορεί να εκτελεστεί συνδρομικά ή παράλληλα, ανάλογα με τη φυσική μηχανή που διαχειρίζεται ο πυρήνας.

 
Μοντέλα Παράλληλου Προγραμματισμού

Μοντέλο Μεταβίβασης Μηνυμάτων

Υλοποιήσεις:


Μοντέλα Παράλληλου Προγραμματισμού

Υβριδικό Μοντέλο

hybrid_model


Ανάπτυξη Παράλληλων Προγραμμάτων

Απλό Πρόγραμμα Πολλαπλά Δεδομένα (Single Program Multiple Data, SPMD):

if (myid == ...) then {...} else {...}

Ετσι εκτελείται το ίδιο πρόγραμμα, όχι όμως αναγκαστικά η ίδια λειτουργία (δηλαδή το ίδιο υποπρόγραμμα), από όλες τις εργασίες. Επίσης κάθε εργασία επίσης μπορεί να επεξεργάζεται διαφορετικά υποσύνολα δεδομένων.


Ανάπτυξη Παράλληλων Προγραμμάτων

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


Σχεδιασμός Παράλληλων Προγραμμάτων

Κατανόηση του Αλγορίθμου και του Προγράμματος

Σχεδιασμός Παράλληλων Προγραμμάτων

Επιμερισμός

Επιμερισμός Δεδομένων:

Επιμερισμός Λειτουργιών:

Συντονιστής - Εργαζόμενοι (Master - Workers):

Δεξαμενή Εργασιών (Pool of Tasks):



Σχεδιασμός Παράλληλων Προγραμμάτων

Επικοινωνία

Γιατί Επικοινωνίες; Πρότυπα επικοινωνιών

Κάθε πρόγραμμα υπολογίζει τον πληθυσμό ενός διαφορετικού είδους, όπου η εξέλιξη του πληθυσμού ενός είδους εξαρτάται από την εξέλιξη των γειτονικών πληθυσμών. Σε κάθε χρονική στιγμή, μια εργασία υπολογίζει τη τρέχουσα κατάστασή της, ανταλλάσσει πληροφορίες με τους γείτονες και συνεχίζει στην επόμενη χρονική στιγμή. Αμφίδρομη επικοινωνία μεταξύ 'γειτονικών' παράλληλων εργασιών.

Παράγοντες  σχεδιασμού επικοινωνίας:



Σχεδιασμός Παράλληλων Προγραμμάτων

Συγχρονισμός

Τύποι Συγχρονισμού:



Σχεδιασμός Παράλληλων Προγραμμάτων

Εξαρτήσεις Δεδομένων

Ορισμοί:

Παραδείγματα:

Χειρισμός των Εξαρτήσεων:



Σχεδιασμός Παράλληλων Προγραμμάτων

Εξισορρόπηση Φορτίου

Πώς Επιτυγχάνεται η Εξισορρόπηση Φορτίου:



Σχεδιασμός Παράλληλων Προγραμμάτων

Κοκκιότητα

Λόγος Υπολογισμού / Επικοινωνίας: 

Λεπτομερής (Fine-grain) Παραλληλισμός:

  • Σχετικά λίγοι υπολογισμοί μεταξύ διαδοχικών επικοινωνιών

  • Μικρός λόγος υπολογισμού προς επικοινωνία

  • Ευχερέστερη εξισορρόπηση φορτίου, η απόδοση καθορίζεται από την επικοινωνία

  • Μεγάλη επιβάρυνση επικοινωνίας, μπορεί η επικοινωνία και ο συχγρονισμός να κοστίζουν πολύ περισσότερο από τον υπολογισμό

  • Απαιτεί υπερταχεία επικοινωνία και συνήθως εφαρμόζεται σε αρχιτεκτονικές ειδικού σκοπού όπου απαιτείται συνεχής ροή δεδομένων και λύσεις πραγματικού χρόνου (πχ audio, video streaming, computer graphics, games).

Αδρομερής (Coarse-grain) Παραλληλισμός:

  • Σχετικά πολλοί υπολογισμοί μεταξύ διαδοχικών επικοινωνιών

  • Μεγάλος λόγος υπολογισμού προς επικοινωνία

  • Δυσκολότερη εξισορρόπηση φορτίου, η απόδοση καθορίζεται από τον υπολογισμό

  • Η ευχερέστερη προσέγγιση στα συνηθισμένα παράλληλα συστήματα όπου το εύρος ζώνης των επεξεργαστών είναι κατά τάξεις μεγέθους μεγαλύτερο του εύρους ζώνης επικοινωνίας.

Ποιά κοκκιότητα είναι καλύτερη;

  • Η βέλτιση κοκκιότητα μιας παράλληλης εφαρμογής εξαρτάται από το συγκεκριμένο σύστημα όπου εκτελείται.
  • Στα περισσότερα συστήματα γενικού σκοπού η επικοινωνία έχει πολύ υψηλότερο κόστος από τον υπολογισμό με αποτέλεσμα την πριμοδότηση του αδρομερούς παραλληλισμού.
  • Ο λεπτομερής παραλληλισμός βρίσκει εφαρμογή κυρίως σε συστήματα ειδικού σκοπού με επικοινωνία υψηλού εύρους ζώνης.
Granularity


Σχεδιασμός Παράλληλων Προγραμμάτων

Είσοδος/'Εξοδος (I/O)

Τα Κακά Νέα:

Τα Καλά Νέα:



Απόδοση Παράλληλων Προγραμμάτων

Όρια και Κόστη Παράλληλου Προγραμματισμού

Νόμος Amdahl:
Amdahl

      Μ = 10^3	P = 10^9   ή 99.70%   (1 - P) = 3*10^6   ή 0.030%
Μ = 10^4 P = 10^12 ή 99.97% (1 - P) = 3*10^8 ή 0.003%
Μ = 10^6 P = 10^18 ή 99.99% (1 - P) = 3*10^12 ή 0.001%

Τα προβλήματα των οποίων το P αυξάνεται μαζί με το μέγεθός τους είναι περισσότερο κλιμακώσιμα (scalable) από οτι προβλήματα με σταθερό P (Νόμος του Gustafson ή isoefficiency). Ο Νόμος Gustafson αναδιατυπώνει το Νόμο Amdahl ως εξής. Για τις ίδιες παραδοχές όπως προηγούμενα, έστω Τπαρ = a + b = 1, όπου a το μη παραλληλοποιήσιμο τμήμα και b το παραλληλοποιήσιμο. Τότε έχουμε Tακ = a + b * N και θέτουμε g = a / (a + b) το ποσοστό μη παραλληποιούμενου τμήματος ως προς το σύνολο. Όσο το μέγεθος του πρόβληματος μεγαλώνει το g τείνει προς το μηδέν (όπως στο προηγούμενο παράδειγμα. Ετσι η μέγιστη επιτάχυνση τείνει στο N.


Τακ a + b * N
Smax = ------- = ----------- = g + N * ( 1 - g ), και Smax --> N αν g --> 0
Τπαρ a + b

gustaf

Πολυπλοκότητα:

Φορητότητα:

Απαιτήσεις σε Πόρους:

Κλιμάκωση:

Για παραπέρα ανάλυση της απόδοσης αλλά και για τη πειραματική μέτρηση της απόδοσης των παράλληλων προγραμμάτων βλ. το βιβλίο του Ian Foster Designing and Building Parallel Programs. όπουθ υπάρχει και σχετική ενότητα μεταφρασμένη  στα Ελληνικά.

Παραδείγματα Παράλληλης Επεξεργασίας

Επεξεργασία Πινάκων

  • Αυτό το παράδειγμα αφορά υπολογισμούς σε 2-διάστατο πίνακα, με τους υπολογισμούς κάθε στοιχείου να είναι ανεξάρτητοι μεταξύ τους.
  • Το ακολουθιακό πρόγραμμα υπολογίζει τη τιμή κάθε στοιχείου του πίνακα με τη σειρά (κατά γραμμή, κατά στήλη).
  • Τυπικός ακολουθιακός κώδικας:


    for (i = 0; i < n; i++)
    for (j = 0; j < n; j++)
    a(i,j) = fcn(i,j)

  • Αφού οι υπολογισμοί είναι ανεξάρτητοι μεταξύ τους η εφαρμογή φυσικού παραλληλισμού είναι προφανής.
  • Η βέλτιστη κοκκιότητα σχετίζεται με την πολυπλοκότητα του υπολογισμού fcn(i,j) καθώς και με την διαθέσιμη αρχιτεκτονική (ισχύς επεξεργαστή, εύρος ζώνης μνήμης, εύρος ζώνης επικοινωνίας).
  • Η εξισορρόπηση φορτίου σχετίζεται με τη σχετική ισχύ των διαθέσιμων επεξεργαστών και με τον ομοιογενή ή μη υπολογισμό της fcn(i,j) για διαφορετικά i,j.
Embarrassingly parallel array calculation

Επεξεργασία Πινάκων
Παράλληλη Λύση 1: Στατική Κατανομή

  • Τα στοιχεία του πίνακα ανατίθενται στις παράλληλες εργασίες έτσι ώστε κάθε εργασία επεξεργάζεται ένα τμήμα του πίνακα. Η ανάθεση μπορεί να είναι λογική, π.χ. οι δείκτες των for λαμβάνουν διαφορετικές τιμές ανά εργασία (μοιραζόμενη μνήμη),  ή φυσική, π.χ. τα τμήματα του πίνακα τοποθετούνται σε τοπική μνήμη που αντιστοιχεί σε κάθε διεργασία (κατανεμημένη μνήμη).
  • Αφού οι υπολογισμοί είνα ανεξάρτητοι μεταξύ τους δεν απαιτείται επικοινωνία μεταξύ τωνε εργασιών.
  • Τα σχήματα επιμερισμού δεδομένων μπορεί να είναι πολλά και σχετίζονται με διάφορα κριτήρια, π.χ. βελτιστοποίηση κοκκιότητας, εξισορρόπηση φορτίου, βελτιστοποίηση επικοινωνίας ή απόδοσης κρυφής μνήμης. Επίσης η γλώσσα προγραμματισμού και οι επιλογές που παρέχει το API παίζουν σημαντικό ρόλο. Στην ενότητα  Επιμερισμού Δεδομένων εμφανίζονται διάφορες δυνατότητες.
  • Μετά τον επιμερισμό των δεδομένων κάθε εργασία επεξεργάζεται τα στοιχεία που της αναλογούν. Για παράδειγμα (με βάση το σχήμα):


    for (j = myfisrtcolumn; j <= mylastcolumn; j++)
    for (i = 0; i < n; i++)
    a(i,j) = fcn(i,j)

  • Αυτό που ουσιαστικά αλλάζει είναι η σχετική σειρά των επαναλήψεων (i,j) και οι δείκτες της εξωτερικής επανάληψης.
Embarrassingly parallel array calculation data decomposition

Μια πιθανή λύση:


Επεξεργασία Πινάκων
Παράλληλη Λύση 2: Δυναμική Κατανομή

Μια πιθανή λύση:

Συζήτηση:



Παραδείγματα Παράλληλης Επεξεργασίας

Υπολογισμός π

  • Ο υπολογισμός του π μπορεί να γίνει με πολλούς τρόπους. Εδώ εφαρμόζεται η μέθοδος Monte Carlo
    1. Εγγράφουμε ένα κύκλο σε ένα τετράγωνο
    2. Παράγουμε τυχαία σημεία μέσα στο τετράγωνο
    3. Μετρούμε πόσα από αυτά τα σημεία βρίσκονται μέσα και στο κύκλο
    4. Έστω r ο λόγος του πλήθους των σημείων μέσα στο κύκλο προς το σύνολο των σημείων
    5. π ~ 4 r
    6. Ο υπολογισμός είναι ακριβής για μεγάλο αριθμό σημείων

  • Ψευδικώδικας της διαδικασίας:


    npoints = 100000
    circle_count = 0
    for (j = 0; j < npoints; j++) {
    generate 2 random numbers between 0 and 1
    xcoordinate = random1 ; ycoordinate = random2
    if (xcoordinate, ycoordinate) inside circle
    then circle_count = circle_count + 1
    }
    PI = 4.0*circle_count/npoints

  • Το σύνολο σχεδόν των υπολογισμών εκτελείται μέσα στο βρόχο.
  • Παράδειγμα φυσικού παραλληλισμού
    • Υπολογιστικά απαιτητικό
    • Ελάχιστη επικοινωνία
    • Ελάχιστη I/O
One method of determining PI

Υπολογισμός π
Παράλληλη Λύση

  • Προφανής λύση φυσικού παραλληλισμού: 
    • Κάθε παράλληλη εργασία απαριθμεί ένα υποσύνολο σημείων, άρα εκτελεί ένα τμήμα του βρόχου.
    • Η κάθε παράλληλη εργασία δεν απαιτεί κάποια πληροφορία από τις άλλες (δεν υπάρχουν εξαρτήσεις δεδομένων), εκτός ίσως από τη μη-ταύτιση των τυχαίων σημείων που επιλέγει κάθε εργασία.
    • Χρήση του μοντέλου SPMD στη μορφή Συντονιστή - Εργαζόμενων. Ο Συντονιστής στο τέλος συλλέγει τα μερικά αθροίσματα για να παράγει το τελικό.

  • Στο ψευδοκώδικα που ακολουθεί το κόκκινο υπογραμμίζει τις αλλαγές της παραλληλοποίησης.


    npoints = 10000
    circle_count = 0
    p = number of tasks
    num = npoints/p

    do j = 1,num
    generate 2 random numbers between 0 and 1
    xcoordinate = random1 ; ycoordinate = random2
    if (xcoordinate, ycoordinate) inside circle
    then circle_count = circle_count + 1
    end do
    if ( I am MASTER ) {
    receive from WORKERS their circle_counts
    sum all circle_counts
    PI = 4*(all circle_counts)/npoints
    } else { // I am WORKER
    send to MASTER circle_count
    }

One method of determining PI


Παραδείγματα Παράλληλης Επεξεργασίας

Απλή Εξίσωση Θερμότητας

  • Πολλά προβλήματα παράλληης επεξεργασίας απαιτούν επικοινωνία μεταξύ των παραλλήλων εργασιών. Σε αρκετά από αυτά η επικοινωνία αφορά σε "γειτονικές" εργασίες.
  • Στο παράδειγμα, η εξίσωση θερμότητας περιγράφει τη μεταβολή της θερμοκρασία σε μια τετράγωνη επίπεδη επιφάνεια, σε συνάρτηση με το χρόνο, με δεδομένη μια αρχική κατάσταση και τις οριακές συνθήκες.
  • Για την αριθμητική επίλυση της διαφορικής εξίσωσης που προκύπτει χρησιμοποιείται η τεχνική της διακριτοποίησης, δηλαδή εξισώσειες πεπερασμένων διαφορών, όπου κάθε σημείο του τετραγωνικού πλέγματος ορίζει μια εξίσωση.
  • Αρχικές συνθήκες: Υψηλή θερμοκρασία στο κέντρο και μηδενική στις τέσσερις κορυφές.
  • Οριακές συνθήκες: Η θερμοκρασία στις τέσσερις κορυφές διατηρείται στο μηδέν.
  • Ο υπολογισμός για κάθε σημείο εξαρτάται από τα τέσσερα γειτονικά του σημεία,. Heat equation
  • Οι εξισώσεις διαφορών επιλύονται για διαδοχικά, μικρά, χρονικά βήματα. Κάθε σημείο του τετραγώνου επιλύεται για διαδοχικά χρονικά βήματα, δηλαδή το Uxy στην αριστερή πλευρά της εξίσωσης είναι η νέα τιμή (για t+1) ενώ οι τιμές στην δεξιά πλευρά δίνονται για t. Επομένως πέρα από την επικοινωνία απαιτείται και συγχρονισμός της επαναληπτικής διαδικασίας (έλεγχος για σύγκλιση και ενημέρωση των παλιών τιμών στο τέλος κάθε επανάληψης).
  • Ένα απόσπασμα ακολουθιακού κώδικα δίνεται παρακάτω. Υποθέτουμε την ύπαρξη μιας περιμέτρου 'ακραίων' σημείων με μηδενικές τιμές για λόγους πληρότητας των εξισώσεων:

    t = 0
    do {
    for (iy = 0; i < ny; iy++)
    for (ix = 0; i < nx; ix++)
    u2(ix, iy) = u1(ix, iy) +
    cx * (u1(ix+1,iy) + u1(ix-1,iy) - 2.*u1(ix,iy)) + cy * (u1(ix,iy+1) + u1(ix,iy-1) - 2.*u1(ix,iy))
    t++
      diff = 0
    for (ix = 0; i < nx; ix++)
    diff += (u1(ix, iy) - u2(ix, iy)) *
    (u1(ix, iy) - u2(ix, iy))
    for (ix = 0; i < nx; ix++)
    u1(ix, iy) =
    u2(ix, iy))
    } while ((diff > error) && (t > max_iter))

Initial heat conditions Heat equation

Απλή Εξίσωση Θερμότητας
Παράλληλη Λύση 1: Ανασταλτική Επικοινωνία

Heat equation - partitioned data


Απλή Εξίσωση Θερμότητας
Παράλληλη Λύση 2: Μη-Ανασταλτική Επικοινωνία



Παραδείγματα Παράλληλης Επεξεργασίας

Μονο-Διάστατη Εξίσωση Κύματος

Wave equation


Μονο-Διάστατη Εξίσωση Κύματος
Παράλληλη Λύση

Wave equation partition


Περισσότερα παραδείγματα αναλύονται στο σύνδεσμο Τεχνικές Παράλληλου Προγραμματισμού.


Tέλος.



Αναφορές και Περισσότερες Πληροφορίες