-
Für verschiedene Zwecke wurden viele eindimensionale
(lineare) Netzwerke vorgeschlagen, die mehrere parallele
Kanäle haben, die in mehreren einzelnen Stufen
pipelineartig verarbeitet werden. Jede Stufe kann in zwei Teile
aufgetrennt werden: einer vermaschungsstufe, in der die
Leitungen permutiert werden, und daran anschließend eine
Schicht von Verarbeitungsmodulen mit zwei Eingängen und
zwei Ausgängen, die nebeneinanderliegende Paare von
Datenkanälen beeinflußt.
-
Kürzlich wurde ein effizienter optischer Computer
vorgeschlagen, der ein Netzwerk ist, in dem der Vermaschungsteil
unter Verwendung einer Optik realisiert wird und der
Modulteil in einem anderen Medium, beispielsweise einem Chip von
Lithiumniobat-Richtungskoppler (P. Granestrand und andere,
"Strictly non-blocking 8x8 integrated optical switch
matrix" Electronic Letters 22 Nr. 15 (1986)), oder in einer
integrierten optoelektronischen Schaltung (J. E. Midwinter,
"Novel approach to optically activated wideband switching
matrices" IEEE Proc. J 134 261 (1987)). Derartige Maschinen
weisen die oben beschriebene körperliche Ausgestaltung auf.
Die Verwendung einer Optik in der Vermaschungsstufe hat den
Vorteil großer Bandbreite, weist keine Zeitverschiebungen
und niedriges Nebensprechen auf, was dem gesamten Prozessor
einen hohen Durchsatz paralleler Daten verleiht. Die
verschiedenen, für das Netzwerk notwendigen Vermaschungsmuster
können erzeugt werden, indem massive oder holographische
optische Komponenten verwendet werden. Eine derartige
Anordnung
nutzt jedoch nicht alle Vorteile der in optischen
Systemen möglichen Parallelverarbeitung aus.
-
In einem Artikel mit dem Titel "2-D Optical Multistage
Interconnection Networks", SPIE Band 752 Digital Optical
Computing (1987) S. 209-216 beschreiben Shing-Hong Lin und
andere die Verwendung von 2-D-Netzwerken, die eine
Vermaschung für vollständige 2-D-Umordnung sowie
2-D-Verarbeitungsmodule mit vier Eingängen und vier Ausgängen
aufweisen. Lin und andere betrachten nicht die für die Erreichung
einer bestimmten Netzwerkvermaschung notwendige
Steuerungsstruktur, sondern weisen vielmehr darauf hin, daß
vollständige, 24-Cross-bar-Schalter prinzipiell eine
gewünschte Konfiguration erreichen können.
-
Aufgabe der Erfindung ist es, ein optisches
Vermaschungsnetzwerk anzugeben, das in seiner Struktur weniger komplex
als die bekannten 2-D-Netzwerke ist. Dementsprechend weist
ein optisches Vermaschungsnetzwerk zumindest eine Stufe
auf, die eine optische Vermaschungsstufe hat, die ein
zweidimensionales Feld von Vermaschungseingangsanschlüssen mit
einem zweidimensionalen Feld von
Vermaschungsausgangsanschlüssen verbindet; ein Feld von optischen
Verarbeitungsmodulen, von denen jedes ein zweidimensionales Feld von
Moduleingangsanschlüssen hat, die optisch jeweils mit
Vermaschungsausgangsanschlüssen verbunden sind, und ein
zweidimensionales Feld von Modulausgangsanschlüssen, dadurch
gekennzeichnet, daß jedes Modul funktional identisch ist mit
einem ersten und einem zweiten Paar von
Verarbeitungssubmodulen mit zwei Eingängen und zwei Ausgängen, wobei jeder
Eingang eines jeden zweiten Paars von
Verarbeitungssubmodulen mit einem jeweiligen Ausgang des ersten Paars von
Verarbeitungssubmodulen verbunden ist, und wobei die Eingänge
eines jeden zweiten Verarbeitungssubmoduls mit den
Ausgängen
aus verschiedenen ersten Verarbeitungssubmodulen
verbunden sind.
-
Das zweidimensionale Netzwerk kann unter Verwendung
optischer Einrichtungen zusammengebaut werden und weist dann
ähnliche Leistungsdaten wie vorher auf. Für die Anzahl der
Kanäle, die aufgenommen werden können, gibt es eine Grenze,
die proportional ist entweder zur Maximalbreite des
Modulelements oder zur Strecke, längs derer die optische
Einrichtung getreu abbilden kann. Liegt diese Grenze im Falle
eines eindimensionalen Netzwerks bei N, wird sie für ein
zweidimensionales Netzwerk N². Ein weiterer Vorteil eines
erfindungsgemäßen Netzwerks ist es, daß ein Netzwerk
gegebener Größe in zweidimensionaler Form wesentlich kompakter
aufgebaut werden kann.
-
Da die vorliegende Erfindung lediglich eine ausreichende
Anzahl von Verarbeitungselementen benötigt, die notwendig
sind, um die gleiche Verarbeitung wie die vier Submodule
auszuführen, vereinfacht sich die strukturelle Komplexität
im Vergleich zu der bisher für eine volle 4x4-Verarbeitung
benötigten, was später erläutert wird, es kann funktionell
identisch zu einer Verkettung der Verarbeitungsmodule eines
eindimensionalen Netzwerks sein und die gleiche
Steuerungsstruktur haben.
-
Die vorliegende Erfindung ermöglicht deshalb die Verwendung
einer eindimensionalen Netzwerksteuerungsstruktur mit einem
zweidimensionalen optischen Netzwerk.
-
Eine Ausführungsform der Erfindung wird nun beispielhaft
bezugnehmend auf die beiliegenden Zeichnungen beschrieben,
es zeigen:
-
Figur 1 ein schematisches, verallgemeinertes Diagramm
eines vorbekannten eindimensionalen Netzwerks,
-
Figur 2 ein schematisches Diagramm eines Austausch- und
Weiterleitungsmoduls, das in einem in Figur 1
gezeigten Vermaschungsnetzwerk verwendet wird,
-
Figur 3 ein schematisches verallgemeinertes Diagramm
eines zweidimensionalen erfindungsgemäßen
Vermaschungsnetzwerks,
-
Figur 4 ein schematisches Diagramm eines beispielhaften
eindimensionalen Netzwerks, das erfindungsgemäß
als zweidimensionales Netzwerk konfiguriert
werden kann,
-
Figur 5 ein schematisches Diagramm eines der Module der
erfindungsgemäßen Ausführungsform nach Figur 31
wenn die Funktionsweise des Netzwerks aus Figur 4
dargestellt werden soll,
-
Figur 6 ein schematisches Diagramm zur Darstellung der
funktionellen Gleichheit eines erfindungsgemäßen
zweidimensionalen Verarbeitungsmoduls zu vier
eindimensionalen Submodulen, und
-
Figur 7 ein schematisches Diagramm zur Darstellung der
Bedingung, unter der Stufen eines
eindimensionalen Netzwerks zur Bildung eines erfindungsgemäßen
zweidimensionalen Netzwerks verkettet werden
können.
-
Es wird nun auf Figur 1 Bezug genommen. Sie zeigt ein
verallgemeinertes, eindimensionales, vorbekanntes
Vermaschungsnetzwerk,
das drei Stufen S&sub1; - S&sub3; aufweist, von
denen jede eine eindimensionale Vermaschungsstufe 2 und eine
Schicht von Verarbeitungsmodulen 4 mit zwei Eingängen und
zwei Ausgängen hat. Genauso wie die von den Modulen
ausführbaren Funktionen können die Vermaschungen auf jeder
Stufe verschieden sein.
-
Die mit der obigen allgemeinen Beschreibung erfaßten
Netzwerke können zur Ausführung vieler
Parallelverarbeitungsaufgaben ausgelegt werden. Die häufigste Funktion ist es,
eine Anzahl von Datenströmen am Eingang zu haben und die
gleichen Datenleitungen am Ausgang in unterschiedlicher
Reihenfolge anzuordnen, wobei die Reihenfolge durch das
Setzen der Module bestimmt wird und die Vermaschungen
festgehalten werden. Solche Schaltnetzwerke haben üblicherweise
normale Vermaschungsmuster sowie Module, die sich, wie in
den Figuren 2a und 2b dargestellt, in einem von zwei
Zuständen befinden, in denen die zwei Eingangsleitungen
entweder ausgetauscht oder weitergeleitet werden. Es
existieren mehrere Netzwerke dieser Art, von denen jedes eine
Steuerungsstruktur hat, um das Setzen der Module zu
spezifizieren, um eine bestimmte Gesamtpermutation zu erhalten.
-
Andere Klassen von Computern sind möglich, wenn die Module
zusätzliche Verarbeitungen vornehmen. Wenn die Module UND-
Gatter oder ODER-Gatter sind, kann bei Verwendung von
Vermaschungen mit vollständiger Umordnung oder Butterfly-
Vermaschung ein programmierbares Logikfeld aufgebaut
werden. Eine Maschine für eine schnelle Fourier-Transformation
wurde vorgeschlagen, bei der die Vermaschungen vollständig
umordnen können und die Module Rechnungen für gewichtete
Summen und Differenzen ausführen. Diese und andere Vorgänge
können in einem optischen zweidimensionalen Netzwerk mit
der erfindungsgemäßen Konfiguration erreicht werden.
-
In Figur 3 ist ein erfindungsgemäßes zweidimensionales
optisches Vermaschungsnetzwerk in verallgemeinerter Form
dargestellt. Es weist drei Stufen 54 bis 57 auf, von denen
jede eine zweidimensionale Vermaschungsstufe 6 gefolgt von
einem zweidimensionalen Feld von Modulen 8 aufweist, wobei
jedes Modul ein zweidimensionales Feld von vier Eingängen
10 und vier Ausgängen 12 hat. Die Vermaschungen 6
permutieren die ankommenden Leitungen zweidimensional.
-
In Figur 4 ist ein bekanntes, eindimensionales
Vermaschungsnetzwerk gezeigt (D. E. Knuth "Sorting and
Searching: Addison Wesley (1973)), das beispielhaft zur
Erläuterung der Schritte verwendet wird, mittels derer ein
gegebenes eindimensionales Netzwerk in ein erf
indungsgemäßes zweidimensionales Netzwerk umkonfiguriert werden kann.
-
Das in Figur 4 gezeigte lineare Netzwerk ist ein
Sortiernetzwerk mit Vermaschungen 14, die eine vollständige
Umordnung darstellen, und Verarbeitungssubmodulen 16, von denen
nur einige beispielhaft der Klarheit wegen mit
Bezugsziffern versehen sind. Mehrere verschiedene Ziffern laufen
über Eingangsleitungen 15 ein; die mit Pfeilen versehenen
Module (16) geben die höhere Ziffer an dem Anschluß aus,
auf den gezeigt wird, nicht gekennzeichnete Module 16
leiten immer weiter. Die an den Ausgängen 17 auftretenden
Ziffern sind ihrer Größe nach von links nach rechts sortiert.
-
Eine Verrnaschung mit vollständiger Umordnung umfaßt das
Aufspalten des Leiterbündels in zwei Hälften, sowie deren
Verschränkung wie in Figur 5 gezeigt. Wenn die mit den vier
binären Bits abcd bezeichneten 2&sup4; Anschlüsse umgeordnet
werden, kann dies als Stellenverschiebung der binären
Adresse der Anschlüsse angesehen werden, es wird nämlich
der Eingangsanschluß, der mit abcd bezeichnet ist, auf den
Ausgangsanschluß mit der Adresse bcda umgeordnet. Wenn ein
Kanal an einem Modul am Anschluß abcd ankommt, kann er
entweder bei abc0 oder abc1 austreten, wobei der Ausgangskanal
davon abhängt, welcher Art das Modul ist und welche
Zieladresse der andere, am gleichen Modul ankommende Kanal hat.
-
Es wird nun der Pfadverlauf durch zwei aufeinanderfolgende
Stufen des Sortiernetzwerks betrachtet: Eine bei abcd
ankommende Leitung wird auf bcda umgeordnet, in einem Modul
(16 oder 18) ausgetauscht oder weitergeleitet auf bcdA,
wobei A entweder 0 oder 1 sein kann, abermals auf cdAb
umgeordnet und schließlich auf cdAB weitergeschaltet, wobei B
wieder 0 oder 1 sein kann.
-
abcd
-
bcda
-
bcdA
-
cdAb
-
Die Leitung hat somit die Wahl zwischen vier
Ausgangsadressen AB = 00, 01, 10 und 11. Genauso gibt es vier ankommende
Leitungen, die an diesen vier Leitungen auftreten könnten,
nämlich die von ab = 00, 01, 10 und 11. stammenden.
-
Es sei nun angenommen, daß die Leitungen im linearen Feld
im Raum in einem quadratischen Feld entsprechend der Regel
abcd -> (Spalte bd, Zeile ac) angeordnet sind.
-
Die Funktion der zwei Stufen des 1D-Netzwerkes kann durch
eine Stufe des in Figur 3 gezeigten 2D-Netzwerks ausgeführt
werden. Die neue Vermaschung ist eine 2D vollständige
Umordnung, die aus einer horizontalen vollständigen
Umordnung,
gefolgt durch eine vertikale vollständige Umordnung
besteht. Eine dieser Permutationen hat die Auswirkung
(bd, ac) -> (db, ca) , was zwei aufeinanderfolgenden 1D-
Umordnungen entspricht. Die Auswirkung der Module der zwei
aufeinanderfolgenden Stufen im linearen Netzwerk ist es,
die zwei Bits a und b in der Adresse festzuhalten. Ein
Modul im zweidimensionalen Netzwerk beeinflußt alle vier
Anschlüsse, die sich in den letzten Bits der Zeilen- und
Spaltenadresse, a und b, unterscheiden, so daß ein 4x4-
Modul die gleiche Tätigkeit ausführen kann wie alle
relevanten Module in den zwei Stufen des alten Netzwerks. Somit
wird durch Zuordnung der Leitungen aus einem 1D- auf ein
2D-Feld entsprechend der obigen Regel die Arbeit von zwei
Stufen des ursprünglichen Netzwerks durch eine Stufe des
neuen Netzwerks mit einer 2D vollständigen Umordnung
ausgeführt, so daß unter Verwendung dieser Regel ein
zweidimensionales Netzwerk aufgebaut werden kann.
-
Es wird nun die Wirkungsweise eines 2D-Moduls genauer
betrachtet. Jedes verbindet die Anschlüsse (d0, c0), (d0,
c1) , (d1, c0) und (d1, c1). Zunächst ist Bit a fest, dann
Bit b, so daß das Modul als aufgeteilt in vier Submodule
mit zwei Eingängen und zwei Ausgängen wie in Figur 6
gezeigt angesehen werden kann. Diese Submodule sind vier der
in Figur 4 gezeigten, im Raum angeordneten Module, und es
kann einfach hergeleitet werden, welche vier in jedem Modul
verbunden sind, indem die Zuordnungsregel verwendet wird.
Das 2D-Modul muß nicht physikalisch in die vier
2x2-Untermodule aufgetrennt werden, solange das Modul insgesamt
funktionell identisch mit der Verkettung der Submodule wie
in Figur 6 gezeigt ist.
-
Die Austausch/Weiterleitungsentscheidungen des
ursprünglichen Netzwerks erzeugen eine sortierte Ausgabe des
Netzwerks,
wohingegen bei der Ausgabe des äquivalenten 2D-
Netzwerks der Kanal mit der n-ten Zieladresse an dem
Anschluß liegt, der dem Anschluß n im linearen Feld
zugeordnet werden kann. Dieses Vertauschen der Leitungen ist
vorweg vollständig bestimmt und ist von der Funktion her
unwichtig; wenn es notwendig ist, die Sortierung in eine
sichtbare Form zu bringen, können die Zieladressen am
Anfang modifiziert werden oder es können genausogut die
Module entsprechend den umgekehrt zugeordneten Adressen gesetzt
werden.
-
Weiter oben wurde ein einzelnes, zweidimensionales Netzwerk
erläutert. Der Ausgangspunkt war ein eindimensionales
Netzwerk. Es wird nun betrachtet, ob und wenn ja, wie ein
beliebiges zweidimensionales erfindungsgemäßes Netzwerk
unabhängig von der Funktion und den Modulen und den
Vermaschungsmustern aus einem linearen Netzwerk konstruiert
werden kann.
-
Analog zur Behandlung des obigen Netzwerks mit
vollständiger Umordnung können zwei aufeinanderfolgende Stufen in
einer Stufe eines 2D-Netzwerks verkettet werden, indem die
Module als im Raum verschoben angesehen werden. Es kann für
eine Vermaschung gefolgt von einer Schicht von 4x4-Modulen
nicht möglich sein, die Arbeit von zwei eindimensionalen
Stufen mit einer Vermaschung, einem 2x2-Modul als
Vermaschung und einer abschließenden 2x2-Modulfolge zu
übernehmen. Unabhängig von der Funktion der Module in Fig. 2 ist
es (nun bezugnehmend auf Figur 7) bekannt, daß die
Zwischenmodulausgabe X' eine Funktion von X und Y ist.
-
X' = X' (X, Y)
-
genauso gilt für die drei anderen Zwischenausgaben
-
= Y' (X, Y)
-
= W' (W, Z)
-
= Z' (W, Z)
-
Die endgültigen Modulausgänge X" und Z" sind Funktionen von
X' und Z'
-
X" = X" (X', X')
-
Z" = Z" (X', Z')
-
so daß gilt
-
X" = X" (X, Y, Z, W)
-
Z" = Z" (X, Y, Z, W)
-
Damit die Funktionen X" und Z" durch ein zweidimensionales
Verarbeitungsmodul mit vier Eingängen und vier Ausgängen
berechnet werden kann, ist es für die anderen zwei Ausgänge
Y" und W" notwendig, daß sie Funktionen der gleichen vier
Eingänge sind
-
Y" = Y" (X, Y, Z, W)
-
W" = W" (X, Y, Z, W),
-
was nur erreicht werden kann, wenn sich die
Zwischenergebnisse Y' und W' an einem gemeinsamen Modul treffen.
-
Y" = Y" (Y', W')
-
W" = W" (Y', W')
-
Dies führt zu einer Nebenbedingung der zweiten Vermaschung
in Figur 7, die wie folgt ausgedrückt werden kann
Das Gegenstück einer aus einem Modul austretenden
Leitung wird als die andere aus diesem kommende
Leitung definiert. Für zwei beliebige Leitungen, die die
zwei Eingänge eines Moduls sind, müssen sich deren
Gegenstücke auch an einem gemeinsamen Modul treffen.
-
Wenn eine Vermaschung diese Bedingung nicht erfüllt, ist es
nicht möglich, die aufeinanderfolgenden Stufen in Figur 7
in funktionell identische Einzelstufen eines
zweidimensionalen erfindungsgemäßen 4x4-Moduls zu verketten.
-
Prinzipiell ist es für ein die obengenannte
Vermaschungsbedingung erfüllendes Netzwerk immer möglich, die Leitungen
in der linearen Anordnung aus Figur 1 aufzunehmen und sie
in ein zweidimensionales Feld wie in Figur 3 gezeigt zu
bringen. Zur Durchführung dieser Zuordnung gibt es viele
Wege, gewunscht wird jedoch eine 2D-Vermaschung, die durch
eine einfache optische Anordnung erhalten werden kann. Ein
Beispiel ist die besondere Zuordnung, die auf das Netzwerk
mit vollständiger Umordnung angewendet wird. Wenn eine
erfolgreiche Zuordnungsregel gefunden werden kann, ist die
Aufgabe des Erzeugens eines 2D-Netzwerks aus seinem
linearen Gegenpart erfüllt.