Melden Sie sich hier an, um auf Kommentare und die Whitepaper-Datenbank zugreifen zu können.

Kein Log-In? Dann jetzt kostenlos registrieren.

Falls Sie Ihr Passwort vergessen haben, können Sie es hier per E-Mail anfordern.

Der Zugang zur Reseller Only!-Community ist registrierten Fachhändlern, Systemhäusern und Dienstleistern vorbehalten.

Registrieren Sie sich hier, um Zugang zu diesem Bereich zu beantragen. Die Freigabe Ihres Zugangs erfolgt nach Prüfung Ihrer Anmeldung durch die Redaktion.

16.03.1990 - 

Zelluläre Automaten erforschen turbulente Strömungen im parallelen Modus

Rechner müssen nicht immer sequentiell arbeiten

Wie aus überaus einfachen Bausteinen manchmal höchst komplexe Systeme entstehen können - dies führt uns nicht allein nur das simple System der Elektronen, Protonen und Neutronen vor, aus dem ja sogar hochkomplexe, lebendige Organismen zusammengesetzt sind. Dies kann man auch am Exempel sogenannter "zellulärer Automaten" studieren.

Zelluläre Automaten sind mit den vieldiskutierten neuronalen Netzen verwandt, denen manche wahre Wunderdinge an Erkennungsfähigkeit zusprechen, geht es etwa darum, zwischen einem erfolgversprechenden Aktien-Kursverlauf und einem, der eher zu Verlusten führen dürfte, zu unterscheiden. Und wie die neuronalen Netze stellen sie einen radikalen Bruch mit herkömmlichen Prinzipien des Computerbaus dar.

Zelluläre Automaten können Punkte im Raum-Zeit-Kontinuum repräsentieren, wobei jeder einzelne - und eher einfache - Prozessor eines Automaten dann exakt einem Punkt beziehungsweise einer "Zelle" entspricht. Dabei werden hier aus der kontinuierlich "fließenden" Zeit diskrete Zeitintervalle und aus dem räumlichen Kontinuum ebenso diskret unterscheidbare Gitterpunkt-Elemente; das kontinuierliche Fließen der Dinge in der realen Welt - Heraklit! - wird also digitalisiert. Und auch das einzelne Element des zellulären Automaten kann nur ein paar wenige, diskret unterscheidbare Werte beziehungsweise Eigenschaften annehmen.

Zelluläre Automaten arbeiten strikt getaktet

Typisch für zelluläre Automaten ist deren strikt getaktetes Arbeiten, denn in jedem Maschinentakt nehmen alle Zellen gleichzeitig einen neuen, den bisherigen ersetzenden Zustand an. Und wie sie sich dabei ändern, hängt erstens und wesentlich von ihrem eigenen bisherigen Zustand ab, zweitens von dem ihrer Nachbarn und drittens von vorgegebenen Regeln, die sozusagen das Programm des Automaten bilden.

Ein einfacher, weithin bekannter und zu verblüffenden Aktionen fähiger zellulärer Automat ist das beliebte Computer-Spiel "Life" von John Conway, bei dem Punkte beziehungsweise Zellen eines schachbrettartigen Gitters je nach Zahl der sie momentan umgebenden Punkte "geboren werden", "weiterleben" oder aber "absterben".

Dieser Automat zeigt in der Simulation auf dem Bildschirm eines gewöhnlichen Digitalrechners nicht nur ein höchst lebendig anmutendes Verhalten; er zeitigt auch Effekte, die man a priori wohl kaum erwartet hätte. Denn manche Strukturen sind beispielsweise so beschaffen, daß sie sich in einer Folge von Zwischenschritten wieder in sich selber zurückverwandeln, unterdessen aber eine weitere Struktur "gebären", freisetzen und in eine bestimmte Richtung "davonwandern" lassen.

Conways "Life" ist ein Beispiel für besonders einfache zelluläre Automaten; und zwar insbesondere für jene, deren Zellen nur einen von zwei Zuständen annehmen können: lebendig oder tot.

"Life" kann jeden Digitalrechner simulieren

Wie ernsthafte theoretische Untersuchungen an diesem so amüsanten Automaten ergeben haben, ist "Life" im Grunde der bekannten Turing-Maschine äquivalent - und damit im Prinzip zu jeder Berechnung in der Lage, die jeder denkbare Digitalrechner ausführen kann. Mit anderen Worten: Ein als "Life"-Spiel ausgeführter zellulärer Automat kann, die passende Ausgangskonfiguration vorausgesetzt, jeden beliebigen Überhaupt denkbaren Digitalrechner simulieren.

Mag nun allein schon diese Erkenntnis manch einen in Staunen versetzen, so lehrt die weitergehende Betrachtung der zellulären Automaten noch Merkwürdigeres: Sie zeigt nämlich, daß es keine andere Möglichkeit gibt, die Langzeit-Verhaltensweise eines beliebigen" jedoch hinreichend komplizierten "Life"-Musters kennenzulernen, als es in der Simulation zu erzeugen und seinen weiteren Lebenweg dann Schritt für Schritt ganz konkret zu verfolgen. Während die scheinbar naheliegende Vorstellung, man müßte doch einfach kurzerhand "ausrechnen" können, wie so ein Muster sich mit der Zeit entwickelt - und so ein Muster muß ja keineswegs immer zweidimensional sein, sondern kann letztlich beliebig viele Dimensionen aufweisen -, sich als Illusion entpuppt. Und zwar als Illusion einer Art, die schon Alan Turing und der Österreicher Kurt Gödel als schlicht und einfach irreal entlarvt haben.

Ein ähnliches Beispiel für die Nichtberechenbarkeit beziehungsweise Nichtvorhersagbarkeit finden wir auch in der Physik, wenden wir uns beispielsweise kurz einem - realen Billardtisch zu. Denn auch dort gilt: Egal, wie exakt Billardkugel und Tisch auch - real - gedreht beziehungsweise gebaut sein mögen -, schon für weniger als ein Dutzend Berührungen der Bande wird es unmöglich, den Kurs der Kugel vorherzubestimmen. Denn jede noch so kleine Abweichung in der Startposition des einen Spiels von der eines anderen wird durch das Hin- und Herprallen der Kugel so vergrößert und verzerrt, daß ihr weiterer Lauf ab irgendeinem Punkt einfach nicht mehr sicher bestimmbar ist.

Ähnlich sensibel reagiert nun auch das "simple" "Life" auf minimale Änderungen selbst einer riesengroßen, überaus komplizierten Ausgangsstruktur; denn selbst bloß eine einzige von vielen Tausend Zellen, die in ihrem Zustand von der entsprechenden Zelle einer ansonsten gleichen Struktur abweicht, kann einen beliebig großen Effekt auf das Geschick der ganzen Struktur haben. Oder aber überhaupt keinerlei Wirkung was man ohne vorheriges Ausprobieren jedoch nicht wissen kann.

In beiden Fällen, also beim Billardspiel wie beim zellulären Automaten namens "Life", haben wir im Grunde chaotisch reagierende dynamische Systeme vor uns, wie sie beispielsweise auch das Wettergeschehen oder die Auspuffwölkchen des Autos darstellen: denn für solche Systeme gilt jeweils, daß denkbar minimale Abweichungen vom Ausgangszustand nach verblüffend kurzer Zeit zu völlig anderen Endresultaten führen. Daß also beispielsweise der Flügelschlag einer Fliege über Island im einen Fall Regenschauer über Hamburg und im anderen strahlenden Sonnenschein auslösen kann; und zwar auch dann, wenn alle anderen Ausgangsbedingungen - idealisiert - die gleichen geblieben sind.

Zelluläre Automaten gehören mit zu den einfachsten Vertretern chaotisch agierender Systeme, wobei dies ganz besonders für die Primitiv-Klasse der eindimensionalen zellulären Automaten gilt; also für einfache Zeilen-Anordnungen einzelner Gitterpunkte, die von Generation zu Generation beziehungsweise von Takt zu Takt jeweils "sterben" oder "neu geboren" werden -je nachdem, ob der fragliche Punkt in der eindimensionalen Zeile während der Generation davor zwei oder nur einen lebenden Nachbarn hatte. Denn selbst diese extrem simplen Zeilen als Primitiv-Varianten des "Life"-Spiels können sich bei minimal veränderter Ausgangssituation grundlegend anders entwickeln, verfolgt man sie über ein- paar Dutzend Generationen hinweg.

Eingehend studiert hat zelluläre Automaten vor allem Stephen Wolfram vom Princetoner Institut for Advanced Studies, das einst auch wissenschaftliche Heimstatt Albert Einsteins gewesen ist. In einer ersten Näherung behandelte er sie zunächst wie diskrete Annäherungen an Differentialgleichungen, die bestimmte physikalische Effekte simulieren -und dadurch wiederum konnte er vertraute Begriffe wie den der Entropie aus der Thermodynamik benutzen, um ihr Verhalten zu beschreiben. Und in einem zweiten Schritt faßte er die zellulären Automaten als sprachgenerierende Maschinen auf, die bei der Erzeugung ihrer Muster an bestimmte, zuvor festgelegte und streng formalisierte "grammatikalische" Regeln unterschiedlicher Komplexität gebunden waren.

Am Beispiel eindimensionaler, zeilenförmiger zellulärer Automaten (siehe Bild 1), bei denen stets die oberste Reihe die erste, die darunterliegende Reihe die nächste Generation und so weiter darstellen, lassen sich die vier grundlegenden Typen zellulärer Automaten vorführen, die Wolfram genauer unter die Lupe nahm. Es sind dies:

(a) Arten, bei denen das vorhandene Muster mit der Zeit verschwindet beziehungsweise ausstirbt,

(b) Arten, deren Muster fortan konstant erhalten bleibt,

(c) Arten, deren Muster im Laufe der Zeit unbegrenzt immer weiter wächst und

(d) Arten, bei denen irreguläres Verhalten in dem Sinne beobachtet werden kann, daß das Muster seine Gestalt unvorhersagbar ändert und dabei teils wächst, teils wieder abnimmt.

Die oben erwähnten Phänomene des chaotisch-dynamischen Verhaltens mit hypersensibler Reaktion auf gewisse - aber mitnichten alle - minimale Änderungen der Ausgangskonstellation lassen sich hier nun an den Strukturen nach Modell (d) beobachten, während die nach Modell (c) wiederum mit den bekannten "Fraktalen" zusammenhängen: Hier sieht man, wie in unendlich weitergehender Abfolge immer wieder "selbstähnliche" Strukturen erzeugt werden. Erweitert man hier nämlich einen Teil des Musters, so sieht er dann stets wieder dem Ganzen ähnlich.

Was nun die Seite der praktischen, wissenschaftlich-technischen Anwendung der zellulären Automaten betrifft, so wären hier Themen wie das Wachstum von Kristallen oder auch strömungsmechanische Analysen zu nennen. Denn der einfachste Weg, um beispielsweise die einzelnen Moleküle eines Gases sowie deren Wechselspiel zu modellieren, ist wohl der Einsatz eines zellulären Automaten.

Strömungsmechanische Simulationen sind möglich

Hier nämlich kann jede einzelne Zelle des Automaten je einen Punkt im Raumgitter repräsentieren und somit durch ihren internen Zustand exakt beschreiben, wie viele Teilchen beziehungsweise Moleküle zur Zeit T gerade diesen Teil des Raumes erreichen beziehungsweise verlassen. Und ferner angeben, aus welchen oder auch in welche Richtungen und mit welchen Impulsen oder Geschwindigkeiten die Teilchen sich bewegen.

Bei jeweils einem neuen Taktimpuls beziehungsweise Zeitschritt berechnet also jede Zelle anhand der momentanen Zustände ihrer Nachbarzellen sowie ihres eigenen, wie ihr nächster Zustand auszusehen hat -und nimmt ihn unverzüglich an.

An Beispielen mit zweidimensionalen Gittern von je 50 Zellen Seitenlänge kann man demonstrieren, wie moderne "feinkörnige" Parallelrechner mit zahlreichen Prozessoren die ja gut als zelluläre Automaten benutzt werden können Strömungen an einem festen Hindernis vorbei, durch Engpässe hindurch simulieren. Dabei wird so ein festes Hindernis einfach durch eine Gruppe von Zellen im gesamten Feld dargestellt, die abweichend von jenen übrigen programmiert ist.

"Numerischer Windkanal"

Sie repräsentieren das Fluid selbst, also ein Gas oder eine Flüssigkeit. Ihr besonderer Programmbefehl lautet natürlich in verkürzter Formulierung: Durch diese speziellen Zellen "hindurch" kann keinerlei Fluid strömen...

Die Arbeit mit zellulären Automaten und ihren speziell programmierten Zellen zur Darstellung von Hindernissen und anderen Besonderheiten im Zuge einer Strömung soll, erläutert Supercomputer-Spezialist Greg Wilson von der Universität Edinburgh, viel einfacher sein als Versuche, die Eigenschaften einer Barriere mit Hilfe komplizierter Differentialgleichungen nachzuformen. Denn zur Simulation eines festen Hindernisses müssen diese Zellen einfach nur so programmiert werden, daß auf sie auftreffende Moleküle des Fluids prompt reflektiert werden...

Unter praktischen Aspekten interessant ist die Erfahrung der Wissenschaftler, daß man die Natur mit einem zweidimensionalen Schachbrett-Gitter nur schlecht nachbilden kann. Ein Gitter allerdings, bestehend aus lauter gleichzeitigen Dreiecken - das gleichzeitig auch bienenwabenartige, gleichzeitige Sechsecke umfaßt, die aus jeweils sechs Dreiecken bestehen -, eignet sich gut zum Simulieren der realen Natur durch zelluläre Automaten (siehe Bild 2).

Doch geht man nun gar auf alle drei Dimensionen der realen Welt über, so stellt sich leider heraus, daß kein bekanntes dreidimensionales Gitter hinreichend symmetrisch aufgebaut ist, um beim Simulieren strömender Fluide durch zelluläre Automaten von praktischem Nutzen sein zu können. Während es wiederum im Vierdimensionalen sehr wohl ein symmetrisches Gitter gibt - so daß man mit einem kleinen Kunstgriff doch weiterkommt: Man simuliert mit Hilfe der zellulären Automaten nun einfach den Weg des Fluids im vierdimensionalen Raum, wählt dabei aber eine der vier Dimensionen extrem "dünn" - so wie ja auch im Dreidimensionalen ein Blatt Papier in einer Dimension extrem dünn ist - und transponiert die Resultate auf diese Weise mit hoher Exaktheit zurück auf das Geschehen in unserer gewohnten 3D-Welt.

Beim Simulieren von Fluiden auf zellulären Automaten wird teilweise auch noch eine Zufallsfunktion mitbenutzt, die dafür sorgt, daß gleiche Ausgangsereignisse mal dieses und mal jenes Ergebnis liefern; denn derart stochastische Elemente sind auch in der realen Natur vorzufinden. Und mit Blick auf weitere, vorerst noch ungelöste Probleme beim Einsatz der zellulären Automaten wäre kurz noch zu erwähnen, daß man derzeit eifrig nach Wegen sucht, auch kompressible Fluide realitätsgetreu zu simulieren. Das betrifft insbesondere Gase, die unter Kompression ja sofort mit Erhöhung ihrer Temperatur reagieren.

Auf der anderen Seite bieten zelluläre Automaten wiederum den großen Vorteil, daß man die einzelnen Prozessoren eines solchen Systems, also quasi die einzelnen Zellen, sehr simpel halten, und mithin gleich Hunderte von ihnen auf einem modernen VLSI-Chip (Very Large Scale Integration) mit seinen Hunderttausenden einzelner Transistorfunktionen unterbringen kann. Werden diese Chips dann gar noch zu Hunderten oder gar Tausenden zusammengeschaltet, so erhält man am Ende eine ganz neue Art eines "numerischen Windkanals"; also einen Spezialrechner hoher Leistung, der nur noch eine Aufgabe kennt: Phänomene der Strömungsmechanik genauer unter die Lupe zu nehmen.

Daß dieser Ausblick längst nicht nur graue Theorie ist, zeigen unter anderem Versuchsrechner der Universität Princeton, USA, die dort von Steve Kugelmass und Kenneth Steiglitz zusammengebaut worden sind.

Und ein Rückblick auf die Geschichte des Konzepts der zellulären Automaten erinnert unter anderem auch an die bekannte "Holland-Maschine", die J. Holland schon 1959 beschrieben hat. Sie besteht aus einer rechteckigen Matrix von Zellen, die untereinander über Daten- sowie Aktivierungsleitungen verbunden sind. Im Prinzip kann sie mehrere Programme gleichzeitig ausführen, wobei jedoch ein zentraler Takt das exakt parallele Arbeiten aller Zellen sicherstellt.

Bei diesem Automaten, der natürlich auch wieder eng mit den neuronalen Netzen unserer Tage verwandt ist, werden "bei der Programmausführung dynamisch Verbindungswege zwischen Zellen auf- und abgebaut", skizziert Professor Wolfgang K. Giloi die Arbeitsweise dieses Konzepts.

Der einzelne Programmschritt besteht hier jeweils aus einer Wegbildungs- sowie aus einer darauffolgenden Ausführungs-Phase.

"Holland-Maschine" gilt heutzutage als überholt

Trotz ihrer zellulären Struktur arbeitet diese Maschine, wie Giloi kritisiert, intern noch weitgehend nach dem Schema des klassischen Zuse- beziehungsweise Von-Neumann-Computers, kennt doch auch sie Steuerwörter, die sich jeweils in einen Befehls- und einen Adreß-Code aufgliedern. Allerdings kennt Hollands interessanter Entwurf abweichend von Zuses Prinzipien nicht mehr die sequentielle Steuerung des Programmablaufs durch einen zentralen Befehlszähler, die für herkömmliche Rechner so typisch ist; denn hier wird die Ausführung der Programme nunmehr doch -verteilt - und zwar in den einzelnen Zellen gesteuert.

Doch auf diesen Feldern sind der Holland-Maschine, ihrer Weiterentwicklung durch W. Comfort sowie anderen Varianten des gleichen Konzepts inzwischen scharfe Konkurrenten gewachsen: die zellulären Automaten der oben skizzierten, allgemein benutzbaren Gestalt - sowie insbesondere die hochinteressanten neuronalen Netze, die ja auf eine ganz besonders aparte Weise programmiert werden. Nämlich eigentlich gar nicht.