Hier finden Sie ein Unterrichtsbeispiel zu Sortiernetzwerken:
Die folgenden Videos zeigen weitere Beispiele zu Sortiernetzwerken:
Nachdem Computer immer mehr zu unserem Alltag gehören und die von uns genutzte Datenmenge beständig ansteigt, möchten wir natürlich, dass Computer all diese Daten so schnell wie möglich verarbeiten. Die Geschwindigkeit eines Computers kann zum einen mithilfe von Programmen beschleunigt werden, die weniger rechnerische Schritte anwenden (wie in den Lektionen zu Sortier- und Suchalgorithmen aufgezeigt). Zum anderen können Probleme schneller gelöst werden, wenn mehrere Computer gleichzeitig an verschiedenen Teilen derselben Aufgabe arbeiten, was in dieser Unterrichtseinheit behandelt wird. Leider ist es nicht immer ganz so einfach, Arbeitsgänge zwischen verschiedenen Prozessoren aufzuteilen!
Sortiernetzwerke werden dazu eingesetzt, Werte durch Vergleichen von Wertepaaren in aufsteigender Reihenfolge zu ordnen. Beispielsweise wendet das von uns in dieser Unterrichtseinheit herangezogene Sortiernetzwerk mit sechs Zahlen insgesamt 12 Vergleiche an, um die Zahlen zu ordnen, es können jedoch bis zu drei Vergleiche gleichzeitig ausgeführt werden. Das bedeutet, dass der Zeitaufwand derselbe ist, wie wenn ein Computer allein nur fünf Vergleichsschritte ausführen würde. Das ist so ähnlich, wie wenn wir vier Seiten an Text abtippen müssten: Wenn vier Personen gleichzeitig an vier Computern tippen, kann die Aufgabe wahrscheinlich viermal so schnell erledigt werden, als wenn nur eine Person daran arbeitet.
Mithilfe eines parallelen Sortiernetzwerks lässt sich ermitteln, wie viel schneller wir Werte in eine Reihenfolge ordnen können, wenn Vergleiche simultan angestellt werden können. Das in diesen Lektionen hauptsächlich verwendete sechswegige Parallelnetzwerk ordnet eine Liste an Werten zweimal so schnell wie ein System, das nur jeweils einen Vergleich ausführen kann.
Es können jedoch nicht alle Aufgabenstellungen durch parallele Verarbeitung schneller abgeschlossen werden. Stellen wir uns als Analogie eine Person vor, die einen zehn Meter langen Graben gräbt. Wenn zehn Personen gleichzeitig jeweils einen Meter des Grabens graben würden, würde die Aufgabe sehr viel schneller abgeschlossen werden. Allerdings könnte dieselbe Strategie nicht auf einen zehn Meter tiefen Graben angewendet werden, da der zweite Meter nicht zugänglich ist, bevor der erste Meter gegraben wurde.
Und was das Abtippen unseres vierseitigen Dokuments anbelangt – wenn uns 400 Personen dabei helfen, verbringen wir vermutlich so viel Zeit damit, die ganze Arbeit zu koordinieren, dass die Aufgabe nicht besonders schnell abgeschlossen würde! Informatiker suchen nach wie vor aktiv nach den besten Möglichkeiten, Aufgabenstellungen so zu zerlegen, dass sie von Computern parallel verarbeitet werden können. Dabei ermitteln sie, welche Teile der Verarbeitung gleichzeitig vorgenommen werden können und welche Teile nacheinander verarbeitet werden müssen.
In diesen Lektionen demonstrieren wir anhand einer unterhaltsamen Teamaktivität eine Methode zum parallelen Sortieren. Die Aktivität kann auf Papier ausgeführt werden, wir möchten sie Schülern jedoch gerne in großem Maßstab näherbringen, indem sie im Netzwerk von Knotenpunkt zu Knotenpunkt rennen.
Hier soll noch angemerkt werden, dass dies zwar als „Netzwerk“ bezeichnet wird, es jedoch nur eines von vielen verschiedenen Netzwerktypen ist, denen wir in der Informatik begegnen. Eine verbreitete Art eines „Netzwerks“ ist ein Kommunikationsnetzwerk, wie beispielsweise die von mobilen Telefonen genutzten Telekommunikationsnetze, und natürlich das Internet! Zudem gibt es Netzwerke zur Darstellung von Dingen wir Straßenkarten und Flugrouten. Es ist wichtig, zu verstehen, dass das Sortiernetzwerk in dieser Aktivität nicht eines dieser Netzwerktypen ist. Es wird Komparatornetzwerk genannt, da es sich um ein Netzwerk handelt, bei dem jeder Knotenpunkt zwei Werte vergleicht und nicht verschiedene Geräte (wie Telefone und Computer) miteinander verbindet.
Um das Sortiernetzwerk einzusetzen, müssen die Schüler einem einfachen Algorithmus folgen und sollten erkennen, dass sie diesen Algorithmus präzise befolgen müssen, genau wie es ein Computer tun würde, damit sie kein falsches Ergebnis oder vielleicht sogar gar kein Ergebnis zu erhalten! Dabei müssen die Schüler gemeinschaftlich arbeiten, um sicherzustellen, dass jeder Teil des Algorithmus koordiniert wird. Wenn sich nämlich nur eine Person zu weit vorbewegt, ohne an den vorgesehenen Knotenpunkten anzuhalten, schlägt der Prozess für alle fehl. Es gibt auch viele Algorithmen, die dazu eingesetzt werden, überaus effiziente Sortiernetzwerke verschiedener Größen zu konstruieren, und Informatiker sind eingehend mit diesen Algorithmen befasst, um zu versuchen, sogar noch bessere zu erstellen. Derartige Netzwerke können jedoch äußerst komplex sein. Wenn Schüler ihre eigenen Netzwerke konstruieren, geschieht dies daher auf vereinfachte Weise.
Diese Aktivität unterstützt in hohem Maße das Erlernen des Vorher-Nachher-Konzepts (Ordnen) für Zahlen, einschließlich der Bestimmung der Beziehung zwischen zwei Zahlen (größer als, kleiner als).
Es ist oftmals kostengünstiger und zeitlich vorteilhafter, etliche langsame Prozessoren an einer rechnerischen Problemstellung arbeiten zu lassen, als einen sehr schnellen. Für Unternehmen mit massiven Cloud-Servern ist es oft wirtschaftlicher, viele langsamere aber günstigere Geräte zu haben, als wenige teure. Dazu ist es allerdings erforderlich, eine rechnerische Aufgabenstellung über mehrere Prozessoren verteilen zu können. Bei manchen rechnerischen Problemen ist dies ein Leichtes, bei anderen wiederum unmöglich. Die von uns hier betrachtete Aufgabenstellung ist zwischen diesen beiden Extremen angesiedelt.
Eine solch kleine Operation (zwei Werte vergleichen) über mehrere Geräte zu verteilen bedeutet, dass diese Art von Algorithmus auf spezialisierter Hardware ausgeführt werden muss. Derartige Algorithmen werden gegenwärtig nur für spezialisierte Programme verwendet, werden jedoch beispielsweise mitunter auf dem Grafikprozesser (GPU) eines Computers ausgeführt, da diese Prozessoren gut für die parallele Verarbeitung einfacher Aufgaben geeignet sind.
Sortiernetzwerke wurden lange vor der Entwicklung leistungsfähiger GPUs erfunden. Dies ist eine interessante Sache an der Informatik – einige unserer Entdeckungen sind der verfügbaren Hardware weit voraus. Wir sind also für die Hardware gerüstet, wenn sie denn allseits zur Verfügung stehen sollte! Hinweis: Die in diesen Lektionen behandelte Methode ist kein konventioneller Sortieralgorithmus, da das in einem konventionellen System ausgeführte Sortieren nur jeweils einen Vergleich anstellen kann. Konventionelle Sortieralgorithmen werden in einer anderen Lektion behandelt. Diese Lektionen sollen Schülern hauptsächlich dabei helfen, die Vor- und Nachteile zu erkunden, die zwischen der Verteilung von Arbeitsgängen über mehrere Computer und der Verwendung nur eines Prozessors bestehen.
Eine zurzeit populäres Modell der parallelen Verarbeitung ist „MapReduce“, das in vielen Cloud-Computing-Systemen Anwendung findet, wo Unmengen an Berechnungen über eine große Anzahl von Prozessoren verteilt werden.
Aus allen Lektionen ergeben sich Verbindungen zu informatischem Denken. Nachstehend sind ein paar allgemeine Verbindungen aufgeführt, die diesen Inhalt betreffen.
Teaching computational thinking through CSUnplugged activities supports students to learn how to describe a problem, identify what are the important details they need to solve this problem, break it down into small logical steps so that they can then create a process which solves the problem, and then evaluate this process. These skills are transferable to any other curriculum area, but are particularly relevant to developing digital systems and solving problems using the capabilities of computers.
Diese informatischen Denkkonzepte sind alle miteinander verbunden und stützen sich gegenseitig. Insoweit möchten wir jedoch anmerken, dass nicht alle Aspekte des informatischen Denkens in jeder Unterrichtseinheit oder Lektion vorkommen. Wir haben jeweils die für Sie wichtigen Verbindungen hervorgehoben, um Ihre Schüler in Aktion zu beobachten. Unser Artikel zu informatischem Denken enthält weitere Hintergrundinformationen dazu, wie wir informatisches Denken definieren.
In diesen Lektionen lernen Schüler, verschiedene Dinge in eine Reihenfolge zu ordnen, der zugrundeliegende Algorithmus zur Ausführung dieser Aufgaben bleibt jedoch gleich. Es ist ein Algorithmus, da es sich um ein schrittweises Verfahren handelt, das stets die richtige Lösung liefert, solange er genau eingehalten wird. In diesem Fall handelt es sich um eine besondere Algorithmuskategorie, die „paralleler Algorithmus“ genannt wird. Die Schüler müssen diesen Algorithmus präzise befolgen, um zur richtigen Lösung zu gelangen (was vor allem dann deutlich wird, wenn Schüler zu „mogeln“ versuchen, indem sie ans Ende des Netzwerks rasen und dann feststellen, dass dadurch andere Schüler in der Mitte feststecken bleiben! Es ergibt ein sehr anschauliches Lernbeispiel, wenn einer der Schüler so vorgeht).
Das in diesen Aktivitäten von uns eingesetzte Sortiernetzwerk ist eine einfache Darstellung von etwas viel komplexerem: wie Sortiernetzwerke mittels spezialisierter Hardware und Software auf manchen Computern implementiert werden, um eine parallele Verarbeitung auszuführen. Die in unseren Sortiernetzwerken verwendeten Linien, Kreise und Quadrate verbergen die komplizierten Details der Hard- und Software.
Ein weiteres Detail, das wir bei der Verwendung eines Sortiernetzwerks ignorieren können: was die von uns sortierten Daten tatsächlich sind oder darstellen. Es spielt keine Rolle, ob wir Zahlen oder Wörter oder Musiknoten in eine Reihenfolge sortieren – wir folgen stets demselben Prozess. Was jedoch hinsichtlich der Daten eine Rolle spielt, ist dass wir die einzelnen Elemente vergleichen können und dass sie nach einer bestimmten Methode sortiert werden (z. B. in alphabethischer Reihenfolge). Dies wird im Abschnitt zu Logik näher geschildert.
Auch die generelle Idee eines Sortiernetzwerks stellt ein abstraktes Konzept dar. Dies wird im Abschnitt Generalisierung erläutert.
Um einen Algorithmus zu erstellen, der rechnerische Aufgabenstellungen mithilfe von Parallelprozessoren effektiv lösen kann, müssen wir die Aufgabe zunächst in äußerst kleine und einfache Operationen zerlegen, die bei vielfacher Wiederholung eine Lösung für das Problem aufbauen können. Diese Operationen sind das, was von jedem Prozessor im Netzwerk ausgeführt wird. Für das Sortiernetzwerk in diesen Lektionen ist die einfache Operation der Vergleich von zwei Werten, den wir an jedem Knotenpunkt durchführen. Diese Operationen müssen so einfach sein, dass sie von Knotenpunkten zeitgleich und unabhängig voneinander ausgeführt werden können. Parallele Algorithmen eigenen sich am besten für Aufgaben, bei denen mehrmalige und unabhängige Kalkulationen mit großen Datenmengen ausgeführt werden müssen.
Dekomposition ist einer der wichtigsten Schritte beim Erstellen von Algorithmen zur parallelen Verarbeitung!
Es gibt viele Zusammenhänge zwischen diesem Abschnitt und dem obigen Abschnitt Abstraktion – schaut genau hin!
Die Sortiernetzwerke, mit denen wir uns beschäftigen werden, sind alle darauf ausgelegt, eine bestimmte Anzahl an Eingaben aufzunehmen, und zwar genau diese Anzahl. Ein Sortiernetzwerk, das sechs Zahlen ordnet, kann nicht dazu verwendet werden, stattdessen zehn Zahlen zu ordnen. Die verallgemeinerte Idee eines Sortiernetzwerks kann jedoch auch auf andere Problemstellungen angewendet werden. Das verallgemeinerte Konzept eines Sortiernetzwerks ist lediglich ein Komparatornetzwerk (Komparator bedeutet einfach, dass es Vergleiche vornimmt, genau wie wir in jedem Kreis im Netzwerk Zahlen vergleichen), das eine Anzahl an Eingaben aufnimmt und diese in eine Reihenfolge sortiert. Diese allgemeine Idee eines Sortiernetzwerks kann dann zur Lösung vieler verschiedener Probleme herangezogen werden, indem ein Sortiernetzwerk für eine bestimmte Anzahl an Eingaben erstellt wird, die für das betreffende Problem benötigt werden, und die Vergleichsknotenpunkte in einem bestimmten Muster angeordnet werden.
Auch in der Gestaltung von Sortiernetzwerken sind Muster vorhanden. Diese zu erkennen hilft uns dabei, größere Netzwerke anzulegen. Beispielsweise folgen (optimale) zwei-, vier- und sechswegige Sortiernetzwerke in ihrer Ausführung ähnlichen Mustern. Ein einfaches Muster zur Erstellung von Sortiernetzwerken wird am Ende von Lektion 3 für die Altersgruppe 11–14 behandelt (dies kann jedoch für jede Altersgruppe verwendet werden, wenn die Schüler daran interessiert sind!).
Zudem können Schüler ein Muster beobachten, das all den verschiedenen Arten von Informationen, die wir mit dem Sortiernetzwerk ordnen, gemeinsam ist, und zwar, dass sie verglichen und auf präzise Weise geordnet werden können. Dies wird im Abschnitt Logik erläutert.
Parallele Systeme müssen auf ihre Genauigkeit hin ausgewertet werden: Werden Werte von ihnen stets richtig geordnet? Außerdem muss ihre Leistungsfähigkeit ausgewertet werden: Wie viel Zeit benötigt diese Netzwerkstruktur, um Werte zu ordnen, oder gibt es eine schnellere Struktur, die wir verwenden könnten? Könnte das Problem mit einem nicht-parallelen System einfacher gelöst werden?
Für Daten, die von Sortiernetzwerken verarbeitet werden können, gibt eine sehr wichtige Regel: Zwischen den Daten muss eine sogenannte transitive Relation bestehen. Transitive Relation bedeutet: wenn a kleiner ist als b, und b kleiner ist als c, dann ist a kleiner als c. Beispielsweise besteht zwischen Zahlen eine transitive Relation: die Zahl 5 ist kleiner als 10, und 10 ist kleiner als 15, was bedeutet, dass 5 ebenfalls kleiner als 15 sein muss. Daten müssen eine solche Beziehung haben, damit sie von einem Sortiernetzwerk geordnet werden können. Wenn Elemente nicht über diese Beziehung verfügen, gibt es keine logische Methode, sie zu ordnen!
Darüber hinaus wird deutlich, dass Sortiernetzwerke nicht dadurch ausgewertet werden können, dass jede nur mögliche Eingabe ausprobiert wird (naja, es wäre möglich, könnte jedoch Stunden, Tage oder sogar Hunderte von Jahren für große Netzwerke dauern!), es sei denn, es wird nur eine kleine Menge an Daten geordnet. Stattdessen müssen wir Logik und Rationalität anwenden, um nachzuweisen, dass sie die Daten stets richtig ordnen. Bei diesen Lektionen sind keine fortgeschrittenen Nachweise zu erbringen, dass das gesamte Netzwerk funktionieren wird. Die Schüler können jedoch ihr logisches Denkvermögen einsetzen, um nachzuweisen, dass der kleinste und der größte Wert stets an die richtige Stelle gelangen werden.