DE69113465T2

DE69113465T2 - Paralleler prozessor für flüssigkeitsdynamik.

Info

Publication number: DE69113465T2
Application number: DE69113465T
Authority: DE
Inventors: Kim Molvig; Gregory Papadopoulos
Original assignee: Massachusetts Institute of Technology
Current assignee: Massachusetts Institute of Technology
Priority date: 1990-07-12
Filing date: 1991-07-12
Publication date: 1996-05-02
Anticipated expiration: 2011-07-13
Also published as: ATE128567T1; DE69113465D1; EP0538415A1; WO1992001993A1; JPH05508498A; EP0538415B1; CA2086930A1

Description

Allgemeiner Stand der Technik

Ein Fluid ist allgemein als irgendeine Substanz definiert, die strömen kann. Fluide umfassen Gase, Flüssigkeiten und Kombinationen von Gasen und Flüssigkeiten. Das Gebiet der Fluiddynamik versucht, das Verhalten von Fluiden zu erklären und zu kennzeichnen. Herkömmlicherweise ist eine solche Kennzeichnung durch Gleichungen geschehen. Die Anwendung von Gleichungen, um große und komplexe physikalische Umgebungen als System zu beschreiben, ist zum mindesten schwierig. Ferner können einer Verarbeitung der Gleichungen inhärente Näherungen signifikante Fehler bewirken.
Ein grundlegendes Bild der Fluiddynamik ist, daß Fluide aus Teilchen bestehen. Ein Folgesatz dieses Bildes ist, daß ein Verhalten der Fluide aus dem Verhalten der Teilchen, die das Fluid bilden, erklärt werden kann. Eine große Mehrheit von Teilchen in dem Fluid ist dauernd in Bewegung. Die Teilchen bewegen sich ungestört, bis sie mit anderen Teilchen kollidieren. Solch ein Bild von Teilchen hat zu einem Simulationsansatz Anlaß gegeben, in dem die Teilchen als sich auf einem Gitter bewegend betrachtet werden und einzeln verarbeitet werden. Solch ein diskretes System leidet jedoch unter mehreren Diskretisierungs-Artefakten, die in realen Fluiden nicht gefunden werden.
Die folgenden Dokumente diskutieren alle Systeme zum Simulieren eines Fluidstroms:
COMPLEX SYSTEMS, Band 1, Nr. 4, August 1987, US, Seiten 649-707.
PROCEEDINGS OF CONPAR 1988, CONFERENCE PAPERS: PLENARY SESSIONS AND STREAM "A", Manchester, 12.-16. September 1988, British Computer Society - Parallel Processing Specialist Group, GB, Seiten 175-185.
EP-A-0 228 915.
Diese Dokumente diskutieren die Schaffung einer Stromsimulation unter Verwendung von Teilchendarstellungen eines Satzes von Teilchen für jeden einer Vielzahl von Plätzen eines Gitters. Stoß- bzw. Kollisionsregeln werden verwendet, um die Teilchendarstellungen zu verarbeiten, um modifizierte Darstellungen zu schaffen, die dann über das Gitter verarbeitet werden, um neue Darstellungen zu erzeugen, die eine Bewegung von Teilchen in dem Gitter zu neuen Plätzen widerspiegeln. Keines dieser Dokumente diskutiert geeignet die Bildung von Teilchendarstellungen, die eine Vielzahl von Energiezuständen, einschließlich mehrfacher Energiezustände von sich bewegenden Teilchen, darstellen. Eine Publikation der Proceedings des Workshops über Discrete Kinetic Theory, Lattice Gas Dynamics and Foundations of Hydrodynamics in Turin, Italien, 20.-24. September 1988, beschreibt ein Fluidsimulationssystem, das Energiezustände von sich bewegenden Teilchen berücksichtigt. In diesem System werden Kollisionsregeln verwendet, die Regeln einschließen, welche eine Energieübertragung zwischen Teilchen widerspiegeln. Der Vorschlag, der darin zum Verarbeiten der Teilchendarstellungen durch Summieren einzelner Prozesse, angewandt auf die Anfangs-Teilchendarstellung, gemacht wird, ist nicht ausführbar.
Die vorliegende Erfindung trachtet danach, ein Fluidsimulationssystem und ein Verfahren zum Simulieren eines Fluids zu schaffen, das eine schnelle, genaue und technisch durchführbare Simulation liefert.
Gemäß einem Aspekt der vorliegenden Erfindung wird ein Datenprozessor geschaffen zum Verarbeiten von Daten einer Vielzahl von Plätzen eines Gitters, um einen wechselwirkenden physikalischen Prozeß über das Gitter zu simulieren, wobei der Datenprozessor umfaßt: ein Speichermittel, das dazu eingerichtet ist, um Teilchendarstellungen eines Satzes von Teilchen zu speichern, die jedem einer Vielzahl von Plätzen eines Gitters zugeordnet sind, wobei die Teilchendarstellungen einen gleichen Satz von Bits enthalten, die Teilchen an einem Platz des Gitters darstellen; ein Eingabemittel, das mit dem Speichermittel gekoppelt ist, um Anfangswerte der Teilchendarstellungen zu empfangen; ein Wechselwirkungs-Verarbeitungsmittel, das gekoppelt ist, um von dem Speichermittel die Anfangs-Teilchendarstellungen zu empfangen, die jedem Gitterplatz zugeordnet sind, und um daraus in einem Zeitschritt modifizierte Teilchendarstellungen gemäß Kollisionsregeln zu erzeugen; und ein Bewegungs-Verarbeitungsmittel, das betreibbar ist, um aus den modifizierten Teilchendarstellungen neue Anfangs-Teilchendarstellungen zu erzeugen, die eine Bewegung von Teilchen in dem Gitter zu neuen Plätzen widerspiegeln, und um zu veranlassen, daß die neuen Teilchendarstellungen in dem Speichermittel gespeichert werden, wodurch der nächste, von dem Wechselwirkungs-Verarbeitungsmittel vorgenommene Schritt an den neuen Anfangswerten ausgeführt wird, dadurch gekennzeichnet, daß die Teilchendarstellungen für jedes Teilchen einen einer Vielzahl möglicher Energiezustände, einschließlich Zuständen von sich bewegenden Teilchen, identifizieren, und dadurch, daß das Speichermittel bei dem Beginn eines Mehrfachzyklus- Zeitschrittes eine zu verarbeitende Anfangs-Teilchendarstellung hält; und ferner gekennzeichnet durch ein Auswahlmittel, um aus den Bits der empfangenen Teilchendarstellungen verschiedene Permutationen von Bits in aufeinanderfolgenden Zyklen innerhalb eines Zeitschrittes auszuwählen, und ein Logikmittel, um eine Kombinationslogik an diesen Bits in jedem Zyklus gemäß den Kollisionsregeln auszuführen, welche Regeln einschließen, die eine Energieübertragung zwischen Teilchen verschiedener Energiezustände widerspiegeln, worin Bits, die in jedem Zyklus zum Verarbeiten ausgewählt werden, durch Verarbeiten in vorherigen Zyklen modifizierte Bits enthalten können.
Gemäß einem anderen Aspekt der vorliegenden Erfindung wird ein Verfahren zum Verarbeiten von Daten einer Vielzahl von Plätzen eines Gitters geschaffen, um einen wechselwirkenden physikalischen Prozeß über das Gitter zu simulieren, wobei das Verfahren umfaßt: Speichern von Teilchendarstellungen eines Satzes von Teilchen, die jedem einer Vielzahl von Plätzen eines Gitters zugeordnet sind, wobei die Teilchendarstellungen einen gleichen Satz von Bits enthalten, die Teilchen an einem Platz des Gitters darstellen; Bereitstellen von Anfangswerten der Teilchendarstellungen; Verarbeiten der Anfangs-Teilchendarstellungen für jeden Gitterplatz, um daraus in einem Zeitschritt modifizierte Teilchendarstellungen gemäß Kollisionsregeln zu erzeugen; Erzeugen neuer Anfangs-Teilchendarstellungen aus den modifizierten Teilchendarstellungen, die eine Bewegung von Teilchen in dem Gitter zu neuen Plätzen widerspiegeln, und Speichern der neuen Teilchendarstellungen, wodurch der nächste Verarbeitungsschritt an den neuen Anfangswerten ausgeführt wird, dadurch gekennzeichnet, dar die Teilchendarstellungen für jedes Teilchen einen einer Vielzahl möglicher Energiezustände, einschließlich Zuständen von sich bewegenden Teilchen, identifizieren, und dadurch, daß der Zeitschritt ein Mehrfachzyklus-Zeitschritt ist, und ferner gekennzeichnet durch die Schritte eines Auswählens verschiedener Permutationen von Bits aus den Bits der zu verarbeitenden Anfangs-Teilchendarstellung in aufeinanderfolgenden Zyklen innerhalb eines Zeitschrittes und Verarbeitens dieser Bits in jedem Zyklus gemäß den Kollisionsregeln, die Regeln einschließen, welche einen Energieubertrag zwischen Teilchen verschiedener Energiezustände widerspiegeln, worin Bits, die in jedem Zyklus zum Verarbeiten ausgewählt werden, durch Verarbeiten in vorherigen Zyklen modifizierte Bits enthalten können.
Das Logikmittel sorgt vorzugsweise für größere Raten eines Energieubertrags in einer Richtung als in einer umgekehrten Richtung. Speziell kann die Anzahl erlaubter Energieübertragungskollisionen und Invers-Übertragungskollisionen reguliert werden, um sicherzustellen, daß das System eine Galilei- Invarianz ohne eine Anomalie des dynamischen Druckes über einen Bereich von Dichten und Temperaturen zeigt.
Die Kollisionen für viele Plätze können in parallelen Prozessoren ausgeführt werden. Die Kollisionsregeln erhalten Masse, Impuls und Energie. Die Teilchendarstellungen definieren vorzugsweise Teilchen mit verschiedenen vierdimensionalen Geschwindigkeiten. Die Teilchen können sich entlang vierdimensionaler flächenzentrierter Hyperwürfel bewegen, die in einen dreidimensionalen Raum projiziert werden. Die Prozessoren können eine Bewegung von Teilchen auf einem nicht gleichförmigen Gitter liefern.
Die Gitterstruktur vereinfacht ein Verarbeiten, indem die Teilchen gezwungen werden, an diskreten Stellen zu liegen. Das System beruht auf einer Kombinationslogik, um einfache Kollisionsregeln zu verarbeiten, so daß keine Gleitkommaarithmetik erforderlich ist, und die solchen Berechnungen infolge einer Näherung inhärenten Fehler werden vermieden. Durch Vorsehen mehrfacher Teilchenenergieniveaus und Kollisionen, die einen Energieubertrag zwischen Teilchen zur Folge haben, können die Diskretisierungs-Artefakte, die sich aus der diskreten Natur des Prozesses ergeben, beseitigt werden.
Die Teilchendarstellungen werden hierin als ein Zustandsvektor bezeichnet. Der Zustandsvektor ist ein Satz von Bits, wobei jedes Bit ein Teilchen einer speziellen Energie und einer speziellen Bewegungsrichtung an dem Platz repräsentiert bzw. darstellt. In dem bevorzugten System wählt ein Sequenzer gleiche Bits einer Vielzahl von Plätzen des Gitters zusammen aus, und eine Kombinations-Kollisionslogik verarbeitet gleichzeitig eine gemeinsame Kollisionsregel an allen ausgewählten Bits. Die Kombinationslogik muß nur eine Kollision durch Setzen von Zustandsbits ausführen, wo die Teilchendarstellung anzeigt, daß alle kollidierenden Teilchen vorhanden sind und daß Löcher vorhanden sind, wo alle resultierenden kollidierten Teilchen in der zweiten Teilchendarstellung vorhanden sein sollen. Die Kombinationslogik kann Maskierungseingaben empfangen, um eine Ausführung von bestimmten Kollisionsregeln zu verhindern; solche Maskierungseingaben sorgen einfach für die verschiedenen Raten einer Energieübertragung. Andere Maskierungseingaben können eine Randregel erzwingen und bei einer Implementierung des nicht gleichförmigen Gitters helfen.

Kurze Beschreibung der Zeichnungen

Figur 1a ist eine Projektion des Untergitters für eine Energie 1 des vierdimensionalen flächenzentrierten Hyperwürfelgitters auf das dreidimensionale Gitter, wo Teilchen liegen.
Figur 1b ist eine Projektion des Untergitters für eine Energie 2 des vierdimensionalen flächenzentrierten Hyperwürfelgitters auf das dreidimensionale Gitter, wo Teilchen liegen.
Die Figuren 2a und 2b listen die möglichen Geschwindigkeitsvektoren auf, die die Teilchen an irgendeinem gegebenen Gitterplatz annehmen können.
Die Figuren 3a und 3b listen die möglichen Teilchenpaarungen für die erste Äquivalenzklasse auf.
Die Figuren 4a und 4b veranschaulichen, wie die Netto- Geschwindigkeitsvektoren der zweiten Äquivalenzklasse durch Anwenden des Theorems von Pythagoras gefunden werden können.
Figur 5 präsentiert zwei Beispiele der Entartung der zweiten Äquivalenzklasse.
Figur 6 veranschaulicht ein einzelnes Beispiel der Entartung der dritten Äquivalenzklasse.
Figur 7 ist eine Tabelle, welche die Äquivalenzklassen zusammenfaßt.
Die Figuren 8a, 8b und 8c stellen Beispiele von Teilchenkollisionen für die jeweiligen ersten drei Äquivalenzklassen dar.
Die Figuren 9a und 9b zeigen Vorwärts- bzw. Invers- Energieübertragungskollisionen.
Figur 10 ist eine Veranschaulichung der Bits in einem Zustandsvektor.
Figur 11 ist eine Veranschaulichung eines Verarbeitungschips einer Ausführungsform der Erfindung.
Figur 12 ist eine vergrößerte Ansicht eines Pipelineelements von Figur 11.
Figur 13 ist ein Beispiel der Überlappstrategie, die verwendet wird, um kontaminierte Daten zu entfernen.
Figur 14 stellt die Abbildung eines Fluidvolumens in die Verarbeitungsfelder dar.
Figur 15 ist ein Blockdiagramm eines alternativen, die Erfindung verkörpernden Prozessors.
Figur 16 ist eine schematische Veranschaulichung der Zustandsvektordaten für einen 4x4x4-Block von Plätzen, die in der ALU von Figur 15 verarbeitet werden.

Ausführliche Beschreibung bevorzugter Ausführungsformen

Die vorliegende Erfindung schafft ein Verfahren und Gerät zum Lösen von Teilchenstromproblemen, wie z.B. in der Fluiddynamik, indem ein Fluidverhalten mit einem Spezial- Datenverarbeitungssystem effektiv simuliert wird. Ferner werden die Teilchenstromprobleme unter Verwendung einer rein binären Logik gelöst. An sich leidet das System nicht unter den Nachteilen einer arithmetischen Gleitkommaberechnung (z.B. einem Fehler, der einer Dezimalstellenrundung zuzuschreiben ist).
Ein Fluidvolumen besteht aus einer Anzahl von Teilchen, wie z.B. Molekülen, die überall in einem Volumen verteilt sind. Die Teilchen in dem Volumen bewegen sich in viele verschiedene Richtungen, und eine Anzahl von Kollisionen findet zwischen den Teilchen statt. Das System erfaßt das physikalische Verhalten des Fluidvolumens innerhalb praktischer Berechnungsbeschränkungen, indem eine dreidimensionale (3-D) Gitterstruktur auf das Fluidvolumen gelegt wird. Ein Teil dieses dreidimensionalen kubischen Gitters 10 ist in Figur 1a dargestellt. Die Gitterstruktur ist von einer geeigneten Größe, um das gesamte Fluidvolumen abzudecken. Teilchen des Fluids können nur an Gitterplätzen (d.h. Vertices bzw. Schnittpunkten) des Gitters liegen. Eine Bewegung der Teilchen ist jedoch nicht darauf beschränkt, entlang der Kanten des dreidimensionalen Gitters zu erfolgen; vielmehr sind Teilchen nur darauf beschränkt, für irgendeinen diskreten Zeitschritt an einem Gitterplatz zu liegen.
Während jedes Zeitschrittes läßt man die Teilchen, die an einem Platz liegen, kollidieren. Die Zustände der Teilchen ändern sich somit gemäß vorher bestimmter Kollisionsregeln. Trotz der Diskretisierung der Gitterstruktur ist bestimmt worden, daß ein wahrer Fluidstrom ohne Diskretierungs-Artefakte durch Zulassen mehrfacher Energieniveaus der Teilchen durch eine geeignete Auswahl der festgelegten Richtungen einer Bewegung der Teilchen entlang der Gitterstruktur und durch eine geeignete Auswahl von Kollisionsregeln simuliert werden kann. Eine geeignete Bewegungsrichtung erfordert, daß die Teilchen als sich in einem vierdimensionalen Raum bewegend betrachtet werden. Die Größe und Orientierung der Gitterstrukturen variieren für jedes Energieniveau. Beim Auswählen der Gitter muß die Summe über die Richtungen des vierfachen Tensorproduktes der Einheitsvektoren in jedem Energieniveau einen rein isotropen Tensor mit Rang 4 bilden. Diese Isotropieeigenschaft mit Rang 4 muß in jedem Energieniveau getrennt gelten. Alle ganzzahligen Energieniveaus existieren und weisen diese Eigenschaft auf. Die Verschiebungs/Geschwindigkeitsvektoren der ganzzahligen Energieniveaus 1, 2, 3 und 4 sind unten beschrieben.
Die Teilchen mit Energie 1 und 2 bewegen sich in einer vierdimensionalen flächenzentrierten Hyperwürfel-(FCHC)- Gitterstruktur. Die Bewegung jedes Teilchens projiziert sich in das dreidimensionale Gitter der Figuren 1a und 1b. Figur 1a veranschaulicht die Projektion einer Bewegung eines Teilchens eines ersten Energieniveaus, und Figur 1b veranschaulicht die Projektion einer Bewegung von Teilchen eines zweiten Energieniveaus auf das gleiche dreidimensionale Gitter.
Die FCHC-Symmetrie für eine einzelne Geschwindigkeit eines Teilchens ist in B. Hasslacher et al., Complex Systems (1987) beschrieben. Haßlacher et al. beschrieben nicht eine FCHC- Symmetrie für mehrfache Energien sich bewegender Teilchen, wie in der vorliegenden Erfindung verkörpert ist. Ferner schlagen sie im Gegensatz zu der vorliegenden Erfindung keine Energieaustauschkollisionen zwischen sich bewegenden Teilchen vor. Diese Änderungen werden unten ausführlicher beschrieben werden.
Eine Bewegung der Teilchen in den vier Dimensionen kann durch Vektoren (x, y, z, w) dargestellt werden. Figur 2a veranschaulicht die Bewegungsvektoren des ersten Energieniveaus, die in drei Dimensionen wie in Figur 1a veranschaulicht projiziert werden. Die Bewegungsvektoren der Teilchen des zweiten Energieniveaus sind in Figur 2b dargestellt und werden in das dreidimensionale Gitter wie in Figur 1b veranschaulicht projiziert. Die in den Figuren 2a und 2b dargestellten Vektoren repräsentieren die Verschiebung eines Teilchens in jede der vier Dimensionen in einem Zeitschritt und sind daher die Geschwindigkeitsvektoren einer Verschiebung pro Zeitschritt. Der Vektor für eine Energie 1 von Figur 2a kann als Permutationen von (±1,±1,0,0) angesehen werden, wo die beiden Werte ±1 zu irgendeiner der vier Dimensionen verschoben werden können. Ähnlich können die Vektoren für eine Energie 2 von Figur 2b als Permutationen von (±1,±1,±1,±1,) und (±2,0,0,0) angesehen werden. Obwohl die hier dargestellten Implementierungen nur drei Energieniveaus, 0,1 und 2, verwenden, können zusätzliche Energieniveaus in dem System dargestellt werden. Zum Beispiel wäre das dritte Energieniveau Permutationen von (±2,±1,±1,0), und ein viertes Energieniveau wäre Permutationen von (±2,±2,0,0).
Die Energie jedes Teilchens ist gleich einer Hälfte der Summe der Quadrate der Einheiten einer Verschiebung in jede Richtung. Somit beträgt die Energie des ersten Niveaus 1/2(1+1) = 1, und die des zweiten Niveaus beträgt 1/2(1+1+1+1)=1/2(4) = 2. Entsprechend sind die ganzzahligen Energiewerte der dritten und vierten Niveaus 3 und 4. Die resultierenden Geschwindigkeiten der Geschwindigkeitsvektoren können aus dem Theorem von Pythagoras als die Quadratwurzel der Summe der Quadrate der Verschiebungen in jede Richtung berechnet werden. Somit beträgt für die Teilchen der Energie 1 die Geschwindigkeit 1+1 = 2, und für Teilchen der Energie 2 beträgt die resultierende Geschwindigkeit 4=2.
Wie aus den Figuren 2a und 2b gesehen werden kann, gibt es 24 mögliche Teilchen in jedem der Energieniveaus 1 und 2, wobei jedes Teilchen eine verschiedene Bewegungsrichtung in vier Dimensionen aufweist. Teilchen der Energie 3 können sich in 96 Richtungen bewegen, und Teilchen der Energie 4 können sich in 24 Richtungen bewegen. In den hier beschriebenen Implementierungen werden zusätzlich zu den 24 Richtungen von Teilchen der Energie 1 und 24 Richtungen von Teilchen der Energie 2 sechs Ruheteilchen zugelassen, um die Diskretisierungs-Artefakte, wie unten beschrieben wird, zu entfernen, zu einer Gesamtzahl von 54 möglichen Teilchen bei jeder Seite des dreidimensionalen Gitters von Figur 1a. Wie unten ausführlich diskutiert wird, läßt man mit jedem Zeitschritt ausgewählte Paare jener Teilchen kollidieren; Paare kollidierender Teilchen an jedem Platz erzeugen Paare kollidierter Teilchen.
Nach Figur 1a gibt es für jeden Gitterplatz 24 Bewegungsrichtungen 3 und 5, die ein Teilchen annehmen kann. Diese Richtungen werden als nächste Nachbarrichtungen bezeichnet, weil die Geschwindigkeitsvektoren, die sie repräsentieren, auf FCHC-Knoten zeigen, die als nächste Nachbarn bezeichnet werden.
Die nächsten Nachbarknoten befinden sich 2-Einheiten von dem Gitterplatz in dem vierdimensionalen Raum entfernt. Außerdem gibt es 24 andere Bewegungsrichtungen 7 und 9 (in Figur 1b), die ein Teilchen annehmen kann. Solche FCHC-Knoten werden als nächstfolgende nächste Nachbarn bezeichnet. Diese Knoten befinden sich 2 Einheiten von dem Gitterplatz entfernt. Ein bei einem gegebenen 3-D-Gitterplatz gelegenes Teilchen kann sich auf einen nächsten FCHC-Nachbarn, einen nächstfolgenden nächsten FCHC-Nachbarn zu bewegen oder in einem einzelnen Zeitschritt stationär bleiben.
Die zu nächsten Nachbarn hin gerichteten Geschwindigkeitsvektoren, die keine Komponenten in der vierten Dimension aufweisen (d.h. die letzte Koordinatenposition ist Null), sind die Vektoren 3 in Figur 1a. Diese Vektoren sind als gepunktete Linien dargestellt. In Figur 1a sind auch die Geschwindigkeitsvektoren 5 dargestellt, die Komponenten in der vierten Dimension aufweisen. Diese Vektortypen sind durch durchgezogene Linien dargestellt, die von dem zentralen Knoten zu den umliegenden Knoten verlaufen. Jede besagte Linie repräsentiert ein Vektorpaar für jeden Knoten, weil die Komponente des Vektors in der vierten Dimension (d.h. eine 1 oder -1 in der letzten Koordinatenposition) in drei Dimensionen nicht gesehen werden kann. An sich projizieren sich die beiden Geschwindigkeitsvektoren auf drei Dimensionen als die gleiche Linie.
Figur 1b liefert eine ähnliche Veranschaulichung der Geschwindigkeitsvektoren für Teilchen der Energie 2. Die ausschließlich in drei Dimensionen existierenden Geschwindigkeitsvektoren 7 sind jedoch durch durchgezogene Linien dargestellt; wohingegen die Geschwindigkeitsvektoren 9, die Komponenten in der vierten Dimension aufweisen, durch gestrichelte Linien dargestellt sind, die von dem zentralen Knoten ausgehen. Außerdem sind in Figur 1b die Vektoren (0,0,0,2) und (0,0,0,-2) nicht dargestellt, weil sie keine Komponenten in den anderen drei Dimensionen haben und sie demgemäß keine Projektion in die drei Dimensionen aufweisen.
Die acht Vektoren (+2,0, 0,0) von Teilchen der Energie 2 bilden zusammen ein Hyperoktaeder. Die 16 Geschwindigkeitsvektoren (±1,±1,±1,±1) bilden zusammen einen Hyperwürfel. Das Hyperoktaeder und der Hyperwürfel, die durch die jeweiligen Geschwindigkeitsvektoren zusammen gebildet werden, bilden ein allgemeines FCHC-Polytop. An sich weisen die die nächstgelegenen nächsten Nachbarn verbindenden Verbindungen eine FCHC-Geometrie auf. Tatsächlich weisen alle zusätzlichen Geschwindigkeiten für höhere ganzzahlige Energien die erforderliche Isotropie mit Rang 4 auf, obwohl nicht notwendigerweise die FCHC-Gitterstruktur. Daher kann dieser Ansatz für höhere Energien zusätzlich zu den vorliegenden drei verallgemeinert werden.
Das System arbeitet in diskreten Zeitschritten. Für jeden diskreten Zeitschritt werden zwei Aktivitätsphasen ausgeführt. In der ersten Phase werden irgendwelche Kollisionen, die stattfinden können und man stattfinden läßt, ausgeführt. Sind die Kollisionen einmal ausgeführt, werden die Teilchen in der zweiten Phase bewegt. Ein Teilchen wird sich mit seiner aktuellen Geschwindigkeit und Richtung ungestört fortbewegen, es sei denn, eine Kollision findet statt. Eine Kollision beeinflußt die Geschwindigkeitsvektoren der kollidierenden Teilchen.
Die Kollisionen können in zwei Arten von Kollisionen kategorisiert werden: Adiabatische Kollisionen und Energieaustauschkollisionen. Adiabatische Kollisionen sind die Kollisionen, die die Anzahl von Teilchen jedes Energieniveaus nicht ändern und daher den Wärmeinhalt des Systems nicht ändern. In den vorliegenden Ausführungsformen sind die einzigen adiabatischen Kollisionen Selbstkollisionen zwischen Teilchen des gleichen Energieniveaus. Selbstkollisionen bestehen aus zwei zusätzlichen Arten: Selbstkollisionen zwischen Teilchen der Energie 1 und Selbstkollisionen zwischen Teilchen der Energie 2. Energieaustauschkollisionen sind im Gegensatz dazu diejenigen Kollisionen, in denen Energie von einem Teilchen zu einem anderen Teilchen Übertragen wird, wie in dem Fall, in dem zwei Teilchen der Energie 1 kollidieren, um ein Teilchen der Energie 2 und ein stationäres Teilchen zu bilden.
Zwecks Klarheit werden beide Arten von Selbstkollisionen hierin zusammen beschrieben. Um Selbstkollisionen besser zu verstehen, ist es am besten, zuerst zu untersuchen, wie Teilchen gepaart werden können. Um Impuls- und Energieerhaltung zu erhalten, ist es notwendig, daß der Netto- Geschwindigkeitsvektor eines Paares kollidierter Teilchen, die sich aus einer Kollision ergeben, gleich dem Netto- Geschwindigkeitsvektor des kollidierenden Paares von Teilchen ist. Es gibt vier Äquivalenzklassen, in die die Teilchen einer gegebenen Energie gepaart werden können. Jede dieser Klassen ist durch die Größe bzw. den Betrag des Netto-Geschwindigkeitsvektors gekennzeichnet, der sich aus dem Summieren der Geschwindigkeitsvektoren der Teilchen, die gepaart werden, ergibt. Die erste Äquivalenzklasse ist für Teilchen, deren Netto-Geschwindigkeitsvektoren einen Betrag von 0 aufweisen. Für jede Energie von Teilchen gibt es 12 Paare von Teilchen, die, wenn man sie kombiniert, einen Netto- Geschwindigkeitsvektor von 0 aufweisen. Solche Paare von Teilchen der Energie 1 sind in Figur 3a dargestellt, und solche Paare von Teilchen der Energie 2 sind in Figur 3b dargestellt. Der Winkel zwischen den Geschwindigkeitsvektoren, die gepaart werden, beträgt 180º.
Der Netto-Geschwindigkeitsvektor mit Betrag 0 zeigt eine als Entartung bekannte Eigenschaft, die mit sich bringt, daß der Geschwindigkeitsvektor mit Betrag 0 das Produkt von irgendeinem von mehreren (d.h. 12) Paaren von Teilchen sein kann. Diese Eigenschaft ist für diese Kollisionen wichtig, um Energie und Impuls zu erhalten.
Die zweite Äquivlenzklasse besteht aus denjenigen Paaren von Teilchen, die unter einem Winkel von 90º kollidieren. Für Teilchen der Energie 1 in dieser Äquivalenzklasse mit einer Geschwindigkeit vom Betrag 2 ist der Betrag des Netto- Geschwindigkeitsvektors der Paare in dieser Äquivalenzklasse 2; für Teilchen der Energie 2 in dieser Äquivalenzklasse mit einer Geschwindigkeit vom Betrag 2 ist der Netto-Geschwindigkeitsbetrag des Paares 4. Diese Netto-Geschwindigkeitsvektorwerte können durch eine einfache Vektoraddition bestätigt werden. Insbesondere werden, um zwei Vektoren zu addieren, die beiden Vektoren 11a und 11b, wie in Figur 4a dargestellt, am vorderen bzw. hinteren Ende für ein Paar der Energie 1 dieser Äquivalenzklasse aneinander angefügt. Die Vektoren 11a und 11b haben jeweils eine Länge von 2. Ihr Produkt wird durch Zeichnen eines Vektors 13 von dem hinteren Ende des ersten Vektors 11a zu dem vorderen Ende des zweiten Vektors 11b gefunden. Weil diese drei Vektoren 11a, 11b und 13 ein rechtwinkliges Dreieck bilden, kann die Geschwindigkeit des Vektors 13 durch Anwenden des Theorems von Pythagoras gefunden werden. Insbesondere ist die Geschwindigkeit (d.h. die Länge) des Vektors 13 gleich der Quadratwurzel der Summe der Quadrate der Geschwindigkeiten (Längen) der Vektoren 11a und 11b. Daher ist die Geschwindigkeit des Vektors 13 gleich 2. Entsprechend kann gefunden werden, daß für Teilchen der Energie 2 in dieser Äquivalenzklasse der Betrag der Geschwindigkeit des Netto- Geschwindigkeitvektors 19 4 ist, indem das Theorem von Pythagoras auf die Geschwindigkeitsvektoren 17a und 17b, die jeweils eine Geschwindigkeit von Betrag 2 aufweisen, angewendet wird.
Jeder Netto-Geschwindigkeitsvektor für diese zweite Äquivalenzklasse kann durch drei Paare von Teilchen erzeugt werden. An sich weist jeder Netto-Geschwindigkeitsvektor eine Entartung von 3 auf. Figur 5 veranschaulicht ein Beispiel der beiden Sätze von drei Paarungen, die die Netto-Geschwindigkeitsvektoren von (2,0,0,0) bzw. (1,1,1,1) erzeugen können, für Teilchen der Energie 1. Weil es für Teilchen der Energie 1 24 mögliche Netto-Geschwindigkeitsvektoren gibt, deren Betrag 2 ist (d.h. die Netto-Geschwindigkeitsvektoren (±1,±1,±1,±1), (±2,0,0,0), (0,±2,0,0), (0,0,±2,0), (0,0,0,±2)) , und es drei Paarungen, die jeden solchen Netto-Geschwindigkeitsvektor zur Folge haben können, (d.h. eine Entartung von 3) gibt, folgt, daß es 24×3 oder 72 Paarungen in der zweiten Äquivalenzklasse für jede Teilchengeschwindigkeit gibt.
Die dritte Äquivalenzklasse wird aus denjenigen Paaren von Teilchen erzeugt, die einen Netto-Geschwindigkeitsvektor mit dem gleichen Betrag wie jeder der Geschwindigkeitsvektoren der Teilchen erzeugen. Für jeden der 24 möglichen Netto- Geschwindigkeitsvektoren können vier Paare von Teilchen den Netto-Geschwindigkeitsvektor erzeugen. Demgemäß gibt es 24×4 oder 96 Teilchenpaare in der dritten Äquivalenzklasse. Ein Beispiel für den Netto-Geschwindigkeitsvektor (1,0,1,0) ist in Figur 6 dargestellt. In dieser Äquivalenzklasse gepaarte Teilchen sind durch einen 120º-Winkel getrennt.
Die vierte und letzte Äquivalenzklasse umfaßt die verbleibenden Selbstkollisionspaare, die nicht in die ersten drei Klassen fallen. Diese Klasse besteht aus 96 Paaren von Teilchen. Jeder Netto-Geschwindigkeitsvektor hat ein eindeutiges Paar von Teilchen, das ihn erzeugt. An sich gibt es keine Entartung, und es kann keine Kollision stattfinden, um ein äquivalentes Paar von Teilchen zu erzeugen. Figur 7 ist eine Tabelle, die die obige Diskussion der Äquivalenzklassen zusammenfaßt.
Die ersten drei Äquivalenzklassen bilden die Paarungen, in denen Selbstkollisionen für Teilchen auf dem FCHC möglich sind. Diese drei Klassen bilden 180 Paarungen aus den möglichen 276 Paarungen oder 15/23 der möglichen Paarungen. Während der ersten Phase einer Operation in einer Implementierung geht das System alle 180 Paarungen durch, um eine Kollision auszuführen, wann immer möglich. Ob eine Kollision ausgeführt wird, wird dadurch vorgeschrieben, ob beide Teilchen des Paares an dem 3- D-Gitterplatz vorliegen oder nicht. Sie wird auch dadurch vorgeschrieben, ob das kollidierte Paar von Teilchen, das sich aus der Kollision ergibt, nicht vorhanden ist. In dieser Ausführungsform dürfen, um Teilchenmasse exakt zu erhalten, Ausgangsteilchen nicht erzeugt werden, die den gleichen Geschwindigkeitsvektor existierender Teilchen aufweisen. Diese Bedingung kann gelockert werden, indem mehr als ein Teilchen pro Zustand pro Platz zugelassen wird.
Wie Kollisionen ausgeführt werden, kann nun im Hinblick auf die obige Diskussion der möglichen Paarungen von Teilchen erläutert werden. Zu Veranschaulichungszwecken werden nur binäre (d.h. zwei Teilchen betreffende) plus Spectator- bzw. Zuschauer-Kollisionen diskutiert werden. Solche binären Kollisionen sind für die Mehrheit von Teilchenkollisionen verantwortlich, die in realen physikalischen Systemen stattfinden. Die in der vorliegenden Erfindung erlaubten Sequenzen binärer Kollisionen häufen sich an, um zu tertiären Kollisionen oder Kollisionen höherer Ordnung äquivalente Ergebnisse zu erzeugen. An sich ist diese Beschränkung auf binäre Kollisionen annehmbar. Solche Kollisionen berücksichtigen, daß Spectator- bzw. Zuschauerteilchen an dem Gitterplatz liegen, so daß die Zuschauerteilchen nicht irgendeine Änderung im Zustand durchmachen. Es sollte dennoch erkannt werden, daß die vorliegende Erfindung nicht auf binäre Kollisionen beschränkt ist, da andere Kollisionen höherer Ordnung gleichermaßen möglich sind.
Wie oben erwähnt wurde, können Kollisionen für die ersten drei Äquivalenzklassen stattfinden. Beispiele solcher Kollisionen für die jeweiligen Äquivalenzklassen sind in den Figuren 8a, 8b und 8c dargestellt. Jede dieser Arten von Kollisionen zeigt eine Erhaltung von Energie, Impuls und Masse. Masse ist erhalten, weil die Anzahl von Teilchen, die in alle Kollisionen eintreten und diese verlassen, die gleiche ist. Die Erhaltung von Impuls und Energie wird evident durch Vergleichen der Geschwindigkeitsvektoren der Teilchenpaare, die zur Kollision gebracht werden sollen, mit den resultierenden Geschwindigkeitsvektoren für die Teilchen nach der Kollision. Eine kursorische Analyse zeigt, daß die Vektorsumme der Teilchenpaare vor einer Kollision gleich der Vektorsumme der Teilchenpaare nach einer Kollision ist. Weil dies der alleinige, Impuls und Energie beeinflussende Faktor ist der in dem System nicht konstant ist, und weil dieser Faktor erhalten ist, ist es einleuchtend, daß die Erhaltungsgesetze für das System in den Kollisionen exakt gelten.
In einem seguentiellen Prozessor werden die Kollisionen ausgeführt, indem durch jede der möglichen Teilchenpaarungen für jeden Gitterplatz in iterativer Weise zyklisch durchgegangen wird. Dieses System beginnt mit der ersten Äquivalenzklasse von Teilchenpaarungen. Das System betrachtet die erste Paarung in der ersten Äquivalenzklasse, um zu überprüfen, ob beide Teilchen für die Paarung vorhanden sind oder nicht. Das Vorhandensein dieser Teilchen kann als eine Wahrheitsbedingung zusammengefaßt werden. Falls die Wahrheitsbedingung angibt, daß beide Teilchen vorhanden sind, geht das System weiter.
Das System kennt den Netto-Geschwindigkeitsvektor für jede Teilchenpaarung. Um Energie- und Impulserhaltung sicherzustellen, müssen die sich aus der Kollision ergebenden Teilchen ebenfalls den gleichen Netto-Geschwindigkeitsvektor teilen. Zum Beispiel weiß, weil es drei mögliche Paarungen gibt, die irgendeinen Netto-Geschwindigkeitsvektor in der zweiten Äquivalenzklasse erzeugen können, das System, daß das sich aus der Kollision ergebende Teilchenpaar eine der anderen beiden Paarungen sein muß, die den gleichen Netto-Geschwindigkeitsvektor erzeugen können. Andere Teilchenpaarungen auf dem Gitter können solch einen Netto-Geschwindigkeitsvektor nicht erzeugen. Das System kann entweder eine dieser Paarungen, die die Ausgabe sein soll, zufällig auswählen oder durch alle Paarungen zyklisch durchgehen. Bevor das System die Kollision ausführen kann, muß es jedoch zuerst eine zweite Wahrheitsbedingung überprüfen. Die zweite Wahrheitsbedingung zeigt das Vorhandensein des ausgewählten Ausgabe- Teilchenpaares, auch bekannt als das Lochpaar, an. Falls beide Wahrheitsbedingungen wahr sind (d.h., Teilchen sind vorhanden und das Lochpaar ist vorhanden), wird die Kollision ausgeführt.
Ist die Kollision einmal für das erste Paar ausgeführt oder bestimmt das System einmal, daß die Kollision nicht ausgeführt werden kann, geht das System weiter zu dem nächsten Teilchenpaar, wie durch das Index-Sequenzschema vorgeschrieben ist. Eine Verarbeitung der Teilchen der Energie 1 und Energie 2 findet parallel statt. Diese Verarbeitung dauert an, bis alle Teilchenpaare für die erste Äquivalenzklasse untersucht worden sind. Ist dies einmal für die erste Äquivalenzklasse beendet, werden die Paarungen in der zweiten Äquivalenzklasse untersucht, und ähnlich werden die Paarungen in der dritten Äquivalenzklasse untersucht.
Die obige Beschreibung macht die Rolle der Entartung beim Ausführen der Kollisionen klar. Insbesondere wählt das System eine der Permutationen von Teilchenpaarungen innerhalb einer Entartungsgruppe für einen Netto-Geschwindigkeitsvektor aus. Aufgrund der Tatsache, daß die vierte Äquivalenzklasse keine Entartung aufweist, ist es unmöglich, mit solchen Kollisionen in dieser Äquivalenzklasse Impuls zu erhalten. Per se werden die Kollisionen nicht ausgeführt.
Entweder kann eine Zufallszahl von Kollisionspermutationen für jede Untersuchung eines Teilchenpaares ausgewählt werden, oder alle von den möglichen Permutationen können untersucht werden. In dem letztgenannten Verfahren werden alle möglichen Ereignisse, die stattfinden können, versucht. Als ein Beispiel nehme man an, daß ein Teilchenpaar aus der ersten Äquivalenzklasse gerade analysiert wird, um zu bestimmen, ob eine Kollision auszuführen ist. Es würde 11 andere Teilchenpaare geben, die den gleichen Netto-Geschwindigkeitsvektor erzeugen könnten, den das gegebene Teilchenpaar erzeugt. Somit könnte das System zufällig irgendeine der 11 anderen Paarungen wählen, falls das Zufallszahlenverfahren benutzt wurde. In der alternativen Ausführungsform würde jedoch jede Paarung in einer fortlaufenden Reihenfolge ausgewählt werden, um zwei mögliche Kollisionen zu ermöglichen. Durch Steuern dieser und aller anderen Kollisionsregeln kann die Viskosität des Fluids reguliert werden.
Die andere Art von Kollisionen, die durch die vorliegende Erfindung ausgeführt werden, sind Energieaustauschkollisionen. Energieaustauschkollisionen finden statt, wenn zwei Teilchen der Energie 1 kollidieren, um ein Teilchen der Energie 2 und ein Teilchen der Energie 0 zu bilden. Ein Diagramm dieses Typs einer Kollision ist in Figur 9a dargestellt. Es gibt 72 mögliche Paarungen, die solch eine Kollision zustande bringen, wenn die Teilchen vorhanden sind. Außerdem ermöglicht die vorliegende Erfindung auch Invers-Energieaustauschkollisionen (Figur 9b), worin ein Teilchen der Energie 2 mit einem gestoppten Teilchen zusammenstößt, um zwei Teilchen der Energie 1 zu erzeugen. Auf diese Typen von Kollisionen wird als Invers- Energiekollisionen verwiesen, weil sie den exakt entgegengesetzten Typ einer Kollision ausführen, die die Vorwärts- Energieaustauschkollision ausführt. Der Einschluß von Energieaustauschkollisionen mit variablen Vorwärts- und inversen Raten fügt dem System einen zusätzlichen Freiheitsgrad hinzu. Wie unten diskutiert werden wird, ist der Einschluß dieses zusätzlichen Freiheitsgrades wichtig, so daß das System ein wahres Fluidverhalten nachvollzieht.
Die Äquivalenzklasse 2 der Teilchen der Energie 1 dient auch als die Basis für Energieübertragungskollisionen. Wie in Figur 5 gesehen werden kann, ist der Netto-Geschwindigkeitsvektor jedes Paares von Teilchen der Energie 1 selbst ein Geschwindigkeitsvektor der Gruppe 2. Somit liefern der Geschwindigkeitsvektor für die Energie 2 und ein stationäres Teilchen zusammen die gleiche Masse, Energie und den gleichen Impuls wie das Paar von Vektoren für die Energie 1. Solch ein Gruppieren kann daher Kollisionsregeln definieren, die Energie zwischen Teilchen übertragen. Die Energie eines Teilchens der Energie 1 kann einem anderen Teilchen der Energie 1 übertragen werden, was ein Teilchen der Energie 2 und ein Teilchen der Energie 0 zur Folge hat. Entsprechend kann ein Teilchen der Energie 2 mit einem Teilchen der Energie 0 zusammenstoßen, was zwei Teilchen der Energie 1 zur Folge hat.
Die Vorwärts-Energieaustauschkollisionen und die Invers- (Rückwärts-) Energieaustauschkollisionen werden auf ungefähr die gleiche Weise, die oben für die Selbstkollisionen beschrieben wurde, ausgeführt. Insbesondere werden mögliche Kollisionsgruppierungen bestimmt, um konstante Netto- Geschwindigkeitsvektoren vor und nach Kollisionen beizubehalten. Das System prüft die erste Wahrheitsbedingung, um zu bestimmen, ob die Teilchen vorhanden sind, und prüft auch die zweite Wahrheitsbedingung, um zu bestimmen, ob das Lochpaar vorhanden ist. Falls beide Wahrheitsbedingungen wahr sind, wird die Energieaustauschkollision (oder die Invers-Energieaustauschkollision) ausgeführt. Wie unten diskutiert werden wird, sind die Vorwärts-Energieaustauschkollisionen und die Invers-Energieaustauschkollisionen durch eine Maske beschränkt, die in dem System eingerichtet ist, um die Rate solcher Kollisionen zu beeinflussen.
Sind die Kollisionen einmal ausgeführt worden, werden die Teilchen in der Bewegungsphase oder -operation bewegt. Die Einzelheiten davon, wie die Bewegung in einer Hardware verwirklicht wird, sind unten angegeben.
Die vorliegende Erfindung kann die Hauptprobleme, an denen Systeme nach dem Stand der Technik leiden, überwinden. Die Systeme sind insofern diskret, als die Teilchen auf diskrete Positionen auf einem Gitter beschränkt sind. Es wird nicht zugelassen, daß solche Teilchen überall in einem Volumen kontinuierlich positioniert werden, wie es im allgemeinen in einem echten physikalischen System sein würde. Drei sich aus der Diskretisierung ergebende Artefakte sind eine Nicht- Isotropie bzw. Anisotropie des Spannungstensors, eine Nicht- Galilei-Invarianz und eine Anomalie des dynamischen Druckes.
Die Anisotropie eines Spannungstensors impliziert, daß ein Gitter eine mechanische Scherbeanspruchung erfährt. Die Tatsache, daß bestimmte Gitter eine isotrope Beanspruchung zeigen, ist wohlbekannt. Siehe B. Hasslacher, P. Lallemand, Y. Pomeau, U. Frisch, D. d'Humieres und J.P. Rivet, Complex Systems, Seite 649 (1987), die eine Isotropie des Spannungstensors für Teilchen erläuterten, die sich bei einer einzigen Geschwindigkeit entlang einer FCHC-Symmetrie ohne Energieaustauschkollisionen bewegen. Gittersymmetrien für eine Teilchenbewegung sind entwickelt worden, die eine solche isotrope Beanspruchung nicht zeigen. Solche Gitter schließen das hexagonale Gitter und das FCHC ein. Um dieses Artefakt einer Diskretisierung zu entfernen, nutzt die vorliegende Erfindung ein vierdimensionales FCHC-Gitter und weiat eine Isotropie mit Rang 4 in allen Energieniveaus auf.
Nicht-Galilei-Invarianz bezieht sich auf den g- bzw. Galileifaktor "g" mit einem anderen Wert als 1. Ein anderer Wert als 1 gibt an, daß das Gittergasfluid eine Tendenz hat, sich verschieden zu verhalten, wenn es sich bei konstanter Geschwindigkeit bewegt, als wenn es sich in Ruhe befindet. Dies ist in erster Linie eine Konsequenz des stationären Gitters, in das das Fluid eingebettet ist, und wird im allgemeinen zu einem Nicht-Fluidverhalten des Gittergases führen.
Der Galileifaktor g erscheint in der Impulserhaltungsgleichung, wie unten zusammen mit den anderen Diskretisierungs- Artefakten gezeigt wird. VISKOSE TERME
Bis auf die drei, durch Pfeile angezeigten Artefakte ist dies die Navier-Stokes-Gleichung der Fluiddynamik, angegeben mit der Massendichte , Fluidgeschwindigkeit u und dem Druck P. Die vorliegende Erfindung beseitigt sowohl den Term einer Anomalie des dynamischen Druckes, f u², als auch die anisotrope Beanspruchung PANIS, während in dem ganzen dynamischen Bereich g=1 beibehalten wird.
Das letzte Artefakt ist die Anomalie des dynamischen Druckes. Typischerweise hängt der Druck von der Fluidgeschwindigkeit ab. Der Grund für diese Abhängigkeit ist wieder eine Konsequenz der Tatsache, daß das Gitter in Ruhe ist, und hat einen gewissen Bezug zu der Galilei-Invarianz.
Die Probleme einer Nicht-Galilei-Invarianz und der Anomalie des dynamischen Druckes werden gelöst, indem der Energiefreiheitsgrad in das System abgebildet wird. Der Galileifaktor "g" wird durch die Rate der Vorwärts-Energiekollisionen und die Rate der Invers-Energiekollisionen direkt beeinflußt. Die Rate der Vorwärts- und Invers-Energiekollisionen wird ausgewählt, um "g" gleich 1 zu zwingen, und somit das System zu zwingen, eine Galilei-Invarianz zu zeigen.
Das Verhältnis von Vorwärts- zu inversen Raten wird theoretisch durch die Galilei-Invarianzbedingung, g = 1, bestimmt, um das geeignete Gleichgewicht sicherzustellen. Ausdrücke werden entwickelt, um dieses Ratenverhältnis mit sehr hoher Genauigkeit zu liefern. Das Verhältnis von Vorwärts- zu Rückwärtsprozessen kann auf den erforderlichen Wert eingestellt werden, um eine Galilei-Invarianz ohne die Anomalie des dynamischen Druckes zu erhalten. Die Druckanisotropie wird aufgelöst, indem sichergestellt wird, daß jedes Energieniveau die Isotropieeigenschaft mit Rang 4 verarbeitet.
Wie aus der obigen Beschreibung des Kollisionsprozesses offensichtlich ist, ist das System extrem rechenintensiv. Um dessen Anwendung durchführbar zu machen, wird das System auf einem Spezial-Parallelverarbeitungssystem implementiert. Zentral für eine Operation des Systems ist der Zustandsvektor 10, der in Figur 10 dargestellt ist. Der Zustandsvektor 10 besteht aus 54 Bits, die einen Wert von 0 oder 1 annehmen können. Jede Bitposition ist einem gegebenen, aus den 54 Teilchen ausgewählten Teilchen zugeordnet, das an irgendeinem gegebenen Gitterplatz vorhanden sein kann. Daher ist jede Bitposition einem gegebenen Geschwindigkeitsvektor für das zugeordnete Teilchen zugeordnet. Eine 1 in der Bitposition zeigt das Vorhandensein des Teilchens an, wohingegen eine 0 das Nichtvorhandensein des Teilchens anzeigt. Die Anzahl von Bits in einem Zustandsvektor muß nicht auf 54 Bits beschränkt sein; vielmehr wird die Anzahl von Bits durch die Anzahl von vorhandenen Energien und Richtungen vorgeschrieben. Somit kann, falls verschiedene Energien oder verschiedene Richtungen verwendet werden oder falls mehr Teilchen pro Zustand pro Platz erlaubt sind, eine verschiedene Bitlänge für den Zustandsvektor gewählt werden. Insbesondere würde für Energieniveaus 0 bis 4 ein Zustandsvektor mit 169 Bits verwendet werden.
Um jede Kollisionsregel auszuführen, müssen die geeigneten Bits, die die beiden kollidierenden Teilchen repräsentieren, überprüft werden, um zu bestätigen, daß die Teilchen vorhanden sind. Dann müssen die die erforderlichen Löcher repräsentierenden Bits überprüft werden; d.h., es muß bestätigt werden, daß die resultierenden kollidierten Teilchen aus einer Kollision in dem Zustandvektor nicht schon vorhanden sind. Wenn diese beiden Bedingungen erfüllt sind, wird die Kollision ausgeführt, indem in dem Zustandsvektor die Bits für die kollidierenden Teilchen entfernt und die Bits für die kollidierten Teilchen erzeugt werden. Diese Logik muß für jede Kollisionsregel ausgeführt werden, wobei die ausgewählten Paare kollidierender und kollidierter Teilchen mit den oben diskutierten Paarungsregeln übereinstimmen.
Zwei Hardware-Architekturen zum Ausführen der Kollisionsregeln und anschließender Bewegungsoperationen werden beschrieben werden. Jede beruht auf einer Kombinationslogik, um die Kollisionsregeln auszuführen. Bei richtiger Auswahl der geeigneten Paare von Bits in einem Zustandsvektor geht die Kombinationslogik wie folgt vor sich. Für jedes Paar kollidierender Geschwindigkeitsvektoren, das durch Bits Si und Sj repräsentiert wird, und entsprechende Paar kollidierter Vektoren, das durch Bits Sk und Sl repräsentiert wird, gibt es eine Vorwärts-Kollisionsregel, die erfordert, daß Si und Sj in dem Zustandsvektor vorhanden sind und daß Sk und Sl Löcher sind. Ferner werden Maskierungsbits MF und MB durch einen Zufallszahlengenerator bei den Raten geliefert, die für die Vorwärts- und Rückwärts-Kollisionen erforderlich sind. Die Rate für eine Richtung kann auf 1 eingestellt werden. Die Kollisionen sind nur zulässig, wo das Bit MF oder MB gesetzt ist. Somit lautet die Vorwärts-Kollisionsregel:
RF = (Si*Sj* k* l)*MF (1)
Für die gleichen Vektorpaare kann eine Rückwärts- Kollisionsregel wie folgt definiert werden:
RB = ( i* j*Sk*Sl)*MB (2)
Die Maskierungsbits MF unf MB liefern verschiedene Kollisionsraten zwischen den Vorwärts- und Rückwärts-Energieübertragungskollisionen.
Nur eine der Vorwärts- und Rückwärts-Regeln oder keine Regel kann in irgendeinem Zeitschritt ausgeführt werden. Somit können die einzelnen Zustandsbits nach einer Kollision bzw. Bits für einen Zustand nach einer Kollision aus der folgenden Logik bestimmt werden:
iE(RF*Si)+RB
jE(RF*Sj)+RB
kE(RB*Sk)+RF
lE(RB*Sl)+RF (3)
Demgemäß ist z.B. das kollidierte Bit Si hoch gesetzt, falls die Vorwärts-Kollisionsbedingung RF nicht gesetzt ist und Si 1 ist oder falls es eine Rückwärts-Kollision mit der gesetzten Bedingung RB gibt.
Das System muß auch Ränder vorsehen. Eine No-Slip-Randbedingung bzw. Randbedingung ohne Schlupf kann vorgesehen werden, indem der Geschwindigkeitsvektor aller Teilchen, die die Oberfläche treffen, einfach umgekehrt wird. Die Oberfläche kann als ein Randbit B für jeden Platz definiert werden, durch den die Oberfläche durchgeht. Wo es ein Randbit gibt, wird die obige Kollisionslogik unterdrückt, und ein Paritäts- Vektorteilchen wird für jedes Teilchen des Zustandsvektors erzeugt. Wo C die Logik von Gleichung (3) ist, sind die Bits für einen Zustand nach einer Kollision mit Randbedingungen:
E(C* )+(PARITÄT* B) (4)
Die vorliegende Erfindung findet eine besondere Anwendung auf ein Verarbeiten eines Fluidstroms mit hohen Reynolds- Zahlen. Die für die hohen Reynolds-Zahlen erforderliche niedrige Viskosität wird durch die große Anzahl von Kollisionen erhalten, die an jedem Platz ausgeführt werden. In einem realen Fluid würde es viel mehr Teilchen geben, als durch die beschränkten Gitterplätze des vorliegenden Systems erlaubt ist, aber Kollisionen sind weniger effizient. Für dieses System kompensiert die hohe Effizienz von Kollisionen die Zunahme in einer Viskosität, die sich aus der geringeren Anzahl von Teilchen ergibt. Das vorliegende Mehrfachgeschwindigkeitsverfahren vermehrt wesentlich die Zahl möglicher Kollisionen und reduziert somit die Viskosität des Systems außerordentlich.
Das Datenverarbeitungssystem in Figur 11 besteht aus einer Vielzahl von Chips. Jeder Chip verarbeitet bestimmten Gitterplätzen zugeordnete Zustandsvektoren parallel. Die Zustandsvektoren werden verarbeitet, um Kollisionen wie vorher beschrieben zu simulieren und um die Teilchen zwischen Gitterplätzen zu bewegen. Es gibt eine Abbildung von dem physikalischen Raum auf den Chips in die Gitterplatzräume.
Ein typischer Chip ist in Figur 11 dargestellt. Der Chip besteht aus 8 Spalten, worin jede Spalte 64 Elemente 20 aufweist und als eine große Tonnenpipeline (Barrel-Pipeline) betrachtet werden kann. Jedes Element 20 verarbeitet Teilchendaten für einen speziellen Gitterplatz in einem Zyklus. Zugleich führen die Elemente einer Pipeline die Kollisionen für diesen gegebenen Gitterplatz über die verschiedenen Maschinenzyklen eines Zeitschrittes aus.
Jedes Pipelineelement 20 besteht aus einem Zustandsvektor 20a, wie z.B. dem in Figur 11 dargestellten. Die Kollisionen werden durch eine Hardware ausgeführt, die aus Permutationsdrähten 20b und Kollisions-Gattern 20c besteht. Die Permutationsdrähte 20b führen geeignete Permutationen ein, um Teilchenpaare und Lochpaare zu erhalten. Die Kollisions-Gatter 20c (siehe Figur 12) führen im Gegensatz dazu die logischen Operationen (z.B. UND, ODER, etc.) aus, die notwendig sind, um die Kollisionen gemäß den Gleichungen 1, 2, 3 und 4 auszuführen. Diese Kollisions-Gatter 20c empfangen Bits gemäß dem ausgewählten Teilchenpaar und sind für die Energieübertragungskollisionen verantwortlich, indem geeignete Teilchenpaare eingeführt werden. Die Kollisions-Gatter 20c sind höchstens zwei logische Gatter tief aus UND-Gattern und ODER- Gattern aufgebaut. Die Permutationsdrähte können aus 54 horizontalen Drähten bestehen, die sich über alle Kollisions- Gatter erstrecken. Im wesentlichen ist ein Draht für jedes Bit in dem Zustandsvektor vorgesehen, und somit hat jeder Satz der Kollisions-Gatter Zugriff auf solche Bits. Die Pipeline hat 64 Elemente. Somit kehrt nach 64 Maschinenzyklen der Platz A entsprechende Zustandsvektor zu Element A zurück. Alle Zustandsvektoren befinden sich dann in einer Position für eine Bewegung einzelner Bits entlang des Gitters in Abhängigkeit von der Richtung und Energie des durch das Bit repräsentierten Teilchens.
Wie oben erwähnt bestehen Spalten des Chips aus 64 Elementen. Die Abbildung-von dem physikalischen Raum auf die Chips ist derart, daß jede Spalte eine XY-Ebene bildet. Die Abbildung beginnt mit X und Y bei 1. Y nimmt entlang der Spalte zu, bis es den Wert 8 erreicht, bei welchem Punkt der X-Wert auf 2 erhöht wird. Die nachfolgenden Spalten bilden neue Z- Ebenen des physikalischen Volumenraums. Sind die 64 Pipelineelemente 20 und die 8 Spalten gegeben, ist es offensichtlich, daß 8×64 oder 512 Gitterplätze für jeden Chip verarbeitet werden. Die Chips sind z.B. in 8×8×8-Würfel 103 von Chips, dargestellt in Figur 14, angeordnet, die wiederum in ein Volumen 102 aus 100 Würfeln aufgebaut sind. Noch allgemeiner sind die Chips aufgebaut, um 100 Bereiche eines Fluids zu behandeln (wobei ein Bereich eines Fluids durch einen 8×8×8- Würfel behandelt wird), die auf die Prozessorblöcke auf viele verschiedene Arten abgebildet werden können. Diese Konfiguration erzeugt annähernd 10&sup4; Chips pro Maschine, um eine grobe bzw. ungefähre Verarbeitungsleistung von 9×10¹&sup5; Bitoperationen pro Sekunde zu ergeben. Ein Fluidvolumen, das verarbeitet werden soll, wird in das Volumen 102 von Verarbeitungselementen abgebildet.
Eine Bewegung zwischen Gitterplätzen in benachbarten Spalten wird durch Verschieben geliefert. Insbesondere kann ein Element eines Zustandsvektors von einer ersten Spalte zu dessen entsprechendem Pipelineelement in der unmittelbar benachbarten Spalte oder dem unmittelbar benachbarten Chip geschoben werden.
Diese Möglichkeit, Bits zu einer benachbarten Pipeline zu verschieben, ermöglicht den Bewegungsabschnitt des Systems. Daher können Teilchen von einem Zustandsvektor zu einem anderen bewegt werden.
Das System ist ausgelegt, so daß jeder Chip gemäß einem Takt von 30 Megahertz arbeitet. Die Chips benutzen maximal 90 Taktzyklen, um Gitterplätze für einen einzelnen Zeitschritt der Simulation zu verarbeiten. Es wird bevorzugt, daß annähernd 200 Datenstifte pro Chip vorhanden sind. Sind die 90 Taktzyklen, um die Gitterplätze für einen einzelnen Zeitschritt zu verarbeiten, und die vorher beschriebene grobe bzw. ungefähre Verarbeitungsfähigkeit gegeben, ist es einleuchtend, daß jeder Chip 10&sup8; Platzaktualisierungen pro Sekunde ausführen kann.
Die Verarbeitung eines Fluidvolumens geht in einer sequentiellen Weise weiter. Um zu veranschaulichen, wie das System arbeitet, ist eine Beispielabbildung in Figur 13 veranschaulicht. Man nehme an, daß ein erstes Fluidvolumen 30 zu Anfang in einem 8×8×8-Würfel von Chips 103, wie z.B. in Figur 14 dargestellt, für eine gegebene Anzahl von Zeitschritten verarbeitet wird. Weil dieses Volumen 30 für sich verarbeitet wird, werden die Teilchen, die sich bei dem äußeren Rand des Volumens befinden, nicht auf eine Weise verarbeitet werden, die ihr wahres Verhalten genau widerspiegelt. Der Grund für diese Schwierigkeit ist, daß Teilchen von anderen Volumina, die mit diesen Randteilchen kollidieren könnten, nicht berücksichtigt werden. An sich wird nach mehreren Zeitschritten das Volumen 30 aus einem inneren Volumen 30a von Teilchen, das korrekt ist, und einem äußeren Volumen 30b bestehen, das kontaminiert ist. Die Tiefe des äußeren Bereichs 30b entspricht direkt der Anzahl von Zeitschritten, weil für jeden Zeitschritt ein externes Teilchen ein Tiefenniveau in dem Fluidvolumen 30 beeinflussen kann.
Wenn das nächste Volumen 32 von Daten verarbeitet wird, wird es ausgewählt, so daß es mit dem Bereich 30 überlappt. Es überlappt in einem ausreichend großen Maß, um den kontaminierten Bereich des Volumens 30 abzudecken. Insbesondere wird es, wenn das Volumen 32 verarbeitet wird, einen äußeren Bereich 32b kontaminierter Daten und einen inneren Bereich 32a von richtigen Daten aufweisen. Dieser innere Bereich 32a schließt den Bereich 34 von Daten, die vorher kontaminiert wurden, für Volumen 30 ein. Die Veranschaulichung in Figur 13 ist ausschließlich für eine rechte Seite des Volumens 30 dargestellt. Die verbleibenden Seiten des Kontaminationsbereichs 30b werden auf ähnliche Weise für folgende Volumina korrigiert, die positioniert werden, um diese jeweiligen Kanten 30b der kontaminierten Daten zu überlappen.
Das System arbeitet somit auf jedem Volumen des Fluids in einer sequentiellen Reihenfolge, bis alle Volumina geeignet verarbeitet worden sind. Sind einmal alle Volumina geeignet verarbeitet worden, beginnt das System wieder mit dem ersten Volumen für eine neue Runde von Zeitschritten. Dieser Prozeß wird wiederholt, bis die Simulation beendet ist.
Um den oben beschriebenen Prozeß zu initialisieren, muß jeder der Zustandsvektoren für alle Gitterplätze gesetzt werden. Dies wird durch eine Software vorgenommen, die jedem Zustandsvektor einen Wert zuweist. Der Benutzer des Systems muß die Zustandsvektoren initialisieren, um das zu modellierende Fluid genau widerzuspiegeln.
Eine zweite Architektur zum Implementieren der vorliegenden Erfindung ist in den Figuren 15 und 16 veranschaulicht. Das System ist vorzugsweise ein massiv paralleles Prozessorsystem, und Figur 15 veranschaulicht einen Prozessor des Systems. Bei jedem Knoten des Verarbeitungssystems werden Mehrfachblöcke von Gitterplätzen in Reihe verarbeitet. In einer Implementierung ist der Gitterraum in Blöcke von 4×4×4 = 64 Plätzen geteilt. Viele solche Blöcke werden in einem dynamischen Speicher mit wahlfreiem Zugriff 202 gespeichert. Die Blöcke von Platzdaten werden als 64-Bit-Wort zugleich durch eine Speicherschnittstelle 204 geholt und durch einen FIFO 208 einem Verarbeitungsspeicher 210 zugeführt. Nach Verarbeiten wird ein Block durch einen FIFO 206 zu dem DRAM 202 zurückgeführt.
Ein Block von Zustandsvektordaten, die von dem DRAM 202 wiedergewonnen und in einem Verarbeitungsspeicher 210 gehalten werden, liegt wie in Figur 16 veranschaulicht vor. Ein Zustandsvektor mit 54 Bits ist für jeden der 64 Gitterplätze des Blocks vorgesehen. Außerdem wird eine Kopfsatzinformation, die sich auf den gesamten Block bezieht, in einem Kopfsatz gespeichert. Diese Kopfsatzinformation kann eine Maskierungsinformation für jeden Platz ebensogut wie eine diagnostische, statistische, geometrische und Fluidvariablen-Information für den Block enthalten.
In der dargestellten Implementierung wird nur eine Kollisionsregel zugleich verarbeitet. Um jedoch eine signifikante Parallelisierung in der ALU 214 zu erhalten, wird die gleiche Kollision auf jedem der 64 Plätze gleichzeitig durchgeführt. Somit wählt der Sequenzer 212 die vier, in einer bestimmten Kollision erforderlichen Zustände Si, Sj, Sk und Sl aus. Diese Zustandsbits für alle 64 Plätze werden gleichzeitig in die ALU gelesen. Dort wird jeder Satz von vier Bits für jeden Platz auf eine Kombinationslogikeinheit angewandt, die die Logik der Gleichungen 1, 2, 3 und 4 ausführt. Die ALU schließt 64 solche parallel arbeitenden Kombinationslogikeinheiten ein. Die Ausgaben dieser Kombinationslogik werden dann in den Speicher 210 zurückgelesen. Danach wählt der Sequenzer 212 einen neuen Satz von vier Zuständen aus, so daß die ALU die nächste Kollision ausführen kann.
Um einen zusätzlichen Durchsatz zu liefern, können mehr als vier Zustände zugleich ausgewählt werden, und mehrfache Kollisionen können gleichzeitig für alle Plätze ausgeführt werden.
Sind einmal alle Kollisionen für einen Block ausgeführt worden, führt die Bewegungs-ALU 216 die Bewegungsoperation an den Teilchendarstellungen aus. Die meisten der Bewegungen müssen nur innerhalb des Blocks von 64 Plätzen vorgenommen werden. Somit müssen die meisten Zustandsbits, die sich während der Bewegungsoperation nicht ändern, nur innerhalb des 64-Bit- Wortes verschoben werden, das diesen Zustand für alle Plätze des Blocks repräsentiert. Das Verschieben wird sich zwischen Zustandsbits unterscheiden, wird aber für einen einzelnen Zustand überall in dem 64-Bit-Block das gleiche sein. Um das Verschieben zu vereinfachen, kann die Bewegungs-ALU 216 die Bits innerhalb des 64-Bit-Wortes sequentiell in jede der x-, y - und z-Dimensionen verschieben. Einige Bits müssen zu anderen Blöcken verschoben werden, die durch den Verarbeitungsknoten bearbeitet werden. Somit müssen diese Bits durch die Bewegungs- ALU 216 gespeichert werden, bis der Block, in den sie verschoben werden, durch die Bewegungs-ALU verarbeitet wird. Schließlich müssen einige Bits zu Blöcken verschoben werden, die durch andere Knoten des Systems verarbeitet werden. Diese Bits werden durch eine Zwischenchip-Bewegungsschaltung 218 durch das Netzwerk übertragen.
Wie in der Ausführungsform der Figuren 11 und 12 führt diese Ausführungsform Kollisionen durch Anwenden von Sätzen von vier Bits eines Zustandsvektors an einem 3D-Gitterplatz auf eine Kombinationslogik aus, um Bits für einen Zustand nach einer Kollision zu erzeugen. Weil jede Kollision durch eine geeignete Auswahl von Zustandsbits, die auf eine einfache Kombinationslogik angewandt werden, welche für alle Kollisionen an allen Plätzen für alle Zeitschritte übereinstimmend ist, ausgeführt wird, können die Daten mehrere 1.000mal schneller verarbeitet werden, als mit einem herkömmlichen programmierten Universalrechner möglich wäre. In beiden System werden viele Kollisionen an jedem Platz eines Volumens in jedem Zeitschritt ausgeführt; danach werden die Zustandsbits zu anderen Plätzen gemäß den Richtungen verschoben, die sie repräsentieren, um eine Teilchenbewegung auszuführen.
In der ersten Ausführungsform werden die Bits des Zustandsvektors, der auf die Kombinationslogik angewandt wird, durch festverdrahtete Permutatoren ausgewählt, wobei ein Satz von Permutatoren für jeden Gitterplatz unabhängig arbeitet und mehrfache Kollisionen parallel für den Gitterplatz auswählt. In der zweiten Ausführungsform werden die Teilchenauswahlpermutationen durch den Sequenzer ausgeführt. Der Sequenzer bei einem Knoten wählt die Zustandsbits zugleich aus, die für nur eine einzelne Kollision erforderlich sind, wählt aber die Bits von 64 Plätzen zum Parallelverarbeiten durch die ALU aus. Weil der Sequenzer leicht programmierbar ist, liefert er eine große Flexibilität in einer Größe des Zustandsvektors und in den Kollisionsregeln, wie für solche Modifikationen wie zusätzliche Energieniveaus erforderlich ist. Das Verschieben in der zweiten Ausführungsform ist für eine größere Flexibilität auch programmierbar.
In der zweiten Ausführungsform werden Blöcke von Platzdaten sequentiell von einem Speicher bei jedem Knoten geholt, und ein ganzes Volumen kann in einem Zeitschritt verarbeitet werden, bevor ein Block wieder geholt und verarbeitet wird. Daher tritt das Problem kontaminierter Bereiche wie in Figur 13 veranschaulicht nicht auf.
Mit der zweiten Ausführungsform können Systeme mit variablem Gitterabstand simuliert werden. Solch eine Simulation mit variablem Gitter ist für die genaue Behandlung realistischer Ströme mit hoher Reynolds-Zahl wichtig, wo eine sehr hohe Auflösung nahe der Oberfläche von Objekten erforderlich ist. Die Grenzflächen zwischen sich unterscheidenden Gittern erfordern einige Erweiterungen an der Kollisionslogik, die dem gleichen allgemeinen Verfahren folgt, wie für Kollisionen oben beschrieben wurde.
Während diese Erfindung mit Bezugnahmen auf deren bevorzugte Ausführungsformen besonders dargestellt und beschrieben worden ist, wird es sich für die Fachleute verstehen, daß verschiedene Änderungen in Form und Einzelheiten darin ohne ein Abweichen von dem Umfang der Erfindung vorgenommen werden können, wie durch die beigefügten Ansprüche definiert wird. Zum Beispiel können die Kollisions- und Bewegungsprozesse in einer gemeinsamen Einheit ausgeführt werden. Ferner findet die Erfindung über die Fluiddynamik hinaus Anwendung. Sie kann verwendet werden, wann immer ein physikalischer Prozeß als Teilchenstrom modelliert werden kann.

Claims

1. Datenprozessor zum Verarbeiten von Daten einer Vielzahl von Plätzen eines Gitters zum Simulieren eines wechselwirkenden physikalischen Prozesses über das Gitter, wobei der Datenprozessor umfaßt:

ein Speichermittel (20a, 202, 210), das dazu eingerichtet ist, Teilchendarstellungen eines Satzes von Teilchen, die jedem von einer Vielzahl von Plätzen eines Gitters zugeordnet sind, zu speichern, wobei die Teilchendar- stellungen einen gleichen Satz von Bits, die Teilchen an einem Platz des Gitters darstellen, umfassen;

ein an das Speichermittel gekoppeltes Eingabemittel zum Erhalten von Anfangswerten der Teilchendarstellungen;

ein Wechselwirkungs-Verarbeitungsmittel (20c, 214), das so gekoppelt ist, daß es von dem Speichermittel die jedem Gitterplatz zugeordneten Anfangs-Teilchendarstellungen erhält und daraus in einem Zeitschritt modifizierte Teilchendarstellungen gemäß Kollisionsregeln erzeugt; und

ein Bewegungs-Verarbeitungsmittel (216), das so betreibbar ist, daß es aus den modifizierten Teilchendarstellungen neue Anfangs-Teilchendarstellungen, welche eine Bewegung von Teilchen in dem Gitter zu neuen Plätzen widerspiegeln, erzeugt und veranlaßt, daß die neuen Teilchendarstellungen in dem Speichermittel gespeichert werden, wodurch der nächste von dem Wechselwirkungs-Verarbeitungsmittel vorgenommene Schritt auf den neuen Anfangswerten ausgeführt wird, dadurch gekennzeichnet, daß die Teilchendarstellungen für jedes Teilchen einen von einer Vielzahl von möglichen Energiezuständen, einschließlich Zuständen sich bewegender Teilchen, identifizieren und daß das Speichermittel (20a, 202) zu Beginn eines Mehrfachzyklus-Zeitschrittes eine zu verarbeitende Anfangs-Teilchendarstellung gespeichert hält; und weiter gekennzeichnet durch ein Auswahlmittel (20b, 212), um von den Bits der erhaltenen Teilchendarstellung verschiedene Permutationen von Bits in aufeinanderfolgenden Zyklen innerhalb eines Zeitschrittes auszuwählen, und ein Logikmittel (20c, 214), um Kombinationslogik auf diesen Bits in jedem Schritt gemäß den Kollisionsregeln auszuführen, welche Regeln, die eine Energieübertragung zwischen sich bewegenden Teilchen verschiedener Energiezustände widerspiegeln, umfassen, wobei die Bits, die in jedem Zyklus zum Verarbeiten ausgewählt werden, Bits umfassen können, die durch Verarbeiten in vorherigen Zyklen modifiziert wurden.

2. Datenprozessor nach Anspruch 1, wobei das Logikmittel eine Spezial-Kombinationslogik (20c, 214) umfaßt, die eine Regel ausführt, welche auf Bits einer Teilchendarstellung für jeden Platz des Gitters in jedem Zyklus jedes Zeitschrittes angewendet wird.

3. Datenprozessor nach Anspruch 2, wobei die Kombinationslogik eine Kollision hervorruft, wenn die Teilchendarstellung anzeigt, daß alle ausgewählten kollidierenden Teilchen vorhanden sind und daß dort Löcher sind, wo alle ausgewählten kollidierenden Teilchen nach der Kollision vorhanden sein sollen.

4. Datenprozessor nach einem der vorhergehenden Ansprüche, wobei das Wechselwirkungs-Verarbeitungsmittel ein Mittel zum Übertragen von Energieraten, die in einer Richtung zwischen Energiezuständen anders als in einer inversen Richtung sind, umfaßt.

5. Datenprozessor nach einem der vorhergehenden Ansprüche, wobei die Teilchendarstellungen Teilchen verschiedener vierdimensionaler Geschwindigkeiten definieren.

6. Datenprozessor nach AnsPruch 5, wobei die Summe über die Richtungen des vierfachen Tensorprodukts von Einheitsvektoren in jedem Energiezustand einen rein isotropen Tensor mit Rang Vier in jedem Energieniveau bilden, so daß die Simulation frei von Diskretisierungs-Artefakten ist.

7. Datenprozessor nach einem der vorhergehenden Ansprüche, wobei das Bewegungs-Verarbeitungsmittel die neuen Anfangs-Teilchendarstellungen erzeugt, um Bewegung von Teilchen auf einem nicht gleichförmigen Gitterraster widerzuspiegeln.

8. Datenprozessor nach einem der vorhergehenden Ansprüchen, wobei das Wechselwirkungs-Verarbeitungsmittel gleiche Bits einer Vielzahl von Plätzen des Gitters zusammen auswählt und eine gemeinsame Kollisionsregel auf allen ausgewählten Bits gleichzeitig bearbeitet.

9. Datenprozessor nach Anspruch 8, wobei das Auswahlmittel einen Sequenzer (212) zum Auswählen eines Teils der Bits von Teilchendarstellungen umfaßt.

10. Datenprozessor nach einem der vorhergehenden Ansprüche, weiter umfassend eine Maskierungseingabe an das Wechselwirkungs-Verarbeitungsmittel, um die Ausführung von Kollisionsregeln zu verhindern.

11. Datenprozessor nach einem der vorhergehenden Ansprüche, der eine Vielzahl der Wechselwirkungs-Verarbeitungsmittel in Parallelschaltung umfaßt.

12. Verfahren zum Verarbeiten von Daten einer Vielzahl von Plätzen eines Gitters zum Simulieren eines wechselwirkenden physikalischen Prozesses über das Gitter, wobei das Verfahren umfaßt:

Speichern von Teilchendarstellungen eines Satzes von Teilchen, die jedem von einer Vielzahl von Plätzen eines Gitters zugeordnet sind, wobei die Teilchendarstellungen einen gleichen Satz von Bits, die Teilchen an einem Platz des Gitters darstellen, umfassen;

Bereitstellen von Anfangswerten der Teilchendarstellungen;

Verarbeiten der Anfangs-Teilchendarstellungen für jeden Gitterplatz, um daraus in einem Zeitschritt modifizierte Teilchendarstellungen gemäß Kollisionsregeln zu erzeugen;

Erzeugen neuer Anfangs-Teilchendarstellungen aus den modifizierten Teilchendarstellungen, die eine Bewegung von Teilchen in dem Gitter zu neuen Plätzen widerspiegeln, und Speichern der neuen Teilchendarstellungen, wodurch der nächste Verarbeitungsschritt auf den neuen Anfangswerten ausgeführt wird, dadurch gekennzeichnet, daß die Teilchendarstellungen für jedes Teilchen einen von einer Vielzahl von möglichen Energiezuständen, einschließlich Zuständen sich bewegender Teilchen, identifizieren und daß der Zeitschritt ein Mehrfachzyklus-Zeitschritt ist, und weiter gekennzeichnet durch die Schritte eines Auswählens verschiedener Bitpermutationen von den Bits der zu verarbeitenden Anfangs-Teilchendarstellung in aufeinanderfolgenden Zyklen innerhalb eines Zeitschrittes und eines Verarbeitens dieser Bits in jedem Zyklus gemäß den Kollisionsregeln, welche Regeln umfassen, die eine Energieübertragung zwischen Teilchen verschiedener Energiezustände widerspiegeln, wobei die Bits, die zum Verarbeiten in jedem Zyklus ausgewählt werden, Bits umfassen können, die durch Verarbeiten in vorherigen Zyklen modifiziert wurden.

13. Verfahren nach Anspruch 12, wobei das Verarbeiten gemäß den Kollisionsregeln in Spezial-Kombinationslogik ausgeführt wird, wobei die Kombinationslogik eine Kollision erlaubt, wenn ein Zustandsvektor anzeigt, daß alle der ausgewählten kollidierenden Teilchen vorhanden sind und daß dort Löcher sind, wo alle ausgewählten kollidierenden Teilchen nach der Kollision vorhanden sein sollen.

14. Verfahren nach Anspruch 12 oder 13, wobei die Teilchendarstellung verarbeitet wird, um die modifizierten Teilchendarstellungen zu erzeugen, wobei andere Energieraten in einer Richtung übertragen werden als in einer inversen Richtung.

15. Verfahren nach Anspruch 12, 13 oder 14, weiter umfassend eine Maskierungseingabe, um die Ausführung von Kollisionsregeln zu verhindern.

16. Verfahren nach einem der Ansprüche 12 bis 15, wobei die neuen Anfangs-Teilchendarstellungen erzeugt werden, um Bewegung von Teilchen auf einem nicht gleichförmigen Gitterraster widerzuspiegeln.

17. Verfahren nach einem der Ansprüche 12 bis 16, bei welchem das Verarbeiten gemäß den Kollisionsregeln ein gemeinsames Auswählen gleicher Bits einer Vielzahl von Plätzen des Gitter und das gleichzeitige Bearbeiten einer gemeinsamen Kollisionsregel auf allen ausgewählten Bits umfaßt.

18. Verfahren nach Anspruch 17, wobei Bits durch einen Sequenzer ausgewählt werden, der einen Teil der Bits von Teilchendarstellungen auswählt.