Στείλτε την καλή δουλειά σας στη βάση γνώσεων είναι απλή. Χρησιμοποιήστε την παρακάτω φόρμα

Φοιτητές, μεταπτυχιακοί φοιτητές, νέοι επιστήμονες που χρησιμοποιούν τη βάση γνώσεων στις σπουδές και την εργασία τους θα σας είναι πολύ ευγνώμονες.

Δημοσιεύτηκε στις http://www.allbest.ru/

Δημοσιεύτηκε στις http://www.allbest.ru/

• Εισαγωγή
• 1. Συνάφεια του θέματος
• 2. Αύξηση του αριθμού των πυρήνων
• 3. Τεχνολογία NVIDIA CUDA
• 4. Διαφορά μεταξύ CPU και GPU
• συμπέρασμα
• Εισαγωγή
• Η παραλληλοποίηση των υπολογισμών είναι η διαίρεση μεγάλων εργασιών σε μικρότερες που μπορούν να εκτελεστούν ταυτόχρονα. Ο παράλληλος υπολογισμός απαιτεί συνήθως κάποια συντονισμένη προσπάθεια. Οι παράλληλοι υπολογιστές έρχονται σε διάφορες μορφές (εντολές, bit, δεδομένα, επίπεδα εργασιών). Ο παράλληλος υπολογισμός έχει βρει την εφαρμογή του με την πάροδο των ετών κυρίως στους υπολογιστές υψηλών επιδόσεων. Όμως η κατάσταση έχει αλλάξει πρόσφατα. Υπήρχε ζήτηση για τέτοιους υπολογισμούς λόγω των φυσικών περιορισμών στην αύξηση της ταχύτητας του ρολογιού του επεξεργαστή. Οι παράλληλοι υπολογιστές έχουν γίνει κυρίαρχη ιδέα στην αρχιτεκτονική των υπολογιστών. Πήρε τη μορφή πολυπύρηνων επεξεργαστών.
• Η χρήση παράλληλων υπολογιστικών συστημάτων καθορίζεται από στρατηγικές κατευθύνσεις ανάπτυξης στον κλάδο των υπολογιστών. Η κύρια περίσταση δεν ήταν μόνο ο περιορισμός της ταχύτητας των μηχανών με βάση τη διαδοχική λογική, αλλά και η παρουσία εργασιών για τις οποίες η διαθεσιμότητα της τεχνολογίας υπολογιστών δεν είναι ακόμη επαρκής. Οι εργασίες σε αυτήν την κατηγορία περιλαμβάνουν μοντελοποίηση δυναμικών διεργασιών.
• Η έλευση των πολυπύρηνων επεξεργαστών σηματοδότησε ένα άλμα στην ανάπτυξη αποδοτικών υπερυπολογιστών, ο οποίος διαθέτει υψηλότερες αναλογίες απόδοσης/κόστους από τα συστήματα που βασίζονται σε υπερυπολογιστές. Η χρήση πολυπύρηνων επεξεργαστών παρέχει ευελιξία, ειδικότερα, για ποικίλες διαμορφώσεις, καθώς και ισχύ κλιμάκωσης σε υπολογιστικά συστήματα - από υπολογιστές, διακομιστές, σταθμούς εργασίας και τελειώνοντας με συστήματα συμπλέγματος.
• 1. Συνάφεια του θέματος
• Τα τελευταία χρόνια, εμφανίστηκε ένας μεγάλος αριθμός φθηνών συστημάτων παράλληλων υπολογιστών συστάδων, τα οποία οδήγησαν στην ταχεία ανάπτυξη τεχνολογιών παράλληλων υπολογιστών, συμπεριλαμβανομένου του τομέα των υπολογιστών υψηλής απόδοσης. Οι περισσότεροι μεγάλοι κατασκευαστές μικροεπεξεργαστών άρχισαν να μεταβαίνουν σε αρχιτεκτονικές πολλαπλών πυρήνων, γεγονός που επηρέασε την αλλαγή της κατάστασης στον τομέα των τεχνολογιών παράλληλων υπολογιστών. Μια αλλαγή στη βάση του υλικού συνεπάγεται μια αλλαγή στην κατασκευή παράλληλων αλγορίθμων. Για την εφαρμογή σε αρχιτεκτονικές υπολογιστών πολλαπλών πυρήνων, χρειάζονται νέοι παράλληλοι αλγόριθμοι που λαμβάνουν υπόψη τις νέες τεχνολογίες. Η αποτελεσματικότητα της χρήσης υπολογιστικών πόρων θα εξαρτηθεί από την ποιότητα των ίδιων των παράλληλων εφαρμογών και των εξειδικευμένων βιβλιοθηκών που στοχεύουν σε αρχιτεκτονικές πολλαπλών πυρήνων.
• Η χρήση τεχνολογίας υψηλής απόδοσης στη μοντελοποίηση πραγματικών τεχνικών, οικονομικών και άλλων διαδικασιών που περιγράφονται από συστήματα συνηθισμένων διαφορικών εξισώσεων υψηλών διαστάσεων δεν είναι μόνο δικαιολογημένη, αλλά και απαραίτητη. Ο παραλληλισμός των υπολογισμών σε πολυεπεξεργαστικές και παράλληλες δομές είναι ένας αποτελεσματικός τρόπος βελτίωσης της απόδοσης. Έτσι, η χρήση παράλληλων υπολογιστικών συστημάτων είναι μια αρκετά σημαντική κατεύθυνση στην ανάπτυξη της τεχνολογίας των υπολογιστών.

2. Αύξηση του αριθμού των πυρήνων

Ο πρώτος επεξεργαστής για μαζική χρήση ήταν ο POWER4 με δύο πυρήνες PowerPC σε ένα μόνο τσιπ. Κυκλοφόρησε από την IBM το 2001.

Οι κατασκευαστές επεξεργαστών Intel, AMD, IBM, ARM έχουν αναγνωρίσει την αύξηση του αριθμού των πυρήνων ως έναν από τους τομείς προτεραιότητας για την αύξηση της απόδοσης.

Το 2011 κυκλοφόρησαν επεξεργαστές 8 πυρήνων για οικιακούς υπολογιστές και επεξεργαστές 16 πυρήνων για συστήματα διακομιστών.

Υπάρχουν εξελίξεις σε επεξεργαστές με μεγάλο αριθμό πυρήνων (πάνω από 20), που έχουν βρει εφαρμογή σε συγκεκριμένες συσκευές.

Υπήρχαν νωρίτερα επεξεργαστές διπλού πυρήνα, για παράδειγμα IBM PowerPC-970MP (G5H). Αλλά τέτοιοι επεξεργαστές χρησιμοποιήθηκαν σε ένα στενό φάσμα εξειδικευμένων εργασιών.

Τον Απρίλιο του 2005, η AMD παρουσίασε τον 2πύρηνο επεξεργαστή Opteron. Αρχιτεκτονική AMD64. σχεδιασμένο για διακομιστές. Τον Μάιο του 2005, η Intel παρουσίασε τον επεξεργαστή Pentium D x86-64. Έγινε ο πρώτος επεξεργαστής 2 πυρήνων για οικιακούς υπολογιστές.

Τον Μάρτιο του 2010, η AMD παρουσίασε σειριακούς επεξεργαστές διακομιστή 12 πυρήνων Opteron 6100 (αρχιτεκτονική x86/x86-64).

Τον Αύγουστο του 2011, η AMD παρουσίασε τους επεξεργαστές διακομιστή 16-πύρηνων Opteron 6200 Ο επεξεργαστής Interlagos περιέχει δύο τσιπ 8 πυρήνων (4 μονάδων) σε ένα μόνο πακέτο και είναι συμβατός με την πλατφόρμα της σειράς AMD Opteron 6100 (Socket G34).

3. Τεχνολογία NVIDIA CUDA

Ένας μεγάλος αριθμός παράλληλων υπολογιστών σχετίζεται με τρισδιάστατα παιχνίδια. Ο παράλληλος διανυσματικός υπολογισμός σε συσκευές γενικής χρήσης με επεξεργαστές πολλαπλών πυρήνων χρησιμοποιείται σε τρισδιάστατα γραφικά, επιτυγχάνοντας υψηλή απόδοση. Οι Universal επεξεργαστές δεν μπορούν να το κάνουν αυτό. Η μέγιστη ταχύτητα επιτυγχάνεται μόνο σε μια σειρά από βολικές εργασίες, με ορισμένους περιορισμούς. Ωστόσο, τέτοιες συσκευές χρησιμοποιούνται ευρέως σε περιοχές όπου δεν προορίζονταν αρχικά. Για παράδειγμα, ο επεξεργαστής Cell, που αναπτύχθηκε από τη συμμαχία Sony-Toshiba-IBM στην κονσόλα παιχνιδιών Sony PlayStation 3 ή σύγχρονες κάρτες βίντεο από τη NVIDIA και την AMD.

Πριν από μερικά χρόνια, άρχισαν να εμφανίζονται τεχνολογίες γενικής χρήσης μη γραφικών υπολογιστών GPGPU για επιταχυντές 3D βίντεο. Τα σύγχρονα τσιπ βίντεο έχουν εκατοντάδες μαθηματικές μονάδες εκτέλεσης, μια τέτοια ισχύς μπορεί να βοηθήσει σημαντικά στην επιτάχυνση πολλών υπολογιστικά εντατικών εφαρμογών. Οι τρέχουσες γενιές των GPU έχουν μια ευέλικτη αρχιτεκτονική, η οποία, μαζί με τις αρχιτεκτονικές λογισμικού και υλικού και τις γλώσσες υψηλού επιπέδου, καθιστά δυνατό να γίνουν πολύ πιο προσιτές.

Η εμφάνιση αρκετά γρήγορων και ευέλικτων προγραμμάτων shader ενδιέφερε τους προγραμματιστές να δημιουργήσουν GPGPU που να είναι σε θέση να εκτελούν σύγχρονα τσιπ βίντεο. Οι προγραμματιστές ήθελαν να χρησιμοποιήσουν τη GPU για να υπολογίσουν όχι μόνο εικόνες σε εφαρμογές παιχνιδιών και 3D, αλλά και για να τις χρησιμοποιήσουν σε άλλους τομείς παράλληλων υπολογιστών. Για να γίνει αυτό, χρησιμοποιήσαμε το API των βιβλιοθηκών γραφικών OpenGL και Direct3D. Τα δεδομένα μεταφέρθηκαν στο τσιπ βίντεο ως υφές και τα υπολογιστικά προγράμματα τοποθετήθηκαν με τη μορφή shaders. Το κύριο μειονέκτημα αυτής της μεθόδου είναι η σημαντική πολυπλοκότητα του προγραμματισμού, η χαμηλή ανταλλαγή δεδομένων μεταξύ της GPU και της CPU και ορισμένοι άλλοι περιορισμοί.

Οι κορυφαίοι κατασκευαστές τσιπ βίντεο NVIDIA και AMD παρουσίασαν πλατφόρμες για παράλληλους υπολογιστές - CUDA και CTM, αντίστοιχα. Οι κάρτες βίντεο διαθέτουν πλέον υποστήριξη υλικού για άμεση πρόσβαση σε υπολογιστικούς πόρους. Το CUDA είναι μια επέκταση της γλώσσας προγραμματισμού C, περισσότερο σαν εικονική μηχανή που εκτελεί μόνο κώδικα συναρμολόγησης. Και οι δύο πλατφόρμες αφαίρεσαν τους περιορισμούς των προηγούμενων εκδόσεων του GPGPU, οι οποίες χρησιμοποιούσαν την παραδοσιακή διοχέτευση γραφικών, και φυσικά τις βιβλιοθήκες γραφικών Direct3D και Open GL.

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

Αυτό ακριβώς συνέβη με τη NVIDIA να κυκλοφορήσει την πλατφόρμα CUDA - μια γλώσσα προγραμματισμού τύπου C, εξοπλισμένη με δικό της μεταγλωττιστή και διαθέτει επίσης βιβλιοθήκες για υπολογιστές GPU. Η σύνταξη καλού κώδικα για τσιπ βίντεο δεν είναι εύκολη, αλλά το CUDA σάς δίνει περισσότερο έλεγχο στο υλικό της κάρτας βίντεο. Το CUDA εμφανίστηκε με κάρτες γραφικών της σειράς 8 Εμφανίστηκε η έκδοση CUDA 2.0, η οποία υποστηρίζει υπολογισμούς διπλής ακρίβειας σε 32- και 64-bit Windows, Linux, MacOS X.

4. Διαφορά μεταξύ CPU και GPU

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

Ειδικές διανυσματικές δυνατότητες (εντολές SSE) για διανύσματα 4 συστατικών (κινητής υποδιαστολής απλής ακρίβειας) και 2 συστατικών (διπλής ακρίβειας) εμφανίστηκαν σε επεξεργαστές γενικής χρήσης λόγω των υψηλών απαιτήσεων των εφαρμογών γραφικών. Επομένως, η χρήση της GPU είναι πιο κερδοφόρα, επειδή Αρχικά είχαν σχεδιαστεί για τέτοιες εργασίες.

Στα τσιπ NVIDIA, η κύρια μονάδα είναι ένας πολυεπεξεργαστής με 8-10 πυρήνες και περίπου εκατό ALU με αρκετές χιλιάδες καταχωρητές και μεγάλη κοινή μνήμη. Η κάρτα γραφικών έχει καθολική μνήμη προσβάσιμη από όλους τους πολυεπεξεργαστές, τοπική μνήμη σε κάθε πολυεπεξεργαστή και έχει επίσης μνήμη για σταθερές.

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

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

Η πολιτική των προγραμματιστών CPU είναι να εκτελούνται περισσότερες εντολές παράλληλα για να αυξήσουν την απόδοση. Επομένως, ξεκινώντας με τους επεξεργαστές Intel Pentium, εμφανίστηκε η τεχνολογία υπερκλιμακωτή εκτέλεσης, η οποία αντιπροσωπεύει την εκτέλεση 2 εντολών ανά κύκλο ρολογιού και ο επεξεργαστής Pentium Pro διακρίθηκε από την εκτέλεση εντολών εκτός σειράς.

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

Μια άλλη διαφορά μεταξύ μιας CPU και μιας GPU: η αρχή της πρόσβασης στη μνήμη. Στην GPU είναι συνεκτικό και προβλέψιμο, γιατί αν μετρήθηκαν οι υφές, σημαίνει ότι μετά από λίγο καιρό θα έρθει η σειρά των γειτονικών υφών. Επομένως, η οργάνωση μνήμης της κάρτας βίντεο και του κεντρικού επεξεργαστή είναι διαφορετική. Και για αυτόν τον λόγο, το τσιπ βίντεο δεν χρειάζεται μεγάλη μνήμη cache και οι υφές απαιτούν μόνο περίπου 128-256 kB.

Η εργασία με τη μνήμη είναι επίσης διαφορετική. Οι CPU έχουν ενσωματωμένους ελεγκτές μνήμης, οι GPU συνήθως έχουν πολλά από αυτά, έως και οκτώ κανάλια 64-bit. Επιπλέον, χρησιμοποιείται πολύ γρήγορη μνήμη, επομένως, το εύρος ζώνης της μνήμης είναι υψηλότερο, γεγονός που αποτελεί πλεονέκτημα για παράλληλους υπολογισμούς που λειτουργούν με τεράστιες ροές δεδομένων.

Σε μια CPU, ένας μεγάλος αριθμός τρανζίστορ ξοδεύεται σε buffer εντολών, πρόβλεψη κλάδου υλικού και τεράστιες ποσότητες μνήμης cache. Όλα αυτά τα μπλοκ χρειάζονται για να επιταχυνθούν οι λίγες ροές εντολών. Στις GPU, τα τρανζίστορ πηγαίνουν σε συστοιχίες μονάδων εκτέλεσης, μικρή κοινόχρηστη μνήμη, μονάδες ελέγχου ροής και ελεγκτές μνήμης. Όλα αυτά δεν επιταχύνουν την εκτέλεση μεμονωμένων νημάτων, αλλά σας επιτρέπουν να επεξεργαστείτε έναν τεράστιο αριθμό από αυτά ταυτόχρονα.

Προσωρινή αποθήκευση. Η CPU χρησιμοποιεί τη μνήμη cache για να μειώσει την καθυστέρηση πρόσβασης στη μνήμη, με αποτέλεσμα την αύξηση της απόδοσης. Η GPU χρησιμοποιεί προσωρινή μνήμη για να αυξήσει την απόδοση. Η CPU μειώνει τον λανθάνοντα χρόνο πρόσβασης στη μνήμη μέσω μιας μεγάλης προσωρινής μνήμης και πρόβλεψης κλάδου κώδικα. Αυτά τα κομμάτια υλικού είναι μεγάλα στο τσιπ, επομένως καταναλώνουν πολλή ισχύ. Οι GPU λύνουν το πρόβλημα της καθυστέρησης πρόσβασης στη μνήμη με έναν άλλο τρόπο: την εκτέλεση χιλιάδων νημάτων ταυτόχρονα. Όταν ένα νήμα περιμένει δεδομένα, ένα άλλο νήμα εκτελεί τους υπολογισμούς χωρίς αναμονή ή καθυστέρηση.

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

5. Πρώτη χρήση υπολογισμών σε επιταχυντές γραφικών

Η ιστορία της χρήσης τσιπ για μαθηματικούς υπολογισμούς ξεκίνησε εδώ και πολύ καιρό. Οι πρώτες απόπειρες ήταν πρωτόγονες και χρησιμοποιούσαν κάποιες συναρτήσεις από το Z-buffering και το rasterization. Αλλά με την εμφάνιση των shaders, άρχισε η επιτάχυνση. Το 2003 Το SIGGRAPH έχει μια νέα ενότητα για υπολογιστές και έλαβε GPGPU.

BrookGPU. Γνωστός μεταγλωττιστής της γλώσσας προγραμματισμού Brook. Γίνεται ροή. Σχεδιάστηκε ειδικά για υπολογιστές GPU. Οι προγραμματιστές χρησιμοποίησαν API: Direct3D ή OpenGL. Αυτό περιόρισε σημαντικά τη χρήση των GPU, επειδή Shaders και textures χρησιμοποιήθηκαν σε τρισδιάστατα γραφικά και οι ειδικοί στον παράλληλο προγραμματισμό δεν απαιτείται να γνωρίζουν τίποτα. Χρησιμοποιούν τρέχοντα νήματα και πυρήνες. Ο Μπρουκ μπόρεσε να βοηθήσει λίγο σε αυτό το έργο. Οι επεκτάσεις στη γλώσσα C βοήθησαν στην απόκρυψη του 3D API από τους προγραμματιστές και στην παροχή του τσιπ βίντεο ως παράλληλου συνεπεξεργαστή. Ο μεταγλωττιστής μεταγλωττίστηκε τον κώδικα και τον συνέδεσε με τη βιβλιοθήκη DirectX, OpenGL ή x86.

6. Περιοχές εφαρμογής παράλληλων υπολογισμών σε επιταχυντές γραφικών

Ακολουθούν τα μέσα στοιχεία για την αύξηση της απόδοσης υπολογιστών που ελήφθησαν από ερευνητές σε όλο τον κόσμο. Κατά τη μετάβαση σε GPU, η αύξηση της απόδοσης είναι κατά μέσο όρο 5-30 φορές και σε ορισμένα παραδείγματα φτάνει έως και 100 φορές (συνήθως πρόκειται για κώδικα που δεν είναι κατάλληλος για υπολογισμούς με χρήση SEE.

Ακολουθούν μερικά παραδείγματα επιταχύνσεων:

· Μικροσκόπιο φθορισμού - 12 φορές.

· Μοριακή δυναμική - 8-16 φορές.

· Ηλεκτροστατική (άμεση και πολυεπίπεδη άθροιση Coulomb) - 40-120 φορές και 7 φορές.

γραφικά πυρήνα επεξεργαστή

συμπέρασμα

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

Η περίληψη δεν εξέτασε τη χρήση παράλληλων υπολογιστών σε κεντρικούς επεξεργαστές με ενσωματωμένο πυρήνα βίντεο. Πρόκειται για επεξεργαστές της σειράς AMD A (AMD A10, AMD A8, AMD A6, AMD A4) και επεξεργαστές της σειράς Intel i3/i5/i7 με ενσωματωμένο πυρήνα βίντεο HD Graphics.

Κατάλογος χρησιμοποιημένης βιβλιογραφίας

1. Ιστότοπος ixbt.com, ιδιοκτήτης της Byrds Research and Publishing, Ltd

2. Ιστότοπος wikipedia.org, ιδιοκτήτης Wikimedia Foundation

3. Ιστότοπος nvidia.ru, ιδιοκτήτης της εταιρείας NVIDIA

Δημοσιεύτηκε στο Allbest.ru

...

Παρόμοια έγγραφα

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

παρουσίαση, προστέθηκε 02/10/2014


Εισαγωγή στην ιστορία της ανάπτυξης πολυεπεξεργαστικών συστημάτων και παράλληλων υπολογιστών. Προσωπικοί υπολογιστές ως κοινά συστήματα ενός επεξεργαστή στην πλατφόρμα Intel ή AMD με λειτουργικά συστήματα ενός χρήστη.

παρουσίαση, προστέθηκε 22/02/2016


Ταξινόμηση συστημάτων παράλληλων υπολογιστών. Βασικές έννοιες και στοιχεία των παράλληλων υπολογιστών, τα στοιχεία τους. Χαρακτηριστικά των ταξινομήσεων των Hender, Hockney, Flynn, Shore. Συστήματα με κοινόχρηστη και τοπική μνήμη. Μέθοδοι για τη διαίρεση της μνήμης.

εργασία μαθήματος, προστέθηκε 18/07/2012


Μαθηματική βάση παράλληλων υπολογιστών. Ιδιότητες της εργαλειοθήκης παράλληλων υπολογιστών. Ανάπτυξη παράλληλων εφαρμογών στο Matlab. Παραδείγματα προγραμματισμού παράλληλων εργασιών. Υπολογισμός ορισμένου ολοκληρώματος. Σειριακός και παράλληλος πολλαπλασιασμός.

εργασία μαθήματος, προστέθηκε 15/12/2010


Ανάπτυξη εννοιών και δυνατοτήτων ΛΣ. Παράλληλα συστήματα υπολογιστών και χαρακτηριστικά του ΛΣ τους. Συμμετρικά και ασύμμετρα συστήματα πολλαπλών επεξεργαστών. Τύποι διακομιστών σε συστήματα πελάτη-διακομιστή. ΛΣ για υπολογιστικό νέφος. Υπολογιστικά συστήματα συμπλέγματος.

διάλεξη, προστέθηκε 24/01/2014


Τεχνολογία για την ανάπτυξη παράλληλων προγραμμάτων για υπολογιστικά συστήματα πολλαπλών επεξεργαστών με κοινόχρηστη μνήμη. Σύνταξη, σημασιολογία και δομή του μοντέλου OpenMP: οδηγίες, διαδικασίες και μεταβλητές περιβάλλοντος. Παραλληλισμός δεδομένων και πράξεων, συγχρονισμός.

παρουσίαση, προστέθηκε 02/10/2014


Παράλληλα υπολογιστικά συστήματα, γενικά χαρακτηριστικά και λειτουργικά χαρακτηριστικά τους, εκτίμηση δυνατοτήτων, εσωτερική δομή και διασύνδεση στοιχείων, τύποι: μονοεπεξεργαστής και πολυεπεξεργαστής. Παράλληλη μορφή αλγορίθμου, αναπαράσταση και εφαρμογή του.

δοκιμή, προστέθηκε 06/02/2014


Πλεονεκτήματα πολυεπεξεργαστικών συστημάτων. Δημιουργία προγράμματος που υλοποιεί τη λειτουργία ενός συστήματος πολλαπλών επεξεργαστών με κοινή μνήμη για την επεξεργασία διαφορετικών αριθμών αιτημάτων, καθώς και διαφορετικών αριθμών επεξεργαστών. Μοντέλα υπολογισμών σε διανυσματικούς και μητρικούς υπολογιστές.

εργασία μαθήματος, προστέθηκε 21/06/2013


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

διατριβή, προστέθηκε 09.09.2010


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

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

Υπάρχουν διάφοροι τρόποι υλοποίησης παράλληλων υπολογιστών: κάθε υπολογιστική διαδικασία μπορεί να υλοποιηθεί ως διεργασία λειτουργικού συστήματος ή υπολογιστικές διεργασίες μπορεί να είναι μια συλλογή από νήματα εκτέλεσης σε μια ενιαία διαδικασία. Ένα νήμα (ή πιο σωστά ένα νήμα εκτέλεσης) είναι η μικρότερη μονάδα επεξεργασίας της οποίας η εκτέλεση μπορεί να εκχωρηθεί από τον πυρήνα του λειτουργικού συστήματος. Πολλαπλά νήματα εκτέλεσης μπορούν να υπάρχουν μέσα στην ίδια διεργασία και να μοιράζονται πόρους όπως η μνήμη, ενώ οι διεργασίες δεν μοιράζονται αυτούς τους πόρους. Τα παράλληλα προγράμματα μπορούν να εκτελεστούν φυσικά είτε διαδοχικά σε έναν μόνο επεξεργαστή - εναλλάσσοντας με τη σειρά τους τα βήματα κάθε υπολογιστικής διαδικασίας, είτε παράλληλα - εκχωρώντας έναν ή περισσότερους επεξεργαστές (που βρίσκονται κοντά ή κατανεμημένοι σε ένα δίκτυο υπολογιστών) σε κάθε υπολογιστική διαδικασία.

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

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

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

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

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

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

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

3. Νήματα POSIXείναι ένα πρότυπο για την υλοποίηση νημάτων εκτέλεσης.

4. Το λειτουργικό σύστημα Windows έχει ενσωματωμένη υποστήριξη για εφαρμογές πολλαπλών νημάτων για C++ σε επίπεδο API.

5. PVM (Παράλληλη εικονική μηχανή)σας επιτρέπει να συνδυάσετε ετερογενείς υπολογιστές που συνδέονται από ένα δίκτυο σε έναν κοινό υπολογιστικό πόρο.

Τα συστήματα που βασίζονται σε πολλούς υπολογιστές ταξινομούνται ως συστήματα κατανεμημένων υπολογιστών. Τέτοιες λύσεις χρησιμοποιούνται εδώ και αρκετό καιρό. Το πιο εντυπωσιακό παράδειγμα τεχνολογίας κατανεμημένων υπολογιστών είναι το MPI (Message Passing Interface). Το MPI είναι το πιο κοινό πρότυπο διεπαφής ανταλλαγής δεδομένων για παράλληλο προγραμματισμό, υπάρχουν υλοποιήσεις για έναν τεράστιο αριθμό πλατφορμών υπολογιστών. Το MPI παρέχει στον προγραμματιστή έναν ενοποιημένο μηχανισμό αλληλεπίδρασης διακλαδώσεων σε μια παράλληλη εφαρμογή, ανεξάρτητα από την αρχιτεκτονική της μηχανής (μονοεπεξεργαστής/πολυεπεξεργαστής με κοινόχρηστη/ξεχωριστή μνήμη), τη σχετική θέση των διακλαδώσεων (στον ίδιο επεξεργαστή ή σε διαφορετικούς).

Δεδομένου ότι το MPI προορίζεται κυρίως για συστήματα με κοινόχρηστη μνήμη, η χρήση του για την οργάνωση μιας παράλληλης διαδικασίας σε ένα σύστημα με κοινόχρηστη μνήμη είναι εξαιρετικά δύσκολη και μη πρακτική. Ωστόσο, τίποτα δεν σας εμποδίζει να δημιουργήσετε λύσεις MPI για ένα μηχάνημα.

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

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

Το OpenMP (Open Multi-Processing) είναι ένα σύνολο οδηγιών μεταγλωττιστή, διαδικασιών βιβλιοθήκης και μεταβλητών περιβάλλοντος που έχουν σχεδιαστεί για τον προγραμματισμό εφαρμογών πολλαπλών νημάτων σε συστήματα πολλαπλών επεξεργαστών κοινής μνήμης.

Η προδιαγραφή OpenMP αναπτύσσεται από αρκετούς μεγάλους κατασκευαστές υλικού και λογισμικού, η εργασία των οποίων ελέγχεται από έναν μη κερδοσκοπικό οργανισμό που ονομάζεται OpenMP Architecture Review Board (ARB).

Η πρώτη έκδοση εμφανίστηκε το 1997 και προοριζόταν για τη γλώσσα Fortran. Η έκδοση C/C++ αναπτύχθηκε το 1998. Το 2008 κυκλοφόρησε το OpenMP 3.0. Η διεπαφή OpenMP έχει γίνει μια από τις πιο δημοφιλείς τεχνολογίες παράλληλου προγραμματισμού. Το OpenMP χρησιμοποιείται με επιτυχία τόσο στον προγραμματισμό συστημάτων υπερυπολογιστών με μεγάλο αριθμό επεξεργαστών, όσο και σε συστήματα επιτραπέζιων χρηστών ή, για παράδειγμα, στο Xbox 360.

Το OpenMP υλοποιεί παράλληλους υπολογισμούς χρησιμοποιώντας multithreading, στο οποίο ένα «κύριο» νήμα δημιουργεί ένα σύνολο slave νημάτων και η εργασία κατανέμεται μεταξύ τους. Τα νήματα υποτίθεται ότι εκτελούνται παράλληλα σε ένα μηχάνημα με πολλούς επεξεργαστές (ο αριθμός των επεξεργαστών δεν χρειάζεται να είναι μεγαλύτερος ή ίσος με τον αριθμό των νημάτων).

Οι εργασίες που εκτελούνται από νήματα παράλληλα, καθώς και τα δεδομένα που απαιτούνται για την εκτέλεση αυτών των εργασιών, περιγράφονται χρησιμοποιώντας ειδικές οδηγίες προεπεξεργαστή της αντίστοιχης γλώσσας - pragmas. Για παράδειγμα, μια ενότητα του κώδικα Fortran που πρέπει να εκτελεστεί από πολλά νήματα, καθένα από τα οποία έχει το δικό του αντίγραφο της μεταβλητής N, προηγείται από την ακόλουθη οδηγία: !$OMP PARALLEL PRIVATE(N)

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

Τα βασικά στοιχεία του OpenMP είναι

1. Κατασκευές για τη δημιουργία νημάτων (παράλληλη οδηγία).

2. Κατασκευές για την κατανομή της εργασίας μεταξύ των νημάτων (Οδηγίες DO/for και τμήματος).

3. Κατασκευές για τη διαχείριση εργασιών με δεδομένα (κοινόχρηστες και ιδιωτικές εκφράσεις για τον καθορισμό της κατηγορίας μνήμης των μεταβλητών).

4. Κατασκευές για συγχρονισμό νημάτων (κρίσιμες, ατομικές οδηγίες και οδηγίες φραγμού).

5. Διαδικασίες βιβλιοθήκης υποστήριξης χρόνου εκτέλεσης (για παράδειγμα, omp_get_thread_num).

6. μεταβλητές περιβάλλοντος (για παράδειγμα, OMP_NUM_THREADS).

Το OpenMP χρησιμοποιεί ένα μοντέλο παράλληλης εκτέλεσης συγχώνευσης διακλάδωσης. Ένα πρόγραμμα OpenMP ξεκινά ως ένα μόνο νήμα εκτέλεσης, που ονομάζεται αρχικό νήμα. Όταν ένα νήμα συναντά μια παράλληλη κατασκευή, δημιουργεί μια νέα ομάδα νημάτων που αποτελείται από το ίδιο και έναν αριθμό πρόσθετων νημάτων και γίνεται ο κύριος της νέας ομάδας. Όλα τα μέλη της νέας ομάδας (συμπεριλαμβανομένης της κύριας ομάδας) εκτελούν κώδικα μέσα στην παράλληλη κατασκευή. Υπάρχει ένα σιωπηρό φράγμα στο τέλος της παράλληλης δομής. Μετά την παράλληλη κατασκευή, μόνο το κύριο νήμα συνεχίζει να εκτελεί τον κωδικό χρήστη. Μια παράλληλη περιοχή μπορεί να είναι ένθετη με άλλες παράλληλες περιοχές, στις οποίες κάθε νήμα της αρχικής περιοχής γίνεται το κύριο νήμα για την ομάδα νημάτων της. Οι ένθετες περιοχές μπορούν με τη σειρά τους να περιλαμβάνουν περιοχές σε βαθύτερο επίπεδο φωλιάς.

Ο αριθμός των νημάτων σε μια ομάδα που τρέχει παράλληλα μπορεί να ελεγχθεί με διάφορους τρόπους. Ένα από αυτά χρησιμοποιεί τη μεταβλητή περιβάλλοντος OMP_NUM_THREADS. Ένας άλλος τρόπος είναι να καλέσετε τη διαδικασία omp_set_num_threads(). Ένας άλλος τρόπος είναι να χρησιμοποιήσετε την έκφραση num_threads σε συνδυασμό με την παράλληλη οδηγία.

Σε αυτό το πρόγραμμα, δύο πίνακες (α και β) προστίθενται παράλληλα κατά δέκα νήματα.

#περιλαμβάνω

#περιλαμβάνω

int main(int argc, char *argv)

float a[N], b[N], c[N];

omp_set_dynamic(0); // εμποδίζει τη βιβλιοθήκη openmp να αλλάξει τον αριθμό των νημάτων κατά την εκτέλεση

omp_set_num_threads(10); // ορίστε τον αριθμό των νημάτων σε 10

// αρχικοποίηση των πινάκων

για (I = 0, I< N; i++)

// υπολογίστε το άθροισμα των πινάκων

#pragma omp parallel shared(a, b, c) private(i)

για (I = 0, I< N; i++)

c[i] = a[i] + b[i];

printf("%f\n", c);

Αυτό το πρόγραμμα μπορεί να μεταγλωττιστεί χρησιμοποιώντας gcc-4.4 και μεταγενέστερα με τη σημαία –fopenmp. Προφανώς, εάν καταργήσετε τη συμπερίληψη του αρχείου κεφαλίδας omp.h, καθώς και τις κλήσεις στη συνάρτηση διαμόρφωσης OpenMP, το πρόγραμμα μπορεί να μεταγλωττιστεί σε οποιονδήποτε μεταγλωττιστή C ως κανονικό διαδοχικό πρόγραμμα.

Το OpenMP υποστηρίζεται από πολλούς σύγχρονους μεταγλωττιστές:

1. Οι μεταγλωττιστές Sun Studio υποστηρίζουν την επίσημη προδιαγραφή - OpenMP 2.5 - με βελτιωμένη απόδοση στο Solaris OS. Η υποστήριξη Linux σχεδιάζεται για την επόμενη έκδοση.

2. Η Visual C++ 2005 και νεότερη έκδοση υποστηρίζει το OpenMP σε εκδόσεις Professional και Team System.

3. Το GCC 4.2 υποστηρίζει OpenMP και ορισμένες διανομές (όπως το Fedora Core 5 gcc) έχουν συμπεριλάβει υποστήριξη στις εκδόσεις του GCC 4.1.

4. Intel C++ Compiler, συμπεριλαμβανομένης μιας έκδοσης του Intel Cluster OpenMP για προγραμματισμό σε συστήματα κατανεμημένης μνήμης.

Διεπαφή διέλευσης μηνυμάτων (MPIδιεπαφή μετάδοσης μηνυμάτων) είναι μια διεπαφή προγραμματισμού μεταφοράς πληροφοριών (API) που επιτρέπει την ανταλλαγή μηνυμάτων μεταξύ διεργασιών που εκτελούν την ίδια εργασία. Αναπτύχθηκε από τους William Group, Evin Lusk και άλλους.

Το MPI είναι το πιο κοινό πρότυπο διεπαφής ανταλλαγής δεδομένων για παράλληλο προγραμματισμό και υπάρχουν υλοποιήσεις για μεγάλο αριθμό πλατφορμών υπολογιστών. Χρησιμοποιείται στην ανάπτυξη προγραμμάτων για συμπλέγματα και υπερυπολογιστές. Το κύριο μέσο επικοινωνίας μεταξύ των διεργασιών στο MPI είναι η μετάδοση μηνυμάτων μεταξύ τους. Η τυποποίηση MPI πραγματοποιείται από το MPI Forum. Το πρότυπο MPI περιγράφει μια διεπαφή μετάδοσης μηνυμάτων που πρέπει να υποστηρίζεται τόσο στην πλατφόρμα όσο και σε εφαρμογές χρήστη. Αυτή τη στιγμή υπάρχει ένας μεγάλος αριθμός δωρεάν και εμπορικών υλοποιήσεων του MPI. Υπάρχουν υλοποιήσεις για γλώσσες Fortran 77/90, C και C++.

Το MPI επικεντρώνεται κυρίως σε συστήματα με κατανεμημένη μνήμη, δηλαδή όταν το κόστος μεταφοράς δεδομένων είναι υψηλό, ενώ το OpenMP επικεντρώνεται σε συστήματα με κοινόχρηστη μνήμη (πολλαπλοί πυρήνες με κοινό ESH). Και οι δύο τεχνολογίες μπορούν να χρησιμοποιηθούν μαζί για τη βέλτιστη χρήση πολυπύρηνων συστημάτων σε ένα σύμπλεγμα.

Η πρώτη έκδοση του MPI αναπτύχθηκε το 1993-1994 και το MPI 1 κυκλοφόρησε το 1994.

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

αποστολή και λήψη μηνυμάτων μεταξύ ξεχωριστών διεργασιών.

συλλογικές αλληλεπιδράσεις διαδικασίας?

αλληλεπιδράσεις σε ομάδες διαδικασιών·

υλοποίηση τοπολογιών διεργασιών.

δυναμική παραγωγή και διαχείριση διαδικασιών·

μονόδρομες επικοινωνίες (Get/Put);

Παράλληλη είσοδος και έξοδος.

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

Η έκδοση MPI 2.1 κυκλοφόρησε στις αρχές Σεπτεμβρίου 2008.

Ο βασικός μηχανισμός επικοινωνίας μεταξύ των διαδικασιών MPI είναι η μετάδοση και η λήψη μηνυμάτων. Το μήνυμα περιέχει μεταδιδόμενα δεδομένα και πληροφορίες που επιτρέπουν στον παραλήπτη να τα λάβει επιλεκτικά:

1. αποστολέας - κατάταξη (αριθμός στην ομάδα) του αποστολέα μηνύματος.

2. παραλήπτης - βαθμός παραλήπτη?

3. σημάδι - μπορεί να χρησιμοποιηθεί για τον διαχωρισμό διαφορετικών τύπων μηνυμάτων.

4. communicator - κωδικός ομάδας διεργασιών.

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

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

Παρακάτω είναι ένα παράδειγμα προγράμματος για τον υπολογισμό του π σε C χρησιμοποιώντας MPI:

// Σύνδεση των απαραίτητων κεφαλίδων

#περιλαμβάνω

#περιλαμβάνω

// Συνδέστε το αρχείο κεφαλίδας MPI

#include "mpi.h"

// Συνάρτηση για ενδιάμεσους υπολογισμούς

διπλό f (διπλό α)

επιστροφή (4,0 / (1,0+ a*a));

// Κύρια λειτουργία του προγράμματος

int main(int argc, char **argv)

// Δήλωση μεταβλητών

int done = 0, n, myid, numprocs, I;

διπλό PI25DT = 3,141592653589793238462643;

διπλό mypi, pi, h, sum, x;

διπλός χρόνος έναρξης = 0,0, χρόνος λήξης.

char processor_name;

// Εκκίνηση του υποσυστήματος MPI

MPI_Init(&argc, &argv);

// Λάβετε το μέγεθος της συσκευής επικοινωνίας MPI_COMM_WORLD

// (συνολικός αριθμός διεργασιών εντός της εργασίας)

MPI_Comm_size(MPI_COMM_WORLD,&nuprocs);

// Λάβετε τον αριθμό της τρέχουσας διαδικασίας εντός

// communicator MPI_COMM_WORLD

MPI_Comm_rank(MPI_COMM_WORLD,&myid);

MPI_Get_processor_name(processor_name,&namelen);

// Εμφάνιση του αριθμού νήματος στο κοινόχρηστο pool

fprintf(stdout, "Η διαδικασία %d του %d βρίσκεται στο %s\n", myid,nuprocs,processor_name);

// αριθμός διαστημάτων

fprintf(stdout, "Εισαγάγετε τον αριθμό των διαστημάτων: (0 τερματισμοί) ");

if(scanf("%d",&n) != 1)

fprintf(stdout, "Δεν έχει εισαχθεί αριθμός, έξοδος\n");

MPI_Bcast(&n, 1, MPI_INT, 0, MPI_COMM_WORLD);

h = 1,0 / (διπλό)n;

// Υπολογίστε το σημείο που έχει εκχωρηθεί στη διαδικασία

for(I = myid + 1 ; (I<= n) ; I += numprocs)

x = h * ((διπλό)I – 0,5);

// Επαναφέρετε τα αποτελέσματα από όλες τις διεργασίες και προσθέστε

MPI_Reduce(&mypi, &pi, 1, MPI_DOUBLE, MPI_SUM, 0, MPI_COMM_WORLD);

// Εάν αυτή είναι η κύρια διαδικασία, βγάζουμε το αποτέλεσμα

printf("PI είναι περίπου %.16f, Σφάλμα είναι %.16f\n", pi, fabs(pi – PI25DT));

endwtime = MPI_Wtime();

printf("ώρα ρολογιού τοίχου = %f\n", endwtime-startwtime);

// Απελευθερώστε το υποσύστημα MPI

Οι πιο κοινές εφαρμογές MPI σήμερα είναι:

Το MPICH είναι η πιο κοινή δωρεάν υλοποίηση, που εκτελείται σε συστήματα UNIX και Windows NT

Το LAM/MPI είναι μια άλλη δωρεάν εφαρμογή του MPI. Υποστηρίζει ετερογενείς διαμορφώσεις, το LAM (http://www.lam-mpi.org) υποστηρίζει ετερογενείς διαμορφώσεις, το πακέτο Globus και ικανοποιεί το IMPI (Interoperable MPI).

Υποστηρίζονται διάφορα συστήματα επικοινωνίας (συμπεριλαμβανομένου του Myrinet).

WMPI - Εφαρμογή MPI για Windows

MPI/PRO για Windows NT - εμπορική εφαρμογή για Windows NT

Intel MPI - εμπορική υλοποίηση για Windows/Linux

Το Microsoft MPI περιλαμβάνεται στο Compute Cluster Pack SDK. Βασίζεται στο MPICH2, αλλά περιλαμβάνει πρόσθετες δυνατότητες διαχείρισης εργασιών. Υποστηρίζεται η προδιαγραφή MPI-2.

HP-MPI - εμπορική υλοποίηση από την HP

SGI MPT - πληρωμένη βιβλιοθήκη MPI από την SGI

Mvapich - δωρεάν εφαρμογή MPI για το Infiniband

Open MPI - δωρεάν υλοποίηση MPI, διάδοχος του LAM/MPI

Oracle HPC ClusterTools - δωρεάν εφαρμογή για Solaris SPARC/x86 και Linux με βάση το Open MPI

MPJ - MPI για Java

Νήματα POSIX- Πρότυπο POSIX για την υλοποίηση νημάτων εκτέλεσης, ορίζοντας ένα API για τη δημιουργία και τη διαχείρισή τους.

Οι βιβλιοθήκες που εφαρμόζουν αυτό το πρότυπο (και τις λειτουργίες αυτού του προτύπου) ονομάζονται συνήθως Pthreads (οι συναρτήσεις έχουν το πρόθεμα "pthread_"). Αν και οι πιο γνωστές επιλογές είναι για λειτουργικά συστήματα παρόμοια με το Unix, όπως το Linux ή το Solaris, υπάρχει επίσης μια εφαρμογή για τα Microsoft Windows (Pthreads-w32)

Το Pthreads ορίζει ένα σύνολο τύπων και συναρτήσεων στη γλώσσα προγραμματισμού C. Το αρχείο κεφαλίδας είναι pthread.h.

Τύποι δεδομένων:

1. pthread_t – περιγραφέας νήματος.

2. pthread_attr_t – λίστα χαρακτηριστικών νημάτων.

Λειτουργίες ελέγχου νήματος:

1. pthread_create() – δημιουργία νήματος.

2. pthread_exit() – τερματισμός του νήματος (πρέπει να καλείται από τη συνάρτηση νήματος κατά τον τερματισμό).

3. pthread_cancel() – ακυρώστε το νήμα.

4. pthread_join() – αποκλεισμός της εκτέλεσης ενός νήματος μέχρι να τερματιστεί ένα άλλο νήμα που καθορίζεται στην κλήση συνάρτησης.

5. pthread_detach() – απελευθερώστε τους πόρους που καταλαμβάνει το νήμα (εάν το νήμα εκτελείται, οι πόροι θα απελευθερωθούν μετά την ολοκλήρωσή του).

6. pthread_attr_init() – αρχικοποίηση της δομής του χαρακτηριστικού νήματος.

7. pthread_attr_setdetachstate() – υποδεικνύει στο σύστημα ότι μετά τον τερματισμό του νήματος, μπορεί να απελευθερώσει αυτόματα τους πόρους που καταλαμβάνει το νήμα.

8. pthread_attr_destroy() – ελευθερώστε μνήμη από τη δομή του χαρακτηριστικού νήματος (καταστρέψτε τον περιγραφέα).

Λειτουργίες συγχρονισμού νημάτων:

2. pthread_mutex_init(), pthread_mutex_destroy(), pthread_mutex_lock(), pthread_mutex_trylock(), pthread_mutex_unlock();

3. pthread_cond_init(), pthread_cond_signal(), pthread_cond_wait().

Παράδειγμα χρήσης νημάτων στο C:

#περιλαμβάνω

#περιλαμβάνω

#περιλαμβάνω

#περιλαμβάνω

static void wait_thread(void)

time_t start_time = time(NULL);

ενώ (time(NULL) == start_time)

/* μην κάνετε τίποτα εκτός από το να μασάτε φέτες CPU για έως και ένα δευτερόλεπτο. */

static void *thread_func(void *vptr_args)

για (I = 0, I< 20; i++)

fputs(“b\n”, stderr);

pthread_t νήμα;

if (pthread_create(&thread, NULL, thread_func, NULL) != 0)

επιστροφή EXIT_FAILURE.

για (I = 0, I< 20; i++)

if (pthread_join(νήμα, NULL) != 0)

επιστροφή EXIT_FAILURE.

επιστροφή EXIT_SUCCESS.

Το πρόγραμμα που παρουσιάζεται χρησιμοποιεί δύο νήματα που εκτυπώνουν μηνύματα στην κονσόλα, ένα που εκτυπώνει "a", το δεύτερο - "b". Η έξοδος μηνυμάτων αναμιγνύεται ως αποτέλεσμα της εναλλαγής εκτέλεσης μεταξύ νημάτων ή της ταυτόχρονης εκτέλεσης σε συστήματα πολλαπλών επεξεργαστών.

Το πρόγραμμα C δημιουργεί ένα νέο νήμα για να εκτυπώσει το "b" και το κύριο νήμα εκτυπώνει το "a". Το κύριο νήμα (μετά την εκτύπωση "aaaaa….") περιμένει να ολοκληρωθεί το θυγατρικό νήμα.

Ερωτήσεις ελέγχου

1. Τι είναι το παράλληλο πρόγραμμα;
2. Ποια είναι η διαφορά μεταξύ μιας διαδικασίας και ενός νήματος εκτέλεσης;
3. Μπορεί ένα πρόγραμμα να δημιουργήσει 5 νήματα όταν εκτελείται σε επεξεργαστή τετραπλού πυρήνα;
4. Ποια είναι τα χαρακτηριστικά των παράλληλων προγραμμάτων κοινής μνήμης;
5. Ποια εργαλεία λογισμικού υπάρχουν για την ανάπτυξη παράλληλων προγραμμάτων;
6. Γιατί το OpenMP έχει γίνει ευρέως διαδεδομένο κατά τη δημιουργία προγραμμάτων για υπολογιστές και όχι, για παράδειγμα, MPI;

Αντίγραφο

1 Μέρος 3. Μέθοδοι παράλληλων υπολογισμών 6. Αρχές ανάπτυξης παράλληλων μεθόδων 6. Αρχές ανάπτυξης παράλληλων μεθόδων Μοντελοποίηση παράλληλων προγραμμάτων Στάδια ανάπτυξης παράλληλων αλγορίθμων Διαχωρισμός υπολογισμών σε ανεξάρτητα μέρη Απομόνωση εξαρτήσεων πληροφοριών Κλιμάκωση ενός συνόλου υποεργασιών Διανομή λύσεων μεταξύ των διεργασιών το πρόβλημα βαρύτητας του Ν-σώματος Διαίρεση υπολογισμών σε ανεξάρτητα μέρη Απομόνωση εξαρτήσεων πληροφοριών Κλιμάκωση και κατανομή υποεργασιών μεταξύ των επεξεργαστών Ανάλυση της αποτελεσματικότητας του παράλληλου υπολογισμού Σύντομη επισκόπηση της ενότητας Ανασκόπηση βιβλιογραφίας Ερωτήσεις δοκιμών Εργασίες και ασκήσεις Ανάπτυξη αλγορίθμων (και ιδιαίτερα παράλληλων υπολογιστών μέθοδοι) για την επίλυση πολύπλοκων επιστημονικών και τεχνικών προβλημάτων είναι συχνά σημαντικό πρόβλημα. Για να μειώσουμε την πολυπλοκότητα του υπό εξέταση θέματος, θα αφήσουμε κατά μέρος τις μαθηματικές πτυχές της ανάπτυξης και της απόδειξης της σύγκλισης των αλγορίθμων, τα ζητήματα αυτά μελετώνται στον έναν ή τον άλλον βαθμό σε έναν αριθμό «κλασικών» μαθηματικών μαθημάτων. Εδώ θα υποθέσουμε ότι τα υπολογιστικά σχήματα για την επίλυση των προβλημάτων που εξετάζονται παρακάτω ως παραδείγματα είναι ήδη γνωστά 1). Λαμβάνοντας υπόψη τις παραπάνω παραδοχές, οι επόμενες ενέργειες για τον προσδιορισμό αποτελεσματικών τρόπων οργάνωσης παράλληλων υπολογιστών μπορεί να είναι οι εξής: Πραγματοποιήστε μια ανάλυση των υπαρχόντων υπολογιστικών σχημάτων και χωρίστε τα (αποσύνθεση) σε μέρη (υποεργασίες) που μπορούν να υλοποιηθούν σε μεγάλο βαθμό ανεξάρτητα το ένα από το άλλο. Επιλέξτε για σχηματισμένο σύνολο υποεργασιών, αλληλεπιδράσεις πληροφοριών που πρέπει να πραγματοποιηθούν κατά την επίλυση της αρχικής εργασίας Καθορίστε το υπολογιστικό σύστημα που είναι απαραίτητο (ή διαθέσιμο) για την επίλυση του προβλήματος και διανείμετε το υπάρχον σύνολο υποεργασιών μεταξύ των επεξεργαστών του συστήματος. Σε γενικές γραμμές, είναι σαφές ότι η ποσότητα υπολογισμού για κάθε επεξεργαστή που χρησιμοποιείται θα πρέπει να είναι περίπου η ίδια, κάτι που θα εξασφαλίσει ομοιόμορφο υπολογιστικό φορτίο (εξισορρόπηση) των επεξεργαστών. Επιπλέον, είναι επίσης σαφές ότι η κατανομή των δευτερευουσών εργασιών μεταξύ των επεξεργαστών πρέπει να γίνεται με τέτοιο τρόπο ώστε η παρουσία συνδέσμων πληροφοριών (αλληλεπιδράσεις επικοινωνίας) μεταξύ των δευτερευουσών εργασιών να είναι ελάχιστη. 1) Παρά το γεγονός ότι για πολλά επιστημονικά και τεχνικά προβλήματα είναι πράγματι γνωστές όχι μόνο διαδοχικές αλλά και παράλληλες μέθοδοι επίλυσης, αυτή η υπόθεση είναι, φυσικά, πολύ ισχυρή, καθώς για νέα αναδυόμενα προβλήματα που απαιτούν μεγάλο αριθμό υπολογισμών για την επίλυσή τους, Η διαδικασία ανάπτυξης αλγορίθμων αποτελεί σημαντικό μέρος όλης της εργασίας που εκτελείται.

2 Διαίρεση υπολογισμών σε ανεξάρτητα μέρη Απομόνωση εξαρτήσεων πληροφοριών Κλιμάκωση υποεργασιών Κατανομή υποεργασιών μεταξύ επεξεργαστών Εικ. Γενικό σχήμα για την ανάπτυξη παράλληλων αλγορίθμων Μετά την ολοκλήρωση όλων των αναφερόμενων σταδίων σχεδιασμού, μπορείτε να αξιολογήσετε την αποτελεσματικότητα των ανεπτυγμένων παράλληλων μεθόδων Αυτό, συνήθως καθορίζονται οι τιμές των δεικτών ποιότητας των παραγόμενων παράλληλων υπολογισμών (επιτάχυνση, απόδοση, επεκτασιμότητα). Με βάση τα αποτελέσματα της ανάλυσης, μπορεί να είναι απαραίτητο να επαναληφθούν μεμονωμένα (στην ακραία περίπτωση όλα) στάδια ανάπτυξης, πρέπει να σημειωθεί ότι η επιστροφή στα προηγούμενα βήματα ανάπτυξης μπορεί να συμβεί σε οποιοδήποτε στάδιο του σχεδιασμού των παράλληλων υπολογιστικών κυκλωμάτων. Από αυτή την άποψη, μια πρόσθετη ενέργεια που εκτελείται συχνά στο παραπάνω σχήμα σχεδίασης είναι η προσαρμογή της σύνθεσης του παραγόμενου συνόλου εργασιών μετά τον προσδιορισμό του διαθέσιμου αριθμού υποεργασιών που μπορούν να μεγεθυνθούν (συγκεντρωτικά) εάν υπάρχει μικρός αριθμός επεξεργαστών ή αντίθετα, αναλυτικά διαφορετικά. Γενικά, αυτές οι ενέργειες μπορούν να οριστούν ως κλιμάκωση του αναπτυγμένου αλγόριθμου και να αναγνωριστούν ως ξεχωριστό στάδιο στο σχεδιασμό παράλληλων υπολογιστών. Για να εφαρμοστεί η παράλληλη μέθοδος που τελικά προέκυψε, είναι απαραίτητο να αναπτυχθούν προγράμματα για την επίλυση του παραγόμενου συνόλου δευτερευουσών εργασιών και να τοποθετηθούν τα αναπτυγμένα προγράμματα σε επεξεργαστές σύμφωνα με το επιλεγμένο σχήμα διανομής υποεργασιών. Για τη διενέργεια υπολογισμών, τα προγράμματα ξεκινούν για εκτέλεση (τα προγράμματα στο στάδιο της εκτέλεσης ονομάζονται συνήθως διαδικασίες για την υλοποίηση αλληλεπιδράσεων πληροφοριών, τα προγράμματα πρέπει να έχουν στη διάθεσή τους μέσα ανταλλαγής δεδομένων (κανάλια μετάδοσης μηνυμάτων). Θα πρέπει να σημειωθεί ότι κάθε επεξεργαστής συνήθως εκχωρείται για την επίλυση μιας μεμονωμένης δευτερεύουσας εργασίας, ωστόσο, εάν υπάρχει μεγάλος αριθμός δευτερευουσών εργασιών ή χρησιμοποιείται περιορισμένος αριθμός επεξεργαστών, αυτός ο κανόνας ενδέχεται να μην τηρηθεί και, ως αποτέλεσμα, πολλά προγράμματα (διεργασίες ) μπορεί να εκτελεστεί ταυτόχρονα στους επεξεργαστές. Ειδικότερα, κατά την ανάπτυξη και την αρχική δοκιμή ενός παράλληλου προγράμματος, ένας επεξεργαστής μπορεί να χρησιμοποιηθεί για την εκτέλεση όλων των διεργασιών (όταν βρίσκεται σε έναν επεξεργαστή, οι διεργασίες εκτελούνται σε λειτουργία χρονομερισμού). Έχοντας εξετάσει προσεκτικά το προσεκτικά αναπτυγμένο σχήμα για το σχεδιασμό και την υλοποίηση παράλληλων υπολογιστών, μπορεί να σημειωθεί ότι αυτή η προσέγγιση επικεντρώνεται σε μεγάλο βαθμό σε υπολογιστικά συστήματα με κατανεμημένη μνήμη, όταν οι απαραίτητες αλληλεπιδράσεις πληροφοριών υλοποιούνται με τη μετάδοση μηνυμάτων μέσω καναλιών επικοινωνίας μεταξύ των επεξεργαστών. Ωστόσο, αυτό το σχήμα μπορεί να χρησιμοποιηθεί χωρίς απώλεια της αποτελεσματικότητας του παράλληλου υπολογισμού και για την ανάπτυξη παράλληλων μεθόδων για συστήματα με κοινόχρηστη μνήμη, σε αυτήν την περίπτωση, μηχανισμοί μετάδοσης μηνυμάτων για να διασφαλιστεί ότι οι αλληλεπιδράσεις πληροφοριών πρέπει να αντικατασταθούν από λειτουργίες πρόσβασης σε κοινές (κοινόχρηστες) μεταβλητές. προγράμματα Το εξεταζόμενο σχήμα για το σχεδιασμό και την υλοποίηση παράλληλων υπολογιστών παρέχει έναν τρόπο κατανόησης παράλληλων αλγορίθμων και προγραμμάτων. Στο στάδιο του σχεδιασμού, μια παράλληλη μέθοδος μπορεί να αναπαρασταθεί με τη μορφή ενός γραφήματος «υποεργασίας μηνύματος», το οποίο δεν είναι τίποτα περισσότερο από μια μεγάλη (συγκεντρωτική) αναπαράσταση του γραφήματος εξάρτησης πληροφοριών (το γράφημα «λειτουργίες-τελεστές», βλέπε Ενότητα 2 ). Ομοίως, στο στάδιο της εκτέλεσης, για την περιγραφή ενός παράλληλου προγράμματος, μπορεί να χρησιμοποιηθεί ένα μοντέλο με τη μορφή γραφήματος «καναλιών διεργασίας», στο οποίο χρησιμοποιείται η έννοια των διεργασιών αντί για υποεργασίες και οι εξαρτήσεις πληροφοριών αντικαθίστανται από τα κανάλια 2.

3 μεταδόσεις μηνυμάτων. Επιπλέον, αυτό το μοντέλο μπορεί να δείξει την κατανομή των διεργασιών μεταξύ των επεξεργαστών ενός συστήματος υπολογιστή εάν ο αριθμός των δευτερευουσών εργασιών υπερβαίνει τον αριθμό των επεξεργαστών, βλ. Εικ. διεργασίες - κανάλι - λήψη (μετάδοση) - κανάλια εισόδου (εξόδου) για αλληλεπίδραση μεταξύ διεργασίες Εικ Μοντέλο παράλληλου προγράμματος με τη μορφή γραφήματος «διαδικασία-κανάλια» Η χρήση δύο μοντέλων παράλληλων υπολογιστών 2) καθιστά δυνατό τον καλύτερο διαχωρισμό των προβλημάτων που προκύπτουν κατά την ανάπτυξη παράλληλων μεθόδων. Το πρώτο μοντέλο του γραφήματος «υποεργασίες - μηνύματα» σάς επιτρέπει να εστιάσετε στα ζητήματα αναγνώρισης δευτερευουσών εργασιών της ίδιας υπολογιστικής πολυπλοκότητας, διασφαλίζοντας παράλληλα χαμηλό επίπεδο εξάρτησης πληροφοριών μεταξύ των δευτερευουσών εργασιών. Το δεύτερο μοντέλο του γραφήματος «κανάλια διεργασίας» εστιάζει στα ζητήματα της κατανομής δευτερευουσών εργασιών μεταξύ των επεξεργαστών, παρέχοντας μια άλλη ευκαιρία να μειωθεί η πολυπλοκότητα των αλληλεπιδράσεων πληροφοριών μεταξύ των δευτερευουσών εργασιών τοποθετώντας διαδικασίες εντατικής αλληλεπίδρασης στους ίδιους επεξεργαστές. Επιπλέον, αυτό το μοντέλο μας επιτρέπει να αναλύσουμε καλύτερα την αποτελεσματικότητα της αναπτυγμένης παράλληλης μεθόδου και παρέχει τη δυνατότητα μιας πιο κατάλληλης περιγραφής της διαδικασίας του παράλληλου υπολογισμού. Ας δώσουμε επιπλέον επεξηγήσεις για τις έννοιες που χρησιμοποιούνται στο μοντέλο «διαδικασία-κανάλια»: Στο πλαίσιο αυτού του εκπαιδευτικού υλικού, ως διεργασία εννοούμε ένα πρόγραμμα που εκτελείται στον επεξεργαστή, το οποίο χρησιμοποιεί μέρος της τοπικής μνήμης του επεξεργαστή για την εργασία του. και περιέχει έναν αριθμό λειτουργιών για τη λήψη/μετάδοση δεδομένων για την οργάνωση της αλληλεπίδρασης πληροφοριών μεταξύ των διεργασιών εκτέλεσης ενός παράλληλου προγράμματος Ένα κανάλι δεδομένων μπορεί να θεωρηθεί από λογική άποψη ως μια ουρά μηνυμάτων στην οποία μία ή περισσότερες διεργασίες μπορούν να στείλουν προωθημένα δεδομένα. και από το οποίο η διαδικασία προορισμού μπορεί να ανακτήσει μηνύματα που έχουν αποσταλεί από άλλες διεργασίες. Γενικά, μπορούμε να υποθέσουμε ότι τα κανάλια προκύπτουν δυναμικά τη στιγμή που εκτελείται η πρώτη λειτουργία λήψης/μετάδοσης στο κανάλι. Σε γενικές γραμμές, ένα κανάλι μπορεί να αντιστοιχεί σε μία ή περισσότερες εντολές για τη λήψη δεδομένων από τη διαδικασία του παραλήπτη. Ομοίως, κατά τη μετάδοση μηνυμάτων, ένα κανάλι μπορεί να χρησιμοποιηθεί από μία ή περισσότερες εντολές μεταφοράς δεδομένων από μία ή περισσότερες διεργασίες. Για να μειώσουμε την πολυπλοκότητα της μοντελοποίησης και της ανάλυσης των παράλληλων μεθόδων, θα υποθέσουμε ότι η χωρητικότητα του καναλιού είναι απεριόριστη και, ως αποτέλεσμα, οι λειτουργίες μεταφοράς δεδομένων εκτελούνται σχεδόν χωρίς καθυστέρηση με απλή αντιγραφή μηνυμάτων στο κανάλι. Από την άλλη πλευρά, οι λειτουργίες λήψης μηνυμάτων ενδέχεται να οδηγήσουν σε καθυστερήσεις (μπλοκάρισμα) εάν τα δεδομένα που ζητούνται από το κανάλι δεν έχουν ακόμη σταλεί από τις διεργασίες πηγής μηνύματος. Θα πρέπει να σημειωθεί ότι το σημαντικό πλεονέκτημα του θεωρούμενου μοντέλου «διαδικασίας-καναλιού» είναι ότι σε αυτό το μοντέλο υπάρχει σαφής διαχωρισμός των τοπικών (που εκτελούνται σε ξεχωριστό επεξεργαστή) υπολογισμούς και 2) Στο Foster (1995), μόνο ένα μοντέλο είναι θεωρηθεί, το μοντέλο του «καναλιού εργασιών» για την περιγραφή παράλληλων υπολογιστών, το οποίο παίρνει κάποια ενδιάμεση θέση σε σύγκριση με τα μοντέλα που παρουσιάζονται εδώ. Έτσι, το μοντέλο του «καναλιού εργασιών» δεν λαμβάνει υπόψη τη δυνατότητα χρήσης ενός επεξεργαστή για την επίλυση πολλών δευτερευουσών εργασιών ταυτόχρονα. 3

4 ενέργειες για την οργάνωση της αλληλεπίδρασης πληροφοριών μεταξύ διαδικασιών που εκτελούνται ταυτόχρονα. Αυτή η προσέγγιση μειώνει σημαντικά την πολυπλοκότητα της ανάλυσης της αποτελεσματικότητας των παράλληλων μεθόδων και απλοποιεί σημαντικά τα προβλήματα ανάπτυξης παράλληλων αλγορίθμων. Ας εξετάσουμε λεπτομερέστερα τη μεθοδολογία για την ανάπτυξη παράλληλων αλγορίθμων. Σε μεγάλο βαθμό, αυτή η τεχνική βασίζεται στην προσέγγιση που συζητήθηκε για πρώτη φορά στο Foster (1995) και, όπως σημειώθηκε νωρίτερα, περιλαμβάνει τα στάδια αναγνώρισης δευτερευουσών εργασιών, προσδιορισμού εξαρτήσεων πληροφοριών, κλιμάκωσης και διανομής δευτερευουσών εργασιών στους επεξεργαστές του συστήματος υπολογιστών (βλ. 6.1). Για να δείξουμε τις συστάσεις που δίνονται, θα χρησιμοποιήσουμε περαιτέρω το εκπαιδευτικό πρόβλημα της εύρεσης της μέγιστης τιμής μεταξύ των στοιχείων του πίνακα Α (ένα τέτοιο πρόβλημα προκύπτει, για παράδειγμα, κατά την αριθμητική επίλυση συστημάτων γραμμικών εξισώσεων για τον προσδιορισμό του κύριου στοιχείου της μεθόδου Gauss) : y = μέγιστο α. 1 i, j N i j Αυτό το πρόβλημα είναι καθαρά ενδεικτικό και μετά την ανασκόπηση των βημάτων ανάπτυξης, το υπόλοιπο αυτής της ενότητας θα παρέχει ένα πιο ολοκληρωμένο παράδειγμα χρήσης αυτής της τεχνικής για την ανάπτυξη παράλληλων αλγορίθμων. Επιπλέον, αυτό το σχήμα ανάπτυξης θα εφαρμοστεί κατά την παρουσίαση όλων των παράλληλων υπολογιστικών μεθόδων που εξετάζονται παρακάτω. Διαίρεση υπολογισμών σε ανεξάρτητα μέρη. πρόβλημα. Οι απαιτήσεις που πρέπει να ικανοποιεί η επιλεγμένη προσέγγιση συνήθως συνίστανται στην εξασφάλιση ίσου υπολογισμού στις επιμέρους εργασίες και ελάχιστης εξάρτησης πληροφοριών μεταξύ αυτών των δευτερευουσών εργασιών (όσον αφορά άλλα πράγματα, θα πρέπει να προτιμώνται σπάνιες λειτουργίες μεταφοράς μεγάλων μηνυμάτων έναντι συχνών μεταφορών μικρών δεδομένων). Στη γενική περίπτωση, η διεξαγωγή ανάλυσης και ο εντοπισμός εργασιών είναι ένα μάλλον περίπλοκο πρόβλημα, η κατάσταση βοηθά στην επίλυση της ύπαρξης δύο τύπων υπολογιστικών σχημάτων: α) β) Εικ. Διαίρεση δεδομένων για τον πίνακα Α: α) σχήμα ταινιών. β) σχήμα μπλοκ Για μια μεγάλη κατηγορία υπολογιστικών προβλημάτων μειώνονται στην εκτέλεση του ίδιου τύπου επεξεργασίας στοιχείων ενός μεγάλου συνόλου δεδομένων Αυτός ο τύπος εργασίας περιλαμβάνει, για παράδειγμα, υπολογισμούς πινάκων, αριθμητικές μεθόδους για την επίλυση μερικών διαφορικών εξισώσεων κ.λπ. Σε αυτήν την περίπτωση, λένε ότι υπάρχει παραλληλισμός δεδομένων και η επιλογή των δευτερευουσών εργασιών καταλήγει στη διαίρεση των διαθέσιμων δεδομένων. Έτσι, για παράδειγμα, για το εκπαιδευτικό μας έργο να βρούμε τη μέγιστη τιμή κατά το σχηματισμό δευτερευουσών εργασιών, ο αρχικός πίνακας Α μπορεί να χωριστεί σε μεμονωμένες σειρές (ή διαδοχικές ομάδες σειρών) - ένα σχήμα διαχωρισμού δεδομένων λωρίδων (βλ. Εικ. 6.3) ή σε ορθογώνιο σύνολα στοιχείων - ένα σχήμα διαχωρισμού δεδομένων μπλοκ. Για μεγάλο αριθμό προβλημάτων που επιλύονται, η διαίρεση των υπολογισμών με τα δεδομένα οδηγεί στη δημιουργία μονοδιάστατων, δύο και τρισδιάστατων συνόλων υποπροβλημάτων για τα οποία υπάρχουν συνδέσεις πληροφοριών μόνο μεταξύ των πλησιέστερων γειτόνων (τέτοια σχήματα ονομάζονται συνήθως πλέγματα ή πλέγματα) , 4

5 Εικ. Κανονικές μονοδιάστατες, δύο και τρισδιάστατες δομές βασικών δευτερευουσών εργασιών μετά την αποσύνθεση δεδομένων Για ένα άλλο μέρος των προβλημάτων, οι υπολογισμοί μπορεί να συνίστανται στην εκτέλεση διαφορετικών πράξεων στο ίδιο σύνολο δεδομένων, σε αυτή την περίπτωση, μιλούν για την ύπαρξη του λειτουργικού παραλληλισμού (παραδείγματα περιλαμβάνουν εργασίες επεξεργασίας μιας ακολουθίας ερωτημάτων σε βάσεις δεδομένων πληροφοριών, υπολογισμούς με την ταυτόχρονη χρήση διαφορετικών αλγορίθμων υπολογισμού κ.λπ.). Πολύ συχνά, η λειτουργική αποσύνθεση μπορεί να χρησιμοποιηθεί για την οργάνωση της επεξεργασίας δεδομένων διοχέτευσης (για παράδειγμα, κατά την εκτέλεση οποιωνδήποτε μετασχηματισμών δεδομένων, οι υπολογισμοί μπορούν να μειωθούν σε μια λειτουργική ακολουθία εισαγωγής, επεξεργασίας και αποθήκευσης δεδομένων). Ένα σημαντικό ζήτημα κατά τον προσδιορισμό των δευτερευουσών εργασιών είναι η επιλογή του επιθυμητού επιπέδου αποσύνθεσης των υπολογισμών. Ο σχηματισμός του μέγιστου δυνατού αριθμού υποεργασιών διασφαλίζει τη χρήση του μέγιστου επιτεύξιμου επιπέδου παραλληλισμού του προβλήματος που επιλύεται, αλλά περιπλέκει την ανάλυση των παράλληλων υπολογισμών. Η χρήση μόνο αρκετά «μεγάλων» δευτερευουσών εργασιών κατά την αποσύνθεση των υπολογισμών οδηγεί σε ένα σαφές σχήμα παράλληλου υπολογισμού, αλλά μπορεί να δυσχεράνει την αποτελεσματική χρήση ενός αρκετά μεγάλου αριθμού επεξεργαστών. Ένας πιθανός εύλογος συνδυασμός αυτών των δύο προσεγγίσεων μπορεί να συνίσταται στη χρήση ως κατασκευαστικών στοιχείων αποσύνθεσης μόνο εκείνων των υποπροβλημάτων για τα οποία είναι γνωστές παράλληλες μέθοδοι υπολογισμού. Για παράδειγμα, όταν αναλύετε ένα πρόβλημα πολλαπλασιασμού πίνακα, μπορείτε να χρησιμοποιήσετε μεθόδους διανυσματικών βαθμωτών γινομένων ή αλγόριθμους προϊόντος μήτρας-διανύσματος ως υποπροβλήματα. Μια τέτοια ενδιάμεση μέθοδος αποσύνθεσης υπολογισμών θα εξασφαλίσει τόσο την απλότητα της αναπαράστασης των υπολογιστικών σχημάτων όσο και την αποτελεσματικότητα των παράλληλων υπολογισμών. Σε αυτήν την προσέγγιση, θα αναφερθούμε περαιτέρω στις επιλεγμένες δευτερεύουσες εργασίες ως βασικές, οι οποίες μπορεί να είναι στοιχειώδεις (αδιαίρετες) εάν δεν επιτρέπουν περαιτέρω διαίρεση ή σύνθετες διαφορετικά. Για την υπό εξέταση εκπαιδευτική εργασία, ένα επαρκές επίπεδο αποσύνθεσης μπορεί να συνίσταται, για παράδειγμα, στη διαίρεση του πίνακα Α σε πολλές μεμονωμένες σειρές και στη λήψη σε αυτή τη βάση ενός συνόλου δευτερευουσών εργασιών για την εύρεση μέγιστων τιμών σε μεμονωμένες σειρές. η δομή των συνδέσεων πληροφοριών που δημιουργούνται σε αυτή την περίπτωση αντιστοιχεί σε ένα γραμμικό γράφημα, βλ. Εικ. Για να αξιολογήσετε την ορθότητα του σταδίου διαίρεσης των υπολογισμών σε ανεξάρτητα μέρη, μπορείτε να χρησιμοποιήσετε τη λίστα ελέγχου των ερωτήσεων που προτείνονται στο Foster (1995): Does the decomposition perform να μην αυξηθεί ο όγκος των υπολογισμών και η απαιτούμενη ποσότητα μνήμης; Με την επιλεγμένη μέθοδο αποσύνθεσης, είναι δυνατή η ομοιόμορφη φόρτωση όλων των διαθέσιμων επεξεργαστών; Είναι επαρκή τα ειδικά μέρη της υπολογιστικής διαδικασίας για την αποτελεσματική φόρτωση των υπαρχόντων επεξεργαστών (λαμβάνοντας υπόψη την πιθανότητα αύξησης του αριθμού τους); Προσδιορισμός εξαρτήσεων πληροφοριών Εάν υπάρχει ένα υπολογιστικό σχήμα για την επίλυση ενός προβλήματος, μετά τον προσδιορισμό των βασικών δευτερευουσών εργασιών, ο προσδιορισμός των εξαρτήσεων πληροφοριών μεταξύ των δευτερευουσών εργασιών συνήθως δεν προκαλεί μεγάλη δυσκολία. Ταυτόχρονα, ωστόσο, θα πρέπει να σημειωθεί ότι στην πραγματικότητα, τα στάδια αναγνώρισης επιμέρους εργασιών και εξαρτήσεων πληροφοριών είναι αρκετά δύσκολο να διαχωριστούν. Η κατανομή των επιμέρους εργασιών θα πρέπει να λαμβάνει υπόψη τις αναδυόμενες συνδέσεις πληροφοριών. Μετά την ανάλυση του όγκου και της συχνότητας των απαραίτητων ανταλλαγών πληροφοριών μεταξύ των δευτερευουσών εργασιών, μπορεί να χρειαστεί να επαναλάβετε το στάδιο των υπολογισμών διαίρεσης. Κατά την ανάλυση των εξαρτήσεων πληροφοριών μεταξύ δευτερευουσών εργασιών, θα πρέπει να γίνει διάκριση (υπογραμμίζονται οι προτιμώμενες μορφές αλληλεπίδρασης πληροφοριών): Τα τοπικά και καθολικά σχήματα μεταφοράς δεδομένων για τοπικά σχήματα μεταφοράς δεδομένων σε κάθε χρονική στιγμή εκτελούνται μόνο μεταξύ ενός μικρού αριθμού δευτερευουσών εργασιών (που βρίσκονται ως 5

6 συνήθως σε γειτονικούς επεξεργαστές), για τις παγκόσμιες λειτουργίες μεταφοράς δεδομένων, όλες οι υποεργασίες συμμετέχουν στη διαδικασία επικοινωνίας Δομικές και αυθαίρετες μέθοδοι αλληλεπίδρασης Για τις δομικές μεθόδους, η οργάνωση των αλληλεπιδράσεων οδηγεί στο σχηματισμό ορισμένων τυπικών σχημάτων επικοινωνίας (για παράδειγμα, σε. τη μορφή ενός δακτυλίου, ενός ορθογώνιου πλέγματος, κ.λπ.), για αυθαίρετες δομές αλληλεπίδρασης, το σχήμα των πράξεων μεταφοράς δεδομένων δεν είναι ομοιογενές στατικά σχήματα ή δυναμικά σχήματα μεταφοράς δεδομένων Η αλληλεπίδραση καθορίζεται στα στάδια του σχεδιασμού και της ανάπτυξης παράλληλων προγραμμάτων για μια δυναμική έκδοση της αλληλεπίδρασης, η δομή της λειτουργίας μεταφοράς δεδομένων καθορίζεται κατά τους υπολογισμούς που εκτελούνται. εκτελείται μόνο όταν όλοι οι συμμετέχοντες στην αλληλεπίδραση είναι έτοιμοι και ολοκληρώνονται μόνο μετά την πλήρη ολοκλήρωση όλων των ενεργειών επικοινωνίας κατά την εκτέλεση ασύγχρονων λειτουργιών, οι συμμετέχοντες στην αλληλεπίδραση δεν χρειάζεται να περιμένουν την πλήρη ολοκλήρωση των ενεργειών μεταφοράς δεδομένων. Για τις παρουσιαζόμενες μεθόδους αλληλεπίδρασης, είναι αρκετά δύσκολο να εντοπιστούν οι προτιμώμενες μορφές οργάνωσης της μεταφοράς δεδομένων: η σύγχρονη επιλογή είναι, κατά κανόνα, πιο εύκολη στη χρήση, ενώ η ασύγχρονη μέθοδος μπορεί συχνά να μειώσει σημαντικά τις χρονικές καθυστερήσεις που προκαλούνται από λειτουργίες αλληλεπίδρασης πληροφοριών. Όπως σημειώθηκε στην προηγούμενη παράγραφο, για το εκπαιδευτικό έργο της αναζήτησης της μέγιστης τιμής, όταν χρησιμοποιείτε δευτερεύουσες εργασίες αναζήτησης μέγιστων τιμών σε μεμονωμένες σειρές του αρχικού πίνακα Α ως βασικά στοιχεία, η δομή των συνδέσεων πληροφοριών έχει τη μορφή που φαίνεται στο Εικ. Εικ. Δομή των συνδέσεων πληροφοριών της εκπαιδευτικής εργασίας Όπως και πριν, για την αξιολόγηση Για να διασφαλίσετε την ορθότητα του σταδίου αναγνώρισης εξαρτήσεων πληροφοριών, μπορείτε να χρησιμοποιήσετε τη λίστα ελέγχου των ερωτήσεων που προτείνονται στο Foster (1995): Αντιστοιχεί η υπολογιστική πολυπλοκότητα των δευτερευουσών εργασιών στην ένταση των αλληλεπιδράσεων πληροφοριών τους; Είναι η ένταση των αλληλεπιδράσεων πληροφοριών η ίδια για διαφορετικές επιμέρους εργασίες; Είναι τοπικό το σχήμα αλληλεπίδρασης πληροφοριών; Αποτρέπει η προσδιορισμένη εξάρτηση από πληροφορίες την παράλληλη επίλυση δευτερευουσών εργασιών; Κλιμάκωση ενός συνόλου δευτερευουσών εργασιών Η κλιμάκωση του αναπτυγμένου σχεδίου παράλληλων υπολογιστών πραγματοποιείται εάν ο αριθμός των διαθέσιμων δευτερευουσών εργασιών διαφέρει από τον αριθμό των επεξεργαστών που έχουν προγραμματιστεί για χρήση. Για να μειωθεί ο αριθμός των δευτερευουσών εργασιών, είναι απαραίτητο να πραγματοποιηθεί μεγέθυνση (συγκέντρωση) των υπολογισμών. Οι κανόνες που χρησιμοποιούνται εδώ συμπίπτουν με τις συστάσεις του αρχικού σταδίου προσδιορισμού δευτερευόντων εργασιών, οι καθορισμένες υποεργασίες, όπως και πριν, πρέπει να έχουν την ίδια υπολογιστική πολυπλοκότητα και ο όγκος και η ένταση των αλληλεπιδράσεων πληροφοριών μεταξύ των δευτερευουσών εργασιών πρέπει να παραμένουν στο ελάχιστο δυνατό επίπεδο. Ως αποτέλεσμα, οι πρώτοι υποψήφιοι για συγχώνευση είναι δευτερεύουσες εργασίες με υψηλό βαθμό αλληλεξάρτησης πληροφοριών. Εάν το διαθέσιμο σύνολο δευτερευουσών εργασιών είναι ανεπαρκές για τη φόρτωση όλων των διαθέσιμων επεξεργαστών για χρήση, είναι απαραίτητο να πραγματοποιήσετε λεπτομερείς υπολογισμούς (αποσύνθεση). Όπως 6

7 Κατά κανόνα, η διεξαγωγή μιας τέτοιας αποσύνθεσης δεν προκαλεί δυσκολίες εάν είναι γνωστές μέθοδοι παράλληλων υπολογιστών για βασικά προβλήματα. Η υλοποίηση του σταδίου κλιμάκωσης υπολογισμού θα πρέπει τελικά να καταλήγει στην ανάπτυξη κανόνων για τη συγκέντρωση και την αποσύνθεση των δευτερευουσών εργασιών, οι οποίες θα πρέπει να εξαρτώνται παραμετρικά από τον αριθμό των επεξεργαστών που χρησιμοποιούνται για τους υπολογισμούς. Για το εκπαιδευτικό έργο της εύρεσης της μέγιστης τιμής που εξετάζεται, η συνάθροιση των υπολογισμών μπορεί να συνίσταται στο συνδυασμό μεμονωμένων σειρών σε ομάδες (σχήμα κορδέλας για τη διαίρεση του πίνακα, βλ. Εικ. 6.3α κατά την αποσύνθεση των δευτερευουσών εργασιών, τις σειρές του αρχικού πίνακα Α). μπορεί να χωριστεί σε πολλά μέρη (μπλοκ). Η λίστα ελέγχου που προτείνεται από τον Foster (1995) για την αξιολόγηση της ορθότητας του βήματος κλιμάκωσης είναι η εξής: Θα επιδεινωθεί η υπολογιστική τοποθεσία μετά την κλιμάκωση του υπάρχοντος συνόλου υποπροβλημάτων; Οι δευτερεύουσες εργασίες μετά την κλιμάκωση έχουν την ίδια υπολογιστική και επικοινωνιακή πολυπλοκότητα; Ο αριθμός των εργασιών ταιριάζει με τον αριθμό των διαθέσιμων επεξεργαστών; Οι κανόνες κλιμάκωσης εξαρτώνται παραμετρικά από τον αριθμό των επεξεργαστών; Κατανομή δευτερευουσών εργασιών μεταξύ επεξεργαστών Η διανομή δευτερευουσών εργασιών μεταξύ επεξεργαστών είναι το τελικό στάδιο ανάπτυξης μιας παράλληλης μεθόδου. Πρέπει να σημειωθεί ότι ο έλεγχος της κατανομής φορτίου για επεξεργαστές είναι δυνατός μόνο για υπολογιστικά συστήματα με κατανεμημένη μνήμη για πολυεπεξεργαστές (συστήματα με κοινόχρηστη μνήμη), η κατανομή φορτίου συνήθως εκτελείται αυτόματα από το λειτουργικό σύστημα. Επιπλέον, αυτό το στάδιο κατανομής δευτερευουσών εργασιών μεταξύ επεξεργαστών είναι περιττό εάν ο αριθμός των δευτερευουσών εργασιών συμπίπτει με τον αριθμό των διαθέσιμων επεξεργαστών και η τοπολογία του δικτύου μετάδοσης δεδομένων του συστήματος υπολογιστή είναι ένα πλήρες γράφημα (δηλαδή, όλοι οι επεξεργαστές διασυνδέονται απευθείας γραμμές επικοινωνίας). Ο κύριος δείκτης της επιτυχίας αυτού του σταδίου είναι η αποτελεσματικότητα της χρήσης του επεξεργαστή, που ορίζεται ως η σχετική αναλογία χρόνου κατά τη διάρκεια του οποίου χρησιμοποιήθηκαν οι επεξεργαστές για υπολογισμούς που σχετίζονται με την επίλυση του αρχικού προβλήματος. Οι τρόποι για την επίτευξη καλών αποτελεσμάτων προς αυτή την κατεύθυνση παραμένουν οι ίδιοι όπως πριν, είναι απαραίτητο να εξασφαλιστεί ομοιόμορφη κατανομή του υπολογιστικού φορτίου μεταξύ των επεξεργαστών και να ελαχιστοποιηθεί ο αριθμός των μηνυμάτων που μεταδίδονται μεταξύ των επεξεργαστών. Με τον ίδιο τρόπο όπως και στα προηγούμενα στάδια σχεδιασμού, η βέλτιστη λύση στο πρόβλημα της κατανομής δευτερευουσών εργασιών μεταξύ των επεξεργαστών βασίζεται σε μια ανάλυση της συνδεσιμότητας πληροφοριών του γραφήματος «υποεργασίες - μηνύματα». Έτσι, ειδικότερα, είναι σκόπιμο να τοποθετούνται υποεργασίες μεταξύ των οποίων υπάρχουν αλληλεπιδράσεις πληροφοριών σε επεξεργαστές μεταξύ των οποίων υπάρχουν άμεσες γραμμές δεδομένων. Θα πρέπει να σημειωθεί ότι η απαίτηση ελαχιστοποίησης των ανταλλαγών πληροφοριών μεταξύ των επεξεργαστών μπορεί να έρχεται σε αντίθεση με την προϋπόθεση του ομοιόμορφου φορτίου διεργασίας. Έτσι, μπορούμε να τοποθετήσουμε όλες τις δευτερεύουσες εργασίες σε έναν επεξεργαστή και να εξαλείψουμε εντελώς τη διέλευση μηνυμάτων μεταξύ των επεξεργαστών, ωστόσο, φυσικά, ο φόρτος στους περισσότερους επεξεργαστές σε αυτήν την περίπτωση θα είναι ελάχιστος. Για το εκπαιδευτικό μας έργο αναζήτησης της μέγιστης τιμής, η κατανομή των δευτερευουσών εργασιών μεταξύ των επεξεργαστών δεν προκαλεί δυσκολίες, είναι απαραίτητο μόνο να διασφαλίσουμε ότι οι δευτερεύουσες εργασίες μεταξύ των οποίων υπάρχουν συνδέσεις πληροφοριών τοποθετούνται σε επεξεργαστές για τους οποίους υπάρχουν απευθείας κανάλια μεταφοράς δεδομένων. . Δεδομένου ότι η δομή των συνδέσεων πληροφοριών μιας εκπαιδευτικής εργασίας έχει τη μορφή γραμμικού γραφήματος, η εκπλήρωση αυτής της απαίτησης μπορεί να διασφαλιστεί για σχεδόν οποιαδήποτε τοπολογία δικτύου υπολογιστών. Η επίλυση των ζητημάτων εξισορρόπησης του υπολογιστικού φορτίου γίνεται πολύ πιο περίπλοκη εάν το σχήμα υπολογισμού μπορεί να αλλάξει κατά την επίλυση του προβλήματος. Ο λόγος για αυτό μπορεί να είναι, για παράδειγμα, τα ανομοιογενή πλέγματα κατά την επίλυση μερικών διαφορικών εξισώσεων, η αραιότητα των πινάκων κ.λπ. 3). Επιπλέον, οι εκτιμήσεις της υπολογιστικής πολυπλοκότητας της επίλυσης υποπροβλημάτων που χρησιμοποιούνται στα στάδια του σχεδιασμού μπορούν να είναι κατά προσέγγιση και, τέλος, ο αριθμός των υποπροβλημάτων μπορεί να αλλάξει κατά τη διάρκεια των υπολογισμών. Σε τέτοιες περιπτώσεις, μπορεί να είναι απαραίτητο να ανακατανεμηθούν οι βασικές δευτερεύουσες εργασίες μεταξύ 3) Μπορεί να σημειωθεί ότι ακόμη και για την απλή εκπαιδευτική μας εργασία, μπορεί να παρατηρηθεί διαφορετική υπολογιστική πολυπλοκότητα των δημιουργούμενων βασικών εργασιών. Έτσι, για παράδειγμα, ο αριθμός των λειτουργιών κατά την αναζήτηση της μέγιστης τιμής για μια σειρά στην οποία το πρώτο στοιχείο έχει τη μέγιστη τιμή και μια σειρά στην οποία οι τιμές ταξινομούνται σε αύξουσα σειρά θα διαφέρει κατά δύο. 7

8 επεξεργαστές βρίσκονται ήδη απευθείας στη διαδικασία εκτέλεσης ενός παράλληλου προγράμματος (ή, όπως συνήθως λένε, θα πρέπει να εκτελέσετε δυναμική εξισορρόπηση του υπολογιστικού φορτίου). Αυτά τα ζητήματα είναι από τα πιο δύσκολα (και πιο ενδιαφέροντα) στον τομέα των παράλληλων υπολογιστών, δυστυχώς, η εξέταση αυτών των θεμάτων ξεφεύγει από το πεδίο εφαρμογής αυτού του σεμιναρίου (πρόσθετες πληροφορίες μπορούν να ληφθούν, για παράδειγμα, από τους Buyya (1999) και Wilkinson. Allen (1999)). Ως παράδειγμα, θα δώσουμε μια σύντομη περιγραφή μιας ευρέως χρησιμοποιούμενης μεθόδου δυναμικής διαχείρισης της κατανομής του υπολογιστικού φορτίου, που συνήθως ονομάζεται σχήμα διαχειριστή-εργαζομένου. Κατά τη χρήση αυτής της προσέγγισης, θεωρείται ότι οι δευτερεύουσες εργασίες μπορούν να προκύψουν και να ολοκληρωθούν κατά τη διάρκεια των υπολογισμών, ενώ οι αλληλεπιδράσεις πληροφοριών μεταξύ των δευτερευουσών εργασιών είτε απουσιάζουν εντελώς είτε είναι ελάχιστες. Σύμφωνα με το υπό εξέταση σχήμα, εκχωρείται ένας ξεχωριστός επεξεργαστής-διαχειριστής για τη διαχείριση της κατανομής φορτίου στο σύστημα, ο οποίος έχει πρόσβαση σε πληροφορίες σχετικά με όλες τις διαθέσιμες δευτερεύουσες εργασίες. Οι υπόλοιποι επεξεργαστές του συστήματος είναι εκτελεστές που επικοινωνούν με τον διαχειριστή επεξεργαστή για να λάβουν το υπολογιστικό φορτίο. Οι νέες δευτερεύουσες εργασίες που δημιουργούνται κατά τους υπολογισμούς μεταφέρονται πίσω στον επεξεργαστή διαχειριστή και μπορούν να ληφθούν για επίλυση κατά τις επόμενες κλήσεις από τους επεξεργαστές που εκτελούν. Η ολοκλήρωση των υπολογισμών πραγματοποιείται τη στιγμή που οι επεξεργαστές που εκτελούν έχουν ολοκληρώσει τη λύση όλων των δευτερευουσών εργασιών που τους έχουν μεταφερθεί και ο επεξεργαστής διαχειριστής δεν έχει καμία υπολογιστική εργασία να εκτελέσει. Η λίστα ελέγχου του Foster (1995) για τον έλεγχο της φάσης κατανομής υποεργασιών είναι η εξής: Η κατανομή πολλαπλών εργασιών σε έναν μόνο επεξεργαστή εισάγει πρόσθετο υπολογιστικό κόστος; Υπάρχει ανάγκη για δυναμική εξισορρόπηση των υπολογισμών; Δεν είναι ο διαχειριστής-επεξεργαστής συμφόρηση κατά τη χρήση του σχήματος διαχειριστή-εκτελεστή; 6.3. Παράλληλη λύση του προβλήματος της βαρύτητας του Ν-σώματος Πολλά υπολογιστικά προβλήματα στον τομέα της φυσικής οφείλονται σε λειτουργίες επεξεργασίας δεδομένων για κάθε ζεύγος αντικειμένων στο υπάρχον φυσικό σύστημα. Ένα τέτοιο πρόβλημα είναι, ειδικότερα, το πρόβλημα που είναι ευρέως γνωστό στη βιβλιογραφία ως πρόβλημα βαρύτητας Ν-σώματος (ή απλά το πρόβλημα του σώματος Ν), βλέπε, για παράδειγμα, Andrews (2000), στην πιο γενική του μορφή, το πρόβλημα μπορεί να περιγραφεί ως εξής. Ας δοθεί ένας μεγάλος αριθμός σωμάτων (πλανήτες, αστέρια κ.λπ.). ), για καθένα από τα οποία είναι γνωστά η μάζα, η αρχική θέση και η ταχύτητα. Υπό την επίδραση της βαρύτητας, η θέση των σωμάτων αλλάζει και η απαιτούμενη λύση στο πρόβλημα είναι η προσομοίωση της δυναμικής αλλαγής ενός συστήματος Ν σωμάτων σε ένα συγκεκριμένο καθορισμένο χρονικό διάστημα. Για να πραγματοποιηθεί μια τέτοια προσομοίωση, ένα δεδομένο χρονικό διάστημα διαιρείται συνήθως σε χρονικά διαστήματα μικρής διάρκειας και στη συνέχεια σε κάθε βήμα μοντελοποίησης υπολογίζονται οι δυνάμεις που δρουν σε κάθε σώμα και στη συνέχεια ενημερώνονται οι ταχύτητες και οι θέσεις των σωμάτων. Ένας προφανής αλγόριθμος για την επίλυση του προβλήματος του σώματος Ν είναι να εξετάζουμε σε κάθε βήμα μοντελοποίησης όλα τα ζεύγη αντικειμένων του φυσικού συστήματος και να εκτελούμε όλους τους απαραίτητους υπολογισμούς για κάθε ζεύγος που προκύπτει. Ως αποτέλεσμα, με αυτήν την προσέγγιση, ο χρόνος εκτέλεσης για μία επανάληψη προσομοίωσης θα είναι 4) T = τ N(N 1) / 2, 1 όπου τ είναι ο χρόνος για τον επανυπολογισμό των παραμέτρων ενός ζεύγους σωμάτων. Όπως προκύπτει από την παραπάνω περιγραφή, το υπολογιστικό σχήμα του εξεταζόμενου αλγορίθμου είναι σχετικά απλό, γεγονός που καθιστά δυνατή τη χρήση του προβλήματος Ν-σώματος ως άλλη μια σαφή επίδειξη της εφαρμογής της μεθοδολογίας για την ανάπτυξη παράλληλων αλγορίθμων. 4) Πρέπει να σημειωθεί ότι υπάρχουν πιο αποτελεσματικοί διαδοχικοί αλγόριθμοι για την επίλυση του προβλήματος του Ν-σώματος, αλλά η μελέτη τους μπορεί να απαιτεί αρκετή προσπάθεια. Λαμβάνοντας υπόψη αυτήν την περίσταση, αυτή η «προφανής» (αλλά όχι η ταχύτερη) μέθοδος επιλέγεται για περαιτέρω εξέταση, αν και, στη γενική περίπτωση, φυσικά, τα καλύτερα σχήματα υπολογισμού θα πρέπει να επιλέγονται για παραλληλισμό. 8

9 Διαίρεση υπολογισμών σε ανεξάρτητα μέρη Η επιλογή μιας μεθόδου για τη διαίρεση των υπολογισμών δεν προκαλεί δυσκολίες - η προφανής προσέγγιση είναι να επιλέξετε ως βασική υποεργασία ολόκληρο το σύνολο των υπολογισμών που σχετίζονται με την επεξεργασία δεδομένων από ένα σώμα ενός φυσικού συστήματος Απομόνωση εξαρτήσεων πληροφοριών Εκτέλεση υπολογισμών που σχετίζεται με κάθε δευτερεύουσα εργασία, καθίσταται δυνατή μόνο εάν οι δευτερεύουσες εργασίες περιέχουν δεδομένα (θέση και ταχύτητα κίνησης) για όλα τα σώματα του υπάρχοντος φυσικού συστήματος. Ως αποτέλεσμα, πριν ξεκινήσει κάθε επανάληψη προσομοίωσης, κάθε δευτερεύουσα εργασία πρέπει να λάβει όλες τις απαραίτητες πληροφορίες από όλες τις άλλες δευτερεύουσες εργασίες του συστήματος. Αυτή η διαδικασία μεταφοράς δεδομένων, όπως σημειώνεται στην Ενότητα 3, ονομάζεται λειτουργία συλλογής δεδομένων (συλλογή ενός κόμβου). Στον αλγόριθμο που εξετάζουμε, αυτή η λειτουργία πρέπει να εκτελείται για κάθε δευτερεύουσα εργασία, αυτή η επιλογή μεταφοράς δεδομένων αναφέρεται συνήθως ως λειτουργία γενικευμένης συλλογής δεδομένων (συλλογή πολλών κόμβων ή συλλογή όλων). Ο καθορισμός των απαιτήσεων για τα απαραίτητα αποτελέσματα της ανταλλαγής πληροφοριών δεν οδηγεί σε σαφή καθιέρωση της απαραίτητης ανταλλαγής πληροφοριών μεταξύ των επιμέρους εργασιών. Ο απλούστερος τρόπος για να πραγματοποιηθεί η απαραίτητη ανταλλαγή πληροφοριών είναι η υλοποίηση μιας ακολουθίας βημάτων, σε καθένα από τα οποία όλες οι υπάρχουσες υποεργασίες χωρίζονται σε ζεύγη και η ανταλλαγή δεδομένων πραγματοποιείται μεταξύ των υποεργασιών των ζευγών που προκύπτουν. Με τη σωστή οργάνωση της κατά ζεύγη διαίρεσης των υποεργασιών, η (Ν-1) επανάληψη των περιγραφόμενων ενεργειών θα οδηγήσει στην πλήρη υλοποίηση της απαιτούμενης λειτουργίας συλλογής δεδομένων. Η μέθοδος οργάνωσης της ανταλλαγής πληροφοριών που συζητήθηκε παραπάνω είναι αρκετά εντατική για τη συλλογή όλων των απαραίτητων δεδομένων απαιτεί (N-1) επαναλήψεις, καθεμία από τις οποίες εκτελεί ταυτόχρονα (N/2) λειτουργίες μεταφοράς δεδομένων. Για να μειώσετε τον απαιτούμενο αριθμό επαναλήψεων, μπορείτε να δώσετε προσοχή στο γεγονός ότι μετά την ολοκλήρωση του πρώτου βήματος της λειτουργίας συλλογής δεδομένων, οι δευτερεύουσες εργασίες θα περιέχουν ήδη όχι μόνο τα δικά τους δεδομένα, αλλά και τα δεδομένα των δευτερευουσών εργασιών με τις οποίες σχημάτισαν ζεύγη . Ως αποτέλεσμα, στη δεύτερη επανάληψη της συλλογής δεδομένων, θα είναι δυνατό να σχηματιστούν ζεύγη δευτερευουσών εργασιών για την ανταλλαγή δεδομένων για δύο σώματα του φυσικού συστήματος ταυτόχρονα, επομένως, μετά την ολοκλήρωση της δεύτερης επανάληψης, κάθε υποεργασία θα περιέχει πληροφορίες για τέσσερις φορείς του συστήματος κ.λπ. Όπως μπορείτε να δείτε, αυτή η μέθοδος υλοποίησης ανταλλαγών σάς επιτρέπει να ολοκληρώσετε την απαραίτητη διαδικασία σε επαναλήψεις log 2 N. Θα πρέπει να σημειωθεί ότι ο όγκος των δεδομένων που αποστέλλονται σε κάθε λειτουργία ανταλλαγής διπλασιάζεται από επανάληψη σε επανάληψη, δεδομένα σχετικά με ένα σώμα του συστήματος αποστέλλονται μεταξύ των δευτερευουσών εργασιών, στη δεύτερη επανάληψη περίπου δύο σωμάτων κ.λπ. Η χρήση της εξεταζόμενης μεθόδου υλοποίησης μιας γενικευμένης λειτουργίας συλλογής δεδομένων οδηγεί στον προσδιορισμό της δομής των συνδέσεων πληροφοριών μεταξύ των υποεργασιών με τη μορφή υπερκύβου Ν-διάστασης Κλιμάκωση και κατανομή των υποεργασιών μεταξύ των επεξεργαστών Κατά κανόνα, ο αριθμός των σωμάτων ενός φυσικού συστήματος Το N υπερβαίνει σημαντικά τον αριθμό των επεξεργαστών p. Ως αποτέλεσμα, οι υποεργασίες που εξετάστηκαν προηγουμένως θα πρέπει να διευρυνθούν συνδυάζοντας υπολογισμούς για μια ομάδα σωμάτων (N/p) σε μία υποεργασία. Μετά από μια τέτοια συνάθροιση, ο αριθμός των δευτερευουσών εργασιών και ο αριθμός των επεξεργαστών θα συμπίπτουν και κατά την κατανομή των δευτερευουσών εργασιών μεταξύ των επεξεργαστών, το μόνο που μένει είναι να εξασφαλιστεί η παρουσία άμεσων γραμμών επικοινωνίας μεταξύ επεξεργαστών με δευτερεύουσες εργασίες, μεταξύ των οποίων υπάρχει ανταλλαγή πληροφοριών κατά τη συλλογή δεδομένων λειτουργία Ανάλυση της αποτελεσματικότητας του παράλληλου υπολογισμού Ας αξιολογήσουμε την αποτελεσματικότητα των αναπτυγμένων μεθόδων παράλληλων υπολογιστών για την επίλυση του προβλήματος του σώματος Ν. Δεδομένου ότι οι προτεινόμενες επιλογές διαφέρουν μόνο στις μεθόδους εκτέλεσης ανταλλαγών πληροφοριών, για να συγκριθούν οι προσεγγίσεις αρκεί να προσδιοριστεί η διάρκεια της γενικευμένης λειτουργίας συλλογής δεδομένων. Χρησιμοποιούμε το μοντέλο που προτείνει ο Hockney για να υπολογίσουμε τον χρόνο μετάδοσης του μηνύματος (βλ. Ενότητα 3), και στη συνέχεια η διάρκεια της λειτουργίας συλλογής δεδομένων για την πρώτη έκδοση του παράλληλου υπολογισμού μπορεί να εκφραστεί ως 1 T p (comm) = (p 1)( α + m (N / p) / β), όπου α, β είναι οι παράμετροι του μοντέλου Hockney (λανθάνουσα κατάσταση και εύρος ζώνης του δικτύου μετάδοσης δεδομένων) και το m καθορίζει την ποσότητα των δεδομένων που αποστέλλονται για ένα σώμα του φυσικού συστήματος. 9

10 Για τη δεύτερη μέθοδο ανταλλαγής πληροφοριών, όπως σημειώθηκε προηγουμένως, ο όγκος των δεδομένων που αποστέλλονται σε διαφορετικές επαναλήψεις της λειτουργίας συλλογής δεδομένων ποικίλλει. Στην πρώτη επανάληψη, ο όγκος των μηνυμάτων που αποστέλλονται είναι (mn/p), στη δεύτερη επανάληψη αυτός ο όγκος διπλασιάζεται και αποδεικνύεται ίσος με 2 (mN/p), κ.λπ. Γενικά, για τον αριθμό επανάληψης i, ο όγκος των μηνυμάτων υπολογίζεται ως 2 i-1 (mn/p). Ως αποτέλεσμα, η διάρκεια της λειτουργίας συλλογής δεδομένων σε αυτήν την περίπτωση μπορεί να προσδιοριστεί χρησιμοποιώντας την ακόλουθη έκφραση T 2 p log p i= 1 i 1 (comm) = (α + 2 m(N / p) / β) = α log p + m (N / p) (p 1) / β. Μια σύγκριση των παραστάσεων που ελήφθησαν δείχνει ότι η δεύτερη αναπτυγμένη μέθοδος παράλληλων υπολογιστών έχει σημαντικά υψηλότερη απόδοση, συνεπάγεται χαμηλότερο κόστος επικοινωνίας και επιτρέπει καλύτερη επεκτασιμότητα με αύξηση του αριθμού των επεξεργαστών που χρησιμοποιούνται. Σύντομη επισκόπηση της ενότητας Η ενότητα που εξέτασε τη μεθοδολογία ανάπτυξη παράλληλων αλγορίθμων που προτείνονται στο Foster (1995). Αυτή η τεχνική περιλαμβάνει τα στάδια αναγνώρισης δευτερευουσών εργασιών, προσδιορισμού εξαρτήσεων πληροφοριών, κλιμάκωσης και διανομής δευτερευουσών εργασιών στους επεξεργαστές ενός συστήματος υπολογιστή. Κατά την εφαρμογή της τεχνικής, θεωρείται ότι το υπολογιστικό σχήμα για την επίλυση του υπό εξέταση προβλήματος είναι ήδη γνωστό. Οι κύριες απαιτήσεις που πρέπει να πληρούνται κατά την ανάπτυξη παράλληλων αλγορίθμων είναι η εξασφάλιση ομοιόμορφου φορτίου στους επεξεργαστές με χαμηλή αλληλεπίδραση πληροφοριών μεταξύ του σχηματισμένου συνόλου υποεργασιών. Για να περιγραφούν τα υπολογιστικά παράλληλα κυκλώματα που αποκτήθηκαν κατά την ανάπτυξη, εξετάζονται δύο μοντέλα. Το πρώτο από αυτά, το μοντέλο «subtask-message» μπορεί να χρησιμοποιηθεί στο στάδιο του σχεδιασμού παράλληλων αλγορίθμων, το δεύτερο μοντέλο «διαδικασίες-κανάλια» μπορεί να χρησιμοποιηθεί στο στάδιο της εφαρμογής μεθόδων με τη μορφή παράλληλων προγραμμάτων. Στο τέλος της ενότητας, παρουσιάζεται η εφαρμογή της εξεταζόμενης μεθοδολογίας για την ανάπτυξη παράλληλων αλγορίθμων χρησιμοποιώντας το παράδειγμα επίλυσης του προβλήματος βαρύτητας Ν-σώματος Ανασκόπηση βιβλιογραφίας Η μεθοδολογία για την ανάπτυξη παράλληλων αλγορίθμων που συζητήθηκε στην ενότητα προτάθηκε για πρώτη φορά στο Foster (1995). ). Σε αυτή την εργασία, η μεθοδολογία παρουσιάζεται με περισσότερες λεπτομέρειες. Επιπλέον, η εργασία περιέχει αρκετά παραδείγματα χρήσης της τεχνικής για την ανάπτυξη παράλληλων μεθόδων για την επίλυση ενός αριθμού υπολογιστικών προβλημάτων. Ο Quinn (2004) μπορεί επίσης να είναι χρήσιμος όταν εξετάζεται ο σχεδιασμός και η ανάπτυξη παράλληλων αλγορίθμων. Το πρόβλημα της βαρύτητας του Ν-σώματος συζητείται λεπτομερέστερα στο Andrews (2000) Test Questions 1. Ποιες είναι οι αρχικές παραδοχές για τη δυνατότητα χρήσης της μεθοδολογίας για την ανάπτυξη παράλληλων αλγορίθμων που συζητούνται σε αυτήν την ενότητα; 2. Ποια είναι τα κύρια στάδια σχεδιασμού και ανάπτυξης μεθόδων παράλληλων υπολογιστών; 3. Πώς ορίζεται το μοντέλο υποεργασίας-μηνύματος; 4. Πώς ορίζεται το μοντέλο διεργασίας-καναλιού; 5. Ποιες βασικές απαιτήσεις πρέπει να πληρούνται κατά την ανάπτυξη παράλληλων αλγορίθμων; 6. Ποιες είναι οι κύριες ενέργειες στο στάδιο του προσδιορισμού των δευτερευουσών εργασιών; 7. Ποιες είναι οι κύριες ενέργειες στο στάδιο του προσδιορισμού των εξαρτήσεων πληροφοριών; 8. Ποιες είναι οι κύριες ενέργειες στο στάδιο της κλιμάκωσης του υπάρχοντος συνόλου υποεργασιών; 9. Ποιες είναι οι κύριες ενέργειες στο στάδιο της κατανομής δευτερευουσών εργασιών μεταξύ των επεξεργαστών ενός υπολογιστικού συστήματος; 10. Πώς ελέγχεται δυναμικά η κατανομή του υπολογιστικού φορτίου χρησιμοποιώντας το σχήμα «διαχειριστής-εκτελεστής»; 11. Ποια μέθοδος παράλληλων υπολογιστών αναπτύχθηκε για την επίλυση του προβλήματος της βαρύτητας του Ν-σώματος; 10

11 12. Ποιος τρόπος εκτέλεσης μιας γενικής λειτουργίας συλλογής δεδομένων είναι πιο αποτελεσματικός; 6.7. Εργασίες και ασκήσεις 1. Εφαρμόστε ένα σχήμα καταρράκτη για τον υπολογισμό του αθροίσματος μιας ακολουθίας αριθμητικών τιμών (βλ. Ενότητα 2) και συγκρίνετε τον χρόνο εκτέλεσης της ολοκληρωμένης υλοποίησης και τη συνάρτηση MPI_Bcast της βιβλιοθήκης MPI. 2. Εφαρμόστε τις εξεταζόμενες μεθόδους για την εκτέλεση μιας γενικευμένης λειτουργίας συλλογής δεδομένων και συγκρίνετε τον χρόνο εκτέλεσής τους. Συγκρίνετε τα χρονικά χαρακτηριστικά που προκύπτουν με τις θεωρητικές εκτιμήσεις. Συγκρίνετε με το χρόνο εκτέλεσης της συνάρτησης βιβλιοθήκης MPI MPI_Allgather. 3. Αναπτύξτε ένα σύστημα παράλληλων υπολογιστών χρησιμοποιώντας τη μεθοδολογία για το σχεδιασμό και την ανάπτυξη παράλληλων μεθόδων που συζητήθηκαν στην ενότητα: για το πρόβλημα της εύρεσης της μέγιστης τιμής μεταξύ των ελάχιστων στοιχείων των σειρών ενός πίνακα (αυτό το πρόβλημα εμφανίζεται για την επίλυση παιχνιδιών μήτρας) y = max min a, 1 i N 1 j N ij (δώστε ιδιαίτερη προσοχή στην κατάσταση όταν ο αριθμός των επεξεργαστών υπερβαίνει τη σειρά του πίνακα, δηλ. p>n), για το πρόβλημα του υπολογισμού του ορισμένου ολοκληρώματος με τη μέθοδο του ορθογωνίου b N 1 y = f (x) dx h fi, a i= 0 f i = f (x), x = i h, h = (b a) / N. i i (μια περιγραφή των μεθόδων ολοκλήρωσης δίνεται, για παράδειγμα, στο Kahaner, Moler και Nash (1988)) 4. Εφαρμογή των ανεπτυγμένων παράλληλων μεθόδων για προβλήματα n Αναπτύξτε ένα παράλληλο σχήμα υπολογισμών για το πρόβλημα του πολλαπλασιασμού πίνακα-διανυσμάτων, χρησιμοποιώντας τη μεθοδολογία για το σχεδιασμό και την ανάπτυξη παράλληλων μεθόδων που συζητήθηκαν στην ενότητα. Αναφορές Andrews, G. R. (2000). Foundations of Multithreaded, Parallel, and Distributed Programming.. Reading, MA: Addison-Wesley (Ρωσική μετάφραση από τον Andrews G.R. Fundamentals of multithreaded, parallel and distributed programming. M.: Williams Publishing House, 2003) Bertsekas, D.P., T.N. (1989) Παράλληλος και κατανεμημένος υπολογισμός. Αριθμητικές Μέθοδοι. - Prentice Hall, Englewood Cliffs, New Jersey. Buyya, R. (Επιμ.) (1999). Υπολογισμός συμπλέγματος υψηλής απόδοσης. Τόμος 1: Αρχιτεκτονικές και Συστήματα. Τόμος 2: Προγραμματισμός και Εφαρμογές. - Prentice Hall PTR, Prentice-Hall Inc. Kahaner, D., Moler, C., Nash, S. (1988). Αριθμητικές Μέθοδοι και Λογισμικό. Prentice Hall (Ρωσική μετάφραση Kahaner D., Mowler L., Nash S. Numerical method and software. M.: Mir, 2001) Foster, I. (1995). Σχεδιασμός και Κατασκευή Παράλληλων Προγραμμάτων: Έννοιες και Εργαλεία για Μηχανική Λογισμικού. Reading, MA: Addison-Wesley. Quinn, M. J. (2004). Παράλληλος προγραμματισμός σε C με MPI και OpenMP. Νέα Υόρκη, Νέα Υόρκη: McGraw-Hill. Wilkinson, Β., Allen, Μ. (1999). Παράλληλος προγραμματισμός. Prenrice Hall. έντεκα

ΚΕΦΑΛΑΙΟ 3 ΑΡΧΕΣ ΑΝΑΠΤΥΞΗΣ ΠΑΡΑΛΛΗΛΩΝ ΜΕΘΟΔΩΝ Η ανάπτυξη αλγορίθμων (και ιδιαίτερα μεθόδων παράλληλων υπολογιστών) για την επίλυση πολύπλοκων επιστημονικών και τεχνικών προβλημάτων είναι συχνά σημαντική

Μέθοδοι και αλγόριθμοι παράλληλων υπολογιστών Σχεδιασμός παράλληλων αλγορίθμων Kulakov Kirill Aleksandrovich 2016 Petrozavodsk Στόχοι σχεδίασης Εξισορρόπηση φορτίου Επεκτασιμότητα Αποτελεσματικότητα

Υπολογισμός υψηλής απόδοσης Διάλεξη 2. Εκτίμηση του μέγιστου δυνατού παραλληλισμού Η παροχή της καλύτερης επιτάχυνσης S T = απόδοση E = 1 δεν είναι δυνατή για όλα τα υπολογιστικά Τ υψηλής έντασης εργασίας

Διαλέξεις Διάλεξη 1. Αρχές κατασκευής παράλληλων υπολογιστικών συστημάτων................................... 23 Διάλεξη 2. Μοντελοποίηση και ανάλυση παράλληλων υπολογιστών.. .... 49 Διάλεξη 3. Αξιολόγηση επικοινωνίας

Κρατικό Πανεπιστήμιο του Νίζνι Νόβγκοροντ που πήρε το όνομά του. N.I Lobachevsky Faculty of Computational Mathematics and Cybernetics Εκπαιδευτικό συγκρότημα Εισαγωγή στις μεθόδους παράλληλου προγραμματισμού Ενότητα 9. Παράλληλος.

Έργο της Προεδρικής Επιτροπής για τον εκσυγχρονισμό και την τεχνολογική ανάπτυξη της ρωσικής οικονομίας «Δημιουργία συστήματος για την εκπαίδευση υψηλά ειδικευμένου προσωπικού στον τομέα των τεχνολογιών υπερυπολογιστών και εξειδικευμένων

Θέμα: Παραλληλισμός εκφράσεων με παράδειγμα την αριθμητική Βασικά χαρακτηριστικά πολυπλοκότητας και παραλληλισμού. Πρόβλημα (αποσύνθεση σε υποπροβλήματα μικρότερης διάστασης) 2Μέθοδος

ΕΡΩΤΗΣΕΙΣ ΓΙΑ ΤΟ ΤΕΣΤ ΣΤΟ ΜΑΘΗΜΑ «ΠΑΡΑΛΛΗΛΑ ΥΠΟΛΟΓΙΣΤΙΚΑ ΣΥΣΤΗΜΑΤΑ» 1. Αρχές κατασκευής παράλληλων υπολογιστικών συστημάτων (15) 1. Σχήματα πολυεπεξεργαστικών συστημάτων με ομοιογενή και ετερογενή πρόσβαση. 2.

Σχεδιασμός παράλληλων αλγορίθμων Διάλεξη 3.1 29/03/2012 T.Yu.Lymar 1 3.1 Μεθοδολογία σχεδιασμού Διαχωρισμός Δημιουργία συνδέσεων Συνάθροιση Σύνδεση με συγκεκριμένο υπολογιστή 29/03/2012 T.Yu.Lymar 2 3.1.1

Κρατικό Πανεπιστήμιο της Μόσχας που πήρε το όνομά του. M.V. Lomonosov Ιστορία και μεθοδολογία παράλληλου προγραμματισμού 9. Σχεδιασμός παράλληλων αλγορίθμων Προγραμματιστές: L.B. Sokolinsky, Διδάκτωρ Φυσικών και Μαθηματικών Επιστημών, Καθηγητής

Ομοσπονδιακή Υπηρεσία Εκπαίδευσης Κρατικό Πανεπιστήμιο του Νίζνι Νόβγκοροντ που πήρε το όνομά του. N.I. Lobachevsky National Project “Education” Καινοτόμο εκπαιδευτικό πρόγραμμα του UNN. Εκπαιδευτικό και επιστημονικό

Κρατικό Πανεπιστήμιο του Νίζνι Νόβγκοροντ που πήρε το όνομά του. Λομπατσέφσκι Σχολή Υπολογιστικών Μαθηματικών και Κυβερνητικής Τμήμα Εργαστηρίου Λογισμικού Υπολογιστών «Τεχνολογίες Πληροφοριών» ItLab Practical.

Κρατικό Πανεπιστήμιο του Νίζνι Νόβγκοροντ που πήρε το όνομά του. N.I. Lobachevsky - Εθνικό Πανεπιστήμιο Ερευνών - Διάλεξη. Μοντελοποίηση παράλληλων υπολογιστών Gergel V.P., Dean of the Computer Science and Computing Center of UNN Supercomputers

Αλγόριθμοι για παράλληλα υπολογιστικά συστήματα 1. Τύποι παραλληλισμού και μέθοδοι σύνθεσης παράλληλων αλγορίθμων. 2. Αξιολόγηση της αποτελεσματικότητας των παράλληλων αλγορίθμων. 1. Είδη παραλληλισμού και μέθοδοι παράλληλης σύνθεσης

ΚΟΙΝΟΠΡΑΞΙΑ ΥΠΕΡΥΠΟΛΟΓΙΣΤΩΝ ΡΩΣΙΚΩΝ ΠΑΝΕΠΙΣΤΗΜΙΩΝ Έργο Δημιουργία συστήματος εκπαίδευσης υψηλά ειδικευμένου προσωπικού στον τομέα των τεχνολογιών υπερυπολογιστών και εξειδικευμένου λογισμικού

Αξιολόγηση της αποτελεσματικότητας των παράλληλων αλγορίθμων Διάλεξη 4. 29/03/2012 T.Yu. Lymar 1 Εισαγωγή Ένα θεμελιώδες σημείο στην ανάπτυξη παράλληλων αλγορίθμων είναι η ανάλυση της αποτελεσματικότητας της χρήσης παραλληλισμού:

Αξιολόγηση της αποτελεσματικότητας των παράλληλων αλγορίθμων Διάλεξη 7 T.Yu. Lymar Ένα θεμελιώδες σημείο στην ανάπτυξη παράλληλων αλγορίθμων είναι η ανάλυση της αποτελεσματικότητας της χρήσης παραλληλισμού: Αξιολόγηση του μέγιστου δυνατού

ΒΑΣΙΚΕΣ ΕΝΝΟΙΕΣ ΤΟΥ ΠΑΡΑΛΛΗΛΟΥ ΥΠΟΛΟΓΙΣΜΟΥ Παράλληλος υπολογισμός (παράλληλη επεξεργασία) είναι η χρήση πολλών ή πολλών υπολογιστικών συσκευών για την ταυτόχρονη εκτέλεση διαφορετικών τμημάτων ενός

Μαθηματικά μοντέλα και μέθοδοι για την αποτελεσματική χρήση κατανεμημένων Ψηφιακών υπολογιστικών συστημάτων 3D ιατρικής Τίτλος Αποτελέσματα Υπότιτλος στον τομέα των γραφικών υπολογιστών και της γεωμετρικής παρουσίασης

UDC 681.5 ΠΑΡΑΛΛΗΛΟΙ ΑΛΓΟΡΙΘΜΟΙ ΓΙΑ ΑΡΙΘΜΗΤΙΚΗ ΛΥΣΗ ΤΟΥ ΠΡΟΒΛΗΜΑΤΟΣ ΚΑΟΥΧΑ ΓΙΑ ΑΝΤΡΟΦΗ ΝΑΖΑΡΟΒΑ Ι.Α. Donetsk National Technical University Παράλληλοι αριθμητικοί αλγόριθμοι μεθόδων ενός βήματος για

ΚΕΦΑΛΑΙΟ ΜΟΝΤΕΛΟΠΟΙΗΣΗ ΚΑΙ ΑΝΑΛΥΣΗ ΤΟΥ ΠΑΡΑΛΛΗΛΟΥ ΥΠΟΛΟΓΙΣΜΟΥ Κατά την ανάπτυξη παράλληλων αλγορίθμων για την επίλυση πολύπλοκων επιστημονικών και τεχνικών προβλημάτων, ένα θεμελιώδες σημείο είναι η ανάλυση της αποτελεσματικότητας της χρήσης παραλληλισμού,

1. Στόχοι και στόχοι του κλάδου: Τεχνολογίες υπερυπολογιστών και υπολογιστές υψηλής απόδοσης που χρησιμοποιούν υπολογιστικά συστήματα πολλαπλών επεξεργαστών (MCS) γίνονται σημαντικός παράγοντας στην επιστημονική και τεχνική

Κατασκευή στατιστικών μοντέλων απόδοσης παράλληλων προγραμμάτων V.N. Beletsky, S.A. Reznikova, A.A. G.E. Pukhov NAS της Ουκρανίας Το άρθρο συζητά

Πληροφορική, διαχείριση, οικονομία MIPT ΠΡΑΚΤΙΚΑ 2 Τόμος 2, (5) UDC 59687+475 AS Khritankov Moscow Institute of Physics and Technology (Κρατικό Πανεπιστήμιο) Μαθηματικό μοντέλο χαρακτηριστικών απόδοσης

ΑΛΓΟΡΙΘΜΟΙ ΙΣΟΡΡΟΦΗΣΗΣ ΦΟΡΤΙΟΥ ΕΠΕΞΕΡΓΑΣΤΩΝ ΠΑΡΑΛΛΗΛΟΥ ΥΠΟΛΟΓΙΣΤΙΚΟΥ ΣΥΣΤΗΜΑΤΟΣ Belkov D.V. Donetsk National Technical University, Donetsk Τμήμα Υπολογιστικών Μαθηματικών και Προγραμματισμού

Υπολογιστές και λογισμικό UDC 681.3.06 P.A. Pavlov ΑΠΟΔΟΤΙΚΟΤΗΤΑ ΚΑΤΑΝΟΜΕΜΕΝΟΥ ΥΠΟΛΟΓΙΣΜΟΥ ΣΕ ΚΛΙΜΑΚΙΣΜΕΝΑ ΣΥΣΤΗΜΑΤΑ Η επεκτασιμότητα είναι μια από τις πιο σημαντικές απαιτήσεις

Μέθοδος Ritz Υπάρχουν δύο κύριοι τύποι μεθόδων για την επίλυση προβλημάτων μεταβλητότητας. Ο πρώτος τύπος περιλαμβάνει μεθόδους που ανάγουν το αρχικό πρόβλημα στην επίλυση διαφορικών εξισώσεων. Αυτές οι μέθοδοι έχουν αναπτυχθεί πολύ καλά

ΔΙΑΓΩΝΙΑ ΜΕΘΟΔΟΣ ΠΟΛΛΑΠΛΑΣΙΑΣΜΟΥ ΠΥΚΝΩΝ ΠΙΝΑΚΩΝ Knyazkova T.V., Ph.D., Αναπληρωτής Καθηγητής, Vyatka State University, Kirov Today, με την αυξανόμενη ισχύ των υπολογιστικών συστημάτων και των σύγχρονων υπερυπολογιστών σε ένα ευρύ φάσμα τομέων της οικονομίας

Εισαγωγή 1 Κεφάλαιο 1 Εργασίες 1.1 Προθέρμανση Η πρώτη εργασία για τη σύνταξη ενός προγράμματος χρησιμοποιώντας τη βιβλιοθήκη MPI είναι μία για όλους. 1.1.1 Υπολογισμός του αριθμού π Υπολογίστε τον αριθμό π χρησιμοποιώντας τον ακόλουθο τύπο: 1 1 dx 4 1 + x

Εργαστηριακή εργασία 4 Παράλληλη εφαρμογή της μεθόδου Jacobi σε ένα τρισδιάστατο πεδίο Στόχος της εργασίας: πρακτική ανάπτυξη μεθόδων για την παραλληλοποίηση αριθμητικών αλγορίθμων σε κανονικά πλέγματα χρησιμοποιώντας ένα παράδειγμα υλοποίησης

R. I. Idrisov ΧΡΟΝΟΣ ΑΝΑΠΤΥΞΗ ΤΗΣ ΕΣΩΤΕΡΙΚΗΣ ΑΝΑΠΑΡΑΣΤΑΣΗΣ IR2 ΤΗΣ SISAL 3.1 ΓΛΩΣΣΑ * Σήμερα, η αύξηση της υπολογιστικής ισχύος δεν συνδέεται πλέον με την επιτάχυνση ενός ατόμου, αλλά με την προσθήκη πρόσθετων

Στρατηγική έρευνας βελτιστοποίησης και μέθοδοι επίλυσης προβλημάτων στατικής και δυναμικής βελτιστοποίησης τεχνολογικών αντικειμένων παραδοσιακά διατυπώνονται προβλήματα στατικής βελτιστοποίησης

ΟΡΓΑΝΩΣΗ ΔΙΑΔΙΚΑΣΙΩΝ ΥΠΟΛΟΓΙΣΜΟΥ ΠΑΡΑΛΛΗΛΩΝ ΚΟΚΚΩΝ (Λήψη παράλληλων ακολουθιών κοκκωδών υπολογισμών) Ας δώσουμε παραδείγματα λήψης παράλληλων αλγορίθμων, τα σύνολα πράξεων των οποίων

ΠΑΡΑΛΛΗΛΕΣ ΙΔΙΟΤΗΤΕΣ ΤΟΥ ΑΛΓΟΡΙΘΜΟΥ Οι παράλληλοι υπολογιστές (υπερυπολογιστές) έχουν σχεδιαστεί για να επιλύουν γρήγορα μεγάλα προβλήματα. Όσο πιο ισχυρός είναι ο υπολογιστής, τόσο πιο γρήγορα μπορεί να λυθεί ένα πρόβλημα σε αυτόν. εκτός

Kalyaev A.V. ΠΡΟΓΡΑΜΜΑΤΙΣΜΟΣ ΕΙΚΟΝΙΚΩΝ ΑΡΧΙΤΕΚΤΟΝΙΚΩΝ ΚΑΙ ΟΡΓΑΝΩΣΗ ΔΟΜΙΚΗΣ-ΔΙΑΔΙΚΑΣΙΑΣ ΥΠΟΛΟΓΙΣΤΙΚΗΣ ΣΕ ΠΟΛΥΕΠΙΚΑΣΤΑΣΤΙΚΑ ΣΥΣΤΗΜΑΤΑ ΜΕ ΜΑΖΙΚΟ ΠΑΡΑΛΛΗΛΙΣΜΟ 1 Περίληψη του Ερευνητικού Ινστιτούτου Πολυεπεξεργαστή Υπολογιστών

Αλγόριθμοι για πολλαπλασιασμό παράλληλων πινάκων 1 Αλγόριθμοι λωρίδων για πολλαπλασιασμό πίνακα Σε αυτούς τους αλγόριθμους, οι πίνακες χωρίζονται σε συνεχείς ακολουθίες σειρών ή στηλών (λωρίδες). Στην πιο απλή περίπτωση

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

ΛΥΣΗ ΜΗ ΓΡΑΜΜΙΚΩΝ ΕΞΙΣΩΣΕΩΝ ΚΑΙ ΣΥΣΤΗΜΑΤΩΝ ΜΗ ΓΡΑΜΜΙΚΩΝ ΕΞΙΣΩΣΕΩΝ ΛΥΣΗ ΜΗ ΓΡΑΜΜΙΚΩΝ ΕΞΙΣΩΣΕΩΝ Αριθμητική λύση μη γραμμικών αλγεβρικών ή υπερβατικών εξισώσεων. είναι να βρεις τις αξίες

«Άλγεβρα και Γεωμετρία» 13. Συστήματα γραμμικών αλγεβρικών εξισώσεων (SLAE). Θεώρημα Kronecker-Capelli. Γενικές και ειδικές λύσεις SLAE. 14. Καμπύλες δεύτερης τάξης: έλλειψη, υπερβολή, παραβολή και οι ιδιότητές τους.

UDC 681.32 ΑΥΞΗΣΗ ΤΗΣ ΠΑΡΑΓΩΓΙΚΟΤΗΤΑΣ ΤΩΝ ΣΥΓΚΡΟΤΗΜΑΤΩΝ ΣΤΑΘΜΩΝ ΕΡΓΑΣΙΑΣ ΜΕ ΧΡΗΣΗ ΚΑΤΑΝΟΜΗ ΑΝΕΜΙΣΤΗΡΑ ΕΠΙΠΛΕΟΝ ΕΡΓΑΣΙΩΝ ΓΙΑ ΕΞΟΠΛΙΣΜΟ Αδράνειας 2012 V. M. Dovgal 1, S. G. Spirin 2 1 καθηγητής

Γράφημα αλγορίθμου και παράλληλοι υπολογισμοί. Εσωτερικός παραλληλισμός προγραμμάτων. Διάλεξη 3 04/12/2012 (C) L.B Sokolinsky 1 3.1 Εσωτερικός παραλληλισμός Ένα πρόγραμμα περιέχει παραλληλισμό εάν ορισμένα από τα μέρη του (τελεστές)

ΥΠΟΥΡΓΕΙΟ ΕΚΠΑΙΔΕΥΣΗΣ ΚΑΙ ΕΠΙΣΤΗΜΗΣ ΤΟΥ ΡΩΣΙΚΟΥ ΟΜΟΣΠΟΝΔΙΑΚΟΥ ΚΡΑΤΙΚΟΥ ΠΡΟΫΠΟΛΟΓΙΣΜΟΥ ΕΚΠΑΙΔΕΥΤΙΚΟ ΕΚΠΑΙΔΕΥΤΙΚΟ ΙΔΡΥΜΑ ΑΝΩΤΕΡΗΣ ΕΠΑΓΓΕΛΜΑΤΙΚΗΣ ΕΚΠΑΙΔΕΥΣΗΣ «SAMARA STATE AEROSSPACE UNIVERSITY NAME OF ACADEMICIAN S.P. KOROLEV

Διάλεξη 5 5 Θεώρημα για την ύπαρξη και τη μοναδικότητα μιας λύσης στο πρόβλημα Cauchy για ένα κανονικό σύστημα ODE Δήλωση του προβλήματος Το πρόβλημα Cauchy για ένα κανονικό σύστημα ODE x = f (, x), () αποτελείται από την εύρεση λύσης x =

Κρατικό Πανεπιστήμιο του Νίζνι Νόβγκοροντ που πήρε το όνομά του. N.I Lobachevsky Faculty of Computational Mathematics and Cybernetics Εκπαιδευτικό συγκρότημα Εισαγωγή στις μεθόδους παράλληλου προγραμματισμού Ενότητα 2. Μοντελοποίηση.

Κεφάλαιο 5. ΜΕΘΟΔΟΙ ΣΙΩΠΗΡΗΣ ΕΡΕΥΝΑΣ Ας εξετάσουμε τη γενική διατύπωση του διακριτού προβλήματος βελτιστοποίησης mif (x), (5.) x D στο οποίο το αναζητούμενο διάνυσμα διαστάσεων x ανήκει σε ένα πεπερασμένο σύνολο εφικτών λύσεων D.

ΠΕΡΙΕΧΟΜΕΝΑ Εισαγωγή.... 12 P a r t I. Βασικές αρχές της παραλληλοποίησης Διάλεξη 1. Για τη διατύπωση του προβλήματος της παραλληλοποίησης... 17 1.1. Εισαγωγή.... 17 1.2. Σχετικά με ορισμένα υπολογιστικά προβλήματα.... 19 1.3. Αριθμητικός

UDC 68.3.06 ΠΡΟΣΔΙΟΡΙΣΜΟΣ ΤΟΥ ΑΡΙΘΜΟΥ ΚΑΙ ΤΟΠΟΛΟΓΙΑΣ ΤΟΠΟΘΕΣΙΑΣ ΣΤΑΘΜΩΝ ΕΝΟΣ ΠΟΛΥΕΠΕΛΕΞΑΤΙΚΟ ΥΠΟΛΟΓΙΣΤΙΚΟ ΣΥΣΤΗΜΑ A.V. Pogrebnoy Institute "Cybernetic Center" TPU E-mail: [email προστατευμένο]Προβλήματα που εξετάζονται

EXTRAPOLATIONAL BLOCK ΜΕΘΟΔΟΙ ΜΟΝΟΥ ΒΗΜΑΤΟΣ ΓΙΑ ΑΡΙΘΜΗΤΙΚΗ ΛΥΣΗ ΥΨΗΛΗΣ ΑΚΡΙΒΕΙΑΣ ΤΟΥ ΠΡΟΒΛΗΜΑΤΟΣ ΚΑΥΣΗΣ Kulakov V.V. Nazarova I. A. Feldman L. P. Ντονέτσκ Εθνικό Τεχνικό Πανεπιστήμιο Εξετάζοντας παράλληλα

Proceedings of ISA RAS, 2008. V. 32 On the concept of performance in distributed computing systems M. A. Posypkin, A. S. Khritankov Institute of System Analysis of the Russian Academy of Sciences (ISA RAS) Σε αυτό

2007 ΕΠΙΣΤΗΜΟΝΙΚΟ ΔΕΛΤΙΟ MSTU GA 26 series Radiophysics and radio engineering UDC 6236:6239 ASSESSMENT OF THE FEASIBILITY OF PARALLELELING INFORMATION-DENDENT TAKS IN COMPUTING SYSTEMS RN άρθρο AKINSH

Μέγιστη παραλληλοποίηση αλγορίθμων που βασίζονται στην έννοια του προσδιοριστή Q Valentina Nikolaevna Aleeva State University South Ural (NRU) Novosibirsk, 2015 ΕΙΣΑΓΩΓΗ Η έκθεση εξετάζει

Υπουργείο Παιδείας και Επιστημών της Ρωσικής Ομοσπονδίας Κρατικό Πανεπιστήμιο Nizhny Novgorod που ονομάστηκε έτσι. N.I. Lobachevsky V.P. Gergel ΥΠΟΛΟΓΙΣΜΟΣ ΥΨΗΛΗΣ ΑΠΟΔΟΣΗΣ ΓΙΑ ΠΟΛΥΠΥΡΗΝΕΣ ΠΟΛΥΠΥΡΗΝΕΣ

LC 1. Μοντελοποίηση. 1. Βασικές έννοιες. 2 Αρχές μοντελοποίησης. 3 Ιδιότητες μοντέλων 4 Ταξινόμηση μεθόδων μοντελοποίησης. 5. Μαθηματική μοντελοποίηση 1. ΒΑΣΙΚΕΣ ΕΝΝΟΙΕΣ. Αντικατάσταση προσομοίωσης

Ομοσπονδιακή Υπηρεσία Εκπαίδευσης Κρατικό εκπαιδευτικό ίδρυμα τριτοβάθμιας επαγγελματικής εκπαίδευσης "Novosibirsk State University" (NSU) Σχολή Τεχνολογιών Πληροφορικής

Κρατικό Πανεπιστήμιο του Νίζνι Νόβγκοροντ που πήρε το όνομά του. N.I. Lobachevsky Research University Δημιουργία εκπαιδευτικής βιβλιοθήκης παράλληλων μεθόδων Parlib Ολοκληρώθηκε από: Kozinov E.A. Kutlaev M.V. Osokin

UDC 681.3.06 ΣΧΕΔΙΑΣΜΟΣ ΔΟΜΗ ΤΟΠΙΚΟΥ ΔΙΚΤΥΟΥ ΓΙΑ ΕΝΑ ΚΑΤΑΝΟΜΗΜΕΝΟ ΥΠΟΛΟΓΙΣΤΙΚΟ ΣΥΣΤΗΜΑ ΠΡΑΓΜΑΤΙΚΟΥ ΧΡΟΝΟΥ A.V. Pogrebnoy, D.V. Pogrebnoy Institute "Cybernetic Center" TPU E-mail: [email προστατευμένο]

PARALLEL ALGORITHMS OF THE CYCLIC SWING METHOD Golovashkin D.L., Filatov M.V Institute of Image Processing Systems RAS Samara State Aerospace University Περίληψη Η εργασία είναι αφιερωμένη

UDC 519.856; 519.854; 519,85 ΣΤΑΤΙΣΤΙΚΗ ΑΝΑΖΗΤΗΣΗ ΠΛΗΡΟΦΟΡΙΩΝ ΥΠΟΛΟΓΙΣΤΙΚΕΣ ΔΟΜΕΣ ΔΙΚΤΥΟΥ V.V. Malygin Οι ιδιότητες της σύγκλισης της συνάρτησης για την εκτίμηση της δομής ενός δικτύου πληροφοριών και υπολογιστών έχουν μελετηθεί. Επί

Κατασκευή αναδρομικών-παράλληλων αλγορίθμων για την επίλυση προβλημάτων υπολογιστικής γεωμετρίας με βάση τη στρατηγική «διανείμετε και κατακτήστε» V.N. Tereshchenko Το έγγραφο εξετάζει μία από τις προσεγγίσεις για την αποτελεσματική οικοδόμηση

12.1. I/O με βάση τη δημοσκόπηση ετοιμότητας συσκευής Η ετοιμότητα ή μη ετοιμότητα μιας εξωτερικής συσκευής για I/O ελέγχεται στον καταχωρητή κατάστασης της εξωτερικής συσκευής Για I/O ελεγχόμενη από λογισμικό

FLYNN'S TAXONOMY Yulia Kirillova 6057/2 11/22/11 Η ταξινόμηση του Flynn είναι μια γενική ταξινόμηση αρχιτεκτονικών υπολογιστών που βασίζεται στην παρουσία παραλληλισμού στις ροές εντολών και δεδομένων. προτάθηκε το 1972 από τον Michael Flynn.

Εργαστηριακή εργασία 4 Επίλυση του προβλήματος Poisson με τη μέθοδο Jacobi σε ένα τρισδιάστατο πεδίο Στόχος είναι η πρακτική ανάπτυξη μεθόδων παραλληλισμού αλγορίθμων για προβλήματα που λύνονται με μεθόδους πλέγματος χρησιμοποιώντας το παράδειγμα λύσης

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

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

Μέθοδοι συγχρονισμού παράλληλης αλληλεπίδρασης

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

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

Ο παραλληλισμός κατανεμημένης μνήμης και ο παραλληλισμός μετάδοσης μηνυμάτων έχουν διαφορετικά χαρακτηριστικά απόδοσης. Τυπικά (αλλά όχι πάντα), η επιβάρυνση της μνήμης διεργασιών και ο χρόνος εναλλαγής εργασιών είναι χαμηλότερος για συστήματα μετάδοσης μηνυμάτων, αλλά η μετάδοση μηνυμάτων είναι πιο ακριβή από τις κλήσεις διαδικασίας. Αυτές οι διαφορές συχνά επισκιάζονται από άλλους παράγοντες που επηρεάζουν την απόδοση.

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

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

• χάρτης - εκτέλεση της ίδιας συνάρτησης σε κάθε στοιχείο του πίνακα δεδομένων εισόδου, λαμβάνοντας έναν πίνακα αποτελεσμάτων υπολογισμού ίσου μεγέθους
• μείωση - εκτέλεση της ίδιας συνάρτησης για την προσθήκη της συνεισφοράς κάθε στοιχείου των δεδομένων εισόδου σε μια τελική τιμή

Εργαλεία παραλληλισμού λογισμικού

• Το OpenMP είναι ένα πρότυπο διεπαφής εφαρμογών για παράλληλα συστήματα κοινής μνήμης.
• Το POSIX Threads είναι ένα πρότυπο για την υλοποίηση νημάτων εκτέλεσης.
• Windows API - εφαρμογές πολλαπλών νημάτων για C++.
• Το PVM (Parallel Virtual Machine) σάς επιτρέπει να συνδυάσετε ένα ετερογενές (αλλά δικτυωμένο) σύνολο υπολογιστών σε έναν κοινό υπολογιστικό πόρο.
• Το MPI (Message Passing Interface) είναι ένα πρότυπο για συστήματα μετάδοσης μηνυμάτων μεταξύ παράλληλων διεργασιών εκτέλεσης.

δείτε επίσης

Γράψε μια αξιολόγηση για το άρθρο "Παράλληλοι Υπολογιστές"

Βιβλιογραφία

• Λεξικό Κυβερνητικής / Επιμέλεια Ακαδημαϊκός V. S. Mikhalevich. - 2ο. - Κίεβο: Κύριο εκδοτικό γραφείο της Ουκρανικής Σοβιετικής Εγκυκλοπαίδειας με το όνομα M. P. Bazhan, 1989. - 751 p. - (C48). - 50.000 αντίτυπα.
• - ISBN 5-88500-008-5.. - IBM RedBook, 1999. - 238 σελ.
• (Αγγλικά) Voevodin V.V., Voevodin Vl. ΣΕ.
• Παράλληλος υπολογισμός. - Αγία Πετρούπολη: BHV-Petersburg, 2002. - 608 p. - ISBN 5-94157-160-7. Olenev N. N.

. - M.: Computer Center RAS, 2005. - 80 p. - ISBN 5201098320.

Σημειώσεις

• . - IBM RedBook, 1999. - 238 σελ.
• . - IBM RedBook, 1999. - 238 σελ.

Συνδέσεις Παράλληλος Υπολογισμός Γενικές προμήθειες Επίπεδα παραλληλισμού Ροή εκτέλεσης Θεωρία Στοιχεία ΑΛΛΗΛΕΠΙΔΡΑΣΗ Προγραμματισμός Τεχνολογία υπολογιστών API

Προβλήματα

Ένα απόσπασμα που χαρακτηρίζει τον Παράλληλο Υπολογισμό
Το πνεύμα του στρατού είναι πολλαπλασιαστής για τη μάζα, δίνοντας το γινόμενο της δύναμης. Ο προσδιορισμός και η έκφραση της αξίας του πνεύματος του στρατού, αυτού του άγνωστου παράγοντα, είναι καθήκον της επιστήμης.
Αυτή η εργασία είναι δυνατή μόνο όταν σταματήσουμε να αντικαθιστούμε αυθαίρετα αντί της τιμής ολόκληρου του αγνώστου Χ εκείνες τις συνθήκες υπό τις οποίες εκδηλώνεται η δύναμη, όπως: εντολές του διοικητή, όπλα κ.λπ., λαμβάνοντας τα ως την τιμή του πολλαπλασιαστή και αναγνωρίζουν αυτό το άγνωστο σε όλη του την ακεραιότητά του, δηλαδή ως μια μεγαλύτερη ή μικρότερη επιθυμία να πολεμήσει και να εκτεθεί σε κίνδυνο. Τότε μόνο εκφράζοντας γνωστά ιστορικά γεγονότα σε εξισώσεις και συγκρίνοντας τη σχετική αξία αυτού του αγνώστου μπορούμε να ελπίζουμε ότι θα προσδιορίσουμε το ίδιο το άγνωστο.
Ο τακτικός κανόνας ότι κάποιος πρέπει να ενεργεί μαζικά όταν προχωρά και χωριστά όταν υποχωρεί ασυναίσθητα επιβεβαιώνει μόνο την αλήθεια ότι η δύναμη ενός στρατού εξαρτάται από το πνεύμα του. Για να οδηγηθούν οι άνθρωποι κάτω από τις οβίδες, χρειάζεται περισσότερη πειθαρχία, η οποία μπορεί να επιτευχθεί μόνο με μαζικές κινήσεις, παρά για την καταπολέμηση των επιτιθέμενων. Αλλά αυτός ο κανόνας, που χάνει τα μάτια του το πνεύμα του στρατού, αποδεικνύεται συνεχώς λανθασμένος και είναι ιδιαίτερα εντυπωσιακά αντίθετος με την πραγματικότητα όπου υπάρχει έντονη άνοδος ή παρακμή στο πνεύμα του στρατού - σε όλους τους λαϊκούς πολέμους.
Οι Γάλλοι, υποχωρώντας το 1812, αν και έπρεπε να αμυνθούν χωριστά, σύμφωνα με τακτική, μαζεύτηκαν μαζί, γιατί το ηθικό του στρατού είχε πέσει τόσο χαμηλά που μόνο η μάζα κρατούσε τον στρατό ενωμένο. Οι Ρώσοι, αντίθετα, σύμφωνα με τακτική, έπρεπε να επιτεθούν μαζικά, αλλά στην πραγματικότητα είναι κατακερματισμένοι, επειδή το πνεύμα είναι τόσο υψηλό που τα άτομα χτυπούν χωρίς τις εντολές των Γάλλων και δεν χρειάζονται καταναγκασμό για να εκτεθούν εργασία και κίνδυνος.

Ο λεγόμενος αντάρτικος πόλεμος ξεκίνησε με την είσοδο του εχθρού στο Σμολένσκ.
Πριν ο ανταρτοπόλεμος γίνει επίσημα αποδεκτός από την κυβέρνησή μας, χιλιάδες άνθρωποι του εχθρικού στρατού - οπισθοδρομικοί επιδρομείς, τροφοσυλλέκτες - εξοντώθηκαν από τους Κοζάκους και τους αγρότες, που ξυλοκόπησαν τόσο ασυνείδητα όσο τα σκυλιά σκοτώνουν ασυναίσθητα ένα λυσσασμένο σκυλί. Ο Denis Davydov, με το ρωσικό του ένστικτο, ήταν ο πρώτος που κατάλαβε το νόημα αυτού του τρομερού κλαμπ, που, χωρίς να ρωτήσει τους κανόνες της στρατιωτικής τέχνης, κατέστρεψε τους Γάλλους και η δόξα του πρώτου βήματος για τη νομιμοποίηση αυτής της μεθόδου πολέμου ανήκει σε αυτόν. .
Στις 24 Αυγούστου ιδρύθηκε το πρώτο παρτιζάνικο απόσπασμα του Νταβίντοφ και μετά το απόσπασμά του άρχισαν να δημιουργούνται και άλλα. Όσο προχωρούσε η εκστρατεία, τόσο αυξανόταν ο αριθμός αυτών των αποσπασμάτων.
Οι παρτιζάνοι κατέστρεψαν το Μεγάλο Στρατό κομμάτι-κομμάτι. Μάζεψαν εκείνα τα πεσμένα φύλλα που έπεσαν μόνα τους από το μαραμένο δέντρο - τον γαλλικό στρατό, και μερικές φορές τίναξαν αυτό το δέντρο. Τον Οκτώβριο, ενώ οι Γάλλοι έφευγαν στο Σμολένσκ, υπήρχαν εκατοντάδες από αυτά τα πάρτι διαφόρων μεγεθών και χαρακτήρων. Υπήρχαν κόμματα που υιοθέτησαν όλες τις τεχνικές του στρατού, με το πεζικό, το πυροβολικό, το αρχηγείο και τις ανέσεις της ζωής. υπήρχαν μόνο Κοζάκοι και ιππικό. υπήρχαν μικρά, προκατασκευασμένα, με τα πόδια και με άλογα, ήταν χωρικοί και γαιοκτήμονες, άγνωστοι σε κανέναν. Υπήρχε ένας sexton ως επικεφαλής του κόμματος, ο οποίος έπαιρνε αρκετές εκατοντάδες αιχμαλώτους το μήνα. Εκεί ήταν η πρεσβυτέρα Βασιλίσα, που σκότωσε εκατοντάδες Γάλλους.
Οι τελευταίες μέρες του Οκτώβρη ήταν η κορύφωση του αντάρτικου πολέμου. Εκείνη η πρώτη περίοδος αυτού του πολέμου, κατά την οποία οι παρτιζάνοι, έκπληκτοι με το θράσος τους, φοβούνταν κάθε στιγμή μήπως τους πιάσουν και τους περικυκλώσουν οι Γάλλοι και, χωρίς να ξεσελαθούν ή σχεδόν να κατέβουν από τα άλογά τους, κρύφτηκαν στα δάση περιμένοντας καταδίωξη. σε κάθε στιγμή, έχει ήδη περάσει. Τώρα αυτός ο πόλεμος είχε ήδη οριστεί, έγινε σαφές σε όλους τι μπορούσε να γίνει με τους Γάλλους και τι όχι. Τώρα μόνο εκείνοι οι αποσπασματάρχες που με το αρχηγείο τους, σύμφωνα με τους κανόνες, απομακρύνθηκαν από τους Γάλλους, θεωρούσαν πολλά πράγματα ακατόρθωτα. Οι μικροί παρτιζάνοι, που είχαν ξεκινήσει από καιρό το έργο τους και παρακολουθούσαν στενά τους Γάλλους, θεωρούσαν πιθανό αυτό που δεν τολμούσαν να σκεφτούν οι αρχηγοί μεγάλων αποσπασμάτων. Οι Κοζάκοι και οι άνδρες που ανέβηκαν ανάμεσα στους Γάλλους πίστευαν ότι τώρα όλα ήταν δυνατά.
Στις 22 Οκτωβρίου, ο Ντενίσοφ, που ήταν ένας από τους παρτιζάνους, ήταν με το κόμμα του εν μέσω κομματικού πάθους. Το πρωί αυτός και η παρέα του ήταν σε κίνηση. Όλη την ημέρα, μέσα από τα δάση δίπλα στον κεντρικό δρόμο, ακολούθησε μια μεγάλη γαλλική μεταφορά εξοπλισμού ιππικού και Ρώσων αιχμαλώτων, χωρισμένος από άλλα στρατεύματα και υπό ισχυρή κάλυψη, όπως ήταν γνωστό από κατασκόπους και αιχμαλώτους, κατευθυνόμενος προς το Σμολένσκ. Αυτή η μεταφορά ήταν γνωστή όχι μόνο στον Ντενίσοφ και τον Ντολόχοφ (επίσης παρτιζάνος με ένα μικρό κόμμα), που περπάτησαν κοντά στο Ντενίσοφ, αλλά και στους διοικητές μεγάλων αποσπασμάτων με αρχηγείο: όλοι ήξεραν για αυτήν τη μεταφορά και, όπως είπε ο Ντενίσοφ, ακονίστηκαν δόντια πάνω του. Δύο από αυτούς τους μεγάλους αρχηγούς αποσπάσματος -ο ένας Πολωνός και ο άλλος Γερμανός- έστειλαν σχεδόν ταυτόχρονα στον Ντενίσοφ μια πρόσκληση να ενταχθεί ο καθένας στο δικό του απόσπασμα για να επιτεθεί στο μεταφορικό μέσο.
«Όχι, bg», είμαι με μουστάκι ο ίδιος», είπε ο Ντενίσοφ, έχοντας διαβάσει αυτά τα χαρτιά, και έγραψε στον Γερμανό ότι, παρά την πνευματική επιθυμία ότι έπρεπε να υπηρετήσει υπό τις διαταγές ενός τόσο γενναίου και διάσημου στρατηγού , πρέπει να στερήσει τον εαυτό του αυτή την ευτυχία, γιατί είχε ήδη μπει υπό τις διαταγές ενός Πολωνού στρατηγού Έγραψε το ίδιο πράγμα στον Πολωνό στρατηγό, ειδοποιώντας τον ότι είχε ήδη μπει υπό τη διοίκηση ενός Γερμανού.
Έχοντας διατάξει αυτό, ο Ντενίσοφ σκόπευε, χωρίς να το αναφέρει στους ανώτατους διοικητές, μαζί με τον Ντολόχοφ, να επιτεθεί και να πάρει αυτή τη μεταφορά με τις δικές του μικρές δυνάμεις. Η μεταφορά πήγε στις 22 Οκτωβρίου από το χωριό Mikulina στο χωριό Shamsheva. Στην αριστερή πλευρά του δρόμου από το Mikulin στο Shamshev υπήρχαν μεγάλα δάση, σε μερικά σημεία πλησίαζαν τον ίδιο τον δρόμο, σε άλλα ένα μίλι ή περισσότερο μακριά από το δρόμο. Μέσα από αυτά τα δάση όλη την ημέρα, τώρα πηγαίνοντας πιο βαθιά στη μέση τους, τώρα πηγαίνοντας προς την άκρη, ο Ντενίσοφ οδήγησε με το πάρτι, χωρίς να αφήσει τους κινούμενους Γάλλους να ξεφύγουν από τα μάτια τους. Το πρωί, κοντά στο Μικουλίν, όπου το δάσος πλησίαζε στο δρόμο, οι Κοζάκοι από το κόμμα του Ντενίσοφ συνέλαβαν δύο γαλλικά βαγόνια με σέλες ιππικού που είχαν λερωθεί στη λάσπη και τα πήγαν στο δάσος. Από τότε μέχρι το βράδυ, το κόμμα, χωρίς να επιτεθεί, ακολουθούσε την κίνηση των Γάλλων. Ήταν απαραίτητο, χωρίς να τους τρομάξουμε, να τους αφήσουμε να φτάσουν ήρεμα στον Σάμσεφ και μετά, ενωμένοι με τον Ντολόχοφ, ο οποίος υποτίθεται ότι θα ερχόταν σε μια συνάντηση το βράδυ στο φρουραρχείο στο δάσος (ένα μίλι από τον Σάμσεφ), την αυγή, να πέσουν από και οι δύο πλευρές από το μπλε και να νικήσει και να πάρει όλους με τη μία.
Πίσω, δύο μίλια από το Mikulin, όπου το δάσος πλησίαζε τον ίδιο τον δρόμο, έμειναν έξι Κοζάκοι, οι οποίοι υποτίθεται ότι έδιναν αναφορά μόλις εμφανίζονταν νέες γαλλικές στήλες.
Μπροστά από τον Shamsheva, ο Dolokhov έπρεπε να εξερευνήσει τον δρόμο με τον ίδιο τρόπο για να μάθει σε ποια απόσταση υπήρχαν ακόμη άλλα γαλλικά στρατεύματα. Αναμενόταν να μεταφερθούν χίλια πεντακόσια άτομα. Ο Ντενίσοφ είχε διακόσια άτομα, ο Ντολόχοφ θα μπορούσε να είχε τον ίδιο αριθμό. Αλλά οι ανώτεροι αριθμοί δεν σταμάτησαν τον Ντενίσοφ. Το μόνο πράγμα που έπρεπε ακόμα να ξέρει ήταν τι ακριβώς ήταν αυτά τα στρατεύματα. και για το σκοπό αυτό ο Ντενίσοφ χρειάστηκε να πάρει μια γλώσσα (δηλαδή έναν άνθρωπο από την εχθρική στήλη). Στην πρωινή επίθεση στα βαγόνια, το θέμα έγινε με τόση βιασύνη που οι Γάλλοι που ήταν με τα βαγόνια σκοτώθηκαν από όλους και μόνο το αγόρι του ντράμερ πιάστηκε ζωντανό, που ήταν καθυστερημένο και δεν μπορούσε να πει τίποτα θετικό για το είδος των στρατευμάτων. στη στήλη.
Ο Ντενίσοφ θεώρησε επικίνδυνο να επιτεθεί μια άλλη φορά, για να μην ανησυχήσει ολόκληρη η στήλη, και ως εκ τούτου έστειλε στο Shamshevo τον αγρότη Tikhon Shcherbaty, ο οποίος ήταν με το κόμμα του, για να συλλάβει, ει δυνατόν, τουλάχιστον έναν από τους προχωρημένους Γάλλους που ήταν εκεί.

Plaksin M.A.

National Research University Higher School of Economics (Perm branch), Perm, Ph.D., Αναπληρωτής Καθηγητής του Τμήματος Τεχνολογιών Πληροφορικής στις Επιχειρήσεις, mapl @ list. ru

«ΥΠΕΡΥΠΟΛΟΓΙΣΤΕΣ» VS «ΠΑΡΑΛΛΗΛΟΣ ΠΡΟΓΡΑΜΜΑΤΙΣΜΟΣ». «ΠΑΡΑΛΛΗΛΟΣ ΠΡΟΓΡΑΜΜΑΤΙΣΜΟΣ» ΕΝΑΝΤΙΟΝ «ΣΥΝΕΡΓΑΤΙΚΗ ΔΡΑΣΤΗΡΙΟΤΗΤΑ». ΠΩΣ ΝΑ ΜΕΛΕΤΗΣΟΥΜΕ ΤΟ ΘΕΜΑ «ΠΑΡΑΛΛΗΛΟΣ ΠΛΗΡΟΦΟΡΙΚΗΣ» ΣΤΗΝ ΔΕΥΤΕΡΟΒΑΘΜΙΑ;

ΛΕΞΕΙΣ ΚΛΕΙΔΙΑ

Πληροφορική, παράλληλος προγραμματισμός, παράλληλοι υπολογιστές, παράλληλοι αλγόριθμοι, υπερυπολογιστές, δημοτικό σχολείο, γυμνάσιο, TRIZformashka.

ΣΧΟΛΙΟ

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

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

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

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

Τα τελευταία τουλάχιστον 20 χρόνια, η έννοια του «αλγόριθμου» έχει εισαχθεί στα σχολεία άρρηκτα συνδεδεμένη με την έννοια του «εκτελεστή». Αυτό είναι φυσικό για έναν διαδοχικό αλγόριθμο. Τι να κάνετε με έναν παράλληλο αλγόριθμο; Εκτελείται από έναν ερμηνευτή ή μια ομάδα ερμηνευτών; Για να γίνουμε συγκεκριμένοι, ας πάρουμε ως παράδειγμα το πρόγραμμα εκπαίδευσης υπολογιστών "Tank Crew". Σε αυτό το πρόγραμμα, ο μαθητής καλείται να προγραμματίσει τις ενέργειες ενός πληρώματος δεξαμενής που αποτελείται από τρία άτομα: έναν πυροβολητή, έναν οδηγό και έναν φορτωτή. Κάθε ένα από αυτά έχει το δικό του σύστημα εντολών. Προκειμένου να ολοκληρωθεί μια αποστολή μάχης (να χτυπήσει όλους τους στόχους), όλα τα μέλη του πληρώματος πρέπει να ενεργήσουν συντονισμένα. Για ένα παράδειγμα του αγωνιστικού χώρου για το πρόγραμμα Tank Crew, δείτε την Εικ. 1.

Ερώτηση: αυτοί οι τρεις ηθοποιοί πρέπει να θεωρούνται ως ανεξάρτητοι ερμηνευτές ή ως τρία συστατικά (συσκευές) ενός πολύπλοκου ερμηνευτή; Για το πλήρωμα του τανκ, η δεύτερη επιλογή φαίνεται πιο φυσική, αφού κανένας χαρακτήρας δεν μπορεί να ολοκληρώσει την εργασία μόνος του. Τι γίνεται όμως αν το παιχνίδι γίνει πιο περίπλοκο και μια αποστολή μάχης ανατεθεί σε δύο τανκς ταυτόχρονα; Για τρία τανκς; Τρία μέλη ενός πληρώματος μπορούν κάλλιστα να θεωρηθούν ως τρία μέρη ενός ερμηνευτή. Αλλά κάθε πλήρωμα είναι προφανώς ένας ανεξάρτητος ερμηνευτής. Αυτό σημαίνει ότι ένας παράλληλος αλγόριθμος για πολλές δεξαμενές θα εκτελεστεί ταυτόχρονα από μια ομάδα εκτελεστών. Αποδεικνύεται ότι για έναν παράλληλο αλγόριθμο είναι απαραίτητο να ληφθούν υπόψη και οι δύο δυνατότητες: η εκτέλεση παράλληλων ενεργειών από έναν εκτελεστή και από μια ομάδα εκτελεστών. Στην περίπτωση πληρώματος δεξαμενής, η τήρηση της γραμμής είναι εύκολη. Ο εκτελεστής είναι αυτός που είναι σε θέση να λύσει την εργασία. Αυτός ο εκτελεστής μπορεί να αποτελείται από πολλά στοιχεία, καθένα από τα οποία εκτελεί ένα συγκεκριμένο μέρος της εργασίας, αλλά δεν μπορεί ανεξάρτητα να ολοκληρώσει ολόκληρη την εργασία χωρίς τη βοήθεια άλλων στοιχείων. Αλλά αν ο διαχωρισμός «ολόκληρων ερμηνευτών» και μερών ενός πολύπλοκου ερμηνευτή θα είναι πάντα τόσο απλός, είναι αδύνατο να πούμε τώρα.

Αρχείο 1*ra Παράθυρο Σχετικά με το πρόγραμμα

Vpolyet τα πάντα

Bbno.n«fTb στην επισημασμένη γραμμή

Επιστροφή στην αρχική σελίδα**"

θα εμφανιζόταν βήμα προς βήμα (μετά την εκτέλεση της εντολής ".order nesykoa^" θα πατηθεί το κουμπί gV ygolg "n-b next uwr")

Ё ГГВД iTHWTt. ειδικό βήμα

Βασικά βήμα προς βήμα

Εικ.1. Τμήμα του αγωνιστικού χώρου του προγράμματος Tank Crew

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

Είναι απαραίτητο να συμφωνηθεί ένας όρος για τον ορισμό μιας ομάδας συνεταιριστικών καλλιτεχνών. Ο όρος "εντολή" δεν είναι κατάλληλος, συνδέεται με το "σύστημα εντολών εκτελεστή" και με "εντολές κεντρικού επεξεργαστή". «Συλλογή ερμηνευτών»; «Ταξιαρχία ερμηνευτών»;

Αλγόριθμος Sh

n Χτύπημα1"; Φορτιστής προγράμματος οδήγησης

1 Μετρήστε το orun* στο “master sgkll V Stop V Charge 1

g Pci V Stop V Charge 2

3 Χονδρική! V Περιστρέψτε δεξιόστροφα 90 μοίρες V Φόρτιση 1 V

L V V πρώτη V Φόρτιση; V

5 Φωτιά! V Stop V Φόρτιση 1

Í P^chm V St*p V Zaryasya; V

7 Φωτιά! V Stop V Φόρτιση 1 V

3 Pa^ V Περιστρέψτε δεξιόστροφα 45 μοίρες V Φόρτιση 2 V

S Παύση V Έναρξη V Παύση V

10 Pvdea V Προώθηση V Παύση ¿δ

11 Plrl V Εμπρός V Παύση V

12 Paum V Περιστρέψτε δεξιόστροφα 45 μοίρες V Παύση V

13 Padm V Προώθηση V Παύση V

14 V

Εικ.2. Τμήμα του προγράμματος για το "Tank Crew" (παράδειγμα γραμμών εντολών) Η παραδοσιακή έννοια του "συστήματος εντολών εκτελεστή" (SCS) και η έννοια της ίδιας της ομάδας απαιτούν βελτίωση. Αν πιστεύουμε ότι τρία μέλη ενός πληρώματος δεξαμενής αποτελούν έναν μόνο ερμηνευτή, τότε τι πρέπει να θεωρείται το SKI αυτού του ερμηνευτή; Και τι θεωρείται ομάδα; Ή να αφήσετε την έννοια του SKI για κάθε χαρακτήρα; Δηλαδή, αυτό δεν είναι πλέον ένα σύστημα εντολών του ΕΚΤΕΛΕΣΤΗ, αλλά ένα σύστημα εντολών ενός από τα στοιχεία του εκτελεστή (για το οποίο δεν υπάρχει ακόμη όνομα);

Είναι βολικό να επεκτείνουμε την έννοια της ομάδας σε μια «γραμμή εντολών». Για παράδειγμα γραμμών εντολών πληρώματος δεξαμενής, βλέπε Εικ. 2. Ωστόσο, η έννοια της «γραμμής εντολών» λειτουργεί καλά μόνο για γραμμικούς αλγόριθμους. Σε άλλες περιπτώσεις οι κυβερνώντες διαμορφώνονται δυναμικά. Είναι αδύνατο να τα απεικονίσετε με τη μορφή οπτικού πίνακα.

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

Ένα ξεχωριστό ζήτημα είναι οι μέθοδοι για την παραλληλοποίηση υπαρχόντων διαδοχικών αλγορίθμων.

Μέχρι πρόσφατα, ο παράλληλος προγραμματισμός ήταν η επαρχία ενός μικρού αριθμού προγραμματιστών συστημάτων υψηλής εξειδίκευσης. Σήμερα γίνεται μέρος της επαγγελματικής ικανότητας. Όμως η τεχνολογία παράλληλου προγραμματισμού διαφέρει σημαντικά από τον παραδοσιακό διαδοχικό προγραμματισμό. Προς υποστήριξη αυτής της δήλωσης, ακολουθώντας τον L.L. Bosova, θα παραθέσουμε τον μεγαλύτερο Ρώσο ειδικό στον τομέα των παράλληλων υπολογιστών V.V. Βοϊβοντίνα:

«... Η μαεστρία της τεχνολογίας υπολογιστών παράλληλης αρχιτεκτονικής... από νέους ειδικούς έρχεται με μεγάλες δυσκολίες. Κατά τη γνώμη μας, αυτό οφείλεται στο γεγονός ότι η γνωριμία με τους παράλληλους υπολογιστές, καθώς και η εκπαίδευση σε αυτόν τον τομέα γενικότερα, δεν ξεκινά από εκεί που πρέπει να ξεκινήσει κανείς. Επιπλέον, αυτό με το οποίο πρέπει να ξεκινήσετε δεν καλύπτεται σε κανένα μάθημα. Η ικανότητα γρήγορης επίλυσης προβλημάτων χρησιμοποιώντας τεχνολογία υπολογιστών παράλληλης αρχιτεκτονικής αναγκάζει τους χρήστες να αλλάξουν ολόκληρο το συνηθισμένο στυλ αλληλεπίδρασης με τους υπολογιστές. Σε σύγκριση, για παράδειγμα, με προσωπικούς υπολογιστές και σταθμούς εργασίας, σχεδόν τα πάντα αλλάζουν: χρησιμοποιούνται άλλες γλώσσες προγραμματισμού, τροποποιούνται οι περισσότεροι αλγόριθμοι, απαιτείται από τους χρήστες να παρέχουν πολυάριθμα μη τυπικά και δύσκολα στην απόκτηση χαρακτηριστικά των εργασιών που επιλύονται, η διεπαφή παύει να είναι φιλική κ.λπ. Ένα σημαντικό γεγονός είναι ότι η αποτυχία να ληφθούν πλήρως υπόψη οι νέες συνθήκες λειτουργίας μπορεί να μειώσει σημαντικά την αποτελεσματικότητα της χρήσης νέου και, επιπλέον, αρκετά ακριβού εξοπλισμού».

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

Σήμερα χρειαζόμαστε μεθόδους μαζικής εκπαίδευσης στην τεχνολογία παράλληλου προγραμματισμού. Ο συγγραφέας αυτού του άρθρου πιστεύει ότι στη μαθησιακή διαδικασία έχει έρθει η ώρα για μια επανάσταση στη σχέση μεταξύ διαδοχικού και παράλληλου προγραμματισμού. Μέχρι τώρα, αρχικά διδάσκαμε διαδοχικό προγραμματισμό και μετά - παραλληλοποίηση διαδοχικών αλγορίθμων. Τώρα πρέπει να θέσουμε αμέσως το ζήτημα της διδασκαλίας του παράλληλου προγραμματισμού. Ένας διαδοχικός αλγόριθμος θα πρέπει να θεωρείται ως ένα ορισμένο μέρος ενός παράλληλου αλγόριθμου, το οποίο δεν απαιτεί επικοινωνία με τα άλλα μέρη του. Πώς να το κάνετε αυτό είναι μια ανοιχτή ερώτηση. Υπάρχουν ακόμα κάποιες ιδέες που χρειάζονται πρακτική εφαρμογή και δοκιμή. Ελπίζεται ότι σε ένα χρόνο στην επόμενη διάσκεψη θα είναι δυνατή η συζήτηση των αποτελεσμάτων που επιτεύχθηκαν.

Πριν από τριάντα χρόνια, η έναρξη της μαζικής μηχανογράφησης της παραγωγής απαιτούσε αύξηση του επιπέδου παιδείας υπολογιστών του πληθυσμού. Αυτό οδήγησε στην εισαγωγή της επιστήμης των υπολογιστών στο σχολικό πρόγραμμα σπουδών το 1985. Αλλά το μάθημα της επιστήμης των υπολογιστών στη σοβιετική (τότε ρωσική) έκδοση δεν περιοριζόταν στην "επιστήμη των υπολογιστών με πάτημα κουμπιών" - στην κυριαρχία της τεχνολογίας εργασίας με πακέτα λογισμικού εφαρμογών και παιχνίδια υπολογιστών. Άρχισε να αλλάζει τον τρόπο σκέψης της νεότερης γενιάς. Πρώτα απ 'όλα, αυτό αφορούσε την αλγοριθμικότητα, την ακρίβεια και την αυστηρότητα. Στη συνέχεια το μάθημα της πληροφορικής ενσωμάτωσε στοιχεία λογικής και ανάλυσης συστημάτων. Στη συνέχεια, όλα αυτά απλοποίησαν σημαντικά τη διανομή της τόσο αναγκαίας τεχνολογίας στον 21ο αιώνα. προσέγγιση του έργου. Η συζήτηση τώρα είναι ότι την επόμενη δεκαετία, θα πρέπει να γίνουν παράλληλοι αλγόριθμοι

στοιχείο της γενικής κουλτούρας της σκέψης. Ερώτηση: πώς θα επηρεάσει η γνώση της έννοιας ενός παράλληλου αλγορίθμου τη σκέψη της επόμενης γενιάς, σε τι θα οδηγήσει η αναδιάρθρωση της συνείδησης «με παράλληλο τρόπο»;

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

Ιστορικά, η πρώτη προσπάθεια να συμπεριληφθεί το θέμα των παράλληλων υπολογιστών σε σχολικό μάθημα πληροφορικής έγινε πριν από είκοσι χρόνια. Πριν από είκοσι χρόνια, σε ένα μάθημα που ονομαζόταν «Αλγόριθμος», περιγράφηκε ένας «Διευθυντής Κατασκευών», ο οποίος διέταξε τις παράλληλες ενέργειες πολλών ομάδων που χτίζουν μια κατασκευή από ορθογώνια και τριγωνικά μπλοκ. Επιπλέον, δημιουργήθηκε μια εφαρμογή λογισμικού για αυτόν τον εκτελεστή. Αλίμονο! Αυτή η υπέροχη μεθοδολογική εξέλιξη δεν ήταν περιζήτητη στα μέσα της δεκαετίας του '90. Ήταν σχεδόν είκοσι χρόνια μπροστά από την εποχή της!

Σήμερα η κατάσταση είναι τέτοια που το θέμα των παράλληλων υπολογιστών στο λύκειο σχετίζεται πρωτίστως με το θέμα των υπερυπολογιστών. Είναι στους υπερυπολογιστές που οι συντάκτες διαφόρων μεθοδολογικών εξελίξεων εστιάζουν την προσοχή των μαθητών, ακόμη και όταν αυτό δεν είναι απαραίτητο. Αρκεί να πούμε ότι η αντίστοιχη ενότητα στο περιοδικό «Πληροφορική στο Σχολείο» ονομάζεται «Εκπαίδευση Υπερυπολογιστή στο Σχολείο». Αυτή η κατάσταση έχει και θετικές και αρνητικές πλευρές. Μεταξύ των θετικών πτυχών είναι:

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

Οργανωτική υποστήριξη από την κοινότητα των υπερυπολογιστών. Κάθε καλοκαίρι, η Σχολή Υπολογιστικών Μαθηματικών και Κυβερνητικής του Κρατικού Πανεπιστημίου της Μόσχας φιλοξενεί τη Θερινή Ακαδημία Υπερυπολογιστών. Και κάθε καλοκαίρι στο πλαίσιο αυτής της Ακαδημίας διοργανώνεται σχολικός στίβος για καθηγητές πληροφορικής. Η εκπαίδευση παρέχεται δωρεάν. Στους μη κατοίκους παρέχεται στέγαση με πολύ ευνοϊκούς όρους. Στο συνέδριο Russian Supercomputing Days τον Σεπτέμβριο του 2015, διοργανώθηκε σχολικό τμήμα και master class για καθηγητές πληροφορικής. Η συνεπής οργανωτική εργασία οδήγησε στον εντοπισμό και τη δημιουργία μιας ομάδας εκπαιδευτικών που ενδιαφέρονται να προωθήσουν αυτό το θέμα.

Η παρουσία ενός φωτεινού, χαρισματικού ηγέτη, όπως ο Βλαντιμίρ Βαλεντίνοβιτς Βοεβοντίν - Διδάκτωρ Φυσικών και Μαθηματικών Επιστημών, Καθηγητής, Αντεπιστέλλον Μέλος της Ρωσικής Ακαδημίας Επιστημών, Αναπληρωτής Διευθυντής του Κέντρου Υπολογιστικών Ερευνών του Κρατικού Πανεπιστημίου της Μόσχας.

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

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

Μια φυσική επέκταση του πεδίου των υπερυπολογιστών είναι η μελέτη του παράλληλου προγραμματισμού. Επί του παρόντος, για την εκτέλεση παράλληλων προγραμμάτων δεν είναι καθόλου απαραίτητο να υπάρχει υπερυπολογιστής. Αρκεί ένας πολυπύρηνος επεξεργαστής ή κάρτα βίντεο με ένα σετ επιταχυντών γραφικών. Και αυτό είναι ήδη διαθέσιμο σχεδόν σε όλους. Μεταξύ των εργασιών προς αυτή την κατεύθυνση, σημειώνουμε την υποψήφια διατριβή του M.A. Sokolovskaya σχετικά με τη μεθοδολογία διδασκαλίας των μελλοντικών δασκάλων επιστήμης υπολογιστών των βασικών στοιχείων του παράλληλου προγραμματισμού και της εμπειρίας του E.Yu. Kiseleva σχετικά με την κατάκτηση της τεχνολογίας CUDA από μαθητές.

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

υπολογισμός» στο γυμνάσιο δεν σημαίνει διδασκαλία «πραγματικού» παράλληλου προγραμματισμού (μελέτη σχετικών γλωσσικών κατασκευών, γλωσσών προγραμματισμού και τεχνολογιών), αλλά εξοικείωση των μαθητών με το αντίστοιχο σύνολο εννοιών και κατανόηση των χαρακτηριστικών της παράλληλης εργασίας. Ο κόσμος γύρω μας και μέσα μας είναι ένα πολύπλοκο παράλληλο σύστημα. Και αυτό το ίδιο το σύστημα παρέχει πολύ υλικό για την κατάκτηση των εννοιών και των μηχανισμών του παραλληλισμού. Δεν χρειάζονται περίπλοκες τεχνητές δομές όπως οι τεχνολογίες MPI και OpenMP για αυτό. Η σχολική επιστήμη των υπολογιστών πρέπει να ενθαρρύνει τη σκέψη με «παράλληλο τρόπο». Και μετά αφήστε το πανεπιστήμιο να ενσωματώσει επαγγελματικές γνώσεις, δεξιότητες και ικανότητες σε αυτή τη σκέψη. Στο σχολείο, είναι λογικό να εστιάσουμε όχι στη γνωριμία με υπερυπολογιστές και στη μελέτη παράλληλου προγραμματισμού, αλλά στην κατοχή των μηχανισμών της «κοινής δραστηριότητας» που χρησιμοποιούνται συνεχώς και ευρέως στη ζωή. Το μάθημα προτείνει να καλύψει τις ακόλουθες ερωτήσεις:

1) Συνεργασία πολλών εκτελεστών (σκάψιμο τάφρου με πολλά σκαπτικά) και παραλληλοποίηση «μέσα» σε έναν εκτελεστή παρουσία πολλών συσκευών επεξεργασίας (διάβασμα και κατανάλωση ενός μήλου). Στην επιστήμη των υπολογιστών, αυτό θα είναι ένα συγκρότημα πολλών μηχανών και ένας επεξεργαστής πολλαπλών πυρήνων.

2) Τύποι παραλληλισμού: αληθινός παραλληλισμός και ψευδοπαραλληλισμός (ένας επεξεργαστής εκτελεί πολλά προγράμματα σε μέρη).

3) Εκτελεστές ίδιου τύπου (σκαπτικά) και διαφορετικών τύπων (πλήρωμα δεξαμενής).

4) Έργα ίδιου τύπου και διαφορετικών τύπων.

5) Η αναλογία «εκτελεστών - εργασιών»: 1 εκτελεστής - 1 εργασία, 1 εκτελεστής - N εργασίες (ψευδοπαράλληλη εκτέλεση ή αληθινός παραλληλισμός παρουσία πολλών συσκευών επεξεργασίας για διαφορετικές εργασίες), Ν εκτελεστές - 1 εργασία, Ν εκτελεστές - N θέσεις εργασίας.

6) Συντονισμός των δραστηριοτήτων των ερμηνευτών. Είδη έγκρισης: ανά μέρη της εργασίας, κατά χρόνο, κατά αποτελέσματα δραστηριοτήτων, ανά πόρους.

7) Πόροι. Οι πόροι είναι κοινόχρηστοι και μη, αναλώσιμοι και επαναχρησιμοποιήσιμοι. Ανακύκλωση των καταναλωμένων πόρων («συλλογή σκουπιδιών» με την ευρεία έννοια).

8) Εκτέλεση του ίδιου έργου από έναν ερμηνευτή και μια ομάδα ερμηνευτών. Εξάρτηση της ταχύτητας εργασίας από τον αριθμό των εκτελεστών. Εξάρτηση του κόστους εργασίας από τον αριθμό των ερμηνευτών. Μη γραμμική αύξηση της ταχύτητας εργασίας με αύξηση του αριθμού των εκτελεστών. Κρίσιμη διαδρομή. Βέλτιστος αριθμός ερμηνευτών. Βέλτιστη φόρτωση εκτελεστών. Βέλτιστη διαδικασία. Εξισορρόπηση φορτίου.

9) Ανταγωνισμός μεταξύ ερμηνευτών για πόρους. Μπλοκάρισμα. Clinch (αδιέξοδο).

10) Μηχανισμοί συντονισμού των ενεργειών των ερμηνευτών.

11) Ψευδοπαράλληλη εκτέλεση διεργασιών σε υπολογιστή (διαίρεση ενός πόρου - ο επεξεργαστής) μεταξύ εκτελεστών-διεργασιών.

12) Καταλληλότητα αλγορίθμων για παραλληλοποίηση. Πιθανός βαθμός παραλληλισμού. Η ύπαρξη αλγορίθμων που δεν μπορούν να παραλληλιστούν.

Σημειώστε ότι η παραπάνω λίστα αντιπροσωπεύει την προσωπική γνώμη του συγγραφέα του άρθρου και είναι ανοιχτή για συζήτηση, προσθήκη και διόρθωση. Επιπλέον, κατά τη γνώμη του συγγραφέα, θα ήταν πολύ χρήσιμο για την «κοινότητα των υπερυπολογιστών» να διατυπώσει μια «κοινωνική τάξη» για το σχολείο: τι είδους γνώσεις και δεξιότητες θέλει να δει στους αποφοίτους του σχολείου. Πώς πρέπει να διαφέρει ένας απόφοιτος της σχολής του «κόσμου των υπερυπολογιστών» από έναν απόφοιτο του σήμερα; Αν υπάρξει παραγγελία, θα υπάρξει αποτέλεσμα. Φρέσκο ​​παράδειγμα. Την πρώτη ημέρα των Russian Supercomputing Days-2015, δύο αναφορές εξέφρασαν την ιδέα ότι η ταχύτητα των σύγχρονων υπερυπολογιστών δεν καθορίζεται από τη δύναμη των επεξεργαστών (που είναι το επίκεντρο της προσοχής του κοινού), αλλά από την ταχύτητα της μνήμης RAM. Είναι αυτό που γίνεται το σημείο συμφόρησης, η απόδοση του οποίου καθορίζει την παραγωγικότητα ολόκληρου του συστήματος. Ως αποτέλεσμα, τη δεύτερη μέρα του συνεδρίου, οι συμμετέχοντες στην κύρια τάξη του δασκάλου δοκίμασαν ένα παιχνίδι που εφευρέθηκε από τον συγγραφέα αυτού του άρθρου, δείχνοντας την αλληλεπίδραση του κεντρικού επεξεργαστή, της μνήμης RAM και της μνήμης cache. Η σειρά και η μορφή παρουσίασης του υλικού είναι ανοιχτό ερώτημα.

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

Όσο το δυνατόν μεγαλύτερο μέρος της εκπαίδευσης θα πρέπει να έχει χαρακτήρα επιχειρηματικών (οργανωτικών και δραστηριοτήτων) παιχνιδιών.

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

Ο συγγραφέας αυτού του άρθρου άρχισε να εργάζεται για την προετοιμασία μιας μεθοδολογίας για τη μελέτη παράλληλων υπολογιστών το 2013 κατά την προετοιμασία του διαγωνισμού TRIZformashka-2013 και συνέχισε τα επόμενα χρόνια.

(Το "TRIZformashka" είναι ένας διαπεριφερειακός διαγωνισμός Διαδικτύου στην επιστήμη των υπολογιστών, στην ανάλυση συστημάτων και στο TRIZ. Πραγματοποιείται ετησίως το δεύτερο μισό του Μαρτίου. Η ηλικία των συμμετεχόντων είναι από την πρώτη τάξη έως το τέταρτο έτος. Γεωγραφία - από το Βλαδιβοστόκ στη Ρίγα. Ο μέσος όρος Ο αριθμός των συμμετεχόντων είναι 100 ομάδες (300 άτομα .), το μέγιστο - 202 ομάδες (περισσότερα από 600 άτομα Ο ιστότοπος του διαγωνισμού είναι www.trizformashka.ru.) Στη συνέχεια, το 2013, ο στόχος της εργασίας διατυπώθηκε ως εξής:

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

2. Να τα προσφέρει (τμηματικά, ετησίως) στους συμμετέχοντες του διαγωνισμού.

3. Αναλύστε την αντίδρασή τους (εκτιμήστε τον αριθμό των επιλυτών, την ηλικία τους, την επιτυχία της λύσης, τυπικά λάθη, ανιχνευμένες ανακρίβειες στη διατύπωση προβλημάτων κ.λπ.). Ο διαγωνισμός TRIZformashka αποδείχθηκε ότι ήταν ένα βολικό εργαλείο για την αποσφαλμάτωση προβλημάτων, καθώς

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

Τα τελευταία χρόνια έχει προετοιμαστεί το ακόλουθο σύνολο μεθοδολογικών εργαλείων και πλατφορμών για τη δοκιμή τους.

1. Εργασίες για τον παραλληλισμό, ξεκινώντας από το 2013, συμπεριλήφθηκαν στον διαγωνισμό «TRIZformashka» (από το 2013 ο διαγωνισμός έχει τον υπότιτλο «Παράλληλος Υπολογισμός»). Μια λίστα τύπων εργασιών δίνεται παρακάτω.

2. Ένα κεφάλαιο για τον παραλληλισμό έχει ετοιμαστεί για τη νέα έκδοση του σχολικού εγχειριδίου πληροφορικής για την 4η τάξη. Η ύλη δοκιμάστηκε στις Γ' και Δ' τάξεις του Λυκείου Νο. 10 στο Περμ.

3. Το παιχνίδι υπολογιστή «Tank Crew» έχει αναπτυχθεί και χρησιμοποιείται από το 2014 στον διαγωνισμό TRIZformashka.

4. Έχει αναπτυχθεί και δοκιμαστεί ένας αριθμός παιχνιδιών, τα οποία αντικατοπτρίζουν τα ακόλουθα ζητήματα:

Συντονισμός των δραστηριοτήτων των ερμηνευτών. Διάφοροι τύποι έγκρισης.

Εκτέλεση του ίδιου έργου από έναν ερμηνευτή και μια ομάδα ερμηνευτών. Εξάρτηση της ταχύτητας εργασίας από τον αριθμό των εκτελεστών. Μη γραμμική αύξηση της ταχύτητας εργασίας με αύξηση του αριθμού των εκτελεστών. Κρίσιμη διαδρομή. Βέλτιστος αριθμός ερμηνευτών. Βέλτιστη φόρτωση εκτελεστών. Βέλτιστη διαδικασία;

Πόροι. Κοινόχρηστοι και μη κοινόχρηστοι πόροι.

Ανταγωνισμός μεταξύ των καλλιτεχνών για πόρους. Μπλοκάρισμα. Clinch (αδιέξοδο). Προτάθηκαν και δοκιμάστηκαν τα ακόλουθα είδη προβλημάτων:

1. Καθήκοντα σχετικά με τους τύπους έγκρισης. (Τι τύποι συντονισμού υπάρχουν στην καφετέρια του σχολείου;);

2. Παιχνίδι "Tank Crew". Εργασία για την κατασκευή ενός παράλληλου αλγόριθμου.

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

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

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

6. Μορφές κλιμακωτές-παράλληλες. Σχεδιασμός εργασιών σύμφωνα με διάφορα κριτήρια. Δίνονται η ανάθεση εργασίας, η παραγωγικότητα των εργαζομένων και οι κανόνες πληρωμής. Είναι απαραίτητο να προσδιοριστεί ο αριθμός των εργαζομένων που απαιτούνται για την ολοκλήρωση της εργασίας σε μια δεδομένη χρονική στιγμή, να καθοριστεί η περίοδος εργασίας για έναν δεδομένο αριθμό εργαζομένων, να καθοριστεί ο αριθμός των εργαζομένων που απαιτούνται για την ελαχιστοποίηση του κόστους εργασίας.

7. Διαγράμματα Gantt. Το κείμενο περιγράφει το σχέδιο εργασίας για την ανακατασκευή του εργαστηρίου: διάρκεια και αμοιβαία αλληλουχία ενεργειών, απαιτούμενοι εργαζόμενοι. Είναι απαραίτητο να καθοριστεί η προθεσμία για την ολοκλήρωση του αντικειμένου, η αλλαγή της προθεσμίας λόγω ορισμένων αλλαγών στο εργατικό δυναμικό και ο κατάλογος των εργαζομένων που συμμετέχουν σε μια συγκεκριμένη ημερομηνία.

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

Σήμερα έχουμε τα εξής αποτελέσματα:

1. Έχει διατυπωθεί μια προσέγγιση για τη μελέτη του θέματος των «παράλληλων υπολογιστών»: να μην φύγουμε από τα προβλήματα της επιστήμης των υπολογιστών, αλλά «από τη ζωή», να επικεντρωθούμε στην «κοινή δραστηριότητα».

2. Έχει διατυπωθεί ένας κατάλογος θεμάτων που προτείνεται να αντικατοπτρίζονται στην αρχική πορεία του παράλληλου υπολογισμού.

3. Διατυπώνονται ορισμένες κατηγορίες προβλημάτων. Με βάση τη συσσωρευμένη εμπειρία, μπορείτε να αξιολογήσετε τι είδους προβλήματα πρέπει να εφευρεθούν.

4. Έχει ετοιμαστεί ένα σύνολο προβλημάτων των ονομαζόμενων τάξεων. Τα προβλήματα δοκιμάστηκαν στους διαγωνισμούς TRIZformashka το 2013, 2014, 2015. ή/και στο δημοτικό σχολείο (σε τάξεις με μαθητές της τρίτης και της τέταρτης τάξης του Λυκείου Νο. 10 στο Περμ).

5. Έχει ετοιμαστεί ένα σετ επαγγελματικών παιχνιδιών. Τα παιχνίδια έχουν δοκιμαστεί σε δημοτικά σχολεία και σε πλήθος εκδηλώσεων για εκπαιδευτικούς. Συγκεκριμένα, παρουσιάστηκαν στο σχολικό κομμάτι της Θερινής Ακαδημίας Υπερυπολογιστών του Κρατικού Πανεπιστημίου της Μόσχας το 2014, σε ένα master class για δασκάλους στο Russian Supercomputing Days-2015, σε πολλά άλλα συνέδρια (συμπεριλαμβανομένου του συνεδρίου IT-education-2015 του η ένωση APKIT) και άλλες εκδηλώσεις για καθηγητές πληροφορικής·

6. Ετοιμάστηκε ένα σύνολο κειμένων για τον παραλληλισμό για ένα σχολικό βιβλίο της τέταρτης δημοτικού. Τα κείμενα δοκιμάστηκαν στο Λύκειο Νο. 10 στο Περμ.

7. Το παιχνίδι στον υπολογιστή “Tank Crew” έχει ετοιμαστεί. Το παιχνίδι δοκιμάστηκε στους διαγωνισμούς TRIZformashka το 2014 και το 2015.

8. Ο διαγωνισμός TRIZformashka έχει αποδειχθεί ως πλατφόρμα έγκρισης.

9. Διατυπώνεται το έργο του «castling» στη διαδικασία διδασκαλίας του αλγοριθμισμού: διδάξτε αμέσως τον παράλληλο προγραμματισμό, παρουσιάζοντας έναν διαδοχικό αλγόριθμο ως μέρος ενός παράλληλου. Υπάρχουν σκέψεις για το πώς μπορεί να υλοποιηθεί αυτή η ιδέα. Υπάρχει η ευκαιρία να δοκιμάσετε αυτές τις ιδέες κατά τη διάρκεια του τρέχοντος σχολικού έτους (για μαθητές των τάξεων 4-5).

10. Υπάρχει ανάγκη, επιθυμία και ευκαιρία να συνεχίσετε να εργάζεστε.

Βιβλιογραφία

1. Αλγόριθμοι: τάξεις 5-7: Βιβλίο και προβληματικό βιβλίο γενικής εκπαίδευσης. εκπαιδευτικά ιδρύματα /Α.Κ. Zvonkin, A.G. Kulakov, S.K. Lando, A.L. Semenov, A.Kh. Σεν. - M.: Bustard, 1996.

2. Bosova L.L. Παράλληλοι αλγόριθμοι σε σχολεία πρωτοβάθμιας και δευτεροβάθμιας εκπαίδευσης. //Πληροφορική στο σχολείο. 2015, αρ. Σελ.24-27.

3. Voevodin V.V. Υπολογιστικά μαθηματικά και η δομή των αλγορίθμων: Διάλεξη 10 σχετικά με το γιατί είναι δύσκολο να λυθούν προβλήματα σε υπολογιστικά συστήματα παράλληλης αρχιτεκτονικής και ποιες πρόσθετες πληροφορίες πρέπει να γνωρίζετε. για να ξεπεράσει με επιτυχία αυτές τις δυσκολίες: ένα σχολικό βιβλίο. Μ.: Εκδοτικός Οίκος MSU 2010.

4. Gavrilova I.V. Πρώτο ταξίδι στον «παράλληλο κόσμο». //Πληροφορική στο σχολείο. 2015, Νο. 6. Σελ.16-19.

5. Dieter M.L., Plaksin M.A. Παράλληλοι υπολογιστές στη σχολική επιστήμη των υπολογιστών. Παιχνίδι "Κατασκευή". //Πληροφορική στο σχολείο: παρελθόν, παρόν και μέλλον.: υλικά του Πανρωσικού. επιστημονική μέθοδος. συνδ. για τη χρήση των ΤΠΕ στην εκπαίδευση, 6-7 Φεβρουαρίου 2014 /Περμ. κατάσταση εθνικός έρευνα παν. - Perm, 2014. - Σελ.258-261.

6. Ivanova N.G., Plaksin M.A., Rusakova O.L. TRIZformashka. //Επιστήμη των υπολογιστών. N05 Ανακτήθηκε 10/10/2015.

14. Plaksin M.A. Πληροφορική: εγχειρίδιο για την 4η τάξη: 2 ώρες / M.A.Plaksin, N.G.Ivanova, O.L.Rusakova. - Μ.: ΜΠΙΝΟΜ. Εργαστήριο Γνώσης, 2012.

15. Plaksin M.A. Σχετικά με τη μέθοδο της αρχικής γνωριμίας με τους παράλληλους υπολογιστές στο λύκειο. //Πληροφορική στο σχολείο: παρελθόν, παρόν και μέλλον.: υλικά του Πανρωσικού. επιστημονική μέθοδος. συνδ. για τη χρήση των ΤΠΕ στην εκπαίδευση, 6-7 Φεβρουαρίου 2014 /Περμ. κατάσταση εθνικός έρευνα παν. - Perm, 2014. - Σελ.256-258.

16. Plaksin M.A. Ένα σύνολο επαγγελματικών παιχνιδιών για την εισαγωγή παράλληλων υπολογιστών στο δημοτικό σχολείο. //Διδασκαλία τεχνολογιών πληροφοριών στη Ρωσική Ομοσπονδία: υλικά του δέκατου τρίτου ανοιχτού πανρωσικού συνεδρίου "IT-0education-2015" (Περμ, 14-15 Μαΐου 2015). Perm State National Research University, - Perm, 2015. P.60-62.

17. Plaksin M.A., Ivanova N.G., Rusakova O.L. Ένα σύνολο εργασιών για εξοικείωση με τους παράλληλους υπολογιστές στον διαγωνισμό TRIZformashka. //Διδασκαλία των τεχνολογιών της πληροφορίας στη Ρωσική Ομοσπονδία: υλικά του δέκατου τρίτου ανοιχτού πανρωσικού συνεδρίου "IT Education-2015" (Περμ, 14-15 Μαΐου 2015). Perm State National Research University, - Perm, 2015. σελ. 232-234.

18. Sokolovskaya M.A. Μεθοδολογικό σύστημα διδασκαλίας των βασικών του παράλληλου προγραμματισμού σε μελλοντικούς καθηγητές πληροφορικής.: περίληψη. dis. ...κανάλι. πεδ. Επιστήμες, Krasnoyarsk, 2012.