DE3688737T2

DE3688737T2 - Kontextadressierbarer umlaufspeicher.

Info

Publication number: DE3688737T2
Application number: DE86905072T
Authority: DE
Inventors: Erik Brunvand; Alan Davis
Original assignee: Fairchild Semiconductor Corp
Current assignee: Fairchild Semiconductor Corp
Priority date: 1985-08-13
Filing date: 1986-08-13
Publication date: 1994-03-10
Anticipated expiration: 2006-08-14
Also published as: JPS63500547A; US4924435A; DE3688737D1; JP2516609B2; EP0232376A4; ATE91815T1; WO1987001222A1; EP0232376A1; CA1266330A; EP0232376B1

Description

Die vorliegende Erfindung betrifft im allgemeinen das Gebiet der Datenverarbeitungsanlagen und insbesondere Speichersysteme zur Anwendung in Datenverarbeitungsanlagen.
Im wesentlichen setzen alle in Systemen der Künstlichen Intelligenz eingesetzte Datenverarbeitungsanlagen voraus, daß Informationen abgespeichert und wahlweise abgerufen werden. Diese Informationen sind im allgemeinen in der Form einer in einem Speicher abgespeicherten Datenbank organisiert, die aus einer Anzahl Datensätzen besteht, die jeweils einzeln abgerufen werden. Im Normalfall wird jeder Datensatz als Einheit abgerufen. Das einfachste Beispiel für das Abrufen aus einer Datenbank besteht darin, daß alle Datensätze abgerufen werden, die ein oder mehrere Schlüsselwörter enthalten. Zum Beispiel könnte die Datenbank aus allen Artikeln einer bestimmten Gruppe wissenschaftlicher Journale bestehen, wobei jeweils ein Artikel in einem Datensatz enthalten ist. Hier könnte jemand alle Artikel abrufen wollen, die ein oder mehrere Schlüsselwörter enthalten, wie z. B. alle Artikel, die die Wörter "Computerberechnung" oder "Künstliche Intelligenz" enthalten.
In "Expertensystemen" ist die Datenbank in Regeln kodifiziert, die wiederholt nach Regeln durchsucht werden müssen, die einer gegebenen Spezifikation genügen. Diese gegebene Spezifikation kann als "Abfragefolge" bezeichnet werden. Dieser Suchtyp, der als "regelbezogene" Suche bezeichnet werden kann, unterscheidet sich signifikant von der Suche nach Datensätzen, die ein oder mehrere Schlüsselwörter enthalten, wie oben beschrieben ist. Wenn das Expertensystem vor ein Problem gestellt wird, muß es entscheiden welche der vielen, in der Datenbank enthaltenen Regeln dem angezeigten Problem am nächsten kommt. Diese Wahl hängt ab von den Daten und den Beziehungen zwischen den Variablen in dem zur Lösung anstehenden Problem. Das Expertensystem muß die Regeln auswählen, die die gleichen Daten und/oder Beziehungen zwischen den Variablen enthalten. Zum Beispiel könnten diese Regeln die folgende Form haben:
Wenn < Bedingung> dann < Handlung oder Schlußfolgerung> . Eine der Regeln in der Datenbank könnte sein wie folgt:
Wenn < x ißt> dann < x ist hungrig> .
Wenn das Problem die Information enthält "Peter ißt", würde sich das System vor die Aufgabe gestellt sehen, alle Regeln zu durchsuchen nach einer, in der es heißt: (x ißt). Hier ist x ein variables Element, das in der bekannten Information durch jedes beliebige Element ersetzt werden kann. Damit würde die obige Regel mit jeder anderen abgerufen, die "ißt" enthält. Sobald das System diese Regel abgerufen hat, substituiert es x durch Peter und schließt daraus, daß Peter hungrig ist.
Die regelbezogene Suche unterscheidet sich signifikant von der einfachen Schlüsselwort- oder Schlüsselelementsuche, in der alle Datensätze abgerufen werden, die ein oder mehrere Schlüsselwörter enthalten. In einer regelbezogenen Suche sind sowohl die Anzahl als auch die Reihenfolge der in den Datenbank-Sätzen enthaltenen Elemente bedeutsam. Betrachten wir eine Datenbank, die die drei Datensätze (a,x,b), (a,z,b) und (b, (d,e),a) enthält. Eine Suche nach allen Datensätzen, die "a" und "b" enthalten, würde alle obigen Datensätze abrufen. Jedoch würde eine Suche nach allen "Regeln" der Form (a,b) von keinem der Datensätze erfüllt sein, weil jeder Datensatz 3 Elemente enthält und die verlangte Regel nur zwei. Eine Abfrage nach allen Regeln der Form (a,?,b), wobei ? ein variables Element kennzeichnet, das von jeder Konstanten, jedem Unterausdruck oder jeder sonstigen Variablen erfüllt wird, würde die ersten beiden Datensätze abrufen, jedoch nicht den dritten, weil "a" und "b" im dritten Datensatz in der falschen Reihenfolge auftreten. Daher kann auch mit dem Variablenkonzept ein regelbezogenes Abrufsystem zur Auswahl von Datensätzen auf der Grundlage von Schlüsselelementen in einer nicht vorgegebenen Reihenfolge in herkömmlicher Weise nicht benutzt werden.
Auf der anderen Seite läßt sich ein System auf der Grundlage der Suche nach einem Schlüsselwort nur schwer für regelbezogene Suchen einsetzen. Um eine regelbezogene Suche in einem Schlüsselwortsystem zu benutzen, muß man zwei Schritte durchführen. Zunächst müssen alle Datensätze, die die Elemente der Regel beinhalten, abgerufen und in einem Hilfsspeicher abgespeichert werden. Dann muß jeder dieser Datensätze gesondert durchsucht werden, um festzustellen, ob er die Elemente in der richtigen Reihenfolge und ohne zusätzliche Elemente enthält.
Ein größeres Problem, das beim Implementieren künstlicher Intelligenzsysteme unter Benutzung der derzeitigen Computerhardware auftritt, ist die Zeit, die erforderlich ist, um eine große Datenbank nach Datensätzen zu durchsuchen, die mit einer gegebenen Abfragefolge übereinstimmen. Um nützlich zu sein, muß ein solches System eine große Anzahl Datensätze enthalten. Da die Zeit, die zum Durchsuchen der Datenbank erforderlich ist, proportional zur Länge der Datenbank ist, wird ein System mit einer festen Durchsuchungsgeschwindigkeit, das durch Anfügen neuer Informationen in der Form neuer Regeln "schlauer" wird, auch langsamer. Dieses Problem läßt sich nur durch Erhöhung der Suchgeschwindigkeit des Systems lösen, wenn die Größe der zu durchsuchenden Datenbank erhöht wird.
Trotz der zahlreichen Verbesserungen, die auf dem Gebiet der integrierten Schaltkreise gemacht wurden, unterscheiden sich moderne Computer nur sehr wenig von der ursprünglichen Konzeption Von Neumanns. Die klassische Von-Neumann-Maschine besteht aus einer Zentraleinheit und einem gesonderten Speicher, der in Wörter fester Länge organisiert ist. Die Zentraleinheit holt Daten aus dem Speicher, immer nur ein Wort auf einmal, durch Angabe der Adresse des gewünschten Worts, gerechnet vom Speicheranfang aus. Bei der Durchführung der obigen Suche würde eine Zentraleinheit vom Von-Neumann- Typ der Reihe nach jedes Wort der Datenbank aus dem Speicher abrufen und mit jedem der Schlüsselwörter in der Abfragefolge vergleichen, die auch im Speicher abgespeichert sind. Da es eine Grenze der Geschwindigkeit gibt, mit der eine einzige Zentraleinheit laufen kann, sind Maschinen vom Von-Neumann- Typ in der Praxis bei der Größe der Datenbank beschränkt, auf die zugegriffen werden kann. Auch bei Geschwindigkeiten von 10 Millionen Vergleichen in der Sekunde würde sich eine Von- Neumann-Maschine schwer tun, den Inhalt einer Bibliothek zu durchsuchen, die z. B. nur die Gerichtsentscheidungen aus den verschiedenen Gerichtsbezirken in den Vereinigten Staaten enthält.
Zusätzlich zu den Geschwindigkeitseinschränkungen zeigt die Von-Neumann-Architektur auch noch eine Anzahl Einschränkungen wegen der ihr innewohnenden Hardwareabhängigkeit. Um eine Speicheradresse anzugeben, wird eine feste Anzahl Adreßzeilen benutzt. Ein System mit N Adreßzeilen kann einen Speicher mit 2N Wörtern adressieren und nicht mehr. Um die Speicherkapazität über diese Grenze hinaus zu vergrößern, muß man die Anzahl der Adreßzeilen vergrößern. Das bedingt sowohl Hardware- als auch Softwareänderungen, da die meisten Systeme eine maximale Speichergröße vorschreiben, die der Befehlssatz des Computers adressieren kann. Ferner, wenn ein Teil des Speichers durch eine Funktionsstörung einer seiner Komponenten ausfällt, ist es schwierig, diesen Speicherteil ohne Umprogrammieren auf ein unbeschädigtes Speichersegment umzulegen. Mit der Vergrößerung der Speicher infolge der Notwendigkeit, eine immer größere Anzahl Datenwörter abzuspeichern, wird auch die Anfälligkeit für eine solche Funktionsstörung in einem Speicherteil immer größer.
Schließlich erfordert das Problem des Durchsuchens einer großen Datenbank nur einen kleinen Teil der Befehle, die in einer herkömmlichen Zentraleinheit vorhanden sind. Eine typische Zentraleinheit hält buchstäblich hunderte von Ausgabe/Eingabebefehlen zur Ausführung bereit, die sich von Befehlen zur Kommunikation mit der Außenwelt bis zu mathematischen Befehlen zur Kombination von Speicherwörtern, die Zahlen darstellen, erstrecken. Das Problem der Datenbankdurchsuchung benötigt aber höchstens 10 bis 20 dieser Befehle. Daher ist das Problem der Durchsuchung einer Datenbank eine Unterforderung des Befehlssatzes der Zentraleinheit.
Die Geschwindigkeitsbeschränkungen der Zentraleinheit können im gewissen Maße überwunden werden durch den Bau eines Systems mit mehreren Zentraleinheiten, wobei jede einen Zugriff auf den Speicher hat. Diese Lösung hat jedoch ihre Grenzen. Die Anzahl der Zentraleinheiten, die sich in einen gegebenen Speicher teilen, wird letztlich beschränkt durch die Zeit, die jede Zentraleinheit für den Zugriff auf den Speicher braucht. Wenn der Speicherbus für jede Zentraleinheit 1/10 der Zeit freigehalten werden muß, dann können sich höchstens 10 Zentraleinheiten in den gleichen Speicher teilen. Somit ist die Vervielfältigung der Zentraleinheit nicht die beste Lösung zur Überwindung der Geschwindigkeitsbeschränkungen der Von-Neumann-Maschinen.
Auch wenn man durch den Einsatz mehrfacher Zentraleinheiten die Suchzeit effektiv einschränken könnte, hat man noch immer mit den Hardware-bedingten Einschränkungen zu tun. Früher oder später wird man die Datenbank über diese Hardwareeinschränkungen hinaus vergrößern wollen, was bei Von- Neumann-Maschinen nur sehr schwer möglich ist. Im Idealfall würde man gern einen modularen Speicher haben, der jederzeit zu einem System hinzugefügt werden kann, wenn mehr Speicherplatz für die Datenbank gefordert wird, ohne daß die Anzahl der Adreßzeilen gleichzeitig erhöht werden muß. Diese Fähigkeit zur Speichererweiterung wird bei solchen Künstlichen Intelligenzsystemen immer wichtiger, wo man versucht, eine Maschine zu bauen, die in der Lage ist, immer größer werdende Informationsmengen zu speichern und zu benutzen.
Rechnersysteme vom Von-Neumann-Typ wurden benutzt im Versuch, die Geschwindigkeit zu erhöhen, mit der ein Rechner eine Datenbank nach einer Datenfolge durchsuchen kann, die mit einer gegebenen Abfrage-Datenfolge übereinstimmt. Z.B. beinhaltet das Kolloquium über ASSOCIATIVE METHODS AND DATA BASE ENGINES, 17. Mai 1982, Seiten 1/1-5/1, IEEE, London, GB, Artikel, die inhaltadressierbare Speicher beschreiben, die parallele Rechnersysteme auf das beschriebene Problem ansenden. In einem dieser Probleme sind die Datensequenzen in einer umlaufenden Speicheranordnung gespeichert, die aus einem langen Schieberegister gebaut ist. Die Abfragefolgen werden an einer Anzahl unterschiedlicher Stellen entlang dem Schieberegister mit der umlaufenden Datensequenz verglichen. Diese Art System sieht eine potentielle Verbesserung bei der Geschwindigkeit vor, mit der die Fragesequenz identifiziert werden kann. Leider ist dieser Systemtyp auf dem Stand der Technik schlecht für die Vergleichstypen geeignet, die bei regelbezogenen Systemen erforderlich sind. Insbesondere arbeitet dieses System schlecht unter Umständen, in denen ein einziges Symbol in einer Sequenz mit einer Vielzahl Symbolen in den anderen Sequenzen verglichen wird. Zusätzlich, sobald einmal eine Datensequenz identifiziert ist, kann die Zeit zur Ausgabe der Sequenz so lang sein wie die Zeit, die benötigt wird, damit alle Datensequenzen einen bestimmten vorgegebenen Punkt im Schieberegister passieren.
Die vorliegende Erfindung sieht vor ein Speichersystem zur Speicherung und Abfrage von Symbol-Datensequenzen mit einem Umlaufspeicher, bestehend aus: Einem ersten Feld von Speicherzellen zur Speicherung von einer oder mehreren Datensequenzen, wobei jede Datensequenz aus einem oder mehreren Symbolen besteht sowie Einrichtungen, welche die sequentielle Zirkulation dieser Symbole an einer Vielzahl von Zugriffseinheiten vorbei veranlassen; Einrichtungen, welche eine an das Speichersystem angekoppelte Symbol-Abfragesequenz empfangen; ein zweites Feld von Speicherzellen umfassenden Einrichtungen zur Speicherung dieser Symbol-Abfragesequenz; Abfrageeinrichtungen, welche operativ mit jeder Zugriffseinheit zum Auffinden von einer oder mehreren Symbolsequenzen von den dem ersten Feld der Symbol-Abfragesequenz entsprechenden Speicherzellen gekoppelt sind, dadurch gekennzeichnet, daß das Speichersystem ferner mit den Zugriffseinheiten gekoppelte Einrichtungen für die Anfrageeinrichtungen zur Kommunikation untereinander auf einen internen Bus umfaßt, wobei die Abfrageeinrichtungen jedesmal, wenn eine der Abfrageeinrichtungen feststellt, daß eine Datensequenz an ihr vorbeizirkuliert wird, diese mit der Abfragesequenz vergleicht, und daß diese Abfrageeinrichtung den Ort der Datensequenz auf dem internen Bus den anderen Abfrageeinrichtungen mitteilt, wobei die erste die Datensequenz feststellende Abfrageeinrichtung diese über den internen Bus zur weiteren Verarbeitung weiterschickt.
Die Erfindung besteht somit aus einem Speichersystem zum Speichern und Abrufen von Datenfolgen aus Symbolen als Antwort auf eine Abfragefolge. Jede dieser Folgen weist drei Symboltypen auf: Konstante, Begrenzer und Variable. Eine Datenfolge wird abgerufen als Antwort auf eine Abfragefolge, wenn die zwei Folgen durch Ersetzen der Variablen in den einzelnen Folgen durch Konstante oder Kombinationen von Konstanten und Begrenzern identisch gemacht werden können, wobei diese Kombinationen jeweils mit einem Begrenzer beginnen und enden. Diese Bestimmung wird gemacht durch Durchführung einer Anzahl paarweiser Vergleiche zwischen Symbolen, die aus den einzelnen Datenfolgen ausgewählt werden, und den entsprechenden Abfragesequenzsymbolen. Die Datenfolgen, die jeden dieser paarweisen Tests bestehen, werden abgerufen.
Die Datensequenzen sind in einem Umlaufspeicher gespeichert, in dem jedes Symbol als Sequenz binärer Bits gespeichert ist, die periodisch an einer Anzahl Zugriffseinheiten vorbeipassieren, an denen sie gelesen werden können. Jede dieser Zugriffseinheiten enthält einen Prozessor, der in der Lage ist, die gespeicherte Datensequenzen mit einer Abfragesequenz zu vergleichen, die ihrerseits aus einer Symbol folge des gleichen Typs besteht, die die im Umlaufspeicher abgespeicherten Daten repräsentiert. Das Speichersystem enthält einen gesonderten Speicherpuffer zum Aufnehmen dieser Abfragesequenz und zum Übersetzen derselben in eine Sequenz aus Binärbits, die bequem mit der Sequenz aus Binärbits verglichen werden kann, die die Datenfolgen im Umlaufspeicher darstellen. Ein einzigartiges Untersystem ist vorgesehen, das neue Datensequenzen in den Umlaufspeicher eingibt, ohne die Operation der Daten-Abruffunktionen zu unterbrechen. Diese Dateneingabetechnik sammelt automatisch fragmentierte Speicherbereiche, die zum Speichern der neuen Datenfolgen zu klein waren und kombiniert sie zu größeren Räumen, in die die neuen Datenfolgen eingeschoben werden. Die Operation der verschiedenen Speicherfunktionen wird gesteuert durch einen eingebauten Prozessor, der zuläßt, daß das System mit einem Minimum an Aufwand in größere Rechnersysteme integriert wird.
Es ist eine Aufgabe der vorliegenden Erfindung, ein Speichersystem vorzusehen für das Speichern und Abrufen von Regeln, die auf regelbezogene KI-Systeme anwendbar sind, in denen die Regeln durch Angabe ihres Inhalts anstatt ihres Standorts im Speicher abgerufen werden können.
Eine weitere Aufgabe der vorliegenden Erfindung ist die Verkürzung der zum Abrufen dieser Datensätze benötigten Zeit durch Anwenden eines sich wiederholenden, gleichzeitig ablaufenden Datenverarbeitungssystems, in dem eine Vielzahl von Verarbeitungseinheiten nach allen Datensequenzen sucht, die einer gegebenen Fragesequenz entsprechen.
Diese und weitere Aufgaben werden klar aus der nachfolgenden detaillierten Beschreibung der Erfindung und aus den begleitenden Zeichnungen.

ZUSAMMENFASSUNG DER ZEICHNUNGEN

Fig. 1 ist ein Blockschaltbild der bevorzugten Ausführungsform der vorliegenden Erfindung.
Fig. 2 ist eine Zusammenfassung der Datenformate, die zum Abspeichern der Symbole in der bevorzugten Ausführungsform benutzt werden.
Fig. 3 ist das Blockschaltbild einer Zugriffseinheit, die in der bevorzugten Ausführungsform benutzt werden.
Fig. 4 ist eine Blockdarstellung des Fragespeicherpuffers, der in der bevorzugten Ausführungsform benutzt wird.
Fig. 5 zeigt das Einschieben der neuen Daten in den Speicher an der Stelle eines oder mehrerer unbenutzter Blöcke.
Fig. 6 ist ein Zustandsdiagramm für die Maschine endlicher Zustände, die benutzt wird, um die Zugriffseinheiten in der bevorzugten Ausführungsform zu implementieren.

DETAILLIERTE BESCHREIBUNG DER ERFINDUNG

AUSWAHL DER SPEICHERORGANISATION

Wie bereits gesagt, ist die Suchzeit proportional zur Länge der durchsuchten Datenbank. Also läßt sich die Suchzeit verkürzen durch Aufteilen der Datenbank in mehrere Untereinheiten, jede mit ihrer eigenen Verarbeitungseinheit. Das ist gleichbedeutend mit dem Aufteilen der Suchaufgabe auf eine Anzahl kleiner Von-Neumann-Maschinen, die jede genügend Speicherplatz aufweist, um die Schlüsselwörter und ein oder mehrere Wörter der Datenbank in die Suchliste auf zunehmen. Die schnellste Suche in einem solchen System ließe sich mit einem Speicher erzielen, der eine Verarbeitungseinheit in jedes Speicherwort eingebaut hätte. Dann könnte in einem Speicherzyklus der Speicher sich selbst mit einem Schlüsselwort vergleichen und jeden Datensatz identifizieren, in dem dieses Schlüsselwort auftritt. Das optimale Verhältnis von Datenbankwörtern zu Verarbeitungseinheiten hängt eindeutig von der Komplexheit der Verarbeitungseinheit im Vergleich zu der des Speichers ab. Da die Verarbeitungseinheit zur Ausführung der Suchfunktion nur einige wenige Befehle braucht, ist eine verhältnismäßig hohe Dichte der Verarbeitungseinheiten möglich. Diese Art hoch-wiederholter Modularstruktur ist besonders gut geeignet für die Technik moderner VSLI-integrierter Schaltkreisfertigung.
Dieser Architekturtyp eignet sich auch gut für Datenbank- Suchprobleme, weil sich die Verarbeitungszeit mit der Vergrößerung der Datenbank nicht erhöht, weil jede Speichereinheit in der Form der eingebauten Verarbeitungseinheit ihre eigene Suchkapazität aufweist. Somit vergrößert sich die Rechnerkapazität mit der Vergrößerung der Datenbank. Ferner hat bei dieser Konstruktion die Zentraleinheit des Systems, im Gegensatz zu den Verarbeitungseinheiten, die die Suchfunktion durch den Speicher liefern, verhältnismäßig wenig zusätzlichen Platzbedarf. Sie braucht Adressen oder sonstige mit dem Speicherinhalt zusammenhängende Daten nicht zu verfolgen. Sie muß nur die Fragesequenz an eine Speichereinheit schicken, die aus einer Reihe Modulen mit der Anweisung besteht, wohin das Ergebnis der Suche abgespeichert werden muß.
Im Prinzip Können die Datenfolgen in einer beliebigen einer Aninzahl physikalischer Speichervorrichtungen abgespeichert werden. Alle diese Vorrichtungen beinhalten irgend einen Speicher zum Halten der Datensequenzen und einen Prozessor zum Vergleichen dieser Sequenzen mit der Fragesequenz. Dieser Vergleich wird ausgeführt als Sequenz paarweiser Vergleiche, die jeweils ein Symbol der Datensequenz mit einem Symbol der Fragesequenz vergleichen. Die Zeit, die gebraucht wird, um die abgespeicherten Datensequenzen auf Sequenzen zu durchsuchen, die einer bestimmten Fragesequenz entsprechen, hängt ab von der Geschwindigkeit der Vergleicherschaltungen, die diese paarweisen Vergleiche durchführen, und von der Anzahl der dafür eingesetzten Schaltungen. Systeme, in denen das Verhältnis der Komparatorschaltungen zu den Speicherstellen groß ist, werden die passenden Sequenzen in der kürzesten Zeit abrufen; solche Systeme haben jedoch eine geringere Speicherdichte und erfordern höhere Allgemeinkosten als Systeme mit weniger Komparatorschaltungen, bei denen die Schaltungen, die für zusätzliche Komparatoren benötigt werden, in zusätzlichen Speicherplatz umgewandelt sind.
In einer Ausführungsform der vorliegenden Erfindung wird ein Umlaufspeichersystem für Datensequenzen benutzt, wobei die Fragesequenz in einen statischen Speicher eingespeist wird und die Datensequenzen mit der Fragesequenz verglichen werden, während die Datensequenz umläuft. Hier wird jede Datensequenz gesondert jeweils eins zu eins mit der Fragesequenz verglichen. Wenn eine bestimmte Datensequenz mit der Fragesequenz übereinstimmt, wird sie ausgelesen bevor der Prozessor zum Testen der nächsten Datensequenz übergeht. Wenn sie nicht übereinstimmt, wartet der Prozessor darauf, daß der Rest der Sequenz vorbei läuft und testet dann die nächste abgespeicherte Datensequenz.
Die meisten Umlaufspeichersysteme sind von Natur aus "Bitseriell". Z.B. lesen Magnetplatten im allgemeinen Spuren, die eine Aufeinanderfolge von einzelnen Bits sind, die durch Umwandlung der Datenwörter in eine serielle Bitsequenz erhalten wurden, und schreiben diese Bits in das umlaufende Speichermedium. Aufgrund der seriellen Natur des Speichermediums gibt es zwei mögliche Strategien für die Konstruktion. Erstens könnte man ein System bauen, in dem der serielle Bitfluß in Wörter zurückverwandelt wird, und die Wörter dann mit den Wörtern der Fragesequenz vergleichen. Ein solches System würde Komparatoren verwenden, die ein Wort breit sind und ein Abfragewort in einem einzigen "Vergleichszyklus" vergleichen würden. Die zweite Alternative wäre es, die Fragesequenzwörter in ein entsprechendes Bit-serielles Muster umzuwandeln und dann die zwei seriellen Bitdarstellungen in einem Komparator zu vergleichen, der nur ein Bit breit ist. Wenn ein Datenwort N Bits lang ist, wären dann N Vergleichszyklen erforderlich. Die Kosten für einen solchen Komparator wären natürlich erheblich geringer, weil an die Stelle des N Bit breiten Komparators des obigen Schemas ein nur ein ein Bit breiter Komparator treten würde.
Zwar sieht es so aus, als ob die erste Alternative schnellere Vergleiche liefern würde, weil sie ja nur einen einzigen Vergleichszyklus zum Testen jedes Frageworts gegen sein entsprechendes Datenwort benötigt im Vergleich zu den N Vergleichszyklen, die bei der zweiten Alternative nötig sind; das ist aber nicht so. Die Zeit, die verbraucht wird, um im ersten Fall einen Vergleich zu machen, ist die Summe der Zeiten, die gebraucht wird, um die N Bits, aus denen das Datenwort besteht, aus dem Bit-seriellen Fluß zu sammeln und diese in das Datenwort umzuwandeln, das durch den N Bit breiten Komparator gegeben ist. Diese Operation würde ausgeführt werden durch Schieben der Daten in ein "Seriell- Eingangs/Parallel-Ausgangs"-Schieberegister. Da die Zeit, die verbraucht wird, um N Bits in ein Seriell-Eingangs/Parallel- Ausgangs-Schieberegister zu schieben, wenigstens so lang ist, wie man für N Vergleiche in einem einzigen Exklusiv-ODER- Gatter benötigt, braucht die erste Alternative mindestens genau so lang zu einem Vergleich wie der einfache Ein-Bit- Vergleichsalgorithmus. Zusätzlich ist diese Lösung viel teuerer, weil je Zugriffseinheit ein Seriell-Eingangs/ Parallel-Ausgangs-Schieberegister nötig ist, zusätzlich zu dem N-Bit breiten Komparator. Daher ist die serielle Bit- Lösung das Mittel der Wahl zum Herstellen eines musteradressierbaren Speichers auf der Grundlage eines umlaufenden Speichermediums, das von Natur aus Bit-seriell ist.

ÜBEREINSTIMMUNGSALGORITHMUS

Das erfindungsgemäße Speichersystem ist so konstruiert, daß es alle Datenfolgen abruft, die einer gegebenen Fragesequenz entsprechen. Jede Datensequenz besteht aus einer Folge von Symbolen. Jedes Symbol gehört zu einem von drei möglichen Typen: Konstante, Variable und Begrenzer. Auch die Fragesequenz setzt sich aus diesen drei Symboltypen zusammen. Eine gespeicherte Sequenz stimmt definitionsgemäß mit einer Fragesequenz überein, wenn die beiden Sequenzen identisch gemacht werden können durch Ersetzen jedes der variablen Elemente in jeder der Sequenzen durch eine Konstante oder durch eine Kombination von Konstanten, die mit einem Begrenzer beginnt und mit einem Begrenzer endet. Die Konstanten bzw. deren Kombinationen können je nach der ersetzten Variablen unterschiedlich sein. So kann z. B. die Sequenz
(a,d,?,e,c,(a,b),g)
identisch gemacht werden mit der Sequenz
(a,d,q, e, c,?,g)
durch Ersetzen des ? in der ersten Sequenz durch q, und der der Variablen in der zweiten Sequenz durch die Kombination (a,b).
Der Übereinstimmungsalgorithmus ist als eine Reihe von paarweisen Vergleichen zwischen einem Element der Fragesequenz und einem Element der getesteten Datensequenz implementiert. Bei jeder erfolgreichen paarweisen Übereinstimmung muß das für den nächsten Vergleich zu benutzende Element spezifiziert werden, denn wenn Unterausdrücke vorkommen, müssen diese Ausdrücke oft übersprungen werden. Das läßt sich anhand der obigen zwei Sequenzen zeigen, wobei die zweite Sequenz die Fragesequenz ist, die mit der Datensequenz verglichen wird, die durch die erste Sequenz dargestellt ist. Der Vergleich startet damit, daß das "(" in der ersten Sequenz mit dem "(" der zweiten Sequenz verglichen wird. Dieser Prozeß wird mit den zweiten und dritten Elementen fortgesetzt. Beim vierten Vergleich wird das Symbol "q" der Fragesequenz mit der Variablen "?" in der Datensequenz verglichen. Da "?" mit allem übereinstimmt, ist dieser Übereinstimmungsvergleich erfolgreich. Der Prozeß wird fortgesetzt, bis das "?" in der Fragesequenz mit dem "(" des in der Datensequenz enthaltenen Unterausdrucks verglichen wird. Da das "?" mit dem nächsten Element, das in diesem Fall der ganze Unterausdruck (a,b) ist, übereinstimmt, ist das nächste in der Datensequenz zu testende Element das "g" nach dem ")", nicht das "a" nach dem "(". Wenn also eine Variable in einer Sequenz mit einem "(" in der anderen Sequenz verglichen wird, sind die nächsten zu vergleichenden Symbole das, das auf das "?" folgt, und das, das auf das ")" folgt, das dem "(" entspricht, das mit dem "?" verglichen wurde. Eine Datensequenz gilt als übereinstimmend mit der Fragesequenz, wenn jeder der obigen paarweisen Vergleiche positiv ausfällt.
Zusätzlich implementiert die vorliegende Erfindung einen "fast genau" Vergleichsmodus, in dem Datensequenzen, die mit der durch die Fragesequenz spezifizierten Sequenz beginnen, zurückgegeben werden, auch wenn sie länger sind als die Fragesequenz. Wenn z. B. die Fragesequenz (a,d) im "fast genau" Vergleichsmodus benutzt wird, werden alle Datensequenzen abgerufen, die mit (a,d . . . . beginnen. Dieser Modus ermöglicht es, Datensequenzen unterschiedlicher Länge abzurufen, die mit der gleichen Sequenz beginnen, ohne alle möglichen Kombinationen der Endsequenzen spezifizieren zu müssen.

ZUSAMMENFASSUNG DER HARDWARE-IMPLEMENTIERUNG

Die bevorzugte Ausführungsform der vorliegenden Erfindung wird in Fig. 1 mit 10 schematisch dargestellt. Sie beinhaltet einen Umlaufspeicher, der als Bit-serieller Datenfluß 12 konfiguriert ist, und eine Anzahl identischer Datenverarbeitungseinheiten 18, die an einer Anzahl unterschiedlicher Zugriffspunkte auf diesen Fluß zugreifen, wofür bei 22 ein Beispiel gezeigt wird.
In der bevorzugten Ausführungsform besteht der Bit-serielle Datenfluß 12 aus einem langen Schieberegister, das aus Ein- Bit-Speicherzellen aufgebaut ist. Jedes Symbol der abgespeicherten Datensequenzen wird als binär-codierte Zahl in einem zusammenhängenden Block dieser Ein-Bit-Speicherzellen abgespeichert. Die im Schieberegister abgespeicherten Symbole werden dann durch Schieben des Inhalts jeder einzelnen Speicherzelle in die nächstliegende Speicherzelle an jedem Zugriffspunkt vorbeigeführt, wobei jeweils der Inhalt der letzten Speicherzeile wieder in die erste Speicherzelle geschoben wird.
Weitere Umlaufspeicher, die mehr als ein Bit breit sind, sind für den Fachmann ohne weiteres denkbar. So ließe sich z. B. ein Schieberegister einrichten, das N Bits breit ist, wobei N die Zahl der Bits ist, die zum Abspeichern der einzelnen Symbole benutzt wird, um einen Umlaufspeicher herzustellen, der dem obigen, ein Bit breiten Schieberegister analog ist.
Die bevorzugte Ausführungsform benutzt eine feste Anzahl Speicherzellen zum Abspeichern der einzelnen Symbole. Ausführungsformen, in denen unterschiedliche Zahlen von Speicherzellen zum Abspeichern der verschiedenen Symbole benutzt werden, sind dem Fachmann ebenfalls verständlich. In einem System, das variable Zahlen von Speicherzellen per Symbol benutzt, steht vor jedem Symbol ein Code, der den Anfang eines Symbols kennzeichnet, und ein Mittel zum Definieren des Endes des Symbols ist vorgesehen, z. B. ein Stop-Code.
Jede der Verarbeitungseinheiten 18, nachstehend als Zugriffseinheiten bezeichnet, ist an einen Fragespeicherpuffer 20 angeschlossen, der die beim Durchsuchen der abgespeicherten Datensequenzen in dem Bit-seriellen Datenfluß 12 zu benutzende Fragesequenz enthält. Ein Eingabeprozessor 16 ist ebenfalls an den Bit-seriellen Datenfluß 12 angeschlossen. Dieser Prozessor wird zusammen mit dem Eingabepuffer 14 benutzt, Daten in den Bit-seriellen Datenfluß 12 einzugeben. Die einzelnen Zugriffseinheiten kommunizieren miteinander über einen internen Bus 26, der auch dazu benutzt wird, mit dem Führungssteuerungsprozessor 24 zu kommunizieren. Der Führungssteuerungsprozessor 24 kommuniziert mit dem äußeren Verarbeitungssystem, in dem der Speicher der vorliegenden Erfindung über einen äußeren Bus 30 funktioniert. Der Führungssteuerungsprozessor 24 ist auch über einen Bus 28 mit dem Fragespeicherpuffer 20 verbunden, der dazu benutzt wird, die Fragesequenz in den Fragespeicherpuffer 20 einzugeben.
Bevor eine Suche eingeleitet werden kann, muß der Bitserielle Datenfluß 12 mit den zu durchsuchenden Datensequenzen geladen werden. Diese Funktion wird vom Eingabeprozessor 16 ausgeführt, der die abzuspeichernden Datensequenzen vom Führungssteuerungsprozessor 24 erhält. Die Operation dieses Eingabesystems wird nachstehend in Einzelheiten beschrieben. Dem Bit-seriellen Datenfluß 12 können jederzeit einzelne Datensequenzen hinzugefügt werden.
Sobald der Bit-serielle Fluß geladen ist, wird eine Suche nach allen Datensequenzen wie folgt durchgeführt, die einer gegebenen Fragesequenz entsprechen. Zunächst gibt der Führungssteuerungsprozessor 24 die Fragesequenz an den Fragespeicherpuffer 20 weiter. Zweitens werden die Zugriffseinheiten 18 und die abgespeicherte Datensequenz, die durch den Bit-seriellen Datenfluß 12 läuft, wie nachstehend beschrieben für die Suche initialisiert. Drittens werden die Zugriffseinheiten 18 angewiesen, Übereinstimmungen mit den Fragesequenzen im Fragespeicherpuffer 20 zu finden. Jedesmal, wenn eine der Zugriffseinheiten 18 eine Datensequenz findet, die mit der Fragesequenz übereinstimmt, sendet sie den Ort dieser Datensequenz über den inneren Bus 26 an die übrigen Zugriffseinheiten 18. Die erste Zugriffseinheit 18, die diese Datensequenz aufspürt, sendet sie dann über den internen Bus 26 an den Ausgabeverwalter, der im Führungssteuerungsprozessor 24 enthalten ist. Der Führungssteuerungsprozessor 24 schickt die betreffende Datensequenz an das Bearbeitungssystem, in dem der erfindungsgemäße Speicher arbeitet.

DATENFORMATE

Jede Datensequenz besteht aus einer Folge von Symbolen. Zur Kennzeichnung des Anfangs und des Endes jeder Datensequenz werden besondere Symbole benutzt. Jedes Symbol wird durch ein Speicher-"Wort" dargestellt, das einen fortlaufenden Block aus Zellen eines verlorenen Speichers belegt. In der bevorzugten Ausführungsform ist jedes Speicherwort 34 Bits lang. Diese 34 Bits laufen im Bit-seriellen Datenfluß 12 um, wenn das Symbol eines der Symbole ist, die eine Datensequenz einschließen. Der Fragespeicherpuffer 20 enthält 34-Bit- Speicherwörter zum Abspeichern der Fragesequenzsymbole im gleichen 34-Bit-Format. Jedes Speicherwort unterteilt sich in eine Identifikationsgruppe und eine Datengruppe. Die ersten zwei Bits jedes Worts sind Identifikationsbits, die den Charakter der Daten anzeigen, die in den restlichen 32 Bits abgespeichert sind und die als die Datenbits bezeichnet werden. In Speicherwörtern, die Konstante oder Variable enthalten, werden die Datenbits benutzt, um den "Namen" der Konstanten oder Variablen abzuspeichern. Der für eine Variable gespeicherte Name wird im Gerät der vorliegenden Erfindung nicht benutzt. Dieser wahlweise Name ist vorgesehen, damit sich die Datensequenz leichter als englische Sprache liest. Er kann auch vom Datenverarbeitungssystem benutzt werden, das mit den erfindungsgemäßen Gerät gekoppelt ist.
In Speicherwörtern, die Begrenzer enthalten oder die dazu benutzt werden, irgendeine Systemfunktion, wie z. B. Anfang oder Ende einer Datensequenz, zu signalisieren, können eines oder auch mehrere der Datenbits zusammen mit den Identifikationsbits benutzt werden, um die Funktion zu spezifizieren. Die verschiedenen Identifikationsbits und die zugehörigen Datenbits sind in Fig. 2 zusammengefaßt. Zusätzlich zum Sondersymbol zum Beenden einer Datensequenz gibt es "Gesehen"- bzw. "Ungesehen"-Sondersymbole zum Anzeigen, daß eine betreffende Datensequenz bereits im Vergleich mit der Fragesequenz getestet wurde, sowie ein Sondersymbol "leer", das angibt, daß das Speicherwort zum Abspeichern einer neuen Datensequenz frei ist. Entweder das "Gesehen"- oder das "Ungesehen"-Symbol wird benutzt, um den Anfang einer Datensequenz anzugeben. Wenn eine Suche initialisiert wird, ist das erste Symbol jeder Datensequenz auf "ungesehen" gestellt. Nachdem eine Zugriffseinheit diese Datensequenz mit der Fragesequenz verglichen hat, wird das erste Symbol zu gesehen" umgewandelt.
Die Symbole, aus denen die Fragesequenz besteht, sind in einem ähnlichen Format codiert, wie in Fig. 2 dargestellt ist. Hier sind jedoch die Begriffe gesehene und ungesehene Datenfolgen und leere Speicherwörter nicht anwendbar; daher sind in der Fragesequenz nur fünf Typen von Datenspeicherwörtern definiert. Diese Datenspeicherwörter sind die gleichen wie die entsprechenden Speicherwörter in den gespeicherten Datensequenzen, abgesehen von den Anfangsbegrenzern.
Die Datenbits eines Anfangsbegrenzers einer Fragesequenz werden benutzt, um den Ort des zugehörigen Endbegrenzers abzuspeichern. Wie oben bereits gesagt, kann, zusätzlich zu einer einfachen Konstanten, eine Variable in einer Datensequenz auch einem ganzen Unterausdruck in der Fragesequenz entsprechen. Jeder solche Unterausdruck beginnt mit einem Anfangsbegrenzer. Dieser Fall wird also signalisiert durch eine Variable in der Datensequenz, die mit einen Anfangsbegrenzer in der Fragesequenz verglichen wird. Wenn ein Anfangsbegrenzer in der Fragesequenz mit einer Variablen in der Datensequenz verglichen wird, muß die Zugriffseinheit 18, die diesen Vergleich macht, auf den Endbegrenzer in der Fragesequenz springen, der dem betreffenden Anfangsbegrenzer zugeordnet ist, und dann die Vergleichsoperation mit dem Fragesymbol fortsetzen, das nach dem Endbegrenzer steht. Das wird in der vorliegenden Erfindung durch Speichern des Ortes des zugeordneten Endbegrenzers in den Datenbits des Fragespeicherworts bewirkt, das den Anfangsbegrenzer enthält. Wenn ein Anfangsbegrenzer in der Fragesequenz mit einer Variablen in der Datenfrequenz verglichen wird, springt die Zugriffseinheit 18 zum Ort im Fragespeicherpuffer 20, der von den Datenbits des Anfangsbegrenzers spezifiziert wird, und fährt dann mit dem Vergleich des Symbols fort, das nach dem steht, das im Sprung spezifiziert ist. Die Sprungstelle wird codiert durch Setzen eines Datenbits in dem Anfangsbegrenzer- Speicherwort für jedes Symbol in der Fragesequenz, das übersprungen werden muß. Wenn daher die Fragesequenz den Unterausdruck (a,b) enthält, würde der Anfangsbegrenzer die beiden ersten Datenbits auf Eins gestellt haben.

PROZESSOR DER ZUGRIFFSEINHEIT

Fig. 3 zeigt ein Blockschaltbild für eine Zugriffseinheit 18. Jede Zugriffseinheit 18 beinhaltet ein Mittel zum Vergleichen eines Datensequenzsymbols mit einem Fragesequenzsymbol. Das Datensequenzsymbol wird in die Zugriffseinheit 18 als Bitsequenz eingespeist, die im Bit-seriellen Datenfluß 12 umläuft. Das für den Vergleich anzuwendende Fragesequenzsymbol wird ebenfalls in einem Bit-seriellen Format der Zugriffseinheit 18 eingegeben. Die Umwandlung des Fragesymbols in dieses Format wird im Fragespeicherpuffer 20 ausgeführt wie nachstehend beschrieben wird. Die Bit-serielle Darstellung des Fragesymbols, die als Fragefluß angesprochen wird, wird der Zugriffseinheit über die Leitung 56 eingegeben, die die betreffende Zugriffseinheit 18 mit dem Fragespeicherpuffer 20 verbindet.
Jede Zugriffseinheit 18 enthält vier Hauptelemente. Erstens enthält jede Zugriffseinheit einen logischen Adreßschaltkreis 30, der die "Adresse" der Datensequenz verfolgt, die im Augenblick am Zugriffspunkt 22 dieser Zugriffseinheit steht. Diese Schaltung besteht aus einem Adressenzähler 32, zum Berechnen der derzeitigen Adresse im Bit-seriellen Fluß 12, der an der Zugriffseinheit 18 vorbeifließt, einem Adressenzwischenspeicher 34 zum Abspeichern einer Adresse zwecks Kommunikation mit den anderen Zugriffseinheiten auf dem Adreßbus 36, der Teil des Busses 26 ist, der die verschiedenen Zugriffseinheiten des Systems miteinander verbindet, und einer Vergleichsschaltung 36 zum Testen der derzeitigen Adresse gegen die, die über den Adreßbus zugeführt wird. Obwohl auf die derzeitige Adresse einer im Bitseriellen Datenfluß 12 abgespeicherten Datensequenz von außerhalb des erfindungsgemäßen Geräts nicht zugegriffen werden kann, sind intern im Gerät die Datenfolgen gemäß Adresse zugreifbar. Jede Zugriffseinheit 18 berechnet ihre Adresse gegenüber den anderen Zugriffseinheiten und relativ zu einem Punkt in Bit-seriellen Datenfluß 12, der neu definiert wird, wenn immer die Adreßschaltung 30 neu initialisiert wird. Das geschieht durch Abspeichern einer vorgegebenen Zahl in jedem dieser Adreßzähler 32, wenn die Adressenschaltung 30 initialisiert wird. Diese Zahl ist in den einzelnen Zugriffseinheiten 18 unterschiedlich. Es ist die Anzahl der Datenbits im Bit-seriellen Datenfluß 12 zwischen der betreffenden Zugriffseinheit und der ersten Zugriffseinheit. Jedesmal wenn ein Datenbit im Bit-seriellen Datenfluß 12 an einer Zugriffseinheit vorbeifließt, inkrementiert die Adreßschaltung 30 dieser Zugriffseinheit den Adressenzähler 32 dieser Zugriffseinheit. Wenn die von einer Zugriffseinheit 18 ausgeführte Operation erfordert, daß die Adresse einer von ihr gefundenen Datensequenz an eine andere Zugriffseinheit 18 gegeben wird, geschieht das durch Einspeichern dieser Adresse in den Adressenzwischenspeicher 34, der dann durch das Gatter 38 auf den Adreßbus 36 geschaltet wird. Wenn z. B. eine Übereinstimmung zwischen einer Datensequenz und der Fragesequenz gefunden wird, schickt die Zugriffseinheit 18, die diese Übereinstimmung gefunden hat, diese Adresse der Datensequenz an alle anderen Zugriffseinheiten. Wenn eine andere Zugriffseinheit 18 diese Adresse findet, schaltet sie den Bit-seriellen Datenfluß 12 auf den Ausgabeverwalter, der im Führungssteuerungsprozessor 24 enthalten ist. In der bevorzugten Ausführungsform versorgt der gleiche Adreßbus alle Zugriffseinheiten 18, und eine Buszuteilungsvorrichtung ist vorgesehen, um Konflikte zwischen zwei oder mehr konkurrierenden Zugriffseinheiten zu lösen.
Das zweite Hauptelement, das in jeder Zugriffseinheit 18 vorkommt, ist der Begrenzerzähler 42, mit dessen Hilfe der Endbegrenzer gefunden wird, der zu einem bestimmten Anfangsbegrenzer gehört, die zusammen einen Unterausdruck in einer Datensequenz markieren. Wenn ein "?" in einer Fragesequenz mit einem Anfangsbegrenzer in der abgespeicherten Datensequenz verglichen wird, muß die Zugriffseinheit 18 warten, bis der entsprechende Endbegrenzer im Datenfluß gefunden wird, bevor er den Vergleich zwischen Daten- und Fragesequenz wieder aufnehmen kann. Das wird bewirkt durch Zählen der Begrenzer, die durch die Zugriffseinheit 18 laufen, bis der eine, der dem betreffenden Anfangsbegrenzer zugeordnet ist, ausfindig gemacht ist. Das Vergleichen wird dann mit dem auf diesen Endbegrenzer folgenden Datensequenzsymbol wieder aufgenommen. Da der übersprungene Unterausdruck seinerseits einen weiteren Unterausdruck enthalten kann, muß der Begrenzerzähler 42 sowohl die "(" als auch die ")" zählen. Der Begrenzerzähler 42 wird auf einen Anfangszustand gesetzt, sobald ein Variablensymbol mit einem Anfangsbegrenzer-Datensequenzsymbol verglichen wird. Bei jedem "(" wird er inkrementiert und bei jedem ")" wird er dekrementiert. Solange der Begrenzerzähler 42 einen anderen Wert enthält als sein Anfangszustand war, ist die Schaltung, die den Fragefluß mit dem Bit-seriellen Datenfluß vergleicht, gesperrt. Sobald der Begrenzerzähler 42 in seinen Anfangszustand zurückkehrt, wird die Vergleichsoperation wieder aufgenommen. Der Anfangsbegrenzer, der den Anfang des betreffenden Unterausdrucks markiert, wird bei diesem Prozeß ebenfalls gezählt. Der Begrenzerzähler arbeitet sowohl als Mittel zur Identifizierung des Endbegrenzers, der einem bestimmten Anfangsbegrenzer in einer Datensequenz entspricht, als auch als "Haltemittel", um anzuzeigen, daß das einem bestimmten Fragesymbol entsprechende Datensymbol an der Zugriffseinheit 18 noch nicht zur Verfügung steht.
Das dritte Hauptelement jeder Zugriffseinheit 18 ist das Vergleichsmittel zum Vergleichen der Daten- und Fragesequenzsymbole. Wie nachstehend noch eingehend besprochen wird, decodiert der Fragesequenzpuffer 20 die Fragesequenzsymbole in einem Bit-seriellen Fluß, der das gleiche Format hat, wie es für die Datensequenzsymbole benutzt wird, die im Bitseriellen Datenfluß 12 umlaufen. Da beide Flüsse Bit-seriell sind, genügt ein Komparator in der Form eines Ausschließlich- ODER-Gatters 50, um die beiden Bitströme zu vergleichen. Der Ausgang des Gatters 50 liegt an einer Flag 47, die auf einen ersten Zustand gesetzt wird, wenn das erste Symbol der zu testenden Datensequenz mit dem ersten Symbol der Fragesequenz verglichen wird. Wenn einer dieser Vergleiche keine Übereinstimmung zwischen den an der Zugriffseinheit 18 gelesenen Datensequenzsymbolen und den entsprechenden Fragesymbolen findet, wird die Flag 47 auf einen zweiten Zustand gesetzt. Wenn die Flag noch immer auf diesen ersten Zustand gesetzt ist, nachdem das letzte Symbol der Daten- und der Fragesequenz verglichen ist, muß die betreffende Datensequenz abgerufen werden. Eine Anzeiger-Weiterschaltung 44 überwacht diese Flag, und der Vergleich wird für die laufende Datensequenz unterbrochen, sobald eine Nichtübereinstimmung festgestellt wird.
Das vierte Hauptelement jeder Zugriffseinheit 18 ist die Anzeiger-Vorschubschaltung 44. Die Anzeiger-Vorschubschaltung 44 kommuniziert mit dem Fragespeicherpuffer 20 über die Signalleitung 55, wie nachstehend noch ausgeführt wird, und mit dem Führungssteuerungsprozessor 24 über den internen Bus 26. Sie kommuniziert auch mit den anderen Zugriffseinheiten über den internen Bus 26, der den Adreßbus 36 als Teil enthält.
Die Hauptfunktion der Anzeigervorschubschaltung 44 ist die Überwachung des Vergleichens der Bit-seriellen Flüsse der Fragesequenz und der Datensequenz, sowie Festlegen, welches Fragesequenzsymbol aus dem Fragespeicherpuffer 20 als nächstes in die Zugriffseinheit 18 geschickt werden soll. Die zu vergleichenden Symbole in jedem Bitfluß lassen sich für die Zwecke dieses Vergleichs in vier Typen einteilen: Konstante, Anfangsbegrenzer, Endbegrenzer und Variable. Es gibt 16 mögliche Kombinationen paarweiser Vergleiche, die an der Zugriffseinheit 18 gemacht werden können. Beim Durchführen dieser Vergleiche vergleicht die Anzeiger-Vorschubschaltung zunächst die Identifizierungsbits des Symbols. Diese Bits sind im Fragestatus-Zwischenspeicher 46 bzw. im Datenstatus- Zwischenspeicher 48 abgespeichert. Wenn die Identifizierungsbits eine mögliche Übereinstimmung zwischen den Symbolen anzeigen, geht die Anzeigervorschubschaltung 44 dazu über, die Datenbits der Symbole zu vergleichen.
Die etwaigen Ergebnisse dieser Vergleiche sind in Tabelle 1 zusammengefaßt. In jedem Fall muß die Anzeigervorschubschaltung 44 festlegen, ob der Vergleich fortgesetzt werden soll und, wenn der Vergleich fortgesetzt werden soll, welches Symbol der Fragesequenz zum nächsten Vergleich heranzuziehen ist. Die Wahl des nächsten Fragesequenzelements wird an den Fragespeicherpuffer 20 durch Signale auf der Kommunikationsleitung 55 gegeben. Jedesmal wenn ein Impuls auf die Leitung 55 gegeben wird, wird ein Zeiger vorgeschoben, der als Fragesequenzzeiger für diesen Zugriffseinheit bezeichnet wird. Jede Zugriffseinheit steuert einen Fragesequenzzeiger, der das Fragesymbol spezifiziert, das an die Zugriffseinheit geschickt werden soll. Wenn keine Impulse geschickt werden, wiederholt der Fragespeicherpuffer 20 den Bit-seriellen Fluß für das derzeitige Symbol. Wenn die Zugriffseinheit einen Impuls auf diese Leitung gibt, schickt der Fragespeicherpuffer 20 das nächste Symbol in der Fragesequenz. Wenn zwei Impulse gegeben werden, überspringt der Fragespeicherpuffer 20 ein Symbol in der Fragesequenz und der nächste Vergleich wird zwischen dem nächsten Symbol im Bit-seriellen Datenfluß 12 und dem Symbol durchgeführt, das zwei Stellen nach dem augenblicklichen im Fragespeicherpuffer 20 gespeichert ist.
In allen Fällen, abgesehen von zwei, ist die Prüfung der Identifikationsbits und höchstens zwei der nachfolgenden Datenbits im Fluß ausreichend, damit die Anzeigervorschubschaltung 44 ihre Entscheidung treffen kann. Diese zwei Fälle jedoch beinhalten den Vergleich einer Konstanten im Fragefluß mit einer Konstanten im Bit-seriellen Datenfluß 12, sowie den Vergleich eines Anfangsbegrenzers im Fragefluß mit einer Variablen im Bit-seriellen Datenfluß 12. Im ersten dieser beiden Fälle (Fall 1 in Tabelle 1) muß die Anzeigervorschubschaltung 44 die ganzen Datenwörter in beiden Flüssen untersuchen, um festzustellen, ob die beiden Konstanten übereinstimmen. Wenn nicht, wird der Vergleichsprozeß für diese Datensequenz abgebrochen. Wenn sie übereinstimmen, wird der Fragesequenzzeiger im Fragespeicherpuffer 20 vorgeschoben, um das nächste Fragesequenzelement durch Senden eines Impulses an den Fragespeicherpuffer 20 über die Leitung 55 anzuzeigen.
Im zweiten dieser Fälle (Fall 15 in Tabelle 1) wird eine Variable in der Datensequenz mit einem Anfangsbegrenzer in der Fragesequenz verglichen. Da diese Variable mit der ganzen Untersequenz verglichen wird, die mit diesem Anfangsbegrenzer beginnt, muß der Fragesequenzzeiger auf den zugehörigen Endbegrenzer in der Fragesequenz vorgeschoben werden. Wie oben bereits besprochen, wird jeder Anfangsbegrenzer in der Fragesequenz mit der Anzahl der zu überspringenden Symbole codiert, um zum zugeordneten Endbegrenzer zu gelangen. Diese Codierung erfolgt in der Form einer Folge von "1"-Bits in den Datenbits des Speicherworts, das zum Abspeichern dieses Anfangsbegrenzers benutzt wird, jeweils eine "1" für jedes zu überspringende Symbol. Wenn also der Endbegrenzer in der Fragesequenz 4 Symbole entfernt ist, enthält der Anfangsbegrenzer vier "1"en. Die Anzeigervorschubschaltung 44 schickt nur diese "1"en über die Leitung 55 in den Fragespeicherpuffer 20. Die Schaltung im Fragespeicherpuffer 20 schiebt den Fragesequenzzeiger vor. Nachdem der Fragesequenzzeiger auf den entsprechenden Endbegrenzer vorgeschoben ist, behandelt die Anzeigervorschubschaltung 44 diesen Falls so, als ob ein Vergleich zwischen Konstanten und einer Variablen betroffen sei, d. h., der Fragesequenzzeiger wird um ein Symbol in der Fragesequenz vorgeschoben und der Vergleich wird mit dem nächsten Symbol im Bit-seriellen Datenfluß 12 fortgesetzt.
Im Komplementärfall, der eine Variable in der Fragesequenz betrifft, die mit einem Anfangsbegrenzer im Datenfluß verglichen wird (Fall 12 in Tabelle 1), muß die Anzeigervorschubschaltung 44 warten, bis der entsprechende Endbegrenzer im Datenfluß vorbeikommt, bevor er den Fragesequenzzeiger vorschiebt. Das wird bewirkt durch Zählen der Anfangs- und Endbegrenzer im Begrenzerzähler 42, wie bereits diskutiert wurde.
In den übrigen 13 Fällen wird der Vergleich entweder fortgesetzt, in welchem Fall der Fragesequenzzeiger auf das nächste Fragesequenzsymbol vorgeschoben wird, oder der Vergleich wird abgebrochen, in welchem Fall die Position des Fragesequenzzeigers unverändert beibehalten wird.
In allen Fällen (Fall 5 bis 8), in denen ein Endbegrenzer in der Fragesequenz angetroffen wird, muß die Anzeigervorschubschaltung 44 die Datenbits prüfen, ob dieser Endbegrenzer auch wirklich die Fragesequenz-Endmarke ist. Wenn er diese Marke ist und die Anzeigervorschubschaltung 44 angewiesen wurde, im Teilvergleichsmodus zu arbeiten, wie nachstehend beschrieben wird, dann behandelt die Anzeigervorschubschaltung 44 diesen Fall so, als ob der Bit-serielle Datenfluß 12 einen Endbegrenzer enthielte, der das Ende der Datensequenz anzeigt. Wenn die Anzeigervorschubschaltung 44 im Vollvergleichsmodus arbeitet, würde ein Vergleich nur dann erfolgen, wenn auch der Datenfluß einen Endbegrenzer zum Datensequenzende aufwiese. Die restlichen Fälle in Tabelle 1 erklären sich selbst.
Zusätzlich zur Überwachung der Vergleichsfunktionen überwacht die Anzeigervorschubschaltung 44 auch das Löschen und die Ausgabe der Datensequenzen, initialisiert die Datensequenz- Identifikationsbits, und initialisiert den Speicher als Ganzes. Diese Operationen werden ausgeführt als Reaktion auf Signale vom Führungssteuerungsprozessor 24 her. Das Löschen und Ausgeben der Datensequenzen erfordert, daß die Anzeigervorschubschaltung 44 die Adresse der gerade zu prüfenden Datensequenz mit der auszugebenden oder zu löschenden Datensequenz vergleicht. Diese Adresse wird auf den Adreßbus 36 gelegt als Ergebnis einer vorhergehenden Vergleichsanweisung. Die Anweisung zum Löschen bzw. Ausgeben wird vom Führungssteuerungsprozessor 24 ausgegeben. Wenn die Adresse mit der Adresse der augenblicklich von der Zugriffseinheit 18 gelesenen Bit-seriellen Datensequenz übereinstimmt, wird eine geeignete Maßnahme getroffen. Wenn die Datensequenz ausgegeben werden soll, wird sie in den Ausgabeverwalter kopiert, der im Führungssteuerungsprozessor 24 angeordnet ist. Wenn die Datensequenz gelöscht werden soll, werden die Identifizierungsbits und die ersten zwei Datenbits von jedem Wort in der Datensequenz auf den betreffenden Wert gesetzt zum Anzeigen, daß das Wort ein Leerraum ist.
Zum Löschen einer gegebenen Sequenz wird diese Sequenz als Fragesequenz zum erfindungsgemäßen Gerät geschickt. Die Vergleichsoperation bewirkt, daß diese Sequenz "abgerufen" wird d. h., ihre Adresse wird auf den Adreßbus 36 gelegt. Dann wird die Löschanweisung gegeben.
Die Initialisierung des Speichers vor der Suche nach allen Datensequenzen, die der Fragesequenz entsprechen, beinhaltet das Setzen der ersten zwei Datenbits des ersten Symbols jeder Datenfolge. Diese Bits werden auf den oben genannten "Ungesehen"-Zustand gesetzt. Die Initialisierung der Speicher als ganzes wird bewirkt durch Setzen der Identifizierung und der ersten zwei Datenbits auf jedem Wort auf den ,'Leer"-Zustand.

BEFEHLSSATZ

Ein herkömmlicher Direktzugriffsspeicher hat einen Befehlssatz von nur zwei Befehlen, nämlich Lesen und Schreiben. Das erfindungsgemäße Gerät weist wegen seiner vergrößerten Funktionalität 7 Befehle auf, die nachstehend zusammenfassend beschrieben werden. Diese Operationen werden eingeleitet durch Setzen eines Code auf Bus 30, der vom Führungssteuerungsprozessor 24 benutzt wird, um mit dem Datenverarbeitungssystem zu kommunizieren, in dem des vorliegende System arbeitet. Jeder Code kann in der Form eines speziellen Fragesymbols oder von Signalen auf einer oder mehreren Steuerleitungen gegeben werden. Der Führungssteuerungsprozessor decodiert diese Codes und leitet die richtige Aktion in Inneren des erfindungsgemäßen Geräts ein.
Die Befehle FIND MATCH [Übereinstimmung suchen] und FIND PARTIAL MATCH [teilweise Übereinstimmung suchen] werden in zwei Schritten ausgeführt. Zunächst wird die Fragesequenz symbolweise über den Verbindungsbus 30 in das erfindungsgemäße Gerät geschickt. Da der Anfang und das Ende der Fragesequenz durch besondere Begrenzersymbole markiert sind, kann der Führungssteuerungsprozessor 24 feststellen, wenn das letzte Symbol eingegangen ist. Sobald das letzte Fragesymbol in den Fragespeicherpuffer 20 eingespeichert ist, werden die geeigneten Bits in jedem Speicherwort, die den Anfang einer Datensequenz im Speicher angeben, auf den "ungesehen" Zustand gesetzt und die Zugriffseinheiten werden angewiesen, die Vergleichsoperation durchzuführen. Der Befehl FIND PARTIAL MATCH unterscheidet sich von dem Befehl FIND MATCH nur dadurch, daß er alle Datenfolgen zurückgibt, die mit der Fragesequenz anfangen, anstatt nur diejenigen Datensequenzen, die ganz mit der Fragesequenz übereinstimmen.
Sobald eine Übereinstimmung gefunden ist, führt der Befehl GIVE MATCH [Übereinstimmung ausgeben] dazu, daß der Führungssteuerungsprozessor 24 die gefundenen Datensequenzen über den Bus 30 an das externe Datenverarbeitungssystem sendet. Wenn dieser Befehl gegeben wird, wenn keine Übereinstimmung entdeckt wurde, wird er ignoriert. Jedes Mal, wenn der Befehl an den Führungssteuerungsprozessor 24 gegeben wird, wird eine der Datensequenzen, die mit der Fragesequenz übereinstimmt, an das externe Datenverarbeitungssystem gegeben.
Der Befehl DELETE MATCH [Übereinstimmung löschen] wird benutzt, um eine Datensequenz aus dem Datenspeicher zu löschen. Er muß nach dem Befehl GIVE MATCH gegeben werden, in dem die Datensequenz, die gelöscht werden soll, als Fragesequenz gesendet wurde. Dieser Löschbefehl führt zur Identifizierung, und die Datenbits aller Wörter in der Datensequenz, deren Adresse im Augenblick vom Zwischenspeicher auf den Adreßbus 36 gelegt werden, werden auf die Bezeichnung "leer" gesetzt, wie oben bereits beschrieben wurde.
Der Befehl ADD RECORD [Datensatz hinzufügen] wird benutzt, um eine neue Datensequenz in den Bit-seriellen Datenfluß 12 einzuspeisen. Das tatsächliche Einschieben der Datensequenz wird vom Eingabepuffer und seinem zugeordneten Eingabeprozessor 16 vorgenommen, wie nachstehend noch genauer beschrieben wird. Der Führungssteuerungsprozessor 24 schickt die einzufügende Datensequenz nur über den internen Bus 26 an den Eingangspuffer 14 sobald sie der Führungssteuerungsprozessor 24 über den aus 30 erhält. Nach dem Eingang des letzten Symbols der neuen Datensequenz signalisiert der Führungssteuerungsprozessor 24 dem Eingabeprozessor 16, die neue Datensequenz einzuschieben.
Die Befehle INIT.MEMORY [Speicher initialisieren] und CLEAR TAGS [Markierung löschen] führen dazu, daß die Identifizierungsbits bzw. die gesamten Datenwörter gelöscht werden. Diese Befehle werden benutzt, um den Speicher zu löschen, bevor er mit der ersten Datensequenz geladen wird.

FRAGESPEICHERPUFFER

In der bevorzugten Ausführungsform der vorliegenden Erfindung ist der Fragespeicherpuffer 20 ein Speicherpuffer mit mehreren Eingängen zum Abspeichern der Fragesequenzen, die im Augenblick benutzt werden, um Datensequenzen aus dem Bitseriellen Datenfluß 12 auszuwählen. Ein einziger Speicherpuffer wird benutzt, um alle Zugriffseinheiten 18 zu bedienen, um den zur Aufnahme der Fragesequenz benötigten Speicherplatz zu minimieren. Zusätzlich zum Abspeichern der Fragefolge ist der Fragespeicherpuffer auch zuständig für das Liefern einer Bit-seriellen Darstellung der Fragesymbole an die verschiedenen Zugriffseinheiten 18. Jede Zugriffseinheit 18 braucht einen unabhängigen Zugriff zu jedem beliebigen Symbol, das im Fragespeicherpuffer 20 abgespeichert ist. Das wird bewirkt durch eine Anordnung von Schaltern und Zeigern. Jede Zugriffseinheit steuert einen Zeiger, der das Wort im Fragespeicherpuffer, das zu ihm geschickt werden soll, durch die Schalteranordnung spezifiziert.
Der Fragespeicherpuffer 20, der in der bevorzugten Ausführungsform der vorliegenden Erfindung eingesetzt wird, ist in Fig. 4 schematisch dargestellt. Er besteht aus einer Speicheranordnung 80, die aus einer Vielzahl von Schieberegistern 84 besteht, die in Fig. 4(a) gezeigt wird, wobei jedes derselben zum Abspeichern eines Symbols aus der Fragesequenz, die im Augenblick gerade durchgesucht wird, benutzt wird, die Symbole werden aus dem Bus vom Führungssteuerungsprozessor 24 in die Speicheranordnung geladen. In der bevorzugten Ausführungsform wird das erreicht durch Verschieben jedes der aufeinanderfolgenden Symbole der Fragesequenz in die Anordnung von Schieberegistern in der Richtung, die durch den vertikalen Pfeil 90 angegeben wird. Jedes der Schieberegister 84 wälzt seinen Inhalt um durch Verschieben in der Richtung, die durch den Pfeil 92 in der Fig. 4(a) gezeigt wird. Diese Umwälzoperation schafft einen Bit-seriellen Datenfluß von jedem Wort. Diese Bit-serielle Darstellung der einzelnen Fragesymbole kann zu einer oder mehreren Zugriffseinheiten 18 geschickt werden. Wenn die Bits am Ende der einzelnen Schieberegister herausgeschoben werden, werden sie als erste Bits in das Register 88 und auch als Eingaben an einen oder mehrere der Zugriffseinheitsschalter 82 benutzt. Jede Zugriffseinheit 18 hat einen Zugriffseinheitsschalter 82. Die Auswahl, welches Wort an eine bestimmte Zugriffseinheit 18 geschickt wird, wird getroffen durch Setzen eines Fragesequenzzeigers 94, der jeder Zugriffseinheit 18 zugeordnet ist.
Jede Zugriffseinheit wird durch einen Zugriffseinheitsschalter 82 bedient, der nur diese eine Zugriffseinheit 18 bedient und der die ganze Länge der Speicheranordnung 80 entlangläuft. Dieser Schalter ermöglicht es, daß die Zugriffseinheit 18 ein beliebiges Fragesequenzsymbol als Bitseriellen Fluß empfängt. Das Schieberegisterwort 84, das auf diese Zugriffseinheit 18 geschaltet ist, wird durch einen Fragesequenzzeiger 94 bestimmt, der unter der Steuerung der betreffenden Zugriffseinheit 18 steht. Jeder Fragesequenzzeiger 94 besteht aus einem Schieberegister, in dem eines der Bits auf "1" und die übrigen Bits auf "0" gesetzt sind. Der Ort der Schiebeanordnung, an dem die "1" steht, liegt an der Leitung 56, die benutzt wird, um eine Bit-serielle Darstellung des an diesem Ort stehenden Fragesequenzsymbols in die diesem Fragesequenzzeiger 94 zugeordnete Zugriffseinheit 18 zu schicken. Jedes dieser Schieberegister kann von dieser Zugriffseinheit 18, die an dieses Schieberegister angeschlossen ist, durch Signale auf einer Leitung 55, die diese Zugriffseinheit 18 mit dem Fragespeicherpuffer 20 verbindet, um ein Signal verschoben werden. Jeder gesendete Impuls bewirkt, daß der Fragesequenzzeiger 94 in der Speicheranordnung 80 um ein Wort weitergeschoben wird. Die Fragesequenzzeiger 94 werden als Teil der Initialisierungsoperationen, die zu Beginn jeder Suche ausgeführt wird, gesteuert vom Führungssteuerungsprozessor 24, der mit dem Steuerprozessor 96 des Fragespeicherpuffers über den Bus 28 kommuniziert, auf das erste Symbol in der Fragesequenz gesetzt. Jede Zugriffseinheit 18 stellt den ihr zugeordneten Fragesequenzzeiger vor dem Beginn eines Vergleichs mit dem ersten Symbol einer Datensequenz, die an dieser Zugriffseinheit 18 gelesen wird, auf das Symbol zurück, das den Anfang der Fragesequenz markiert.

DATENEINGABE

Das Hinzufügen einer Datensequenz zu dem Speicher ist wegen der seriellen Art der abgespeicherten Datensequenzen kompliziert. Obwohl der absolute Ort einer bestimmten Datensequenz nicht bedeutsam ist, muß doch jede Datensequenz in einem zusammenhängenden Speicherstellenblock abgespeichert werden. Wenn Datensequenzen gelöscht werden und dem Bitseriellen Datenfluß 12 neue Daten hinzugefügt werden, kann der freie Speicherraum aufgesplittert und über den Bitseriellen Datenfluß 12 verteilt werden, wodurch es unmöglich wird, eine neue Datensequenz hinzuzufügen, auch wenn genügend freier Raum vorhanden ist. Zur Korrektur dieses Problems ist besondere Hardware vorgesehen, um diesen Raum durch Konsolidierung des freien Raums rückzugewinnen, so daß er zum Abspeichern neuer Datensequenzen benutzt werden kann. Dieser Prozeß wird nachstehend als "Garbage Collection" [Speicherbereinigung] bezeichnet.
Die Speicherbereinigung ist ein Problem, das bei jedem Speichersystem auftritt, in dem Daten in Datensequenzen abgespeichert sind, die zusammenhängende Speicherwörter ausfüllen müssen. Dieses Problem wird herkömmlicherweise dadurch gelöst, daß die Daten im Speicher in einen einzelnen zusammenhängenden Speicherwörterblock umkopiert werden, wobei die freien Räume zwischen den Datensequenzen zu einem einzigen Speicherwortblock, üblicherweise am Ende des von den bereits abgespeicherten Datensequenzen im Speicher eingenommenen Raumes verschoben werden. Diese Lösung setzt voraus, daß auf den Speicher während dieser Umkopierungsaktion nicht zugegriffen werden kann. Die vorliegende Erfindung vermeidet diese Stillstandzeit.
In der vorliegenden Erfindung ist die Speicherbereinigungsfunktion kombiniert mit der Dateneingabefunktion auf eine Weise, die es ermöglicht, daß die Speicherbereinigung jedesmal, wenn neue Datensequenzen in den Bit-seriellen Datenfluß 12 eingespeichert werden, automatisch ausgeführt wird. Das Verfahren benutzt eine Schleife des Schieberegisterspeichers variabler Länge, genannt "Bubble" [Blase], die in den Bit-seriellen Datenfluß 12 eingeschoben werden kann. Nehmen wir jetzt Bezug auf Fig. 5a; wenn die Blase 120 in den Bit-seriellen Datenfluß 12 eingeschoben wird, verlassen die umlaufenden Daten im Bit-seriellen Datenfluß 12 diesen Bit-seriellen Datenfluß 12 an einem bestimmten Punkt 100, treten am Punkt 102, der wie nachstehend noch ausgeführt wird, vom Inhalt der Blase 120 bestimmt ist, in die Blase 120 ein, durchqueren die Blase 120 und treten am Punkt 104, den sie als nächstes durchquert hätten, wenn die Blase 120 nicht eingeschoben worden wäre, wieder in den Bit-seriellen Datenstrom 12 ein.
Durch die Blase 120 wird eine neue Datensequenz in den Bitseriellen Datenfluß 12 eingefügt. Die Datensequenz wird zunächst unter der Steuerung durch den Führungssteuerungsprozessor 24 in die Blase 120 geladen. Dann wird die Blase 120 in den Bit-seriellen Datenfluß 12 eingefügt, wie in Fig. 5(a) gezeigt wird. Nehmen wir jetzt Bezug auf Fig. 5(b); während die Daten im Bit-seriellen Datenfluß 12 in die Blase 120 fließen, wie durch den gestrichelten Bereich 106 angedeutet wird, wird die neue, in der Blase 120 abgespeicherte Datensequenz in den Bit-seriellen Datenfluß 12 geschoben, wie durch den kreuzweise schraffierten Bereich bei 108 angezeigt ist. Die Daten werden in die Blase 120 hinein- bzw. herausgeschoben, so als ob die Blase ein Teil des Bit-seriellen Datenflusses 12 wäre.
Die Länge der Blase 120 kann geändert werden durch Verändern des Punkts 102 in der Blase 120, an dem die Daten, die den Bit-seriellen Datenfluß 12 verlassen, in die Blase 120 eintreten. Wenn leere Speicherwörter in die Blase 120 eingeschoben werden, wie in Fig. 5(c) bei 110 gezeigt wird, bewegt sich der Eingangspunkt von 102 zu einem Punkt 142 eben am Anfang der leeren Wörter. Das läßt die Blase 120 in der Konfiguration, wie in Fig. 5(d) gezeigt wird. Das bewirkt, daß die Blase "schrumpft" und die leeren Wörter in dem ungebrauchten Teil der Blase gelassen werden. Wenn die Länge der Blase auf Null schrumpft, ist die Eingabeoperation abgeschlossen. Wenn also eine neue Datenfolge eingegeben wird und nicht genügend zusammenhängender Platz zum Abspeichern vorhanden ist, werden automatisch zwei oder mehr kleinere Räume kombiniert, um einen Raum zu schaffen, der groß genug zum Abspeichern ist, und diese Operation verbraucht nicht mehr Zeit, als sie zur Eingabe der Datensequenz ohne Speicherbereinigung erforderlich wäre, weil andere Speicherfunktionen weiterlaufen können während die Daten in die Blase 120 eingeschoben werden.
Wenn eine einzuschiebende Datenfolge größer ist als die Blase 120, wird sie in eine Reihe kurzer Einschübe unterteilt, deren jeder kleiner oder gleich der maximalen Größe der Blase 120 ist. Nach jedem Einschub verzeichnet der Eingangsprozessor 14, der die Blasenoperation steuert, den Ort, an dem der letzte Eingang gemacht wurde. Die Blase 120 wird dann neu geladen und eingeschoben, sobald dieser Ort den Blaseneinschubpunkt 104 passiert.

GENAUE BESCHREIBUNG DER HARDWARE-IMPLEMENTIERUNG

Die Vorrichtung der vorliegenden Erfindung wurde auf einem einzigen Chip implementiert unter Anwendung der Standard-CMOS Integrierten Schaltungstechniken. Der Speicher für den Bitseriellen Datenfluß 12 besteht aus einem 32000-Bit-Schieberegister, das nach den CMOS Intergrierten-Schaltungstechniken gebaut wurde, die dem Fachmann in der Herstellung integrierter Schaltkreise geläufig sind. Diese besondere Ausführungsform enthält 8 Zugriffseinheiten 18, und der Fragespeicherpuffer 20 hat 36 Wörter zum Abspeichern der Fragesequenz.
Jeder der oben besprochenen Steuerschaltkreise ist als endlicher Automat in der Form programmierbarer logischer Felder konstruiert unter Anwendung der dem Fachmann in der Schaltkreisherstellung bekannten Techniken. Die Anzeigervorschubschaltung 44 in jeder der Zugriffseinheiten 18 ist typisch. Der von dem endlichen Automaten der Anzeigervorschubschaltung ausgeführte Algorithmus ist in Fig. 6 schematisch dargestellt. Diese Maschine läßt sich in zwei Teile unterteilen. Der erste Teil wird zum Erfassen der Übereinstimmungen benutzt und der zweite verzeichnet jeden erfolgreichen Vergleich. Nehmen wir jetzt Bezug auf Fig. 6; der Übergang vom Anfangszustand, Zustand 0, zum Zustand 1 erfolgt, wenn die Vergleichsfunktion verlangt wurde, die Statusidentifikationsbits des derzeitigen Datenwortes und der Fragesequenz in den Datenstatus-Zwischenspeicher 48 bzw. in den Fragezustandstatus-Zwischenspeicher 46 eingespeist wurden, und diese Identifikationsbits angeben, daß das Datenwort der Start einer "ungesehenen" Datenfolge ist. Wenn diese Bedingungen erfüllt sind, wird die Zustandsmaschine initialisiert und geht auf den Vergleichszustand über, der in Fig. 6 als Zustand 1 markiert ist, und die Adresse des ersten Symbols der untersuchten Datensequenz wird in den Adressen- Zwischenspeicher 34 eingegeben, der dieser Zugriffseinheit 18 zugeordnet ist. Das Vergleichen erfolgt dann in einem oder zwei weiteren Zuständen, in Abhängigkeit von den Identifikationsbits der betreffenden Daten- und Fragewörter. Wenn entweder das Datenwort oder das Fragewort ein Endbegrenzer ist, geht die Maschine auf Zustand 2 über und Tests zur Suche nach dem Ende der Vergleichsoperation oder nach sonstige Bedingungen, die einem Vergleich mit einem Endbegrenzer zugeordnet sind, werden gemacht. Wenn keines der Wörter einen Endbegrenzer enthält, geht die Zustandsmaschine auf Zustand 3 über, in dem die zwei Wörter miteinander verglichen werden. Wenn die Ergebnisse der Operation in Zustand 3 anzeigen, daß die Wörter übereinstimmen, wird das nächste im Vergleich zu benutzende Element spezifiziert, und die Maschine kehrt in den Zustand 1 zurück, um auf die nächste Vergleichsoperation zwischen dem Fragewort und dem nächsten Datenwort im Umlaufspeicher zu warten. Wenn das Datenwort als nicht übereinstimmend mit dem Fragewort befunden wird, kehrt die Maschine in den Zustand 0 zurück. Wenn eine Übereinstimmung gefunden wird, geht die Zustandsmaschine auf den zweiten Abschnitt über, in dem Übereinstimmungen gemeldet werden.
Ein dem Umlaufspeichersystem innewohnendes Problem ist, daß zu dem Zeitpunkt, an dem feststeht, daß die Datensequenz mit der Fragesequenz übereinstimmt, diese die Zugriffseinheit 18 bereits passiert hat, an der die Vergleiche gemacht wurden, und daher nicht mehr zum Auslesen an dieser Zugriffseinheit 18 zur Verfügung steht, bis sie wieder rezirkuliert wird. Die Lösung für dieses Problem, die bei der vorliegenden Erfindung angewandt wurde, ist, die Startadresse der zu prüfenden Datensequenz als Teil der Initialisierungsfunktion ab zuspeichern, wenn die Maschine vom Zustand 0 auf den Zustand 1 übergeht. Sobald gefunden wird, daß die Datensequenz übereinstimmt, wird diese Adresse den anderen Zugriffseinheiten 18 mitgeteilt. Wenn dann eine andere Zugriffseinheit 18 die an dieser Adresse stehende Datensequenz liest, kopiert sie den Datenfluß in den Ausgabeverwalter im Führungssteuerungsprozessor 24. Somit kann die Datensequenz ausgelesen werden, bevor sie wieder an der Zugriffseinheit 18 vorbei läuft, in der die Übereinstimmung festgestellt wurde. Da sich alle Zugriffseinheiten 18 für die Zwecke dieser Kommunikation in einen Adreßbus 36 teilen, wird ein Zuteilungsverfahren benutzt, ähnlich wie im UNIBUS-Zuteilungsverfahren, um Konflikte auf dem Adreßbus 36 zu vermeiden. Dieses Verfahren ist in den Zuständen 4, 5 und 6 im Zustandsdiagramm in Fig. 6 dargestellt. Die Zugriffseinheit fordert eine Busfreigabe durch ein Signal auf der FAM-Leitung auf dem Bus an. Wenn der Bus frei ist, bekommt die Zugriffseinheit 18 eine "Freigabe", die sie durch das "Sack"-Signal quittiert. Sobald der Bus frei ist, übernimmt die Zugriffseinheit 18 die Adreßbussteuerung 36 durch Generieren eines Bus "Busy" [besetzt] Signals. Sobald die Zugriffseinheit 18 die Steuerung des Adreßbusses 36 übernommen hat, wird die Adresse einer übereinstimmenden Datensequenz auf dem Adreßbus 36 gehalten, bis die Datensequenz gefunden und die Ausgabe abgeschlossen ist.
Verfahren zum Umsetzen der oben und in Fig. 6 beschriebenen Logik eines endlichen Automaten in ein programmierbares logisches Feld zur Ausführung des oben beschriebenen Algorithmus sind dem Fachmann in der VLSI (hochintegrierten) Schaltkreistechnologie bekannt (vgl. J. Millman, MICRO- ELECTRONICS, McGraw-Hill Book Co.). Sobald die Funktionen eines endlichen Automaten definiert sind, wird ein Programm für das programmierbare logische Feld geschrieben. Dieses Programm kann dann in einem beliebigen einer Anzahl Systeme implementiert werden, die zum Bau solcher Anordnungen im VLSI-Schaltkreisbau benutzt werden.
Ein Programm für ein programmierbares logisches Feld zum Implementieren der Funktionen der Anzeiger-Vorschubschaltung 44 wie oben besprochen und in Fig. 6 schematisch dargestellt, ist in Tabelle 2 als Beispiel gezeigt, wie die von den verschiedenen endlichen Automaten durchgeführten Funktionen, die in der bevorzugten Ausführungsform benutzt werden, implementiert werden können. Die Eingänge zur Anzeiger-Vorschubschaltung im programmierbaren logischen Feld sind in Tabelle 2 oben gezeigt, durch eine senkrechte Linie von den Ausgängen getrennt. Die Eingaben und Ausgaben, die nur in den Zuständen 4, 5 und 6 funktionieren, sind in der Tabelle 2 unten gezeigt. An einem beliebigen Platz in der Tabelle, an dem ein leerer Platz in einer Eingabespalte ist, wird dieser Eingang ignoriert. An einer beliebigen Stelle in Tabelle 2, an der in einer Ausgabespalte ein leerer Platz ist, wird diese Ausgangsleitung nicht aktiviert. Der augenblickliche Zustand des endlichen Automaten ist in drei "Zustand"-Bits codiert - State0, State1 und State2. Die Bits des Fragesequenzsymbols, die verglichen werden, sind durch "P" bezeichnet, wobei P0 und P1 die Identifikationsbits des derzeitigen Fragesequenzsymbols sind, das in den Fragesequenz-Zwischenspeicher 46, gezeigt in Fig. 3, eingegeben ist. Pbit und Dbit beziehen sich auf die laufenden Bits in den zwei Bit-seriellen Flüssen, die miteinander verglichen werden. Die dem Datensequenzsymbol zugeordneten Bits werden mit "D" bezeichnet, wobei D0 und D1 die Identifikationsbits des laufenden Datensymbols sind, die in den Datenzustandszwischenspeicher 48 gemäß Fig. 3 eingespeichert sind. Die Flag ist die Flag 42, die den Ausgang des Ausschließlich-ODER-Gatters 50 gemäß Fig. 3 überwacht. Diese Flag speichert das Ergebnis des letzten Vergleichs, der vom Ausschließlich-ODER-Gatter gemacht wurde, wenn das "WE" Ausgangssignal "1" war. Die XOR Eingabeleitung zeigt an, daß ein Start eines Datensequenzsymbols von der Zugriffseinheit 18 gesehen wurde, während der Führungssteuerungsprozessor 24 einen Vergleich angefordert hat. Die "STATUS" Eingangsleitung zeigt an, daß die Identifikationsbits D0, D1, P0 und P1 über den Zwischenspeicher gelaufen sind. Der "SLOT" Eingang zeigt an, daß im Datenfluß ein neues Wort angefangen hat. Schließlich zeigt die "J=0" Leitung daß durch Zählen der Anfangs- und Endbegrenzer im Begrenzerzahler 42 gemäß Fig. 3 ein Unterausdruck im Datenfluß übersprungen wird. Dieser Eingang wird durch das Initialisierungssignal INIT. auf 1, und durch den COUNT Ausgang auf 1 gesetzt. Die INCR.- und DECR.-Ausgänge bewirken, daß dieser Zähler inkrementiert bzw. dekrementiert wird. Wenn der Zähler zu seinem ursprünglichen Zustand zurückkehrt, wird "J=0" von 0 auf 1 zurückgesetzt.
Die ausschließlich in den Zuständen 4, 5 und 6 benutzten Ein- und Ausgänge werden zum Implementieren des in der bevorzugten Ausführungsform angewandten Buszuteilungsverfahrens benutzt. Der Eingang "BG" zeigt an, daß der Bus für die Zugriffseinheit 18 freigegeben wurde. Wenn der Bus nicht freigegeben wurde, behält das Programm das "FAM" Signal bei, das eine Busfreigabe anfordert. Sobald der Bus freigegeben ist, quittiert die Zugriffseinheit 18 die Freigabe durch den "Sack" -Ausgang und tritt in den Zustand 5 ein, wo es darauf wartet, daß der Bus frei wird, was durch den "BBSY" [Bus Busy] Eingang angezeigt wird. Sobald der Bus frei ist, übernimmt die Zugriffseinheit 18 die Bussteuerung durch den "BBSY" Ausgang, der an bleibt, bis der Führungssteuerungsprozessor 24 signalisiert, daß die betreffende Datensequenz über den "Ssync" Eingang ausgegeben wurde.
Der Einfachheit halber wurden der "Unvollständige Vergleichs- Modus, in dem Datenfolgen, die länger als die Fragesequenzen sind, die aber mit der Fragesequenz beginnen, ebenfalls zurückgegeben werden, nicht im Programm für das programmierbare logische Feld gezeigt. Auf ähnliche Weise wird das Programmieren für die verschiedenen nicht übereinstimmenden Funktionen, die von der Zugriffseinheit ausgeführt werden (Datensequenz löschen, Speicher initialisieren, usw.) weggelassen.
Die logischen Schaltungen, die im Eingangsprozessor 16, im Führungssteuerungsprozessor 24 und im Fragespeicherpuffer 20 benutzt werden, sind ähnlich konstruiert wie endliche Automaten. Detaillierte Zustandsdiagramme für diese Maschinen sind dem Fachmann der VSLI hochintegrierten Schaltkreistechnologie geläufig.
Hier wurden verschiedene Ausführungsformen der Erfindung diskutiert, jedoch ist es offensichtlich, daß verschiedene Änderungen und Modifikationen möglich sind, ohne vom Umfang und dem Sinngehalt der vorliegenden Erfindung abzuweichen. TABELLE I Spezifische Vergleichsoperationen Identifikationsgruppenvergleiche Fragesequenz ID-Gruppe Datensequenz ID-Gruppe [Konstante] Unbenannt Bits Keine Übereinstimmung stop Symbole Übereinst. Keine Übereinstimmung Fall 1 Satzende überprüfen Fälle 5-8 Symbole Übereinst.* Fragesymbol halten bis Zähler=0 Keine Übereinstimmung Stop Frage-Sequenz um so viele Wörter überspringen in Daten-Bits codiert * Nächste zu vergl. Symbole ist jeweils nächstes Symbol im Datenfluß

TABELLE II

PLA Programm für Statusübereinstimmung Eingänge Ausgänge

Claims

1. Speichersystem (10) zur Speicherung und Abfrage von Symbol-Datensequenzen mit einem Umlaufspeicher (12) bestehend aus:

einem ersten Feld von Speicherzellen zur Speicherung von einer oder mehreren Datensequenzen, wobei jede Datensequenz aus einem oder mehreren Symbolen besteht sowie Einrichtungen, welche die sequentielle Zirkulation dieser Symbole an einer Vielzahl von Zugriffspunkten (22) vorbei veranlassen;

Einrichtungen (24), welche eine an das Speichersystem (10) angekoppelte Symbol-Abfragesequenz empfangen;

ein zweites Feld von Speicherzellen umfassenden Einrichtungen (20) zur Speicherung dieser Symbol-Abfragesequenz;

Abfrageeinrichtungen (18), welche operativ mit jedem Zugriffspunkt zum Auffinden von einer oder mehreren Symbolsequenzen von den dem ersten Feld der Symbol-Abfragesequenz entsprechenden Speicherzellen gekoppelt sind, dadurch gekennzeichnet, daß das Speichersystem (10) ferner mit den Zugriffspunkten gekoppelte Einrichtungen (30) für die Anfrageeinrichtungen zur Kommunikation untereinander auf einen internen Bus (26, 36) umfaßt, wobei die Abfrageeinrichtungen (18) jedesmal, wenn eine der Abfrageeinrichtungen (18) feststellt, daß eine Datensequenz an ihr vorbeizirkuliert wird, diese mit der Abfragesequenz vergleicht,

und daß diese Abfrageeinrichtung (18) den Ort der Datensequenz auf dem internen Bus (26, 36) den anderen Abfrageeinrichtungen mitteilt, wobei die erste die Datensequenz feststellende Abfrageeinrichtung (18) diese über den internen Bus (26, 36) zur weiteren Verarbeitung weitersendet.

2. Speichersystem nach Anspruch 1, dadurch gekennzeichnet, daß Einrichtungen (14) zum Empfang einer Symbol-Datensequenz mit dem Umlaufspeicher (12) und zur Speicherung der empfangenen Symbol-Datensequenz in dem ersten Feld von Speicherzellen gekoppelt sind.

3. Speichersystem nach Anspruch 1 oder 2, dadurch gekennzeichnet, daß die Abfrageeinrichtungen (18) alle Symbol-Datensequenzen auffinden, welche identisch mit der Symbol-Abfragesequenz sind.

4. Speichersystem nach Anspruch 1 oder 2, dadurch gekennzeichnet, daß die Symbol-Datensequenzen und die Symbol-Abfragesequenz drei verschiedene Symboltypen, nämlich Begrenzer, Konstanten und Variable umfassen,

und daß die Abfrageeinrichtungen (18) alle Symbol-Datensequenzen auffinden, die der Symbol-Abfragesequenz entsprechen, wobei eine Symbol-Datensequenz als einer Abfragesequenz entsprechend definiert ist, wenn beide Sequenzen dadurch identisch werden, daß jede Variable in jeder Sequenz durch eine Konstante oder eine Kombination von Konstanten und Begrenzern ersetzbar ist, wobei die Kombination mit einem Begrenzer beginnt und endet.

5. Speichersystem nach Anspruch 4, dadurch gekennzeichnet, daß die Abfrageeinrichtungen (18) eine Vielzahl von Zugriffsprozessoren umfassen, die operativ mit den Zugriffspunkten (22) verbunden sind, und jeder Zugriffsprozessor erste Anzeigeeinrichtungen (32) zur Identifikation einer Symbol- Datensequenz umfaßt,

daß zweite Anzeigeeinrichtungen (94) zur Identifikation einer Symbol-Abfragesequenz vorhanden sind,

daß Vergleichseinrichtungen (50) die durch die ersten Anzeigeeinrichtungen identifizierte Symbol-Datensequenz mit der durch die zweiten Anzeigeeinrichtungen (94) identifizierten Symbol-Abfragesequenz vergleichen und ein Ausgangssignal in einem von zwei alternativen Zuständen erzeugen, wobei ein Übereinstimmungszustand anzeigt, daß zwei miteinander verglichene Symbole gleich oder zumindest eines der Symbole eine Variable ist, und ferner ein Nicht-Übereinstimmungszustand anzeigt, daß zwei Symbole verschieden und keines der beiden Symbole eine Variable ist,

daß Kennzeichnungseinrichtungen (47) auf das Eingangssignal der Vergleichseinrichtungen ansprechen und die Erzeugung eines Ausgangssignals im nicht übereinstimmenden Zustand anzeigen,

und daß Anzeigeweiterschaltungen (44) umfassen:

Einrichtungen, welche einerseits die ersten Anzeigeeinrichtungen zur Anzeige des ersten Symbols einer ausgewählten Datensequenz und andererseits die zweiten Anzeigeeinrichtungen (94) zur Anzeige des ersten Symbols der Abfragesequenz sowie die Vergleichseinrichtungen veranlassen, diese identifizierten Symbole zu vergleichen;

Einrichtungen, welche die ersten Anzeigeeinrichtungen (32) zur Identifizierung eines nachfolgenden Symbols der Datensequenz und andererseits die zweiten Anzeigeeinrichtungen (94) zur Identifizierung eines nächstfolgenden Symbols der Abfragesequenz sowie die Vergleichseinrichtungen (50) veranlassen, diese identifizierten Symbole zu vergleichen, bis eine Endbedingung festgestellt wird;

Einrichtungen zur Feststellung der Endbedingung;

und Einrichtungen (30), welche auf die Endbedingung ansprechen und die ausgewählte Datensequenz ausgeben, wenn die Kennzeichnungseinrichtungen (47) anzeigen, daß bei keinem der Vergleiche ein Nicht-Übereinstimmungssignal erzeugt worden ist.

6. Speichersystem nach Anspruch 5, dadurch gekennzeichnet, daß die Endbedingung definitionsgemäß auftritt, wenn die Vergleichseinrichtungen (50) das letzte Symbol der Abfragesequenz mit einem Symbol der Datensequenz vergleichen.

7. Speichersystem nach Anspruch 5, dadurch gekennzeichnet, daß die Endbedingung definitionsgemäß auftritt, wenn die Vergleichseinrichtungen (50) das letzte Symbol der ausgewählten Datensequenz mit einem Symbol der Abfragesequenz vergleichen.

8. Speichersystem nach Anspruch 5, dadurch gekennzeichnet, daß die Endbedingung definitionsgemäß auftritt, wenn die Vergleichseinrichtungen (50) das letzte Symbol der ausgewählten Datensequenz mit dem letzten Symbol der Abfragesequenz vergleichen oder wenn ein Ausgangssignal im Nicht-Übereinstimmungszustand erzeugt wird.

9. Speichersystem nach einem oder mehreren der Ansprüche 5 bis 8, dadurch gekennzeichnet, daß die Begrenzer paarweise auftreten, wobei ein Anfangsbegrenzer zur Kennzeichnung des Anfangs einer Symbolsequenz oder einer Symboluntersequenz, welche in eine Symbolsequenz eingebettet ist, und ein entsprechender Endbegrenzer zur Kennzeichnung des Endes einer Symbolsequenz oder einer Symboluntersequenz benutzt wird,

daß in den Anzeigeweiterschaltungen Einrichtungen (42) zur Bestimmung des zu jedem Anfangsbegrenzer gehörigen Endbegrenzers vorhanden sind,

und daß die nächste Symbol-Datensequenz und die nächste Symbol-Abfragesequenz von den Anzeigeweiterschaltungen (44) jeweils als nächste benachbarte Symbol-Datensequenz und Symbol-Abfragesequenz identifiziert werden, es sei denn, daß der vorausgehende Vergleich zwischen einer Variablen und einem Anfangsbegrenzer stattgefunden hat, in welchem Fall die nächsten Symbole das nächste benachbarte Symbol nach der Variablen und das nächste benachbarte Symbol nach dem Endbegrenzer sind, der zu dem Anfangsbegrenzer gehört.

10. Speichersystem nach Anspruch 9, dadurch gekennzeichnet, daß die Einrichtungen zur Bestimmung des zu einem gegebenen Anfangsbegrenzer gehörigen Endbegrenzers weitere Einrichtungen umfassen, um als Teil eines jeden Anfangsbegrenzers den Ort des zugehörigen Endbegrenzers in der Symbolsequenz zu speichern.

11. Speichersystem nach Anspruch 10, dadurch gekennzeichnet, daß jedes Symbol in einem angrenzenden Block von 1-Bit- Speicherzellen gespeichert wird, wobei dieser Block in eine aus zwei oder mehr Zellen bestehende Identifikation-Zellengruppe und eine Daten-Zellengruppe unterteilt ist und die Identifikation-Zellengruppe die Art der in diesem Block aus 1-Bit-Speicherzellen gespeicherten Datensymbole bezeichnet, wobei die Daten-Zellengruppe die restlichen 1-Bit-Speicherzellen des Blockes umfaßt,

und daß die Einrichtungen zum Speichern des Ortes eines einem gegebenen Anfangsbegrenzer zugeordneten Endbegrenzers Einstellvorrichtungen umfassen, um ein für die Speicherung eines Anfangsbegrenzers benutztes Bit in der Daten-Zellengruppe des Blockes für jedes Symbol, welches übersprungen werden muß, auf "1" zu setzen, um den zum zugehörigen Anfangsbegrenzer korrespondierenden Endbegrenzer in der Symbolsequenz mit dem Anfangsbegrenzer zu erreichen.

12. Speichersystem nach Anspruch 9, dadurch gekennzeichnet, daß die Einrichtungen zur Bestimmung des mit einem gegebenen Anfangsbegrenzer in einer Symbolsequenz korrespondierenden Endbegrenzers in einer Symbol-Datensequenz Einrichtungen (42) umfassen, die operativ mit jeder Verarbeitungseinheit (18) zum Zählen der Begrenzer in der den Anfangsbegrenzer umfassenden Symbol-Datensequenz verbunden sind, wobei die Zähleinrichtungen in einen bestimmten ersten Zustand gesetzt werden, wenn der Anfangsbegrenzer von den Leseeinrichtungen gelesen wird,

und daß die Zähleinrichtungen (42) einerseits bei jedem Auslesen eines Anfangsbegrenzers aus der Symbol-Datensequenz, die den Anfangsbegrenzer umfaßt, weitergeschaltet und andererseits jeweils um einen gleichen Betrag zurückgeschaltet werden, wenn ein Endbegrenzer in der Symbolsequenz festgestellt wird, wobei der korrespondierende Endbegrenzer derjenige ist, der die Zähleinrichtungen (42) veranlaßt, einen zweiten vorgegebenen Zustand anzuzeigen.

13. Speichersystem nach einem oder mehreren der Ansprüche 9 bis 12, dadurch gekennzeichnet, daß die ersten Anzeigeweiterschaltungen (44) Halteeinrichtungen zum Anhalten der Vergleichseinrichtungen (50) umfassen,

daß die Halteeinrichtungen zwei Zustände, nämlich einen Bereitschaftszustand und einen Nichtbereitschaftszustand haben, wobei der Nichtbereitschaftszustand einerseits anzeigt, daß die Symbol-Datensequenz, welche mit der durch die zweiten Anzeigeeinrichtungen spezifizierten Symbol-Abfragesequenz zu vergleichen ist, nicht das am Zugriffspunkt (22) zu lesende nächste Symbol ist, sowie andererseits anzeigt, daß die Funktion der Vergleichseinrichtungen (50) zu unterdrücken ist, und wobei der Bereitschaftszustand anzeigt, daß die mit der durch die zweiten Anzeigeeinrichtungen (94) spezifizierten Symbol-Abfragesequenz zu vergleichende Symbol-Datensequenz die nächste am Zugriffspunkt zu lesende Symbol- Datensequenz ist,

daß die Anzeigeweiterschaltungen (44) den Zustand der Halteeinrichtungen auf den Nichtbereitschaftszustand schalten, wenn ein variables Symbol der Anfragesequenz durch die Vergleichseinrichtungen (50) mit einem Anfangsbegrenzersymbol der Datensequenz verglichen wird,

und daß die Anzeigeweiterschaltungen (44) den Zustand der Halteeinrichtungen auf den Nichtbereitschaftszustand schalten, wenn ein variables Symbol der Abfragesequenz durch die Vergleichseinrichtungen (50) mit einem Anfangsbegrenzersymbol der Datensequenz verglichen wird,

und daß die Anzeigeweiterschaltungen (44) die Halteeinrichtungen in den Bereitschaftszustand zurückschalten, wenn der entsprechende Endbegrenzer am Zugriffspunkt (22) gelesen wird.

14. Speichersystem nach Anspruch 11, dadurch gekennzeichnet, daß die zweiten Anzeigeeinrichtungen einen Zeiger (94) in dem Abfrage-Pufferspeicher (20) umfassen,

daß die Anzeigeweiterschaltungen (44) Einrichtungen zum Inkrementieren des Zeigers enthalten, wobei der Zeiger nach jedem Vergleich einer Symbol-Datensequenz mit einer Symbol- Abfragesequenz, welcher die Erzeugung eines abgeglichenen Ausgangssignals durch Vergleichseinrichtungen (50) zur Folge hat, inkrementiert wird,

und daß der Zeiger (94) für jedes Bit der Datengruppe, welches auf eine "1" in der Datengruppe des Blocks der zur Speicherung des Anfangsbegrenzers verwendeten 1-Bit-Speicherzellen gesetzt ist, inkrementiert wird, wenn ein Begrenzersymbol der Abfragesequenz mit einem variablen Symbol der Datensequenz verglichen wird.

15. Speichersystem nach Anspruch 2 oder einem oder mehreren der Ansprüche 3 bis 14, dadurch gekennzeichnet, daß der empfangene, als Umlaufspeicher konfigurierte serielle Bit-Datenfluß (12) ein Speichersegment mit einem dritten Feld von Speicherzellen (120) und ferner Einrichtungen zum Einsetzen des Speichersegments in den Umlaufspeicher (12) an einem vorbestimmten Austrittspunkt (100) derart umfaßt, daß die Datensymbole den Umlaufspeicher (12) an dem Austrittspunkt (110) verlassen, das Speichersegment durchqueren und dann in den Umlaufspeicher (12) bei der Speicherzelle (104) unmittelbar nach dem Austrittspunkt (100) zurückkehren, welchen die Symbole in dem Umlaufspeicher (12) passiert haben würden, wenn das Speichersegment nicht eingesetzt worden wäre,

und daß die Anzahl der Speicherzellen im Speichersegment durch die Veränderungen des Orts der Speicherzelle in dem Segment (120), an welchem die Daten in das Speichersegment in Abhängigkeit von dem im Segment gespeicherten Symbolen eingefügt werden, variiert werden können, wobei der Eintrittsort geändert wird, wenn immer ein Symbol, das vom Umlaufspeicher (12) zu eliminieren ist, in das Speichersegment an einem Punkt vor diesem Symbol eingefügt wird.

16. Speichersystem nach Anspruch 15, dadurch gekennzeichnet, daß Einrichtungen zum Einfügen des Speichersegments in den Umlaufspeicher vorhanden sind, wenn eine vorgegebene Sequenz von Datensymbolen den Austrittspunkt passiert hat.

17. Speichersystem nach Anspruch 15 oder 16, dadurch gekennzeichnet, daß Einrichtungen das Einfügen einer Sequenz von Symbolen in das Speichersegment in Abhängigkeit von einem Signal bewirken, das dem Speichersystem zugeführt wird.

18. Speichersystem nach einem der Ansprüche 15 bis 17, dadurch gekennzeichnet, daß das erste und das dritte Speicherfeld 1-Bit-breite Schieberegister umfassen.