Das Konzept des Parallelrechnens ist ein allgemeines Organisationsschema. Parallele Computersysteme

Parallele Rechenprozesse und -systeme (Vorlesung 13)

Arten der Parallelität

Es gibt zwei Arten der parallelen Datenverarbeitung: Pipeline und tatsächliche Parallelität.

Parallelverarbeitung. Wenn ein bestimmtes Gerät eine Operation pro Zeiteinheit ausführt, führt es in tausend Einheiten tausend Operationen aus. Wenn wir davon ausgehen, dass es fünf identische unabhängige Geräte gibt, die gleichzeitig arbeiten können, dann kann ein System aus fünf Geräten die gleichen tausend Vorgänge nicht in tausend, sondern in zweihundert Zeiteinheiten ausführen.

Förderbandverarbeitung. Was wird benötigt, um zwei in Gleitkommaform dargestellte reelle Zahlen zu addieren? Eine ganze Reihe kleiner Operationen wie das Vergleichen von Bestellungen, das Ausrichten von Bestellungen, das Hinzufügen von Mantissen, das Normalisieren usw. Die Prozessoren der ersten Computer führten alle diese „Mikrooperationen“ für jedes Argumentpaar nacheinander durch, bis sie das Endergebnis erreichten, und begannen erst dann mit der Verarbeitung des nächsten Termpaares. Die Idee der Pipeline-Verarbeitung besteht darin, einzelne Phasen der Ausführung einer allgemeinen Operation zu isolieren, und jede Phase würde nach Abschluss ihrer Arbeit das Ergebnis an die nächste weitergeben und gleichzeitig einen neuen Teil der Eingabedaten empfangen. Durch die Kombination zuvor beabstandeter Vorgänge ergibt sich ein offensichtlicher Gewinn an Verarbeitungsgeschwindigkeit. Nehmen wir an, dass es in einer Operation fünf Mikrooperationen gibt, die jeweils in einer Zeiteinheit ausgeführt werden. Wenn ein unteilbares serielles Gerät vorhanden ist, verarbeitet es 100 Argumentpaare in 500 Einheiten. Wenn jede Mikrooperation in eine separate Stufe (oder auch Stufe genannt) eines Fördergeräts unterteilt wird, werden in der fünften Zeiteinheit in verschiedenen Verarbeitungsstufen eines solchen Geräts die ersten fünf Argumentpaare lokalisiert , und der gesamte Satz von einhundert Paaren wird in 5 + 99 = 104 Zeiteinheiten verarbeitet – die Beschleunigung im Vergleich zu einem seriellen Gerät beträgt fast das Fünffache (basierend auf der Anzahl der Pipeline-Stufen).

Es scheint, dass die Pipeline-Verarbeitung erfolgreich durch gewöhnliche Parallelität ersetzt werden kann, bei der wir das Hauptgerät so oft duplizieren, wie die Anzahl der Stufen der Pipeline zugewiesen werden soll. Aber indem wir die Anzahl der Geräte verfünffachen, erhöhen wir sowohl das Volumen als auch die Kosten der Geräte deutlich.

Implementierung paralleler Systeme

Die Computerleistung ist von 1945 bis heute exponentiell gestiegen (im Durchschnitt alle 10 Jahre). Die Computerarchitektur hat erhebliche Veränderungen erfahren und ist von seriell auf parallel umgestiegen.

Die Computerleistung steht in direktem Zusammenhang mit der Zeit, die zum Ausführen grundlegender Funktionen erforderlich ist, und mit der Anzahl dieser grundlegenden Operationen, die gleichzeitig ausgeführt werden können. Die Ausführungszeit einer einfachen Anweisung ist letztendlich begrenzt.

Daraus lässt sich leicht schließen, dass man sich nicht darauf beschränken kann, die Geschwindigkeit nur auf Kosten der Prozessortaktrate zu erhöhen. Die Abhängigkeit von Prozessoren führt letztlich in eine Sackgasse. Eine weitere Strategie in diesem Bereich besteht darin, interne Parallelität im Prozessorchip zu nutzen. Aber eine solche Technologie ist sehr teuer. Moderne Supercomputer basieren größtenteils auf der Idee, eine große Anzahl bereits verfügbarer, relativ kostengünstiger Prozessoren zu nutzen.

Dazu gehören auch Systeme wie: Supercomputer, die mit Tausenden von Prozessoren ausgestattet sind; Netzwerke von Arbeitsplätzen; Multiprozessor-Workstations usw.

Multicomputer - das ist ein bestimmter Betrag von Neumann-Maschinen(Knoten), die durch ein Netzwerk miteinander verbunden sind. Jeder Computer führt sein eigenes Programm aus. Diese Programme können auf den lokalen Speicher zugreifen und Nachrichten über das Netzwerk senden und empfangen. Nachrichten, die für die Kommunikation zwischen Computern verwendet werden, entsprechen Lese- oder Schreibvorgängen aus dem Remote-Speicher. In einem idealisierten Netzwerk hängt die Zustellungszeit einer Nachricht zwischen Maschinen nicht von der Entfernung zwischen Knoten oder dem Netzwerkverkehr ab, sondern von der Länge des gesendeten Briefs.

Der entscheidende Parameter des Multicomputermodells besteht darin, dass der Zugriff auf lokalen Speicher (im selben Knoten) kostengünstiger ist als auf entfernten Speicher (in einem anderen Knoten). Diese. Lese- und Schreibvorgänge sind kostengünstiger als das Senden oder Empfangen von Nachrichten. Daher ist es wünschenswert, dass auf lokale Daten viel häufiger zugegriffen wird als auf entfernte Daten. Diese grundlegende Eigenschaft von Software wird Lokalität genannt. Der Wert der Lokalität hängt vom Verhältnis der Kosten des Fernzugriffs zum lokalen Zugriff ab.

Andere Automodelle. Schauen wir uns die wichtigsten Computerarchitekturen an. Ein Multicomputer ist dem sogenannten MIMD-Computer (Multiple Instruction Multiple Data) mit verteiltem Speicher sehr ähnlich. MIMD bedeutet, dass jeder Prozessor einen separaten Befehlsstrom über seine eigenen lokalen Daten verarbeiten kann. Verteilter Speicher bedeutet, dass der Speicher auf die Prozessoren verteilt ist. Der grundlegende Unterschied zwischen einem MIMD-Computer und einem Multicomputer besteht darin, dass die Kosten für die Übermittlung einer Nachricht zwischen zwei Knoten nicht vom Standort des Knotens und dem Netzwerkverkehr abhängen. Die Hauptvertreter dieser Klasse: IBM SP, Intel Paragon, Thinking Machines CM 5, Cray T 3D, Meiko CS-2 und CUBE.

Eine weitere Klasse von Supercomputern sind Multiprozessor- oder MIMD-Computer mit gemeinsam genutztem Speicher. In einem Multiprozessor greifen alle Prozessoren gemeinsam auf einen gemeinsamen Speicher zu, normalerweise über einen Bus oder über eine Bushierarchie. In einem idealisierten PRAM-Modell (Parallel Random Access Machine), das häufig theoretisch untersuchte parallele Algorithmen verwendet, kann jeder Prozessor gleichzeitig auf jedes Speicherelement zugreifen. Bei dieser Architektur handelt es sich normalerweise um eine spezielle Form eines Speichergeräts. Die Anzahl der Zugriffe auf den gemeinsam genutzten Speicher wird reduziert, indem Kopien häufig aufgerufener Daten in einem jedem Prozessor zugeordneten Cache gespeichert werden.

Der Zugriff auf diesen Cache ist viel schneller als der Zugriff auf den gemeinsam genutzten Speicher, daher ist die Lokalität sehr wichtig. Für Multicomputer konzipierte Programme können auf Multiprozessoren genauso effizient ausgeführt werden, da der gemeinsame Speicher eine effiziente Nachrichtenübermittlung ermöglicht. Vertreter dieser Klasse sind Silicon Graphics Challenge, Sequent Symmetry und viele Multiprozessor-Workstations.

Eine speziellere Klasse paralleler Computer sind SIMD-Computer (Single Instruction Miltiple Data). In SIMD-Maschinen arbeiten alle Prozessoren mit demselben Befehlsstrom für verschiedene Daten. Dieser Ansatz kann die Komplexität von Software und Hardware reduzieren, ist jedoch nur für spezielle Probleme sinnvoll, die durch ein hohes Maß an Regelmäßigkeit gekennzeichnet sind, wie z. B. Bildverarbeitung und bestimmte Arten der digitalen Modellierung. Auf Multicomputern anwendbare Algorithmen können im Allgemeinen nicht effizient auf SIMD-Computern ausgeführt werden.

Neurocomputationale Systeme.

Ein Neurocomputing-Gerät ist ein System, dessen Funktion maximal auf die Implementierung neuronaler Netzwerkalgorithmen ausgerichtet ist. Der Hauptunterschied zwischen Neurocomputern und anderen Computersystemen besteht in der Bereitstellung einer hohen Parallelität der Berechnungen durch die Verwendung einer speziellen logischen Basis eines neuronalen Netzwerks oder spezifischer Architekturlösungen. Die Fähigkeit zur Darstellung neuronaler Netzalgorithmen zur Implementierung auf neuronaler Netzlogischer Basis ist die Hauptvoraussetzung für eine starke Leistungssteigerung von Neurocomputern.

Derzeit wird die Entwicklung digitaler Neurocomputer am aktivsten in den folgenden Bereichen betrieben:

· Software-Emulation neuronaler Netzwerkalgorithmen basierend auf der Verwendung herkömmlicher Computerwerkzeuge und Software zur Modellierung neuronaler Netzwerke;

· Software- und Hardware-Emulation neuronaler Netze auf der Grundlage von Standard-Computertools mit einer Plug-in-Einheit für virtuelle neuronale Netze, die grundlegende Neurooperationen ausführt, und Software, die allgemeine Steuerfunktionen ausführt;

· Hardware-Implementierung neuronaler Netze.

Trotz der Tatsache, dass der größte Effekt bei der Implementierung neuronaler Netzwerkalgorithmen nur durch den Einsatz von Neurocomputern der dritten Richtung erzielt werden kann, ist ihre weit verbreitete Verwendung durch Hochtechnologie begrenzt. Beispielsweise ist der Neurocomputer Synaps1 einer der Vertreter der Neurocomputer der dritten Richtung, verfügt über eine Multiprozessorarchitektur, ein originelles Design des Speichersubsystems und verwendet Signalprozessoren und spezielle Signalmatrixprozessoren MA16 zur Durchführung von Rechenoperationen. Dadurch betrug die Leistung des Neurocomputers mehrere Milliarden Multiplikationen und Additionen pro Sekunde. Die Software dieses Systems umfasst das Synaps1-Betriebssystem mit einer Bibliothek von Neuroalgorithmen sowie Software: eine grundlegende NS-Bibliothek, einen Compiler für die Neuroalgorithm-Programmiersprache (nAPL) (eine Reihe von Bibliotheksfunktionen für C++) usw. Angewandte Forschung hat gezeigt, dass der Einsatz von Neurocomputern der dritten Richtung es ermöglicht, die Leistung herkömmlicher Computersysteme um mindestens drei Größenordnungen zu steigern und neuronale Netze mit Millionen von Verbindungen zu simulieren. Mit Synaps1 können Sie beispielsweise mithilfe verschiedener Aktivierungsfunktionen ein neuronales Netzwerk mit 64 Millionen Synapsen simulieren.

Zwei Klassen von Computersystemen, die manchmal als Parallelcomputer verwendet werden, sind ein lokales Netzwerk (LAN), in dem Computer in physischer Nähe (z. B. im selben Gebäude) über ein schnelles Netzwerk verbunden sind, und ein Weitverkehrsnetzwerk (WAN). , in dem sie geografisch verbunden sind. Remote-Computer. Obwohl Systeme dieser Art zusätzliche Probleme wie Sicherheit und Zuverlässigkeit mit sich bringen, können sie für verschiedene Zwecke als Multicomputer betrachtet werden, wenn auch mit hohen Kosten für den Fernzugriff.

Schwierigkeiten bei der Verwendung paralleler Systeme

Die enorme Leistungsfähigkeit von Parallelrechnern und Supercomputern wird durch die Schwierigkeiten bei deren Nutzung mehr als ausgeglichen.

Sie haben ein Programm und Zugriff auf beispielsweise einen Computer mit 256 Prozessoren. Was erwarten Sie? Ja, es ist klar: Sie erwarten völlig berechtigt, dass das Programm 256-mal schneller ausgeführt wird als auf einem einzelnen Prozessor. Aber genau das wird höchstwahrscheinlich nicht passieren.

Amdahls Gesetz. Angenommen, in einem Programm ist der Anteil der Operationen, die nacheinander ausgeführt werden müssen, gleich f, wobei 0 ist<=f <=1 (при этом доля понимается не по статическому числу строк кода, а по числу операций в процессе выполнения). Крайние случаи в значениях f соответствуют полностью параллельным (f = 0) и полностью последовательным (f = 1) программам. Тогда для того, чтобы оценить, какое ускорение S может быть получено на компьютере из "p" процессоров при данном значении f, можно воспользоваться законом Амдала: если 9/10 программы исполняется параллельно, а 1/10 по-прежнему последовательно, то ускорения более, чем в 10 раз получить в принципе невозможно вне зависимости от качества реализации параллельной части кода и числа используемых процессоров (10 получается только в том случае, когда время исполнения параллельной части равно 0).

Konsequenz des Amdahlschen Gesetzes. Um die Ausführung eines Programms um das Q-fache zu beschleunigen, muss die Geschwindigkeit mindestens um das q-fache des (1-1/q)-ten Teils des Programms erhöht werden. Wenn Sie also ein Programm im Vergleich zu seiner sequentiellen Version um das Hundertfache beschleunigen möchten, müssen Sie mindestens 99,99 % des Codes nicht weniger beschleunigen!

Daher ist es keine leichte Aufgabe, ein paralleles Computersystem mit maximaler Effizienz für ein bestimmtes Programm arbeiten zu lassen, da die Struktur von Programmen und Algorithmen sorgfältig auf die architektonischen Merkmale paralleler Computersysteme abgestimmt werden muss.

Parallele Systemprogrammierung

Das von Neumann-Maschinenmodell geht davon aus, dass der Prozessor eine Folge von Anweisungen ausführt. Anweisungen können zusätzlich zu verschiedenen arithmetischen Operationen die Adressen von Daten angeben, die im Speicher gelesen/geschrieben werden sollen, und/oder die Adresse der nächsten auszuführenden Anweisung. Während es nur möglich ist, einen Computer anhand dieses Grundmodells zu programmieren, ist diese Methode für die meisten Zwecke unerschwinglich komplex, da wir Millionen von Speicherpositionen im Auge behalten und die Ausführung von Tausenden von Maschinenanweisungen orchestrieren müssen. Folglich wird eine modulare Entwurfstechnik angewendet, bei der komplexe Programme aus einfachen Komponenten erstellt und Komponenten anhand von Abstraktionen höherer Ebenen (wie Datenstrukturen, Iterationsschleifen und Prozeduren) strukturiert werden. Abstraktionen (z. B. Prozeduren) erleichtern die Ausnutzung der Modularität, indem sie die Manipulation von Objekten ermöglichen, ohne ihre interne Struktur zu stören. Auf diese Weise entstehen Hochsprachen wie Fortran, C, Ada und Java, die eine Entwicklung im Hinblick auf diese Abstraktionen ermöglichen, die automatisch in ausführbaren Code übersetzt werden. Parallele Programmierung bringt zusätzliche Komplexitätsquellen mit sich: Wenn wir auf der untersten Ebene programmieren müssen, müssen wir nicht nur die Anzahl der ausgeführten Anweisungen erhöhen, sondern auch die Ausführung von Tausenden von Prozessoren verwalten und Millionen von Kommunikationen zwischen Prozessoren koordinieren. Daher sind Abstraktion und Modularität mindestens genauso wichtig wie bei der sequentiellen Programmierung. Tatsächlich heben wir Modularität neben Parallelität, Skalierbarkeit und Lokalität als vierte Grundvoraussetzung für parallele Software hervor.

Die bei der parallelen Programmierung verwendeten Hauptabstraktionen beschränken sich auf Aufgaben und Kanäle:

1. Paralleles Rechnen besteht aus einer oder mehreren Aufgaben. Aufgaben werden parallel ausgeführt. Die Anzahl der Aufgaben kann sich während der Programmausführung ändern.

2. Die Aufgabe isoliert das sequentielle Programm und den lokalen Speicher. Darüber hinaus definiert eine Reihe von Ein- und Ausgängen seine Schnittstelle in seiner Umgebung.

3. Eine Aufgabe kann zusätzlich zum Lesen und Schreiben im lokalen Speicher vier grundlegende Aktionen ausführen: eine Nachricht an ihre Ausgangsports senden, eine Nachricht von ihren Eingangsports empfangen, neue Aufgaben erstellen und eine Aufgabe zerstören (abschließen).

4. Der Vorgang zum Senden einer Nachricht ist asynchron und wird sofort abgeschlossen. Der Empfangsvorgang ist synchron und veranlasst die Ausführung einer Aufgabe, wodurch der Prozess blockiert wird, bis die Nachricht empfangen wird.

5. E/A-Paare können durch in der Warteschlange befindliche Nachrichten, sogenannte Kanäle, verbunden werden. Kanäle können erstellt und gelöscht werden und Verweise auf Kanäle (Ports) können in Nachrichten eingefügt werden, sodass sich die Konnektivität dynamisch ändert.

6. Jobs können auf verschiedene Weise physischen Prozessoren zugeordnet werden; Die Anzeigeanwendung hat keinen Einfluss auf die Semantik des Programms. Konkret können mehrere Jobs einem einzelnen Prozessor zugeordnet werden (man könnte sich auch vorstellen, dass eine einzelne Aufgabe mehreren Prozessoren zugeordnet werden könnte, diese Möglichkeit wird hier jedoch nicht berücksichtigt.)

Die Abstraktion von Aufgaben erfordert die Eigenschaft der Lokalität: Die im lokalen Speicher der Aufgabe enthaltenen Daten sind „geschlossen“; andere Daten werden „gelöscht“. Die Kanalabstraktion bietet einen Mechanismus zum Angeben, welche Daten von einer Aufgabe berechnet werden müssen, bevor eine andere Aufgabe ausgeführt werden kann. (Dies ist durch Datenabhängigkeit gekennzeichnet). Das Aufgaben- und Kanalmodell verfügt außerdem über einige weitere Eigenschaften:

Leistung . Sequentielle Programmierabstraktionen wie Prozeduren und Datenstrukturen sind effektiv, weil sie einfach und effizient auf einen Von-Neumann-Computer abgebildet werden können. Aufgaben und Kanäle haben in einem Multicomputer eine ähnlich direkte Verteilung. Eine Aufgabe stellt einen Codeabschnitt dar, der sequentiell auf einem einzelnen Prozessor ausgeführt werden kann. Wenn zwei Aufgaben, die sich einen Kanal teilen, anderen Prozessoren zugeordnet werden, wird die Kanalverbindung als Interprozessorverbindung implementiert; Wenn sie demselben Prozessor zugeordnet sind, können einige effizientere Mechanismen verwendet werden.

Unabhängigkeit der Verteilung . Da Aufgaben unabhängig vom Standort der Aufgabe über denselben Mechanismus (Kanäle) kommunizieren, hängt das vom Programm berechnete Ergebnis nicht davon ab, wo die Aufgabe ausgeführt wird. Daher können Algorithmen entworfen und implementiert werden, ohne sich Gedanken über die Anzahl der Prozessoren machen zu müssen, auf denen sie ausgeführt werden; Tatsächlich sind Algorithmen oft so konzipiert, dass sie viel mehr Aufgaben erstellen als Prozessoren. Dies ist eine einfache Möglichkeit, eine Skalierung zu erreichen: Mit zunehmender Anzahl von Prozessoren nimmt die Anzahl der Aufgaben pro Prozessor ab, der Algorithmus selbst muss jedoch nicht geändert werden. Wenn es mehr Aufgaben gibt, als die Prozessoren bewältigen können, um Kommunikationsverzögerungen zu maskieren, werden andere Berechnungen bereitgestellt, die während der Kommunikation durchgeführt werden können, um auf entfernte Daten zuzugreifen.

Modularität. Bei der modularen Programmierung werden verschiedene Programmbestandteile separat als eigenständige Module entwickelt und dann zu einem Gesamtprogramm kombiniert. Die Interaktion zwischen Modulen ist auf klar definierte Schnittstellen beschränkt. Folglich können modulare Implementierungen geändert werden, ohne andere Komponenten zu modifizieren, und die Eigenschaften eines Programms können aus der Spezifikation seiner Module und dem Code, der diese Module miteinander verbindet, bestimmt werden. Wenn die modulare Entwicklung erfolgreich angewendet wird, wird die Softwarekomplexität reduziert und die Wiederverwendung von Code erleichtert.

Determinismus. Ein Algorithmus oder Programm ist deterministisch, wenn es bei Ausführung mit einer bestimmten Eingabe immer die gleiche Ausgabe erzeugt. Es ist nicht deterministisch, wenn mehrere Ausführungen derselben Eingabe zu einer unterschiedlichen Ausgabe führen können. Während Nichtdeterminismus manchmal nützlich ist und unterstützt werden sollte, ist ein paralleles Programmiermodell, das das Schreiben deterministischer Programme erleichtert, äußerst wünschenswert. Deterministische Programme sind tendenziell verständlicher. Außerdem sollte bei der Prüfung auf Korrektheit nur eine Ausführungssequenz eines parallelen Programms berechnet werden und nicht alle möglichen Ausführungssequenzen.

Die aktuelle Version der Seite wurde noch nicht überprüft

Die aktuelle Version der Seite wurde noch nicht von erfahrenen Teilnehmern verifiziert und kann erheblich von der am 5. Oktober 2014 verifizierten Version abweichen; Kontrollen sind erforderlich.

Paralleles Rechnen- eine Methode zur Organisation von Computer-Computing, bei der Programme als eine Reihe interagierender Computerprozesse entwickelt werden, die parallel (gleichzeitig) ablaufen. Der Begriff umfasst eine Reihe von Fragen der Parallelität in der Programmierung sowie die Erstellung effizienter Hardware-Implementierungen. Die Theorie des Parallelrechnens stellt einen Zweig der angewandten Algorithmentheorie dar.

Es gibt verschiedene Möglichkeiten, paralleles Rechnen zu implementieren. Beispielsweise kann jeder Computerprozess als Betriebssystemprozess implementiert sein, oder Computerprozesse können eine Sammlung von Ausführungsthreads innerhalb eines einzelnen Betriebssystemprozesses sein. Parallele Programme können physisch entweder sequentiell auf einem einzelnen Prozessor ausgeführt werden – wobei sich die Schritte jedes Rechenprozesses abwechseln – oder parallel – indem jedem Rechenprozess ein oder mehrere Prozessoren (in der Nähe oder in einem Computernetzwerk verteilt) zugewiesen werden.

Die Hauptschwierigkeit beim Entwurf paralleler Programme besteht darin, die korrekte Reihenfolge der Interaktionen zwischen verschiedenen Rechenprozessen sowie die Koordination der zwischen Prozessen gemeinsam genutzten Ressourcen sicherzustellen.

In einigen parallelen Programmiersystemen ist die Datenübertragung zwischen Komponenten dem Programmierer verborgen (z. B. mithilfe eines Promise-Mechanismus), während sie in anderen explizit angegeben werden muss. Explizite Interaktionen können in zwei Typen unterteilt werden:

Parallele Systeme zur Nachrichtenübermittlung sind oft einfacher zu verstehen als Shared-Memory-Systeme und gelten im Allgemeinen als überlegene Methode der parallelen Programmierung. Für die Untersuchung und Analyse von Nachrichtenübermittlungssystemen gibt es eine breite Palette mathematischer Theorien, darunter das Akteurmodell und verschiedene Arten der Prozessrechnung. Messaging kann effizient auf symmetrischen Multiprozessoren mit oder ohne gemeinsam genutztem kohärentem Speicher implementiert werden.

Die Parallelität des verteilten Speichers und die Parallelität der Nachrichtenübermittlung weisen unterschiedliche Leistungsmerkmale auf. Typischerweise (aber nicht immer) ist der Mehraufwand an Prozessspeicher und Taskwechselzeit bei Systemen zur Nachrichtenübermittlung geringer, die Nachrichtenübermittlung ist jedoch teurer als Prozeduraufrufe. Diese Unterschiede werden oft von anderen Faktoren überschattet, die sich auf die Leistung auswirken.

Plaksin M.A.

National Research University Higher School of Economics (Zweigstelle Perm), Perm, Ph.D., außerordentlicher Professor der Abteilung für Informationstechnologien in der Wirtschaft, mapl@list. ru

„SUPERCOMPUTER“ VS „PARALLELPROGRAMMIERUNG“. „PARALLELE PROGRAMMIERUNG“ VS. „ZUSAMMENARBEITENDE AKTIVITÄT“. WIE STUDIERT MAN DAS THEMA „PARALLEL COMPUTING“ IN DER SEKUNDARSCHULE?

STICHWORTE

Informatik, parallele Programmierung, paralleles Rechnen, parallele Algorithmen, Supercomputer, Grundschule, weiterführende Schule, TRIZformashka.

ANMERKUNG

Der Artikel widmet sich der Frage der Einbeziehung des Themas „Parallelrechnen“ in den schulischen Informatikunterricht. Eine Reihe von in diesem Fall auftretenden Problemen werden erwähnt, der Zweck des Studiums des Themas, die Auswahl des Materials, einige Vorschläge für Lehrmethoden, Mechanismen zum Testen der vorgeschlagenen Methodik und die gesammelten Erfahrungen werden berücksichtigt. Die Frage nach dem Platz dieses Materials im Lehrplan wird nicht behandelt.

Der aktuelle Entwicklungsstand der Informatik ist mit der massiven Verbreitung der Parallelität von Berechnungen auf allen Ebenen (Mehrmaschinencluster, Mehrprozessorrechner, Mehrkernprozessoren) verbunden.

Die massive Ausbreitung der Parallelität hat schwerwiegende Folgen, die noch identifiziert und analysiert werden müssen. Beginnen wir mit der Auflistung einiger theoretischer Probleme.

Die moderne Algorithmentheorie wurde mit dem Konzept eines sequentiellen Algorithmus entwickelt. Wie wird sich die Weigerung, eine Abfolge von Schritten zu fordern, auf das Konzept eines Algorithmus auswirken?

Seit mindestens 20 Jahren wird in Schulen das Konzept des „Algorithmus“ eingeführt, das untrennbar mit dem Konzept des „Darstellers“ verbunden ist. Dies ist für einen sequentiellen Algorithmus selbstverständlich. Was tun mit einem parallelen Algorithmus? Wird es von einem Künstler oder einer Gruppe von Künstlern aufgeführt? Konkret nehmen wir als Beispiel das Computertrainingsprogramm „Tank Crew“. In diesem Programm muss der Student die Aktionen einer Panzerbesatzung programmieren, die aus drei Personen besteht: einem Richtschützen, einem Fahrer und einem Ladeschützen. Jeder von ihnen verfügt über ein eigenes Befehlssystem. Um einen Kampfauftrag abzuschließen (alle Ziele zu treffen), müssen alle Besatzungsmitglieder an einem Strang ziehen. Ein Beispiel für das Spielfeld für das Tank Crew-Programm finden Sie in Abb. 1.

Frage: Sollten diese drei Akteure als unabhängige Darsteller oder als drei Komponenten (Geräte) eines komplexen Darstellers betrachtet werden? Für die Panzerbesatzung erscheint die zweite Option natürlicher, da kein einziger Charakter in der Lage ist, die Aufgabe alleine zu erledigen. Was aber, wenn das Spiel komplizierter wird und ein Kampfauftrag zwei Panzern gleichzeitig zugewiesen wird? Für drei Panzer? Drei Mitglieder einer Crew können durchaus als drei Teile eines Künstlers betrachtet werden. Aber jede Crew ist offensichtlich ein unabhängiger Künstler. Dies bedeutet, dass ein paralleler Algorithmus für mehrere Tanks von einer Gruppe von Ausführenden gleichzeitig ausgeführt wird. Es stellt sich heraus, dass für einen parallelen Algorithmus beide Möglichkeiten berücksichtigt werden müssen: die Ausführung paralleler Aktionen durch einen Ausführenden und durch eine Gruppe von Ausführenden. Im Falle einer Panzerbesatzung ist es einfach, die Grenze zu ziehen. Der Ausführende ist derjenige, der in der Lage ist, die Aufgabe zu lösen. Dieser Executor kann aus mehreren Komponenten bestehen, von denen jede einen bestimmten Teil der Aufgabe ausführt, die gesamte Aufgabe jedoch ohne die Hilfe anderer Komponenten nicht selbstständig erledigen kann. Aber ob die Trennung von „ganzen Darstellern“ und Teilen eines komplexen Darstellers immer so einfach sein wird, lässt sich derzeit nicht sagen.

Datei 1*ra Fenster Über das Programm

Vpolyet alles

Bbno.n«fTb zur markierten Zeile

Zurück zur Startseite**"

würde Schritt für Schritt popnlt (nach Ausführung des „.order command nesykoa^“ wird der Button gV ygolg „n-b next uwr“ gedrückt)

Ё ГГВД iTHWTt. besonderer Schritt

Informationen Schritt für Schritt

Abb.1. Fragment des Spielfelds des Tank Crew-Programms

Um die Teile des Darstellers zu identifizieren, die zu unabhängigen Handlungen fähig sind, müssen diese Teile irgendwie benannt werden. Darüber hinaus muss der Name eine Rekursion ermöglichen, da die handelnden Teile des Darstellers selbst eine komplexe Struktur haben können.

Es ist notwendig, sich auf einen Begriff für die Benennung einer Gruppe kooperierender Künstler zu einigen. Der Begriff „Befehl“ ist ungeeignet; er wird mit dem „Executor-Befehlssystem“ und mit „Zentralprozessorbefehlen“ in Verbindung gebracht. „Interpretenkollektiv“? „Brigade der Darsteller“?

Sh. Algorithmus

n Schlagen1"; Fahrerladegerät

1 Messen Sie orun* auf „master sgkll V Stop V Charge 1“.

g Pci V Stopp V Laden 2

3 Großhandel! V Um 90 Grad im Uhrzeigersinn drehen. V 1 V laden

L V V erste V-Ladung? V

5 Feuer! V Stop V Charge 1

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

7 Feuer! V Stopp V Laden 1 V

3 Pa^ V 45 Grad im Uhrzeigersinn drehen V 2 V aufladen

S Pause V Start V Pause V

10 Pvdea V Vorwärts V Pause ¿d

11 Plrl V Vorwärts V Pause V

12 Paum V 45 Grad im Uhrzeigersinn drehen V Pause V

13 Padm V Vorwärts V Pause V

14 V

Abb.2. Fragment des Programms für die „Tank Crew“ (Beispiel für Befehlszeilen) Das traditionelle Konzept des „Executor Command System“ (SCS) und das Konzept des Teams selbst müssen verbessert werden. Wenn wir glauben, dass drei Mitglieder einer Panzerbesatzung einen einzigen Darsteller bilden, was sollte dann als SKI dieses Darstellers angesehen werden? Und was gilt als Team? Oder das Konzept von SKI für jeden Charakter belassen? Das heißt, es handelt sich nicht mehr um ein Befehlssystem des AUSFÜHRERS, sondern um ein Befehlssystem einer der Komponenten des Ausführenden (für die es noch keinen Namen gibt)?

Es ist praktisch, das Konzept eines Teams auf eine „Befehlszeile“ zu erweitern. Ein Beispiel für Befehlszeilen der Panzerbesatzung finden Sie in Abb. 2. Allerdings funktioniert das Konzept einer „Befehlszeile“ nur für lineare Algorithmen gut. In anderen Fällen werden die Lineale dynamisch gebildet. Es ist unmöglich, sie in Form einer visuellen Tabelle darzustellen.

Unter den Eigenschaften von Algorithmen sticht ein neues, praktisch bedeutsames Merkmal hervor: die Fähigkeit zur Parallelisierung. Eine klärende Frage ist der mögliche Grad der Parallelisierung (inwieweit ist es sinnvoll, die Anzahl der Prozessoren bei der Ausführung eines bestimmten Algorithmus zu erhöhen).

Ein separates Problem sind Methoden zur Parallelisierung bestehender sequentieller Algorithmen.

Bis vor Kurzem war die parallele Programmierung die Domäne einer kleinen Anzahl hochqualifizierter Systemprogrammierer. Heute wird es Teil der Fachkompetenz. Die parallele Programmiertechnologie unterscheidet sich jedoch erheblich von der herkömmlichen sequentiellen Programmierung. Zur Unterstützung dieser Aussage folgt L.L. Bosova, wir zitieren den größten russischen Spezialisten auf dem Gebiet des Parallelrechnens V.V. Vojvodina:

„... Die Beherrschung der Computertechnologie mit paralleler Architektur... durch junge Spezialisten ist mit großen Schwierigkeiten verbunden. Das liegt unserer Meinung nach daran, dass die Vertrautheit mit dem Parallelrechnen sowie die Ausbildung in diesem Bereich im Allgemeinen nicht dort beginnt, wo man anfangen sollte. Darüber hinaus wird das, was man zum Einstieg braucht, in keinem Kurs behandelt. Die Fähigkeit, Probleme mithilfe der Computertechnologie mit paralleler Architektur schnell zu lösen, zwingt Benutzer dazu, ihren gesamten gewohnten Interaktionsstil mit Computern zu ändern. Im Vergleich zum Beispiel zu Personalcomputern und Workstations ändert sich fast alles: Es werden andere Programmiersprachen verwendet, die meisten Algorithmen werden modifiziert, Benutzer müssen zahlreiche nicht standardmäßige und schwer zu erhaltende Merkmale der zu lösenden Aufgaben angeben. die Benutzeroberfläche ist nicht mehr benutzerfreundlich usw. Eine wichtige Tatsache ist, dass die Nichtberücksichtigung neuer Betriebsbedingungen die Effizienz des Einsatzes neuer und darüber hinaus recht teurer Geräte erheblich verringern kann.“

„Wichtig ist nur, dass der Schüler so früh wie möglich lernt, dass es andere Möglichkeiten gibt, Rechenprozesse zu organisieren, und nicht nur die sequentielle Ausführung von „Operation für Operation“, dass die leistungsstärkste moderne Computertechnologie auf diesen anderen Methoden aufbaut. dass es nur mit einer solchen Technologie möglich ist, große Probleme, industrielle und wissenschaftliche Aufgaben usw. zu lösen. Wichtig ist zunächst, die Aufmerksamkeit der Studierenden möglichst frühzeitig auf die Notwendigkeit einer kritischen Haltung gegenüber der Philosophie des Sequential Computing zu lenken. Schließlich ist es diese Philosophie, mit der sie sich während ihrer gesamten Ausbildung auseinandersetzen müssen, sowohl in der Schule als auch an der Universität. Und genau diese Philosophie behindert das Verständnis der Besonderheiten der Arbeit an Computern mit paralleler Architektur.“

Heute brauchen wir Methoden für das Massentraining in paralleler Programmiertechnologie. Der Autor dieses Artikels glaubt, dass im Lernprozess die Zeit für eine Revolution in der Beziehung zwischen sequentieller und paralleler Programmierung gekommen ist. Bisher haben wir zuerst die sequentielle Programmierung und dann die Parallelisierung sequentieller Algorithmen gelehrt. Jetzt müssen wir die Frage stellen, ob man paralleles Programmieren lehren kann. Ein sequentieller Algorithmus sollte als ein bestimmter Teil eines parallelen Algorithmus betrachtet werden, der keine Kommunikation mit seinen anderen Teilen erfordert. Wie das geht, ist eine offene Frage. Es gibt noch einige Ideen, die praktisch umgesetzt und getestet werden müssen. Es besteht die Hoffnung, dass es in einem Jahr auf der nächsten Konferenz möglich sein wird, die erzielten Ergebnisse zu diskutieren.

Vor dreißig Jahren erforderte der Beginn der Masseninformatisierung der Produktion eine Erhöhung der Computerkenntnisse der Bevölkerung. Dies führte 1985 zur Einführung der Informatik in den Lehrplan der Schulen. Der Informatikkurs in der sowjetischen (damals russischen) Version beschränkte sich jedoch nicht auf „Informatik auf Knopfdruck“ – auf die Beherrschung der Technologie der Arbeit mit Anwendungssoftwarepaketen und Computerspielen. Er begann, den Denkstil der jüngeren Generation zu verändern. Dabei ging es vor allem um Algorithmizität, Genauigkeit und Stringenz. Anschließend wurden im Informatikstudium Elemente der Logik und Systemanalyse integriert. All dies vereinfachte in der Folge die Verbreitung dringend benötigter Technologie im 21. Jahrhundert erheblich. Projektansatz. Derzeit ist die Rede davon, dass im Laufe des nächsten Jahrzehnts parallele Algorithmen entstehen sollen

Element der allgemeinen Denkkultur. Frage: Wie wird sich die Beherrschung des Konzepts eines parallelen Algorithmus auf das Denken der nächsten Generation auswirken, wozu wird die Umstrukturierung des Bewusstseins „auf parallele Weise“ führen?

Die massive Verbreitung der parallelen Informationsverarbeitung macht es dringend erforderlich, die relevanten Konzepte in die Kategorie der öffentlich zugänglichen und allgemeinkulturellen zu überführen. Die Vertrautheit mit parallelen Algorithmen sollte Teil der Alphabetisierung werden, so wie es im letzten Vierteljahrhundert mit Grundkonzepten der Algorithmentheorie geschehen ist. Dies kann nur auf eine Weise geschehen – durch die Einbeziehung relevanter Themen in den schulischen Informatikunterricht. Das bedeutet, dass wir eine Methodik für die erste Bekanntschaft mit paralleler Programmierung auf High-School-Ebene benötigen.

Historisch gesehen wurde der erste Versuch, das Thema Parallelrechnen in einen schulischen Informatikkurs einzubeziehen, vor zwanzig Jahren unternommen. Vor zwanzig Jahren wurde in einem Kurs mit dem Titel „Algorithmik“ ein „Baudirektor“ beschrieben, der die parallelen Aktionen mehrerer Teams beim Aufbau einer Struktur aus rechteckigen und dreieckigen Blöcken leitete. Darüber hinaus wurde für diesen Performer eine Softwareimplementierung erstellt. Ach! Diese wunderbare methodische Entwicklung war Mitte der 90er Jahre nicht gefragt. Sie war ihrer Zeit fast zwanzig Jahre voraus!

Heutzutage ist die Situation so, dass das Thema Parallelrechnen im Gymnasium vor allem mit dem Thema Supercomputer verknüpft ist. Auf Supercomputer richten die Autoren verschiedener methodischer Entwicklungen die Aufmerksamkeit der Studierenden, auch wenn dies nicht notwendig ist. Es genügt zu sagen, dass der entsprechende Abschnitt in der Zeitschrift „Informatics at School“ „Supercomputer Education at School“ heißt. Diese Situation hat sowohl positive als auch negative Seiten. Zu den positiven Aspekten zählen:

Das Thema Supercomputer ist in der Gesellschaft von Interesse, auch bei Studierenden. Dieses Interesse wiederholt auf moderner Ebene das Interesse, das vor einem halben Jahrhundert großen Maschinen entgegenbrachte – den Supercomputern ihrer Zeit;

Organisatorische Unterstützung durch die Supercomputing-Community. Jeden Sommer veranstaltet die Fakultät für Computermathematik und Kybernetik der Moskauer Staatlichen Universität die Summer Supercomputer Academy. Und jeden Sommer wird im Rahmen dieser Akademie ein Schulkurs für Informatiklehrer organisiert. Die Schulung erfolgt kostenlos. Ausländischen Studierenden wird Wohnraum zu sehr günstigen Konditionen zur Verfügung gestellt. Auf der Konferenz „Russian Supercomputing Days“ im September 2015 wurden eine Schulabteilung und eine Meisterklasse für Informatiklehrer organisiert. Konsequente organisatorische Arbeit führte zur Identifizierung und Bildung einer Gruppe von Lehrern, die an der Förderung dieses Themas interessiert waren;

Die Anwesenheit eines klugen, charismatischen Führers wie Vladimir Valentinovich Voevodin – Doktor der physikalischen und mathematischen Wissenschaften, Professor, korrespondierendes Mitglied der Russischen Akademie der Wissenschaften, stellvertretender Direktor des Forschungsrechenzentrums der Moskauer Staatlichen Universität;

Interesse und Unterstützung (einschließlich Material) seitens der russischen Repräsentanz von Intel und des strategischen Entwicklungsmanagers von Intel, Igor Olegovich Odintsov.

Der Nachteil des „Supercomputer“-Ansatzes besteht darin, dass er den Umfang des parallelen Rechnens einschränkt. Supercomputer selbst sind für Schulkinder in der Regel nicht zugänglich (es sei denn, sie sind in Großstädten auf Exkursionen zu sehen). Die Aufgaben, die sie lösen sollen, sind für Schüler zu komplex und haben in den meisten Fällen keine unmittelbare praktische Bedeutung und sind nicht von praktischem Interesse.

Eine natürliche Erweiterung des Supercomputing-Bereichs ist das Studium der parallelen Programmierung. Zur Ausführung paralleler Programme ist derzeit überhaupt kein Supercomputer erforderlich. Ein Multi-Core-Prozessor oder eine Grafikkarte mit einem Satz Grafikbeschleunigern reicht aus. Und das ist bereits für fast jeden verfügbar. Unter den Arbeiten in dieser Richtung erwähnen wir die Dissertation des Kandidaten M.A. Sokolovskaya über die Methodik, zukünftigen Informatiklehrern die Grundlagen der parallelen Programmierung und die Erfahrung von E.Yu. Kiseleva über die Beherrschung der CUDA-Technologie durch Schulkinder.

Laut dem Autor dieses Artikels verarmt und verkompliziert die Konzentration auf Supercomputer und parallele Programmierung das Thema Parallelrechnen erheblich und lenkt die Schüler von vielen wichtigen und zugänglichen Themen ab. Der Zweck des Themas „parallel

„Computer“ in der High School bedeutet nicht, „echte“ parallele Programmierung zu lehren (das Studium relevanter Sprachkonstrukte, Programmiersprachen und Technologien), sondern die Schüler mit den entsprechenden Konzepten vertraut zu machen und die Merkmale der parallelen Arbeit zu verstehen. Die Welt um uns herum und in uns ist ein komplexes Parallelsystem. Und dieses System selbst bietet viel Material für die Beherrschung der Konzepte und Mechanismen der Parallelität. Hierfür sind keine komplexen künstlichen Strukturen wie MPI- und OpenMP-Technologien erforderlich. Die Schulinformatik soll das „parallele Denken“ fördern. Und dann lassen Sie die Universität Fachwissen, Fertigkeiten und Fähigkeiten in dieses Denken einfließen. In der Schule ist es sinnvoll, sich nicht auf das Kennenlernen von Supercomputern und das Studium der parallelen Programmierung zu konzentrieren, sondern auf die Beherrschung der Mechanismen der „gemeinsamen Aktivität“, die im Leben ständig und weit verbreitet sind. Der Kurs schlägt vor, die folgenden Fragen zu behandeln:

1) Zusammenarbeit mehrerer Testamentsvollstrecker (Ausheben eines Grabens mit mehreren Baggern) und Parallelisierung „innerhalb“ eines Testamentsvollstreckers bei Vorhandensein mehrerer Verarbeitungsgeräte (Lesen und Essen eines Apfels). In der Informatik handelt es sich dabei um einen Mehrmaschinenkomplex und einen Mehrkernprozessor.

2) Arten der Parallelität: echte Parallelität und Pseudoparallelität (ein Prozessor führt mehrere Programme in Teilen aus).

3) Darsteller des gleichen Typs (Bagger) und unterschiedlicher Typen (Panzerbesatzung).

4) Werke gleicher und unterschiedlicher Art.

5) Das Verhältnis von „Ausführenden – Jobs“: 1 Ausführender – 1 Job, 1 Ausführender – N Jobs (pseudoparallele Ausführung oder echte Parallelität bei Vorhandensein mehrerer Verarbeitungsgeräte für verschiedene Jobs), N Ausführender – 1 Job, N Ausführender - N Arbeitsplätze.

6) Koordination der Aktivitäten der Künstler. Genehmigungsarten: nach Arbeitsabschnitten, nach Zeit, nach Tätigkeitsergebnissen, nach Ressourcen.

7) Ressourcen. Ressourcen sind geteilt und nicht geteilt, verbrauchbar und wiederverwendbar. Recycling verbrauchter Ressourcen („Müllabfuhr“ im weiteren Sinne).

8) Aufführung desselben Werks durch einen Künstler und eine Gruppe von Künstlern. Abhängigkeit der Arbeitsgeschwindigkeit von der Anzahl der Darsteller. Abhängigkeit des Arbeitsaufwands von der Anzahl der ausübenden Künstler. Nichtlinearer Anstieg der Arbeitsgeschwindigkeit mit zunehmender Anzahl der Darsteller. Kritischer Pfad. Optimale Anzahl an Darstellern. Optimale Beladung der Darsteller. Optimaler Ablauf. Lastverteilung.

9) Wettbewerb zwischen Künstlern um Ressourcen. Blockierung. Clinch (Deadlock).

10) Mechanismen zur Koordinierung der Aktionen der Darsteller.

11) Pseudoparallele Ausführung von Prozessen auf einem Computer (Aufteilung einer Ressource – des Prozessors) zwischen Executor-Prozessen.

12) Eignung von Algorithmen zur Parallelisierung. Möglicher Grad der Parallelisierung. Die Existenz von Algorithmen, die nicht parallelisiert werden können.

Bitte beachten Sie, dass die obige Liste die private Meinung des Autors des Artikels darstellt und zur Diskussion, Ergänzung und Korrektur offen steht. Darüber hinaus wäre es nach Ansicht des Autors für die „Supercomputer-Community“ sehr nützlich, eine „soziale Ordnung“ für die Schule zu formulieren: Welche Kenntnisse und Fähigkeiten wünscht sie sich von Schulabsolventen? Wie sollte sich ein Absolvent der „Supercomputer World“-Schule von einem heutigen Absolventen unterscheiden? Wenn es einen Auftrag gibt, wird es ein Ergebnis geben. Frisches Beispiel. Am ersten Tag der Russischen Supercomputing-Tage 2015 äußerten zwei Berichte die Idee, dass die Geschwindigkeit moderner Supercomputer nicht von der Leistung der Prozessoren (die im Mittelpunkt der öffentlichen Aufmerksamkeit steht), sondern von der Geschwindigkeit des Arbeitsspeichers bestimmt wird. Dies wird zum Flaschenhals, dessen Durchsatz die Produktivität des Gesamtsystems bestimmt. Infolgedessen testeten die Teilnehmer der Meisterklasse des Lehrers am zweiten Tag der Konferenz ein vom Autor dieses Artikels erfundenes Spiel und demonstrierten das Zusammenspiel von Zentralprozessor, RAM und Cache-Speicher. Die Reihenfolge und Form der Präsentation des Materials ist eine offene Frage.

Der Stoff soll anhand von Beispielen demonstriert werden, die keinen Bezug zur Bedienung eines Computers haben. Darsteller müssen materielle Objekte manipulieren.

Ein möglichst großer Teil des Trainings sollte den Charakter von Geschäftsspielen (Organisations- und Aktivitätsspielen) haben.

Die Erfüllung dieser Anforderungen erleichtert das Verständnis des untersuchten Materials. Dies wird sowohl beim Einsatz dieser Technik im Informatikunterricht in der Schule (auch in der Grundschule!) als auch beim Unterrichten von Erwachsenen (Informatiklehrer und -schüler) nützlich sein. Ein Schulkind, ein Schullehrer, ein Student eines nicht zum Kernfach gehörenden Fachgebiets kann auf der Ebene der Eingewöhnung und des Verständnisses stehen bleiben. Der professionelle Student muss den nächsten Schritt machen und vom Kennenlernen zum Studium dieser Mechanismen auf professioneller Ebene übergehen. Dies ist jedoch bereits ein Schritt über die Methoden der ersten Einarbeitung in das Thema hinaus.

Der Autor dieses Artikels begann 2013 während der Vorbereitung des TRIZformashka-2013-Wettbewerbs mit der Vorbereitung einer Methodik für das Studium des Parallelrechnens und setzte sie in den Folgejahren fort.

(„TRIZformashka“ ist ein interregionaler Internetwettbewerb in Informatik, Systemanalyse und TRIZ. Findet jährlich in der zweiten Märzhälfte statt. Das Alter der Teilnehmer reicht von der ersten Klasse bis zum vierten Jahr. Geographie – von Wladiwostok bis Riga. Der Durchschnitt Die Teilnehmerzahl beträgt 100 Teams (300 Personen), maximal - 202 Teams (mehr als 600 Personen). Wettbewerbswebsite www.trizformashka.ru.) Dann, im Jahr 2013, wurde das Ziel der Arbeit wie folgt formuliert:

1. Bereiten Sie innerhalb von zwei bis drei Jahren eine Beschreibung der Darsteller, eine Reihe von Spielen und Aufgaben im Zusammenhang mit Parallelrechnen vor;

2. Bieten Sie sie (in Teilen, jährlich) den Teilnehmern des Wettbewerbs an;

3. Analysieren Sie ihre Reaktion (bewerten Sie die Anzahl der Löser, ihr Alter, den Erfolg der Lösung, typische Fehler, festgestellte Ungenauigkeiten bei der Formulierung von Problemen usw.). Der TRIZformashka-Wettbewerb erwies sich seitdem als praktisches Werkzeug zum Debuggen von Problemen

ermöglichte es, Reaktionen aus allen Altersgruppen (von der ersten Klasse bis zum vierten Jahr), aus verschiedenen Regionen und von verschiedenen Bildungseinrichtungen zu erhalten.

In den letzten Jahren wurden die folgenden methodischen Werkzeuge und Plattformen für deren Prüfung vorbereitet.

1. Aufgaben zur Parallelität wurden ab 2013 in den Wettbewerb „TRIZformashka“ aufgenommen (ab 2013 trägt der Wettbewerb den Untertitel „Parallel Computing“). Nachfolgend finden Sie eine Liste der Aufgabentypen.

2. Für die Neuauflage des Informatik-Lehrbuchs für die 4. Klasse wurde ein Kapitel zum Thema Parallelität vorbereitet. Das Material wurde in der 3. und 4. Klasse des Lyzeums Nr. 10 in Perm getestet;

3. Das Computerspiel „Tank Crew“ wird seit 2014 im TRIZformashka-Wettbewerb entwickelt und eingesetzt;

4. Es wurde eine Reihe von Spielen entwickelt und getestet, die die folgenden Probleme widerspiegeln:

Koordination der Aktivitäten der Künstler. Verschiedene Zulassungsarten;

Aufführung desselben Werks durch einen Künstler und eine Gruppe von Künstlern. Abhängigkeit der Arbeitsgeschwindigkeit von der Anzahl der Darsteller. Nichtlinearer Anstieg der Arbeitsgeschwindigkeit mit zunehmender Anzahl der Darsteller. Kritischer Pfad. Optimale Anzahl an Darstellern. Optimale Beladung der Darsteller. Optimales Vorgehen;

Ressourcen. Geteilte und nicht geteilte Ressourcen;

Wettbewerb zwischen Künstlern um Ressourcen. Blockierung. Clinch (Deadlock). Folgende Problemtypen wurden vorgeschlagen und getestet:

1. Aufgaben zu Genehmigungsarten. (Welche Koordinationsarten gibt es in der Schulkantine?);

2. Spiel „Panzerbesatzung“. Aufgabe zur Konstruktion eines parallelen Algorithmus;

3. Darsteller „Bau“. Gleichzeitig bauen Arbeitsteams eine Struktur aus horizontalen und vertikalen Balken. Zu den Aufgaben gehören Aufgaben zur Ausführung des angegebenen Algorithmus, zur Entwicklung eines neuen Algorithmus, zur Suche nach Fehlern in einem bestimmten Algorithmus, zur Erforschung von Algorithmen (Vergleich der Bauzeiten mit verschiedenen Algorithmen, Vergleich der Baukosten, Bewertung der Einsparmöglichkeiten durch Umverteilung). Arbeit usw.);

4. Wettbewerb um Ressourcen. Drei kleine Schweinchen kochen jeweils ihr eigenes Mittagessen. Für jedes Ferkel wird angegeben, welche Gerichte es zubereitet, welche Ressourcen (Geräte, Utensilien etc.) es dafür benötigt und wie lange diese Ressourcen genutzt werden sollen. Es ist notwendig, für jedes Ferkel einen Arbeitsplan zu erstellen, wenn es alleine in der Küche kocht, wenn es zu zweit kocht, wenn alle drei gleichzeitig kochen. Die Garzeit sollte minimiert werden;

5. Netzwerkdiagramm. Ein Netzwerkdiagramm wird angegeben. Es ist erforderlich, die Struktur, die gebaut werden soll, (schematisch) darzustellen, zu bestimmen, wie viele Tage der Bau mit einer bestimmten Anzahl von Teams dauern wird und welcher Teil der Arbeit zu einem bestimmten Zeitpunkt abgeschlossen sein wird;

6. Stufenparallele Formen. Planungsarbeiten nach verschiedenen Kriterien. Der Arbeitsauftrag, die Arbeitsproduktivität und die Zahlungsregeln werden angegeben. Es ist notwendig, die Anzahl der Arbeitskräfte zu bestimmen, die erforderlich sind, um die Arbeit in einer bestimmten Zeit abzuschließen, die Arbeitsdauer für eine bestimmte Anzahl von Arbeitskräften zu bestimmen und die Anzahl der Arbeitskräfte zu bestimmen, die zur Minimierung der Arbeitskosten erforderlich sind;

7. Gantt-Diagramme. Der Text beschreibt den Arbeitsplan für den Umbau der Werkstatt: Dauer und gegenseitige Abfolge der Maßnahmen, benötigte Arbeitskräfte. Es ist erforderlich, die Frist für die Fertigstellung des Objekts, die Änderung der Frist aufgrund bestimmter Veränderungen in der Belegschaft und die Liste der an einem bestimmten Datum beteiligten Arbeitnehmer festzulegen.

8. Koordination sich wiederholender Arbeiten. Es soll die Aufgabe gestellt werden, eine Charge von Geräten in kürzester Zeit herzustellen, vorausgesetzt, dass jedes Gerät auf unterschiedlichen Geräten verarbeitet werden muss; es gibt unterschiedliche Mengen an Geräten mit unterschiedlicher Produktivität. Es ist notwendig, die Start- und Betriebszeit jedes Geräts zu planen und Ausfallzeiten zu minimieren.

Heute haben wir folgende Ergebnisse:

1. Für die Untersuchung des Themas „Parallel Computing“ wurde ein Ansatz formuliert: nicht von den Problemen der Informatik, sondern „vom Leben“ auszugehen, sich auf „gemeinsame Aktivität“ zu konzentrieren;

2. Es wurde eine Liste von Themen formuliert, die im ersten Kurs des Parallelrechnens berücksichtigt werden sollen.

3. Einige Problemklassen werden formuliert. Anhand der gesammelten Erfahrungen können Sie beurteilen, welche Art von Problemen erfunden werden sollten;

4. Eine Reihe von Aufgaben der genannten Klassen wurde vorbereitet. Die Probleme wurden in den TRIZformashka-Wettbewerben 2013, 2014, 2015 getestet. und/oder in der Grundschule (in Klassen mit Schülern der dritten und vierten Klasse des Lyzeums Nr. 10 in Perm);

5. Eine Reihe von Planspielen wurde vorbereitet. Die Spiele wurden in Grundschulen und bei verschiedenen Veranstaltungen für Lehrer getestet. Insbesondere wurden sie auf dem Schulkurs der Sommer-Supercomputer-Akademie der Moskauer Staatsuniversität im Jahr 2014, bei einem Meisterkurs für Lehrer bei den Russischen Supercomputer-Tagen 2015 und auf mehreren anderen Konferenzen (einschließlich der IT-Bildung-2015-Konferenz) vorgestellt des APKIT-Vereins) und andere Veranstaltungen für Informatiklehrer;

6. Für ein Lehrbuch der vierten Klasse wurde eine Reihe von Texten zum Thema Parallelität erstellt. Die Texte wurden am Lyzeum Nr. 10 in Perm getestet;

7. Das Computerspiel „Tank Crew“ wurde vorbereitet. Das Spiel wurde bei den TRIZformashka-Wettbewerben 2014 und 2015 getestet;

8. Der TRIZformashka-Wettbewerb hat sich als Testplattform bewährt;

9. Die Aufgabe der „Rochade“ im Prozess der Algorithmisierungslehre wird formuliert: Parallele Programmierung sofort lehren und einen sequentiellen Algorithmus als Teil eines parallelen Algorithmus vorstellen. Es gibt Überlegungen, wie diese Idee umgesetzt werden kann. Die Möglichkeit, diese Ideen auszuprobieren, besteht im laufenden Schuljahr (für Schülerinnen und Schüler der Jahrgangsstufen 4-5);

10. Es besteht das Bedürfnis, der Wunsch und die Möglichkeit, weiterzuarbeiten.

Literatur

1. Algorithmen: Klassen 5-7: Lehr- und Problembuch für die Allgemeinbildung. Bildungseinrichtungen /A.K. Zvonkin, A.G. Kulakov, S.K. Lando, A.L. Semenov, A.Kh. Shen. - M.: Bustard, 1996.

2. Bosova L.L. Parallele Algorithmen in Grund- und weiterführenden Schulen. //Informatik in der Schule. 2015, Nr. 2. S.24-27.

3. Voevodin V.V. Computermathematik und die Struktur von Algorithmen: Vorlesung 10 darüber, warum es schwierig ist, Probleme auf Computersystemen mit paralleler Architektur zu lösen und welche zusätzlichen Informationen Sie wissen müssen. um diese Schwierigkeiten erfolgreich zu überwinden: ein Lehrbuch. M.: MSU-Verlag 2010.

4. Gavrilova I.V. Erster Ausflug in die „Parallelwelt“. //Informatik in der Schule. 2015, Nr. 6. S.16-19.

5. Dieter M.L., Plaksin M.A. Paralleles Rechnen in der Schulinformatik. Spiel "Bau". //Informatik in der Schule: Vergangenheit, Gegenwart und Zukunft.: Materialien des Allrussischen. wissenschaftliche Methode. conf. zum Einsatz von IKT in der Bildung, 6.-7. Februar 2014 /Perm. Zustand National Forschung univ. - Dauerwelle, 2014. - S.258-261.

6. Ivanova N.G., Plaksin M.A., Rusakova O.L. TRIZformashka. //Informatik. N05 Abgerufen am 10.10.2015.

14. Plaksin M.A. Informatik: Lehrbuch für die 4. Klasse: 2 Stunden / M.A.Plaksin, N.G.Ivanova, O.L.Rusakova. - M.: BINOM. Wissenslabor, 2012.

15. Plaksin M.A. Über die Methode der ersten Bekanntschaft mit Parallelrechnen im Gymnasium. //Informatik in der Schule: Vergangenheit, Gegenwart und Zukunft.: Materialien des Allrussischen. wissenschaftliche Methode. conf. zum Einsatz von IKT in der Bildung, 6.-7. Februar 2014 /Perm. Zustand National Forschung univ. - Dauerwelle, 2014. - S.256-258.

16. Plaksin M.A. Eine Reihe von Planspielen zur Einführung des Parallelrechnens in der Grundschule. //Unterricht in Informationstechnologien in der Russischen Föderation: Materialien der Dreizehnten Offenen Allrussischen Konferenz „IT-0education-2015“ (Perm, 14.-15. Mai 2015). Perm State National Research University, - Perm, 2015. S.60-62.

17. Plaksin M.A., Ivanova N.G., Rusakova O.L. Eine Reihe von Aufgaben zum Kennenlernen des Parallelrechnens im TRIZformashka-Wettbewerb. //Lehren von Informationstechnologien in der Russischen Föderation: Materialien der Dreizehnten Offenen Allrussischen Konferenz „IT-Bildung-2015“ (Perm, 14.-15. Mai 2015). Perm State National Research University, - Perm, 2015. S. 232-234.

18. Sokolovskaya M.A. Methodisches System zur Vermittlung der Grundlagen der parallelen Programmierung an zukünftige Informatiklehrer.: Zusammenfassung. dis. ... offen. Päd. Wissenschaften, Krasnojarsk, 2012.

Das Konzept des Parallelrechnens

GRUNDLAGEN DES PARALLELCOMPUTING

Vorlesung Nr. 6

Unter parallele oder gleichzeitige Berechnungen Sie können Problemlösungsprozesse verstehen, bei denen mehrere Rechenoperationen gleichzeitig ausgeführt werden können

Paralleles Rechnen bildet die Grundlage für Supercomputing-Technologien und Hochleistungsrechnen

Parallelverarbeitung

Wenn ein bestimmtes Gerät eine Operation pro Zeiteinheit ausführt, führt es in tausend Einheiten tausend Operationen aus. Wenn wir davon ausgehen, dass es fünf identische unabhängige Geräte gibt, die gleichzeitig arbeiten können, dann kann ein System aus fünf Geräten die gleichen tausend Vorgänge nicht in tausend, sondern in zweihundert Zeiteinheiten ausführen.

Ebenso wird ein System aus N Geräten die gleiche Arbeit in 1000/N Zeiteinheiten ausführen. Ähnliche Analogien lassen sich im Leben finden: Wenn ein Soldat in 10 Stunden einen Garten umgräbt, dann schafft eine Kompanie von fünfzig Soldaten mit gleichen Fähigkeiten, die gleichzeitig arbeiten, die gleiche Arbeit in 12 Minuten – das Prinzip der Parallelität in Aktion!

Der Pionier der Parallelverarbeitung von Datenströmen war der Akademiker A.A. Samarsky, der Anfang der 50er Jahre die notwendigen Berechnungen zur Simulation nuklearer Explosionen durchführte. Samarsky löste dieses Problem, indem er mehrere Dutzend junge Damen mit Rechenmaschinen an Tische setzte. Die jungen Damen übermittelten einander Daten einfach in Worten und trugen die erforderlichen Zahlen auf Rechenmaschinen ein. So wurde insbesondere die Entwicklung der Druckwelle berechnet.

Es gab viel Arbeit, die jungen Damen waren müde und Alexander Andrejewitsch ging zwischen ihnen umher und ermutigte sie. Man könnte sagen, dass dies das erste Parallelsystem war. Obwohl die Berechnungen für die Wasserstoffbombe meisterhaft durchgeführt wurden, war ihre Genauigkeit sehr gering, da nur wenige Knoten im verwendeten Gitter vorhanden waren und die Berechnungszeit zu lang war.

Förderbandverarbeitung

Die Idee der Pipeline-Verarbeitung besteht darin, einzelne Phasen der Ausführung einer allgemeinen Operation zu isolieren, und jede Phase würde nach Abschluss ihrer Arbeit das Ergebnis an die nächste weitergeben und gleichzeitig einen neuen Teil der Eingabedaten empfangen. Durch die Kombination zuvor beabstandeter Operationen erzielen wir einen offensichtlichen Gewinn an Verarbeitungsgeschwindigkeit.

Nehmen wir an, dass es in einer Operation fünf Mikrooperationen gibt, die jeweils in einer Zeiteinheit ausgeführt werden. Wenn ein unteilbares serielles Gerät vorhanden ist, verarbeitet es 100 Argumentpaare in 500 Einheiten. Wenn jede Mikrooperation in eine separate Stufe (oder auch Stufe genannt) eines Fördergeräts unterteilt wird, werden in der fünften Zeiteinheit in verschiedenen Verarbeitungsstufen eines solchen Geräts die ersten fünf Argumentpaare lokalisiert , und der gesamte Satz von einhundert Paaren wird in 5 + 99 = 104 Zeiteinheiten verarbeitet – die Beschleunigung im Vergleich zu einem seriellen Gerät beträgt fast das Fünffache (je nach Anzahl der Förderstufen).

Modelle paralleler Computer (Flynn-Klassifikation)

· „Ein Befehlsstrom – ein Datenstrom“ (SISD – „Single Instruction Single Data“)

Bezieht sich auf die von Neumann-Architektur. SISD-Computer sind gewöhnliche, „traditionelle“ sequentielle Computer, bei denen jeweils nur eine Operation an einem Datenelement (numerisch oder ein anderer Wert) ausgeführt wird. Die meisten modernen Personalcomputer fallen in diese Kategorie.

· „Ein Befehlsstrom – viele Datenströme“ (SIMD – „Single Instruction – Multiple Data“)

SIMD (Einzelbefehl, mehrere Daten)- ein Prinzip des Computerrechnens, das Parallelität auf Datenebene ermöglicht. SIMD-Computer bestehen aus einem Befehlsprozessor (Steuermodul), der als Controller bezeichnet wird, und mehreren Datenverarbeitungsmodulen, die als Verarbeitungselemente bezeichnet werden. Das Steuermodul empfängt, analysiert und führt Befehle aus.

Werden im Befehl Daten gefunden, sendet der Controller einen Befehl an alle Prozessorelemente und dieser Befehl wird auf mehreren oder allen Prozessorelementen ausgeführt. Jedes Verarbeitungselement verfügt über einen eigenen Speicher zum Speichern von Daten. Einer der Vorteile dieser Architektur besteht darin, dass in diesem Fall die Berechnungslogik effizienter implementiert wird. SIMD-Prozessoren werden auch Vektorprozessoren genannt.

· „Viele Befehlsströme – ein Datenstrom“ (MISD – „Multiple Instruction – Single Data“)

Es gibt praktisch keine Computer dieser Klasse und es ist schwierig, ein Beispiel für ihre erfolgreiche Implementierung zu nennen. Einer der wenigen ist ein systolisches Array von Prozessoren, bei dem sich die Prozessoren an den Knoten eines regelmäßigen Gitters befinden, dessen Kanten durch Verbindungen zwischen Prozessoren übernommen werden. Alle Prozessorelemente werden von einem gemeinsamen Taktgenerator gesteuert. In jedem Betriebszyklus empfängt jedes Verarbeitungselement Daten von seinen Nachbarn, führt einen Befehl aus und überträgt das Ergebnis an seine Nachbarn.

Arrays von PEs mit direkten Verbindungen zwischen benachbarten PEs werden aufgerufen systolisch. Solche Arrays sind äußerst effizient, aber jedes von ihnen konzentriert sich auf die Lösung einer sehr engen Klasse von Problemen. Betrachten wir, wie Sie ein systolisches Array erstellen können, um ein bestimmtes Problem zu lösen. Angenommen, Sie möchten ein Gerät zur Berechnung einer Matrix erstellen D=C+AB, Wo

Hier sind alle Matrizen Bandmatrizen der Ordnung N. Matrix A hat eine Diagonale über und zwei Diagonalen unter der Hauptdiagonale; Matrix B- eine Diagonale unter und zwei Diagonalen über der Hauptdiagonale; Matrix C drei Diagonalen über und unter der Hauptdiagonale. Lassen Sie jedes PE in der Lage sein, eine Skalaroperation auszuführen c+ab und gleichzeitig Daten übertragen. Jedes PE muss daher drei Eingänge haben: a, b, c und drei Ausgänge: a, b, c. Eingabe ( In) und Wochenenden ( aus) Die Daten sind durch Beziehungen miteinander verbunden

a out = a in , b out = b in , c out = c in + a in *b in ;

Wenn zum Zeitpunkt der Operation einige Daten nicht empfangen wurden, gehen wir davon aus, dass sie als Nullen definiert sind. Nehmen wir weiter an, dass sich alle PEs auf einer Ebene befinden und jedes von ihnen mit sechs benachbarten verbunden ist. Wenn Sie die Daten wie in der Abbildung dargestellt anordnen, berechnet die Schaltung die Matrix D.

Das Array arbeitet in Taktzyklen. Während jedes Taktzyklus werden alle Daten in den durch die Pfeile angegebenen Richtungen zu benachbarten Knoten verschoben.

Die Abbildung zeigt den Zustand des systolischen Arrays zu einem bestimmten Zeitpunkt. Im nächsten Taktzyklus werden alle Daten zu einem Knoten und Elementen verschoben a11, b11, c11 wird in einem PE landen, das sich am Schnittpunkt der gestrichelten Linien befindet. Daher wird der Ausdruck ausgewertet c11+a11b11.Zur gleichen Zeit, Daten a12 Und b21 wird dem PE sehr nahe kommen, der sich an der Spitze der systolischen Reihe befindet.

Im nächsten Taktzyklus bewegen sich alle Daten erneut um einen Knoten in Richtung der Pfeile und erscheinen im oberen PE a12 Und b21 und das Ergebnis der vorherigen Operation des unten stehenden PE, d.h. c11+a11b11. Daher wird der Ausdruck ausgewertet c11+a11b11+a12b21. Das ist ein Element d11 Matrizen D.

Wenn wir die schrittweise Untersuchung des Prozesses fortsetzen, können wir überprüfen, dass an den PE-Ausgängen, die der oberen Grenze des systolischen Arrays entsprechen, nach drei Schritten Matrixelemente periodisch ausgegeben werden D, während an jedem Ausgang Elemente derselben Diagonale erscheinen. In ungefähr 3n Zyklen wird die Berechnung der gesamten Matrix abgeschlossen D. In diesem Fall ist die Belastung jeder systolischen Zelle asymptotisch gleich 1/3 .

„Viele Befehlsströme – viele Datenströme“ (MIMD – „Multiple Instruction – Multiple Data“)

Diese Kategorie von Computerarchitekturen ist die reichhaltigste, wenn Denken Sie an Beispiele für erfolgreiche Implementierungen. Es umfasst symmetrisch parallele Rechensysteme, Arbeitsplätze mit mehreren Prozessoren, Workstation-Cluster usw.

Die enorme Leistungsfähigkeit von Parallelrechnern und Supercomputern wird durch die Schwierigkeiten bei deren Nutzung mehr als ausgeglichen. Beginnen wir mit den einfachsten Dingen. Sie haben ein Programm und Zugriff auf beispielsweise einen Computer mit 256 Prozessoren. Was erwarten Sie? Ja, es ist klar: Sie erwarten völlig berechtigt, dass das Programm 256-mal schneller ausgeführt wird als auf einem einzelnen Prozessor. Aber genau das wird höchstwahrscheinlich nicht passieren.

Paralleles Rechnen ist eine Methode zur Organisation des Computerrechnens, bei der Programme als eine Reihe interagierender, gleichzeitig laufender Rechenprozesse entwickelt werden.

Es gibt verschiedene Möglichkeiten, paralleles Rechnen zu implementieren: Jeder Rechenprozess kann als Betriebssystemprozess implementiert werden, oder Rechenprozesse können eine Sammlung von Ausführungsthreads innerhalb eines einzelnen Prozesses sein. Ein Thread (oder genauer gesagt ein Ausführungsthread) ist die kleinste Verarbeitungseinheit, deren Ausführung vom Betriebssystemkernel zugewiesen werden kann. Innerhalb desselben Prozesses können mehrere Ausführungsthreads vorhanden sein und Ressourcen wie Speicher gemeinsam nutzen, während Prozesse diese Ressourcen nicht gemeinsam nutzen. Parallele Programme können physisch entweder sequentiell auf einem einzelnen Prozessor ausgeführt werden – wobei sich die Schritte jedes Rechenprozesses abwechseln – oder parallel – indem jedem Rechenprozess ein oder mehrere Prozessoren (in der Nähe oder in einem Computernetzwerk verteilt) zugewiesen werden.

Die größte Herausforderung beim Entwurf paralleler Programme besteht darin, die korrekte Reihenfolge der Interaktionen zwischen verschiedenen Rechenprozessen sowie die gemeinsame Nutzung von Ressourcen wie RAM oder Peripheriegeräten sicherzustellen.

In einigen parallelen Programmiersystemen bleibt die Datenübertragung zwischen Komponenten dem Programmierer verborgen, während sie in anderen explizit angegeben werden muss. Explizite Interaktionen können in zwei Typen unterteilt werden:

1. Interaktion über Shared Memory (z. B. in Java oder C#). Diese Art der parallelen Programmierung erfordert normalerweise eine Form der Steuerungserfassung, um die Threads untereinander zu koordinieren.

2. Interaktion durch Nachrichtenübermittlung. Nachrichten können asynchron oder über die Rendezvous-Methode ausgetauscht werden, bei der der Absender bis zur Zustellung seiner Nachricht blockiert wird. Die asynchrone Nachrichtenübertragung kann zuverlässig (mit Zustellungsgarantie) oder unzuverlässig sein. Parallele Systeme zur Nachrichtenübermittlung sind oft einfacher zu verstehen als Shared-Memory-Systeme und gelten im Allgemeinen als überlegene Methode der parallelen Programmierung. Messaging kann effizient auf symmetrischen Multiprozessoren mit oder ohne gemeinsam genutztem kohärentem Speicher implementiert werden.

Es gibt eine ganze Reihe verschiedener paralleler Programmiertechnologien. Darüber hinaus unterscheiden sich diese Technologien weniger in den Programmiersprachen als vielmehr in den architektonischen Ansätzen zum Aufbau paralleler Systeme. Bei einigen Technologien geht es beispielsweise um den Aufbau paralleler Lösungen auf Basis mehrerer Computer (sowohl gleicher als auch unterschiedlicher Art), bei anderen geht es um die Arbeit auf einer Maschine mit mehreren Prozessorkernen. Derzeit sind die wichtigsten Softwaretools zum Erstellen paralleler Programme:

1. OpenMP wird in parallelen Systemen mit gemeinsam genutztem Speicher verwendet (z. B. moderne Computer mit Mehrkernprozessoren);

2. MPI (Message Passing Interface) ist ein Standard für Nachrichtenübertragungssysteme zwischen parallel ausgeführten Prozessen, der bei der Entwicklung von Programmen für Supercomputer verwendet wird;

3. POSIX-Threads ist ein Standard für die Implementierung von Ausführungsthreads;

4. Das Windows-Betriebssystem verfügt über integrierte Unterstützung für Multithread-Anwendungen für C++ auf API-Ebene;

5. PVM (Parallel Virtual Machine) ermöglicht es Ihnen, heterogene Computer, die über ein Netzwerk verbunden sind, zu einer gemeinsamen Computerressource zu kombinieren.

Systeme, die auf mehreren Computern basieren, werden als Systeme für verteiltes Rechnen klassifiziert. Solche Lösungen werden schon seit geraumer Zeit eingesetzt. Das auffälligste Beispiel für verteilte Computertechnologie ist MPI (Message Passing Interface). MPI ist der gebräuchlichste Datefür die parallele Programmierung; es gibt Implementierungen für eine Vielzahl von Computerplattformen. MPI bietet dem Programmierer einen einheitlichen Mechanismus für die Interaktion von Zweigen innerhalb einer parallelen Anwendung, unabhängig von der Maschinenarchitektur (Einprozessor/Multiprozessor mit gemeinsam genutztem/separatem Speicher) und der relativen Position der Zweige (auf demselben Prozessor oder auf verschiedenen).

Da MPI in erster Linie für Systeme mit gemeinsam genutztem Speicher gedacht ist, ist es äußerst schwierig und unpraktisch, damit einen parallelen Prozess in einem System mit gemeinsam genutztem Speicher zu organisieren. Es hindert Sie jedoch nichts daran, MPI-Lösungen für eine Maschine zu entwickeln.

Die Entwicklung paralleler Programmiersysteme für die Arbeit an einer Maschine begann jedoch erst vor relativ kurzer Zeit. Natürlich handelt es sich hierbei nicht um grundsätzlich neue Ideen, doch erst mit dem Aufkommen von Multicore-Systemen auf dem Markt für Personalcomputer und Mobilgeräte erfuhren Technologien wie OpenMP eine bedeutende Entwicklung.

Es ist sehr wichtig, dass die parallele Programmiertechnologie die Fähigkeit unterstützt, ein Programm schrittweise parallel zu machen. Natürlich sollte ein ideales Parallelprogramm sofort parallel geschrieben werden, vielleicht in einer funktionalen Sprache, in der das Problem der Parallelisierung überhaupt nicht auftritt. In der Praxis ist es jedoch notwendig, die geschriebene sequentielle schrittweise zu parallelisieren, um die Leistung zu steigern. In diesem Fall ist die OpenMP-Technologie eine sehr gute Wahl. Damit können Sie die Stellen in der Anwendung auswählen, die am meisten einer Parallelisierung bedürfen, und sie zunächst parallelisieren. Der parallele Versionsentwicklungsprozess kann unterbrochen, Zwischenversionen des Programms freigegeben und bei Bedarf wieder aufgenommen werden. Aus diesem Grund erfreut sich insbesondere die OpenMP-Technologie großer Beliebtheit.

OpenMP (Open Multi-Processing) ist eine Reihe von Compileranweisungen, Bibliotheksprozeduren und Umgebungsvariablen, die für die Programmierung von Multithread-Anwendungen auf Multiprozessorsystemen mit gemeinsam genutztem Speicher konzipiert sind.

Die OpenMP-Spezifikation wird von mehreren großen Hardware- und Softwareherstellern entwickelt, deren Arbeit von einer gemeinnützigen Organisation namens OpenMP Architecture Review Board (ARB) reguliert wird.

Die erste Version erschien 1997 und war für die Fortran-Sprache gedacht. Die C/C++-Version wurde 1998 entwickelt. Im Jahr 2008 wurde OpenMP 3.0 veröffentlicht. Die OpenMP-Schnittstelle hat sich zu einer der beliebtesten parallelen Programmiertechnologien entwickelt. OpenMP wird sowohl bei der Programmierung von Supercomputersystemen mit einer großen Anzahl von Prozessoren als auch in Desktop-Benutzersystemen oder beispielsweise in der Xbox 360 erfolgreich eingesetzt.

OpenMP implementiert paralleles Rechnen mithilfe von Multithreading, bei dem ein „Master“-Thread eine Reihe von Slave-Threads erstellt und die Aufgabe auf diese verteilt wird. Es wird davon ausgegangen, dass die Threads parallel auf einer Maschine mit mehreren Prozessoren ausgeführt werden (die Anzahl der Prozessoren muss nicht größer oder gleich der Anzahl der Threads sein).

Von Threads parallel ausgeführte Aufgaben sowie die zur Ausführung dieser Aufgaben erforderlichen Daten werden mithilfe spezieller Präprozessordirektiven der entsprechenden Sprache – Pragmas – beschrieben. Beispielsweise wird einem Abschnitt des Fortran-Codes, der von mehreren Threads ausgeführt werden muss, von denen jeder über eine eigene Kopie der Variablen N verfügt, die folgende Anweisung vorangestellt: !$OMP PARALLEL PRIVATE(N)

Die Anzahl der erstellten Threads kann sowohl vom Programm selbst durch den Aufruf von Bibliotheksprozeduren als auch extern über Umgebungsvariablen reguliert werden.

Die Schlüsselelemente von OpenMP sind

1. Konstrukte zum Erstellen von Threads (parallele Direktive);

2. Konstrukte zum Verteilen der Arbeit zwischen Threads (DO/for- und section-Anweisungen);

3. Konstrukte zur Verwaltung der Arbeit mit Daten (gemeinsame und private Ausdrücke zur Definition der Speicherklasse von Variablen);

4. Konstrukte zum Synchronisieren von Threads (kritische, atomare und Barriere-Anweisungen);

5. Prozeduren der Laufzeitunterstützungsbibliothek (z. B. omp_get_thread_num);

6. Umgebungsvariablen (z. B. OMP_NUM_THREADS).

OpenMP verwendet ein Branch-Merge-Parallelausführungsmodell. Ein OpenMP-Programm beginnt als einzelner Ausführungsthread, der als Anfangsthread bezeichnet wird. Wenn ein Thread auf ein paralleles Konstrukt trifft, erstellt er eine neue Thread-Gruppe, die aus sich selbst und einer Reihe zusätzlicher Threads besteht, und wird zum Master der neuen Gruppe. Alle Mitglieder der neuen Gruppe (einschließlich der Hauptgruppe) führen Code innerhalb des Parallelkonstrukts aus. Am Ende der Parallelstruktur befindet sich eine implizite Barriere. Nach der parallelen Konstruktion führt nur der Hauptthread weiterhin Benutzercode aus. Eine parallele Region kann mit anderen parallelen Regionen verschachtelt werden, wobei jeder Thread der ursprünglichen Region zum Haupt-Thread für seine Thread-Gruppe wird. Verschachtelte Regionen können wiederum Regionen auf einer tieferen Verschachtelungsebene umfassen.

Die Anzahl der parallel laufenden Threads in einer Gruppe kann auf verschiedene Weise gesteuert werden. Eine davon ist die Verwendung der Umgebungsvariablen OMP_NUM_THREADS. Eine andere Möglichkeit besteht darin, die Prozedur omp_set_num_threads() aufzurufen. Eine andere Möglichkeit besteht darin, den Ausdruck num_threads in Kombination mit der parallelen Direktive zu verwenden.

In diesem Programm werden zwei Arrays (a und b) von zehn Threads parallel hinzugefügt.

#enthalten

#enthalten

int main(int argc, char *argv)

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

omp_set_dynamic(0); // verhindern, dass die OpenMP-Bibliothek die Anzahl der Threads während der Ausführung ändert

omp_set_num_threads(10); // setze die Anzahl der Threads auf 10

// die Arrays initialisieren

für (I = 0; I< N; i++)

// Berechne die Summe der Arrays

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

für (I = 0; I< N; i++)

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

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

Dieses Programm kann mit gcc-4.4 und höher mit dem Flag –fopenmp kompiliert werden. Wenn Sie die Einbindung der Header-Datei omp.h sowie Aufrufe der OpenMP-Konfigurationsfunktion entfernen, kann das Programm natürlich auf jedem C-Compiler als reguläres sequentielles Programm kompiliert werden.

OpenMP wird von vielen modernen Compilern unterstützt:

1. Sun Studio-Compiler unterstützen die offizielle Spezifikation – OpenMP 2.5 – mit verbesserter Leistung unter Solaris OS; Linux-Unterstützung ist für die nächste Version geplant.

2. Visual C++ 2005 und höher unterstützt OpenMP in den Editionen Professional und Team System.

3. GCC 4.2 unterstützt OpenMP und einige Distributionen (wie Fedora Core 5 gcc) haben Unterstützung in ihren Versionen von GCC 4.1 integriert.

4. Intel C++ Compiler, einschließlich einer Version von Intel Cluster OpenMP für die Programmierung in verteilten Speichersystemen.

Schnittstelle zur Nachrichtenübermittlung (MPI Message Passing Interface) ist eine Programmierschnittstelle (API) für die Informationsübertragung, die den Austausch von Nachrichten zwischen Prozessen ermöglicht, die dieselbe Aufgabe ausführen. Entwickelt von William Group, Evin Lusk und anderen.

MPI ist der gebräuchlichste Datefür die parallele Programmierung und es gibt Implementierungen für eine Vielzahl von Computerplattformen. Wird bei der Entwicklung von Programmen für Cluster und Supercomputer verwendet. Das Hauptkommunikationsmittel zwischen Prozessen in MPI ist die gegenseitige Weitergabe von Nachrichten. Die MPI-Standardisierung wird vom MPI-Forum durchgeführt. Der MPI-Standard beschreibt eine Message-Passing-Schnittstelle, die sowohl auf der Plattform als auch in Benutzeranwendungen unterstützt werden muss. Derzeit gibt es eine große Anzahl kostenloser und kommerzieller Implementierungen von MPI. Es gibt Implementierungen für die Sprachen Fortran 77/90, C und C++.

MPI konzentriert sich hauptsächlich auf Systeme mit verteiltem Speicher, also wenn die Datenübertragungskosten hoch sind, während OpenMP sich auf Systeme mit gemeinsam genutztem Speicher (Mehrkernkerne mit gemeinsam genutztem ESH) konzentriert. Beide Technologien können gemeinsam eingesetzt werden, um Multicore-Systeme in einem Cluster optimal zu nutzen.

Die erste Version von MPI wurde 1993–1994 entwickelt und MPI 1 wurde 1994 veröffentlicht.

Die meisten modernen MPI-Implementierungen unterstützen Version 1.1. Der MPI-Standard Version 2.0 wird von den meisten modernen Implementierungen unterstützt, einige Funktionen sind jedoch möglicherweise nicht vollständig implementiert.

Senden und Empfangen von Nachrichten zwischen separaten Prozessen;

kollektive Interaktionen von Prozessen;

Interaktionen in Prozessgruppen;

Implementierung von Prozesstopologien;

dynamische Prozessgenerierung und Prozessmanagement;

Einwegkommunikation (Get/Put);

paralleler Ein- und Ausgang;

erweiterte kollektive Operationen (Prozesse können kollektive Operationen nicht nur innerhalb eines Kommunikators, sondern auch innerhalb mehrerer Kommunikatoren durchführen).

Version MPI 2.1 wurde Anfang September 2008 veröffentlicht.

Der grundlegende Kommunikationsmechanismus zwischen MPI-Prozessen ist das Senden und Empfangen von Nachrichten. Die Nachricht enthält übermittelte Daten und Informationen, die es der empfangenden Partei ermöglichen, diese gezielt zu empfangen:

1. Absender – Rang (Nummer in der Gruppe) des Absenders der Nachricht;

2. Empfänger – Rang des Empfängers;

3. signieren – kann verwendet werden, um verschiedene Arten von Nachrichten zu trennen;

4. Kommunikator – Prozessgruppencode.

Empfangs- und Übertragungsvorgänge können blockierend oder nicht blockierend sein. Für nicht blockierende Vorgänge werden Funktionen definiert, um die Bereitschaft zu prüfen und auf den Abschluss des Vorgangs zu warten.

Eine weitere Kommunikationsmethode ist der Remote Memory Access (RMA), der es ermöglicht, den Speicherbereich eines Remote-Prozesses zu lesen und zu ändern. Ein lokaler Prozess kann den Speicherbereich eines Remote-Prozesses (innerhalb eines durch die Prozesse festgelegten Fensters) in seinen Speicher und zurück übertragen und außerdem an den Remote-Prozess übertragene Daten mit in seinem Speicher verfügbaren Daten kombinieren (z. B. durch Summieren). ). Alle Remote-Speicherzugriffe sind nicht blockierend; blockierende Synchronisationsfunktionen müssen jedoch vor und nach ihrer Ausführung aufgerufen werden.

Nachfolgend finden Sie ein Beispielprogramm zur Berechnung von π in C mithilfe von MPI:

// Verbinden der notwendigen Header

#enthalten

#enthalten

// MPI-Header-Datei einbinden

#include „mpi.h“

// Funktion für Zwischenberechnungen

doppeltes f(doppeltes a)

return (4.0 / (1.0+ a*a));

// Hauptfunktion des Programms

int main(int argc, char **argv)

// Variablen deklarieren

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

doppeltes PI25DT = 3,141592653589793238462643;

double mypi, pi, h, sum, x;

double startwtime = 0.0, endwtime;

char Prozessorname;

// Initialisieren Sie das MPI-Subsystem

MPI_Init(&argc, &argv);

// Ermitteln Sie die Größe des Kommunikators MPI_COMM_WORLD

// (Gesamtzahl der Prozesse innerhalb der Aufgabe)

MPI_Comm_size(MPI_COMM_WORLD,&numprocs);

// Die Nummer des aktuellen Prozesses abrufen

// Kommunikator MPI_COMM_WORLD

MPI_Comm_rank(MPI_COMM_WORLD,&myid);

MPI_Get_processor_name(processor_name,&namelen);

// Zeigt die Thread-Nummer im gemeinsam genutzten Pool an

fprintf(stdout, „Prozess %d von %d ist auf %s\n“, myid,numprocs,processor_name);

// Anzahl der Intervalle

fprintf(stdout, „Geben Sie die Anzahl der Intervalle ein: (0 beendet)“);

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

fprintf(stdout, „Keine Zahl eingegeben; wird beendet\n“);

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

h = 1,0 / (doppelt) n;

// Berechne den dem Prozess zugewiesenen Punkt

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

x = h * ((doppelt)I – 0,5);

// Ergebnisse aller Prozesse zurücksetzen und hinzufügen

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

// Wenn dies der Hauptprozess ist, wird das Ergebnis ausgegeben

printf(“PI ist ungefähr %.16f, Fehler ist %.16f\n“, pi, fabs(pi – PI25DT));

endwtime = MPI_Wtime();

printf(“Wanduhrzeit = %f\n”, endwtime-startwtime);

// Geben Sie das MPI-Subsystem frei

Die heute am häufigsten verwendeten MPI-Implementierungen sind:

MPICH ist die am weitesten verbreitete kostenlose Implementierung und läuft auf UNIX-Systemen und Windows NT

LAM/MPI ist eine weitere kostenlose Implementierung von MPI. Unterstützt heterogene Konfigurationen, LAM (http://www.lam-mpi.org) unterstützt heterogene Konfigurationen, Globus-Paket und erfüllt IMPI (Interoperable MPI).

Verschiedene Kommunikationssysteme werden unterstützt (einschließlich Myrinet).

WMPI – MPI-Implementierung für Windows

MPI/PRO für Windows NT – kommerzielle Implementierung für Windows NT

Intel MPI – kommerzielle Implementierung für Windows/Linux

Microsoft MPI ist im Compute Cluster Pack SDK enthalten. Basiert auf MPICH2, umfasst jedoch zusätzliche Jobverwaltungsfunktionen. Die MPI-2-Spezifikation wird unterstützt.

HP-MPI – kommerzielle Implementierung von HP

SGI MPT – kostenpflichtige MPI-Bibliothek von SGI

Mvapich – kostenlose MPI-Implementierung für Infiniband

Open MPI – freie Implementierung von MPI, Nachfolger von LAM/MPI

Oracle HPC ClusterTools – kostenlose Implementierung für Solaris SPARC/x86 und Linux basierend auf Open MPI

MPJ – MPI für Java

POSIX-Threads- POSIX-Standard zur Implementierung von Ausführungsthreads und zur Definition einer API für deren Erstellung und Verwaltung.

Bibliotheken, die diesen Standard (und die Funktionen dieses Standards) implementieren, werden normalerweise Pthreads genannt (den Funktionen wird „pthread_“ vorangestellt). Obwohl die bekanntesten Optionen für Unix-ähnliche Betriebssysteme wie Linux oder Solaris gelten, gibt es auch eine Implementierung für Microsoft Windows (Pthreads-w32).

Pthreads definiert eine Reihe von Typen und Funktionen in der Programmiersprache C. Die Header-Datei ist pthread.h.

Datentypen:

1. pthread_t – Thread-Deskriptor;

2. pthread_attr_t – Liste der Thread-Attribute.

Thread-Kontrollfunktionen:

1. pthread_create() – Thread erstellen;

2. pthread_exit() – Beendigung des Threads (muss bei Beendigung von der Thread-Funktion aufgerufen werden);

3. pthread_cancel() – Thread abbrechen;

4. pthread_join() – blockiert die Ausführung eines Threads, bis ein anderer im Funktionsaufruf angegebener Thread beendet wird;

5. pthread_detach() – die vom Thread belegten Ressourcen freigeben (wenn der Thread läuft, werden die Ressourcen nach seiner Fertigstellung freigegeben);

6. pthread_attr_init() – Thread-Attributstruktur initialisieren;

7. pthread_attr_setdetachstate() – zeigt dem System an, dass es nach Beendigung des Threads die vom Thread belegten Ressourcen automatisch freigeben kann;

8. pthread_attr_destroy() – Speicher aus der Thread-Attributstruktur freigeben (den Deskriptor zerstören).

Thread-Synchronisationsfunktionen:

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().

Beispiel für die Verwendung von Threads in C:

#enthalten

#enthalten

#enthalten

#enthalten

static void wait_thread(void)

time_t start_time = time(NULL);

while (time(NULL) == start_time)

/* tut nichts außer CPU-Slices bis zu einer Sekunde lang zu kauen. */

static void *thread_func(void *vptr_args)

für (I = 0; I< 20; i++)

fputs(“b\n”, stderr);

pthread_t-Thread;

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

return EXIT_FAILURE;

für (I = 0; I< 20; i++)

if (pthread_join(thread, NULL) != 0)

return EXIT_FAILURE;

return EXIT_SUCCESS;

Das vorgestellte Programm verwendet zwei Threads, die Nachrichten an die Konsole ausgeben, einen, der „a“ ausgibt, der zweite – „b“. Die Nachrichtenausgabe ist aufgrund des Ausführungswechsels zwischen Threads oder der gleichzeitigen Ausführung auf Multiprozessorsystemen gemischt.

Das C-Programm erstellt einen neuen Thread zum Drucken von „b“ und der Hauptthread druckt „a“. Der Hauptthread wartet (nach dem Drucken von „aaaaa…“) auf den Abschluss des untergeordneten Threads.

Kontrollfragen

1. Was ist ein Parallelprogramm?
2. Was ist der Unterschied zwischen einem Prozess und einem Ausführungsthread?
3. Kann ein Programm 5 Threads erstellen, wenn es auf einem Quad-Core-Prozessor läuft?
4. Was sind die Merkmale von Shared-Memory-Parallelprogrammen?
5. Welche Softwaretools gibt es für die Entwicklung paralleler Programme?
6. Warum hat sich OpenMP bei der Erstellung von Programmen für PCs durchgesetzt und nicht beispielsweise MPI?