-
Die Erfindung bezieht sich im allgemeinen auf eine Datenbanksuche
und im speziellen auf ein Verfahren zum Suchen einer assoziativen
Matrix.
-
Eine Methode um nach verwandten Objekten zu suchen unter Verwendung
eines assoziativen Matrixrechners ist in "Proceedings of Compcon.
Spring 1981, IEEE Computer Soc. Press, 1981" in einem Artikel mit
der Überschrift "Utilizing Associative Array Devices in a Data Base
Computer Design" von E.J. Olivier beschrieben. Bei dieser Methode,
um nach verwandten Objekten zu suchen, wird ein assoziativer
Matrixrechner, bestehend aus einer Vielzahl programmierbarer
Matrixen von Verbindungen verwendet, um nach der Existenz von und
der Verwandschaft zwischen verschiedenen formen von Namen zu
suchen, die in verschiedenen Datenspeichern des Prozessors
gespeichert sind.
-
Die meisten Computeranwendungen beinhalten die Suche einer
Zusammenstellung von Daten für Abschnitte die eine spezielle
Charakteristik haben, wie das Anpassen eines speziellen
Schlüsselfeldes oder eine spezifische Vorlage von Datenwerten.
Beispiele von dieser Art von Operationen beinhalten die Suche in
einer Datenbank mit Kreditkartennummern zum Auffinden des Status
einer speziellen Karte, die Suche in digital kodierten Bildern zum
Auffinden von Bildelementen die ein Muster anpassen, Suchen einer
Datenbank von Komponenten und Verbindungen in einer elektronischen
Schaltung zum Auffinden eines Stromkreises zwischen zwei
Komponenten und Suchen eines sprachverarbeiteten Dokuments um einen
speziellen Text zu finden. Seitdem Suchen ein Teil der meisten
Computeranwendungen ist, ist die Geschwindigkeit mit der die Suche
ausgeführt werden kann der wichtigste Faktor der darauf Einfluß
nimmt wie schnell die Computeranwendung auszuführen ist.
-
Assoziative Matrixen sind Datenstrukturen bestehend aus Knoten und
Verbindungen, die die Knoten untereinander verbinden. Die
Verbindungen verbinden in einer Richtung, aber zwei Knoten können
zwei Verbindungen haben, einen in jede Richtung. Es wird
vorausgesetzt, daß alle Verbindungen die gleichen "cost" oder
"weight" haben. Im allgemeinen kann eine assoziative Matrix zur
Speicherung der Verhältnisse zwischen Zuständen oder Komponenten
benutzt werden, wobei die Achsen der Matrix vordefinierte
Verhältnisse repräsentieren. Ein spezielles Beispiel einer
möglichen Benutzung einer solchen assoziativen Matrix könnte zur
Darstellung von Verbindungen zwischen Komponenten digitaler,
elektronischer Schaltungen sein. Eine andere assoziative Matrix
würde dann für jede Art von Signal in dem System benutzt.
-
Andere mögliche Benutzungen von assoziativen Matrixen können die
Darstellung von Hierarchien von Komponenten sein, bei denen eine
Komponente aus einer Vielzahl von anderen besteht, sogenannte
"objekt inheritence"-Netzwerke in objektorientierter
Computerprogrammierung und die Darstellung von planaren Schnitten durch
dreidimensionale Objekte, wobei alle Teile des Objektes in einer
Ebene miteinander verbunden sein sollen.
-
Die wichtigsten Suchoperationen die häufig mit diesen assoziativen
Matrixen ausgeführt werden, sind:
- Finden aller der Komponenten die mit einer gegebenen
Komponente verbunden sind;
- ob ein Pfad zwischen zwei Komponenten existiert;
- welche Komponenten von einer gegebenen Komponente aus mit
einer bestimmten Anzahl von Verbindungen erreicht werden
können;
- Auffinden aller Komponenten die eine neue Komponente
bilden; und
- Auffinden aller Komponenten von denen eine andere
Komponente einen Teil bildet.
-
Mit konventionellen Architekturen ist dieses Problem in einem von
zwei Wegen gelöst. Erstens, alle Verbindungen zu einem gegebenen
Knoten müssen als eine verbundene Liste die an dem Punkt startet,
gespeichert werden. Dies ermöglicht ein gutes Funktionieren zum
Auffinden aller Knoten die mit einem gegebenen Knoten verbunden
sind, hat aber auch einen hohen Bedarf an Speicherplatz wenn die
Anzahl an Verbindungen relativ groß ist.
-
Zum Beispiel, wenn jeder von 1000 Knoten mit 100 anderen Knoten
verbunden ist und ein 32 Bit Zeiger für jede Verbindung benutzt
wird, werden 32 Megabit Speicher benötigt für die Verbindungen.
Zusätzlich ist das Auffinden von allen Komponenten die von einer
anderen Komponente aus erreicht werden können sehr langsam und
benötigt häufige Schichtungsoperationen.
-
Zweitens kann die Verbindung zwischen Komponenten oder Knoten in
einer rechtwinkeligen Matrix von Bits gespeichert werden, wobei die
Achsen der Matrix die Komponenten oder Knoten repräsentieren und
das Setzen der Bits zu 1 in einem Zeilen/Spalten Schnittpunkt
anzeigt, daß die zwei korrespondierenden Knoten oder Komponenten
verbunden sind. Diese Anwendung ist ökonomisch für Speicherplatz,
ist aber üblicherweise sehr langsam bei konventionellen
Prozessoren, weil das Auffinden oder Testen einzelner Bits aus
einem Wert heraus häufig viele Instruktionen benötigt und wiederum
viele solcher Operationen werden benötigt zum Suchen der Matrix.
-
Die vorliegende Erfindung versucht eine Methode zum Suchen einer
assoziativen Matrix mit einer erhöhten Geschwindigkeit zur
Verfügung zu stellen.
-
Gemäß der vorliegenden Erfindung wird ein Verfahren zum Suchen nach
verwandten Objekten unter Verwendung eines assoziativen
Matrixrechners vorgeschlagen, dadurch gekennzeichnet, daß jedes Objekt
durch eine Reihe und eine Spalte einer assoziativen Matrix von dem
Rechner dargestellt ist, wobei der Rechner eine Matrix von
Ein-Bit-Rechner-Zellen enthält, die zu Reihen und Spalten verbunden
sind und die Ein-Bit-Register enthalten und Datenspeicher und der
die Verhältnisse zwischen den Objekten speichert, wobei jedes
Verhältnis vordefiniert und mit einer der Achsen der Matrix assoziiert
wird, was durch eine logische 1 im Schnittpunkt der Reihe des einen
Objektes mit der Spalte des anderen Objektes angezeigt wird, und
weiterhin bestehend aus den Schritten der Identifikation der
Reihen- und Spaltenposition eines ausgewählten Objekts um in der
assoziativen Matrix gesucht zu werden, und simultane Suche aller
Reihen in der Spalte die mit dem ausgewählten Objekt identifiziert
wurden oder simultane Suche aller Spalten in der Reihe die mit dem
ausgewählten Objekt identifiziert wurden, um ein vorbestimmtes
Verhältnis zwischen dem ausgewählten Objekt und den anderen
Objekten zu identifizieren, wobei die simultane Suche aller Reihen in
einer identifizierten Spalte oder aller Spalten in einer
identifizierten Reihe durch den Einsatz einer vertikalen oder
horizontalen Maske welche die Operation des assoziativen
Matrixrechners auf eine oder mehr ausgewählte Spalten oder eine oder mehr
ausgewählte Reihen von der Matrix beschränkt und eine Statusanzeige
die mit dem Ein-Bit-Register der Zellen verbunden ist, um während
der Suchoperation als eine Maske für folgende Instruktionen zu
dienen.
-
Die simultane Suche der Reihen und Spalten trägt zu der Erhöhung
der Suchgeschwindigkeit bei.
-
Das Herausbilden der Verwandtschaft aus der Matrix erfolgt schnell
und leicht mittels des Rechners, indem die horizontalen und
vertikalen Masken, die den Suchmechanismus kontrollieren, manipuliert
werden.
-
Zum leichteren Verständnis der Erfindung und seiner verschiedenen
anderen vorteilhaften Ausgestaltungen, werden einige
Ausführungsbeispiele anhand der folgenden Figuren erläutert. Folgende Figuren
zeigen:
-
Fig. 1 Schematische Darstellung eines assoziativen
Matrixrechners,
-
Fig. 2 Blockschaltbild eines assoziativen Matrixrechners,
-
Fig. 3 Zellenverbindung in einer Matrix,
-
Fig. 4 Layout für ein Indexfile,
-
Fig. 5 Zustandsdiagramm eines assoziativen Matrixrechners in
einem Punkt während der Suche,
-
Fig. 6 Zustandsdiagramm eines assoziativen Matrixrechners in
einem Punkt während der Suche,
-
Fig. 7 Vereinfachte assoziative Matrix,
-
Fig. 8 Verzeichnis und assoziative Matrix für eine 16·16 Mitmatrix
mit einem Verzeichnis von 10 Seiten,
-
Fig. 9, 10, 11a, 11b, 12, 13, 14a und 14b
zeigen verschiedene Zustände eines assoziativen
Matrixrechners zu verschiedenen Zeitpunkten während der
Ausführung einer Suche.
-
Die vorliegende Erfindung beschreibt ein Verfahren zum Suchen einer
assoziativen Matrix mit Benutzung assoziativer Suchtechniken. Die
Methode ist entworfen worden zur Benutzung eines speziellen Typs
von Rechner, einem als Assoziativrechner bekannten Rechners. Ein
Rechner vom Typ eines assoziativen Rechners stellt die
Eigenschaften zur Verfügung, die nötig sind um die in dieser Erfindung
beschriebenen zu erreichenden assoziativen Suchtechniken zur
Verfügung zu stellen. Ein assoziativer Rechner, mit der die
vorliegende Methode ausgeführt werden kann, ist in der
US-Patentanmeldung, No. 404,242, angemeldet am 2. August 1992, beschrieben,
deren Anmeldung zusammen mit dieser Anmeldung an einen gemeinsamen
Zessionar übertragen wurde. Zur Ausführung des Verfahrens der
vorliegenden Erfindung muß der assoziative Rechner verschiedene
wichtige Eigenschaften haben. Der assoziative Rechner muß aus einer
Matrix geformt sein, die weitgehend als assoziativer Matrixrechner
bekannt ist oder als AAR (associative array processor) und wie
Fig. 1 als schematische Darstellung eines Beispiels zeigt. Die AAP
28 stellt eine Form von sequentieller Verarbeitung zur Verfügung,
bei welcher eine einzelne sequentielle Kontrollinstruktion 30
simultan die gleiche Berechnung von vielen Elementen von Daten
ausführt.
-
Die AAP ist gebildet aus einer rechteckigen Matrix 32 mit separaten
einzelnen Ein-Bit-Rechnerzellen 34. Jede Rechnerzelle 34 beinhaltet
seine eigene arithmetische, logische Einheit
(ALU = arithmetic-logic-unit), einen Satz von vielen
Ein-Bit-Registern und einen Datenspeicher 36 zur Speicherung von
einer Vielzahl an Bits von Informationen, so zum Beispiel 64 kBits.
Die korrespondierenden Ein-Bit-Register für die verschiedenen
Zellen bilden Register für die AAP.
-
Die Zellen der Matrix sind unterteilt in Reihen und Spalten, so daß
Zellen in einer Reihe mehrfach Bitdatenelemente verarbeiten können
und daß Daten vertikal zwischen den Reihen übergeben werden können.
-
Ein Mittel ist vorgesehen, um die Begrenzungen von Datenelementen
festzustellen und dies kann vorgenommen werden, indem spezielle
Bits in einer Reihe als das signifikanteste und das am wenigsten
signifikante Bit festgestellt werden. Die Größe der Datenelemente
in jeder Reihe muß innerhalb der Matrix nicht gleich sein,
besonders dann, wenn die Matrix für Datenbasis-Anwendungen
verwendet werden, die verschiedenen Datenelemente verschiedene
Bereiche von Werten und Größen benötigen. Wie bereits zuvor erwähnt
folgen alle Zellen innerhalb der Matrix derselben Instruktion; es
muß ebenfalls möglich sein sowohl Reihen als auch Spalten von
Zellen zu maskieren oder arbeitsunfähig zu machen, damit die Zellen
nicht den Instruktionen folgen.
-
Wenn ein Datenelement in Position und Größe definiert wurde, dann
kann der ganze Inhalt des Ein-Bit-Registers verbunden mit jedem
Ein-Bit-Rechner innerhalb dieser speziellen Datenelementposition
arithmetische, verschiedene oder boole'sche Instruktionen zwischen
ihnen ausführen. Das Ergebnis solcher Instruktionen wird nicht nur
die arithmetischen oder logischen Ergebnisse beinhalten, sondern
auch einen geeigneten Statusindikator wie Überlauf für das
Hinzufügen oder das Wegnehmen, Null für Gleichheit, Plus für das
Vergleichen größer als, Minus für das Vergleichen kleiner als,
etc. Beides, das Ergebnis und der geeignete Indikator, werden als
eine Maske für folgende Instruktionen zur Benutzung zur Verfügung
gestellt.
-
Es gibt einen vertikalen Bus für jede Spalte, um eine Kommunikation
zwischen den Zellen der Spalte und einer externen
Ausgabe-Register-Zelle zur Verfügung zu stellen. Der vertikale Bus
ist so ausgelegt, daß nur eine Zelle zu jedem Zeitpunkt übermittelt
werden kann. Die Auswahl dieser Zelle wird von Mitteln des
Maskenmechanismus, der oben beschrieben wurde, vorgenommen.
-
Adressen zum Holen von Daten aus den Speicherbits werden in einem
Speicheradressenregister generiert. Es ist möglich, Daten von dem
Ausgaberegister zu dem Adressenregister zu übermitteln. Es gibt
auch ein Eingaberegister, um Werte zum Laden in die Matrix zu
beinhalten, oder um Werte, die für die Suche oder den Vergleich
benutzt werden, zu beinhalten. Die Werte die in diesem
Eingaberegister gespeichert sind, werden für alle Reihen zur
Verfügung gestellt, in den geeigneten Spalten gleichzeitig, so daß
simultane Suche oder Vergleich in allen Reihen stattfinden kann,
oder der Inhalt des Eingaberegisters zu allen möglichen Reihen
übermittelt werden kann.
-
Eine Konfiguration, die die genannten Merkmale beinhaltet, ist in
der Fig. 2 dargestellt. Eine Matrix von Zellen ist dargestellt als
202 und hat damit verbunden einen Speicher für jede Zelle, wie
bereits in Fig. 1 gezeigt wurde.
-
Die Verbindung-zwischen einer Zelle und der benachbarten Zelle ist
in Fig. 3 gezeigt. Die Verbindung zwischen Zellen in einer Spalte
sind gezeigt als 302 und 304, während die Verbindung zwischen
Zellen in einer Reihe als 321 bis 326 dargestellt sind. Die
Funktion der horizontalen Verbindungen 321 bis 326 zwischen Zellen
in einer Reihe sind vollständig beschrieben in der U.S.
Patentanmeldung mit der Nummer No. 404,242, die bereits vorher
zitiert wurde. Jede Zelle hat eine Verbindung 312 zu einer
vertikalen Maske und eine Verbindung 314 zu einer horizontalen
Maske. Ein vertikaler Bus 316 ist ebenfalls vorgesehen, um Daten
vertikal zwischen Zellen und dem Ausgaberegister 214 und von dem
Eingaberegister 206 zu den Zellen in einer Spalte zu übermitteln,
während Daten horizontal zwischen Zellen in einer Reihe und dem
horizontalen Daten/Status-Register 208 mittels des horizontalen
Busses 318 übermittelt werden.
-
Nochmals bezugnehmend auf Fig. 2 ist dort ein vertikales
Maskenregister 204 gezeigt, worin jede Bitposition des Registers
mit der vertikalen Maskenverbindung 312 von jeder Zelle der
korrespondierenden Spalte der Matrix verbunden ist. Das vertikale
Maskenregister 204 stellt die zuvor diskutierten vertikalen
Maskenfunktionen zur Verfügung und stellt zusätzlich die Mittel zur
Identifizierung der Grenzen der Datenelemente, in der Weise wie in
der U.S. Patentanmeldung No. 404,242 beschrieben, zur Verfügung.
Ein horizontales Maskenregister 210 stellt die horizontalen
Maskenfunktionen zur Verfügung und besitzt eine Vielzahl von
Bitpositionen die alle mit der Leitung 314 von jeder Zelle der
korrespondierenden Reihe der Matrix 202 verbunden sind. Wenn die
zuvor beschriebenen arithmetischen Instruktionen ausgeführt werden,
müssen die Statusanzeigen, die abhängig sind von den Ergebnissen
von den Daten aus jeder Reihe, erhalten werden, übertragen werden
und gespeichert werden. Dies ist möglich bei Benutzung des
horizontalen Busses 318, um die Statusanzeigen zu den
korrespondierenden Bitpositionen von einem horizontalen
Datenregister 208 zu übertragen, wo sie gespeichert werden können.
Das horizontale Datenregister kann also ebenfalls Statusregister
genannt werden. Das horizontale Datenregister 208 wird dann über
die Verbindung 212 mit dem horizontalen Maskenregister 210
verbunden, welches die Statusanzeigen der arithmetischen Anzeigen
als horizontale Maske zur Verfügung stellt. Der vertikale Bus 316
verbindet die korrespondierenden Bits eines vertikalen
Dateneingaberegisters 206 mit allen Zellen in einer Spalte und
verbindet ebenfalls alle Zellen der Spalten mit den
korrespondierenden Bits eines Datenausgaberegisters 214. Daten aus
dem Ausgaberegister 214 können mittels Mittel zur Verbindung 218 zu
einem Adressenregister 216 übertragen werden. Die Funktion des
Ein- und Ausgaberegisters kann in einem Eingabe/Ausgabe-Register
kombiniert werden.
-
Die Arbeitsweise des AAP, der zuvor beschrieben wurde, und in den
Fig. 2 und 3 gezeigt wird, kann mit Hilfe eines einfachen
Beispiels besser verstanden werden. Angenommen, wir haben ein
Indexfile und angenommen, daß jeder Datensatz oder jede Reihe
Datenelemente A, B, C beinhaltet, von denen einige oder alle
benutzt werden können, um einen speziellen gespeicherten Datenblock
zu erkennen, und daß in dem File ein Zeiger zu dem Ort des
gespeicherten Datenblocks hinweist. Ein vorgeschlagenes Format für
das Indexfile ist in Fig. 4 gezeigt. Angenommen, ein 16·16 Matrix
wird benutzt, dann werden 3 Seiten des Matrixspeichers 16
Datensätze mit dem gezeigten Format beinhalten.
-
Seite 1 identifiziert als 38 enthält Datenelemente A, von denen
jedes 16 Bits für 16 Datensätze hat und eine Reihe für jeden
Datensatz und eine Spalte für jedes der 16 Bits von Information in
den Datenelementen A. Seite 2 gekennzeichnet als 40 beinhaltet
Datenelemente B und C für jeden der 16 Datensätze, wobei die
Datenelemente B 10 Bits beinhalten und die Datenelemente C 6 Bits.
Seite 3 gekennzeichnet als 42 wird 16 Zeiger beinhalten, einen für
jeden der 16 Datensätze der gespeicherten Datenblöcke.
-
Angenommen, eine Seite von dem Index wird durchsucht nach einem
Wert 25 im Datenelement B oder Feld B, gezeigt als Teil von Seite
2, und daß nur ein Datensatz der Seite diesen Wert enthält. Es muß
festgehalten werden, daß die zu suchenden Werte (Feld B) in keiner
speziellen Reihenfolge sein müssen. Die Abfolge beschrieben in
Abhängigkeit von den Fig. 5 und 6 ist folgendermaßen:
-
1. Die Adresse der Seite 2 wird in das Adressenregister 216
geladen, wie in Fig. 5 gezeigt wird, und die Felder B und C
von den 16 Datensätzen die auf Seite 2 gespeichert sind, werden
als Speicher für ein Register, zum Beispiel Register 1, von dem
Satz von Registern verbunden mit jeder Zelle der Matrix 202,
wie gezeigt in Fig. 2.
-
2. Der zu suchende Wert, z. B. 25, wird in die signifikantesten 10
Bits des Dateneingaberegisters geladen und eine Maske, die die
signifikantesten 10 Bits der Matrix bereitstellt, z. B.
korrespondierend zu Feld B, wird in das vertikale
Maskenregister 204 geladen.
-
3. Eine Suche wird unter den 16 Datenwerten in Feld B nach dem
Eingabedatenwert 25 angeführt. Die Reihe 9 in dem Beispiel,
welche den Wert 25 enthält, paßt zu dem gesuchten Wert 25 und
dies wird durch eine 1, welche in der korrespondierenden
Bitposition in dem horizontalen Datenregister 208, welches
ebenfalls Statusregister genannt wird, angezeigt.
-
4. Das Adressenregister 216 wird in die Adresse der Seite 3
gewechselt, die die Zeiger enthält, die Zeiger der Seite 3
werden genommen und in einem Register, zum Beispiel Register 2,
aus dem Satz von Registern, gespeichert.
-
5. Eine Maske mit allen Einsen wird in das vertikale
Maskenregister 204 geladen, um alle Spalten der Matrix bereit
zu stellen und der Inhalt des Statusregisters 208 wird zu dem
horizontalen Maskenregister übermittelt. Der Zustand zu diesem
Punkt des Prozesses ist in Fig. 6 gezeigt.
-
6. Der spezielle Zeiger P9, gefunden in Reihe 9, ist von dem
horizontalen Maskenregister 210 bereitgestellt und wird über
den vertikalen Bus 316 zu dem Ausgaberegister 214 (siehe Fig.
2) übertragen und von dort aus zu dem Adressenregister. Diese
Adresse kann nun benutzt werden, um die erste Seite des
gespeicherten Datenblocks zu nehmen, der mit dem in dem Index
gefundenen Eingang 25 korrespondiert.
-
Das Verfahren der vorliegenden Erfindung benutzt die Vorteile der
assoziativen Suchmerkmale des zuvor beschriebenen AAP's.
-
Wie bereits vorher erwähnt, benutzt diese Methode zwei Typen von
Datenstrukturen. Um die Position der gewünschten Beziehungen von
Informationen in der Assoziationsmatrix zu lokalisieren, können
verschiedene Typen von Indexmechanismen benutzt werden. Wir haben
ein Verzeichnis zur Benutzung ausgewählt, welches lediglich eine
Aufzählung von Zuständen oder Komponenten ist, die repräsentiert
werden von Reihen und Spalten der Matrix. Die Reihenfolge in der
diese Zustände oder Komponenten gespeichert sind und die Methoden,
mit welcher ein spezieller Zustand gefunden wird oder neue
Zustände, die hinzugefügt werden, sind keine grundlegenden
Eigenschaften von dieser Erfindung. Jede aus dem Stand der Technik
bekannte Methode kann verwendet werden. In dem Verzeichnis- wird
sich keine Information bezüglich der Beziehung von Zuständen oder
Komponenten zueinander befinden, aber die Verzeichniseingänge
können Informationen wie die Identität von den Komponenten oder
Zuständen beinhalten. So kann das Verzeichnis zum Beispiel
lediglich eine Liste von numerierten Komponenten sein. Die
Komponenten können in der Matrix gefunden werden, indem in der
Matrix nach der Reihe und Spalte mit der gleichen Nummer gesucht
wird.
-
Die Definition der Art von Beziehung die zwischen Komponenten oder
Zuständen existiert und die Art wie diese Beziehung gespeichert
werden sollte, kann vordefiniert werden. Fig. 7 repräsentiert eine
Matrix für ein Verzeichnis mit 8 Komponenten oder Zuständen. Die
Asoziationsmatrix, gezeigt in Fig. 7, illustriert, wie Beziehungen
von Informationen gespeichert werden können. Zwei Typen von
Assoziationen, Verknüpfungen oder Beziehungen können gespeichert
werden. Eine ist die spaltenweise Beziehung und die andere ist die
reihenweise Beziehung. Diese Beziehungen werden vor dem Besetzen
der Matrix vordefiniert.
-
Als ein Beispiel wird die Matrix so eingerichtet, um hierarchische
Beziehungen von Komponenten zu beinhalten, worin eine Komponente
aus anderen Komponenten besteht und ein Teil anderer Komponenten
ist. Die Beziehungen werden von den Achsen der Matrix
repräsentiert. Die spaltenweise Beziehung kann definiert werden
als: alle Komponenten die "bestehen aus" oder "bilden" die
Komponente identifiziert durch die Spalte. Sollte jemand alle
Komponenten, die einen Teil der Komponenten C3 darstellen, zu
finden wünschen, würde er nach jedem Satz von Bits von dem einen
Level in der dritten Reihe unter C3 suchen und er würde
herausfinden, daß C3 aus den Komponenten C2 und C7 besteht. Ebenso
besteht C1 aus C3 und C6, C5 besteht aus C2 und C8, C6 besteht aus
C2, und C8 besteht aus C7. Die Komponenten C2, C4 und C7 sind die
Grundelemente, weil sie aus keiner anderen Komponente bestehen wie
gezeigt wird dadurch, daß die Spalten C2, C4 und C7 alle Nullen
beinhalten.
-
Die reihenweise Beziehungen kann so definiert werden: alle
Komponenten die "ein Teil von" höheren Komponenten sind. Eine Art,
um diese Beziehung einzuführen, kann in der reihenweisen Art
ausgeführt werden. Eine Suche nach der zweiten Reihe zeigt, daß C2
in den Komponenten C3, C5 und C6 benutzt wird. Zusätzlich, bei der
Ausführung der reihenweisen Suche nach diesen Komponenten, sehen
wir, daß C3 und C6 in C1 benutzt werden, während C7 ein Teil von C3
und C8 ist, und C8 ein Teil von C5 ist.
-
Dieser iterative Suchmechanismus kann jederzeit in jeder Richtung
ausgeführt werden und der Mechanismus ist aufgebaut durch die
Manipulation von Masken für die Reihen und Spalten. Die
Identifikation der Zeilen und Spaltenwerte ist eine Aufgabe, die
später diskutiert werden wird, aber die Wichtigkeit sollte auf
einem viel höheren Level verstanden werden, weil es eine wichtige
Rolle in der Suche bei sehr großen Datenbanken spielt.
-
Ein Beispiel der Suche in einer großen Reihe kann mit Hilfe des
Diagrammes in Fig. 8 erklärt werden. In dem Fall wurde willkürlich
entschieden, eine 16·16 Bit Matrix zu benutzen; dennoch kann jede
Konfiguration von Bits benutzt werden. Angenommen, diese
Konfiguration besteht, so ist das physikalische Layout des
Verzeichnisses von Zuständen und die Darstellung der Beziehungen
zwischen diesen Zuständen gezeigt. Zur Vereinfachung wird
angenommen, daß eine Wortgröße 16 Bits ist, und daß die Anzahl der
Seiten in dem Verzeichnis 10 beträgt. Für das Beispiel wird eine
lineare Suchmethode empfohlen. Die assoziativen Merkmale des AAP's
erlauben es die Eingänge in beliebiger Reihenfolge anzuordnen. Für
den Fall, daß die vorzunehmende Aktion ist, alle Beziehungen einer
Komponente C20 zu allen anderen Komponenten aufzufinden, dann wird
die Abfolge von Vorgängen beinhalten:
-
1) Suchen in dem Verzeichnis nach der Position der Komponente, die
von einem Knoten in der Assoziationsmatrix repräsentiert wird,
-
2) Setzen der entsprechenden Masken zur Manipulation der in der
Assoziationsmatrix gespeicherten Daten,
-
3) Durchsehen der Assoziationsmatrix nach diesen Beziehungen.
-
Wenn C20 in der fünften Reihe auf der fünften Seite in dem
Verzeichnis gefunden wird, muß, um alle Komponenten, die C20
bilden, zu finden, eine Suche der Spalten 5 über die Seiten 5, 15,
25, 35, 45, 55, 65, 75, 85 und 95 in der Assoziationsmatrix
durchgeführt werden. Ähnlich, zum Auffinden aller Komponenten von
denen C20 ein Teil ist, wird die Suche in den fünften Reihen der
Seiten 51 bis 60 durchgeführt. Sollten tiefergehende Level von
Informationen gewünscht sein, wird das Durchsuchen der Matrix
durchgeführt, indem weitere Manipulationen der Masken, die von den
Bits gesetzt werden, die während dem ersten Durchsuchen als aktive
Bits gefunden wurden, durchgeführt werden.
-
Zur Vereinfachung werden wir die Schritte der Implementierung der
oben beschriebenen Suchmechanismen lediglich für eine Seite in
einem Verzeichnis bezogen auf den AAP-Instruktionssatz beschreiben.
Suchen des Verzeichnisses
-
Eine lineare Suchmethode kann benutzt werden zum Suchen eines
ungeordneten Verzeichnisses, worin eine Komponentenidentifikation
willkürlich gespeichert ist. Bei gegebenen Parametern, ist der
Ablauf der Suche nach einer Komponente C20 in einem Verzeichnis
folgendermaßen:
-
1. Ein die Komponente C20 repräsentierender Wert wird in das
Eingaberegister 206 geladen. Die horizontalen und vertikalen
Maskenregister 210 und 204 sind gesetzt, um alle Reihen und
Spalten zur Verfügung zu stellen. Die Adresse der ersten Seite
im Speichel wird zu dem Speicheradressenregister 216 gesendet,
und Seite 1 des Verzeichnisses wird in die Matrix gebracht und
wird in einem Register gespeichert, wie zum Beispiel Register
1, gezeigt in Fig. 9.
-
2. Ein paralleler Vergleich oder Subtraktion zwischen dem
Eingaberegister 206 und dem Register 1 wird ausgeführt, wobei
die resultierende Statusanzeige für jede Reihe in dem
korrespondierenden Bit des Statusregisters 208 gespeichert
wird. Eine 1 in dem Statusregister bedeutet, daß etwas
passendes gefunden wurde, während eine 0 bedeutet, daß nichts
passendes gefunden wurde.
-
Der Inhalt des Statusregisters 208 wird dann getestet, um
festzustellen, ob irgendwelche Bits aktiv sind, z. B. 1. Falls
nicht, wird dann die Adresse der nächsten Seite generiert und der
zuvor erläuterte Ablauf wird wiederholt. Die Zustände der Register
der obigen Funktion sind in der Fig. 9 gezeigt, und zeigen ein
Passendes in dem Statusregister 208 in Reihe 5.
-
Die Position des passenden Zustandes innerhalb des Verzeichnisses
ist der wesentliche Faktor um die Assoziationsmatrix zu
manipulieren, die die Beziehungen zwischen den Komponenten
speichert. Wenn z. B. die fünfte Reihe der fünften Seite mit C20
zusammenpaßt, würde das Bit des Statusregisters, das korrespondiert
mit der fünften Reihe, eine 1 beinhalten, wenn die fünfte Seite
gesucht wird.
-
Ebenso wird normalerweise der Inhalt des Maskenregisters benutzt,
um Reihen oder Spalten der Matrix in die Lage zu versetzen, die
Suche in der Matrix durchzuführen, wobei es eine Alternative ist,
eine logische AND Operation zwischen einem Bereich von Daten, die
eine Reihe von Einsen (oder eine Spalte in Abhängigkeit von der Art
von Suche) beinhalten, durchzuführen, wobei die Reihe von Einsen
korrespondiert mit der Reihe (Spalte), die von der Maske
bereitgestellt wird. Der Vorteil dieser Alternative ist, daß dieses
Muster auf einer Seite des Hauptspeichers gesichert werden kann, um
es bei späteren Operationen zu benutzen.
-
Die horizontale Masse kann wie folgt erstellt werden. Der Inhalt des
Statusregisters 208 wird in das horizontale Maskenregister 210
geschoben, wobei nur die fünfte Reihe in die Lage versetzt wird,
der nächsten Instruktion zu antworten. Eine Reihe von allen Einsen
wird in das Eingaberegister 206 geladen und wird zu einem der
Register aus dem Satz von Registern wie Register 2, das in Fig. 10
gezeigt ist, übermittelt, so daß Einsen in die aktivierte Reihe 5
geladen werden. Dieses Muster kann für zukünftige Anwendungen
gespeichert werden.
-
Die vertikale Maske wird folgendermaßen erstellt:
Der Bereich von Daten, die eine Diagonale von Einsen haben, wie in
Fig. 11a gezeigt, kann in ein Register aus dem Satz von Registern
so wie zum Beispiel Register 4 geladen werden. Nur die aktivierte
Reihe wird geladen, so daß in diesem Fall das fünfte Bit gesetzt
wird und diese Information wird dann zu dem
Eingabe/Ausgabe-Register 206 übertragen. Beide, der Maskenregister
204 und 210 sind gesetzt, um alle Reihen und Spalten zu aktivieren
und das Muster in dem Eingabe/Ausgabe-Register wird zu allen in dem
Muster resultierender Reihen übertragen, wie in Fig. 11b gezeigt.
Durchqueren der Assoziationsmatrix
-
Das Durchqueren der Assoziationsmatrix ist eine iterative Prozedur.
Die Tiefe der Suche kann beendet werden, wenn keine zusätzliche
Beziehung mehr existiert, oder nachdem eine Anzahl an Beziehungen
gefunden worden ist oder wenn ein bestimmter Wert erreicht worden
ist.
-
Ein Beispiel von der Assoziationsmatrix, die für das Verzeichnis in
Fig. 9 existieren könnte, ist in Fig. 12 gezeigt. Ein passendes
zu C20 wurde in der Position 5 des Verzeichnisses gefunden und die
horizontale und vertikale Maske werden in dieser Reihenfolge im
Register 2 und 4 gespeichert. Um alle Teile zu finden, aus denen
C20 gebildet wurde, würde man nach allen aktiven Bits in der
fünften Spalte schauen und das würde fortgeführt werden, bis kein
anderes aktives Bit gefunden wird. Dies kann mit dem Folgenden
ausgeführt werden:
-
1. Aktivieren aller Reihen und Spalten
-
2. Laden der Assoziationsmatrixdaten in das Register 8. Ausführen
einer AND Operation zwischen Register 4, gezeigt in Fig. 11b,
worin die vertikale Maske gespeichert wird, und Register 8. Das
Ergebnis von der AND Operation wird in das Statusregister 208
gesetzt, wie in Fig. 12 gezeigt wird, und zeigt an, daß es ein
Passendes in der zweiten, vierten und dreizehnten Position in
Abhängigkeit zu C10, C30 und T07 gibt, wie in Fig. 9 gezeigt,
welche die Teile sind, die C20 bilden.
-
Die Ergebnisse können ausgegeben werden, indem die Statusbits zu
dem Verzeichnis in Beziehung gesetzt werden, indem:
-
1. Bewegen der Statusbits zu der horizontalen Maske 210,
Aktivieren aller Bits in der vertikalen Maske 204, Laden der
Verzeichnisseite, dann Übertragen des Inhalts von den aktiven
Reihen zu dem Ausgaberegister 206, eins zu jedem Zeitpunkt, um
ausgedruckt zu werden, wie Fig. 13 zeigt.
-
Dieses einfache Beispiel zeigte, wie man einen Level durchquert. Um
eine Vielzahl von Leveln zu durchqueren, z. B. zum Identifizieren
der Komponenten, die ebenfalls C10, C30 und T07 bilden, werden die
folgenden Operationen iterativ ausgeführt. Wegen dieser iterativen
Suche, müssen die Statusbits in einem Register gesichert werden und
jedes Mal, wenn eine Unterkomponente nach ihren Komponenten
durchsucht wird, werden die Statusbits in die horizontale Maske 210
geladen.
-
1. Erstellen einer neuen vertikalen Maske für jedes von den
Statusbits, indem die beiden Statusbits in das horizontale
Maskenregister 210 geladen werden. Dies erlaubt den zuvor
gesetzten Bits, ihre assoziierten Reihen zu aktivieren. Lade
eine neue Reihe von diagonalen Einsen in das Register 9 und
übermittele zu dem Ausgaberegister 206 die aktiven Reihen von
Bits, eine Reihe zu einem Zeitpunkt. Von dem Ausgaberegister
wird zu jedem Zeitpunkt jede Reihe zu der vertikalen Maske 204
geschoben, wie in Fig. 14a gezeigt, welche die genannten
Aktionen der Bits in Beziehung zu C10 zeigt.
-
2. Setze das horizontale Maskenregister und Ausgaberegister zu
allen Einsen.
-
3. Vergleiche alle Bits in der aktiven Spalte der
Assoziationsmatrix. Fig. 14b zeigt, daß es keine anderen
Komponenten gibt, die C10 bilden, wie durch die Nullen in der
gesamten zweiten Spalte angezeigt wird. Die Ausführung für C30
und T07 wird in der gleichen Weise ausgeführt und zeigt an, daß
keine anderen Komponenten diese Komponenten bilden, wie durch
die Nullen angezeigt wird, die in den gesamten Spalten, vier
und dreizehn angezeigt wird.