DE1945215C3 - Assoziativer Speicher - Google Patents

Description

Die Erfindung bezieht sich auf einen assoziativen Speicher mit Speicherzellen für jeweils eine Binärziffer, die in Zeilen und Spalten zu einer Matrix verdrahtet sind, wobei jede Zeile wenigstens einen Speicherplatz mit mehreren Binärzifferstellen umfaßt und die einander entsprechenden Ziffernsteilen zugeordneten Speicherzellen der Speicherplätze in den gleichen Spalten der Matrix liegen, und wobei jede Speicherzelle ein bistabiles Speicherelement, eine Vergleichsschaltung, eine Schreibtorschaltung und eine Lesetorschaltung enthält, mit einem Informationswortregister, an dessen Stufenausgänge Informationsleitungen angeschlossen sind, die jeweils mit den Vergleichsschaltungen aller in einer Spalte liegenden Speicherzellen derart verbunden sind, daß jede Vergleichsschaltung ein die Übereinstimmung bzw. Nichtübereinstimmung zwischen dem Inhalt des zugehörigen Speicherelements und der über die Informationsleitung übertragenen Binärziffer anzeigendes Signal abgibt, mit einem Adressierregister, an dessen Slufenausgänge Adressierleitungen angeschlossen sind, die jeweils mit den Steuereingängen der Vergleichsschaltungen aller in einer Spalte liegenden Speicherzellen verbunden sind, mit Zeüenleitungen, die jeweils an die Ausgänge der Vergleichsschaltungen der zu einem Speicherplatz gehörenden Speicherzellen derart angeschlossen sind, daß sie dann und nur dann einen die Übereinstimmung anzeigenden Spannungswert führen, wenn in allen dem Vergleich unterworfenen Spalten eine Übereinstimmung besieht, mit Leselcitungen, die jeweils mit den Ausgängen der Lesctorschaltungen aller in der gleichen Spalte liegenden Speicherzellen verbunden sind, und mit Schreibsteuerleitungen, von denen jede mit den Steuereingängen der Schreiblorschaltungen bestimmter Speicherzellen verbunden ist.

Ein assoziativer Speicher ist bekanntlich ein digitaler Informationsspeicher, bei dem der Zugriff zu den Speicherplätzen nicht auf Grund der Angabe über die örtliche Lage der einzelnen Speicherplätze (»Adresse«) erfolgt, sondern auf Grund des Inhalts der Speicherzellen; solche Speicher werden deshalb auch als «inhaltsadressierte Speicher« bezeichnet. Das Auffinden einer bestimmten gespeicherten Information erfolgt dadurch, daß die Inhalte oder ein bestimmter Teil der Inhalte sämtlicher Speicherplätze mit einem vorgegebenen Vergleichskriterium verglichen wird; für diejenigen Speicherplätze, für die eine vollständige Übereinstimmung festgestellt wird, wird ein Signal abgegeben, das den betreffenden Speicherplatz kennzeichnet und das Auslesen des Inhalts dieses Speicherplatzes oder das Einschreiben einer neuen Information in diesen Speicherplatz ermöglicht.

Die bekannten assoziativen Speicher haben im

Prinzip alle den eingangs angegebenen Aufbau. Ein besonders anschauliches Beispiel für diesen Stand der Technik ist in der Zeitschrift »Frequenz« 1966, S. 69 bis 82, beschrieben und insbesondere in Bild 7 auf S. 75 dargestellt. Bei diesen bekannten assoziativen Speichern enthält das eingangs erwähnte Informationsregister das Vergleichskriterium, das über die Informationsleitungen den Vergleichsschaltungen der einzelnen Speicherzellen zugeführt wird. Das Adressier register ist ein Masken register, das den Vergleich nur in bestimmten Spalten der Speichermatrix zuläßt, während es die übrigen Spalten »maskiert«. An die Zeilenleitungen sind Detektoren angeschlossen, die das Signal feststellen und speichern, das die vollständige Übereinstimmung zwischen dem Vergleichskriterium und dem Inhalt der dem Vergleich unterworfenen Speicherzellen eines Speicherplatzes anzeigt. Durch diese Teile des Speichers werden die durch das Vergleichskritenum »adressierten« Speicherplätze aufgefunden.

Das anschließende 1 esen des Inhalts des gefundenen Speicherplatzes oder das Einschreiben einer neuen Information in diesen Speicherplatz erfolgt dann bei dem zuvor erwähnten bekannten assoziativen Speicher dadurch, daß auf Grund des im Detektor stehenden Vergleichsergebnisses durch einen Verschlüßler eine interne Adresse für den gefundenen Speicherplatz gebildet und mit Hilfe dieser internen Adresse über einen Entschlüßler ein Wort-Treiber angesteuert wird. In diesem Fall sind also die Suchvorgänge von den Lese- und Schreibvorgängen zeillich und organisatorisch getrennt.

Aus der DT-AS 12 69182 ist ein assoziativer Speicher bekannt, der ohne Bildung einer inneren Adresse mit direktem Zugriff zu der Zeile arbeitet, für die eine Übereinstimmung festgestellt wurde. Zu diesem Zweck ist für jede Zeile ein Zeilenzugriffschalter vorgesehen, der in Abhängigkeit vom Suchergebnis eingestellt wird und den Zugriff für die beabsichtigten Lese- oder Schreiboperationen freigibt. Auch in diesem Fall erfolgt das Lesen oder Schreiben in zwei Phasen: In der ersten Phase wird der richtige Speicherplatz durch den Assoziativsuchvorgang aufgesucht und mit Hilfe eines Speicherelementes markiert, und in der zweiten Phase erfolgt das Auslesen oder Einschreiben des Inhalts des markierten Speicherplatzes.

In der zuerst erwähnten Literalurstelle »Frequenz« ist auch die Möglichkeit des direkten Zugriffs zum Datenteil eines assoziativen Speichers erwähnt, die aber die festgelegte Unterteilung des Speichers in einen assoziativen Teil und einen Dater.leil voraussetzt.

Aufgabe der Erfindung ist die Schaffung eines assoziativen Speichers der eingangs angegebenen Art, der bei verringertem Schaltungsaufwand eine wesentliche Verkürzung des Speicherzyklus ergibt und bei dem alle Speicherzellen unterschiedslos als Datenspcicherzellen oder als assoziative Speicherzellen verwendbar sind.

Nach der Erfindung wird diese Aufgabe dadurch gelöst, daß die Signaleingänge der Schrcibtorschaltungen aller in einer Spalte liegenden Speicherzellen an die dieser Spalte zugeordnete Informationsleitung angeschlossen sind, daß jede Schreibstcuerleitung mit den Steuereingängen der Schreibtorschallungen aller in einer Spalte liegenden Speicherzellen verbunden ist, 6j, daß ein weiterer Steuereingang jeder Schreibtorschaltung mit der zugehörigen Zeilenleitung verbunden ist, daß der Steuereingang jeder Lesetorschaltung mit der zugehörigen Zeilenleitung \erbunden ist, und daß der die Übereinstimmung anzeigende Spannungswert auf der Zeilenleitung als Entsperrungssignal für die angeschlossenen Lesetorschaltungen und Schreibtorsch.iltungen wirkt.

Die erfindungsgemäße Ausbildung ergibt die Wirkung, daß das Auslösen des sich an einen Suchvorgang anschließenden Schreib- bzw. Lesevorgangs sofort möglich ist, ohne daß erst ein speicherndes Detektorelemcnt abgefragt oder ein Zugriffschalter eingestellt werden muß, und ohne daß eine äußere Adressierung notwendig ist. In dem Augenblick, in welchem für einen Speicherplatz die Übereinstimmung mit dem Vergleichskriterium festgestellt worden ist, steht somit unmittelbar der Inhalt des gesamten Speicherplatzes auf den Leseleitungen zur Verfügung: wenn außerdem bestimmte Schreibsteuerleitungen erregt sind, wird in die an diese Schreibsteuerleitungen angeschlossenen Speicherzellen des betreffenden Speicherplatzes das von der jeweils zugeordneten fnfonii:iiionsleiiung übertragene Bit im gleichen Zuge eingeschrieben. Somit entfällt nicht nur der zusätzliche Zeitaufwand für die Ansteuerung des betreffenden Speicherplatzes und die Auslösung des Lese- oder Schreibvorgings mit Hilfe einer internen Adresse oder \on Speicherelementen oder Zugriffsschaltern, sondern vor allem auch der gesamte hierfür erforderliche Schallungsaufwand.

Bei dem assoziativen Speicher nach der Erfindung wird die Tatsache ausgenutzt, daß in der Regel bei assoziativen Speichern der inhalt der dem Verg'cich unterworfenen Speicherzellen bei einem Schreibvorgang nicht geändert werden soli, da dieser Inhalt ja die assoziative Adresse darstellt. Diese Speicherzellen werden daher vom Schreibvorgang grundsätzlich ausgenommen, was durch die entsprechende selektive Erregung der Schreibslcurleilungcn möglich ist. Der Schreibvorgang kann daher durchgeführt werden, während die Vergleichshits noch anliegen. Diese Organisation ergibt weitere Vorteile: die einzuschreibende Information kann in dem gleichen Informationswortregister gespeichert sein wie das Vergleichskriterium, so daß ein besonderes Eingabercgister entfällt, und es wird pro Spalte der Speichermatrix nur eine einzige Informationsleitung benötigt, die wahlweise entweder die Vergleichsbits oder die einzuschreibenden Informationsbits führt. Praktisch erfolgt durch die selektive Erregung der Schreibsteuerleitungen und der Adressierleitungen eine Unterteilung der Speicherplätze in einen assoziativen Teil und einen Datenteil, wie dies bei assoziativen Speichern üblich ist, wobei aber diese Aufteilung nach Belieben jederzeit geändert werden kann.

Wie bei den bekannten assoziativen Speichern ist es auch beim erfindungsgemäßen Speicher möglich, eine Prioritätslogikschal'.ung vorzusehen, die eine Prioritätssteuerung bewirkt, wenn mehrere Speicherplätze das gleiche Vergleichskriterium erfüllen. Dies kann gemäß einer vorteilhaften Ausgestaltung des IZrfindungsgegenstandes dadurch geschehen, daß die Prioritätslogikschaltung eine Kaskade von Vcrriegclungsschallungcn enthält, die in einer Folge der Reihe nach durch das Programmsignal freigegeben werden und bei jedem Schritt der Folge jeweils eine Zeilenlcilung zur Annahme des die Übereinstimmung anzeigenden Spannungswertes freigeben und alle übrigen Zeilenleitungen auf einem der scheinbaren Nichtübereinstimmung entsprechenden Spannungswert halten.

Ein Ausführungsbeispiel der Erfindung ist in der Zeichnung dargestellt. Darin zeigt

F i g. 1 ein teilweise als Blockschaltbild ausgeführtes Schaltbild eines Spcichcrmoduls des assoziativen Speichers nach der Erfindung und

F i g. 2 ein Blockschaltbild eines assoziativen Speichers nach der Erfindung, welcher aus den in F i g. 1 dargestellten Speichermodulen aufgebaut ist.

Der in F i g. 2 dargestellte assoziative Speicher besteht aus einer Anzahl von Speichcrmodulcn 5, die in Hi horizontalen Reihen und η vertikalen Reihen angeordnet sind und dementsprechend mit 5,„ 5₂, ... 51„, ... 5,„, 5₂„ ... 5m« bezeichnet sind. Jeder Speichermodul 5 hat den in F i g. 1 gezeigten Aufbau; er enthält mehrere Speicherzellen 10, die zu bestimmten Zeilen und Spalten des Speichers gehören; dem Bezugszeichen 10 sind deshalb in F i g. I zwei Indizes hinzugefügt, welche die Spalte und die Zeile kennzeichnen, in denen die bclrffende Speicherzelle 10 liegt. Der Speichermodul 5 von F i g. 1 enthält acht Speicherzellen 10. die in zwei Spalten /, / -|- 1 und in vier Zeilen k, k I- 1, k ~|· 2, A- + 3 liegen. Die am Kreuzungspunkl der Spalte / und der Zeile k liegende Speicherzelle 1Oi, ι-,., ist in F i g. 1 genauer dargestellt, während die übrigen sieben Speicherzellen ΙΟ,·.*,,; 10i.fr ,„; 10_Μ·;₃: 10^,.»·: 10,·,*- + ,; 10_f._A ,.,; ΙΟ,-./,·!;, nur angedeutet sind.

Die acht Speicherzellen 10 des Speichcrmoduls 5 können auch als LJntermairix bezeichnet werden, aus denen größere Speichermatrizen zusammengesetzt sind. Der kleinste Speicher, welcher mit solchen Spcichermodulen gebaut werden kann, besteht nur aus einem einzigen Speichermodul. Ein aus Speichermodulen dieser Art aufgebauter Speicher ist weiter so organisiert, daß alle in einer Zeile k liegenden Speicherzellen einen einzigen Speicherplatz bilden. Der Index / definiert eine Bitslelle innerhalb dieses Speicherplatzes, und alle der gleichen Bitstclle in den verschiedenen Speicherplätzen zugeordneten Speicherzellen liegen in der gleichen Spalte /.

Die Speichermatrix im allgemeinen und der dargestellte Speichermodul insbesondere hat drei Eingangsleilungen II', /, L und eine Ausgangsleitung D für jede Spalte, wie die Eingansleitungen Wi, /?, £-? und die Ausgangsleitung D,- für die Spalte ;. Die Leitung Wi ist die Schrcibsteuerleitung, welche bei Erregung die Aufzeichnung eines Bits in mindestens eine Speicherzelle 10 der Spalte / bewirkt. Die Leitung /,· ist die Adressierleitung, welche bei Erregung anzeigt, daß für den laufenden assoziativen Suchvorgang angenommen wird, daß die Bitstelle / der Speicherplätze ein Adressenbit enthält. Die Leitung Lt ist die Informationsleitung, die das entsprechende Informationsbit führt. Wenn die Schreibsteuerleitung W₁ gleichzeitig mit der Leitung Z,< erregt ist, ist das auf die Informationsleitung Li gegebene Bit ein aufzuzeichnendes Datenbit. Wenn die Adressierleitung /j gleichzeitig erregt wird, definiert das Bit auf der Informationsleitung Li ein assoziatives Suchbit und es wird eine Speicherzelle in der Spalte / gesucht, welche ein Bit enthält, das gleich dem von der Informationsleitung U gelieferten Bit ist. Die Ausgangsleitung Di ist die Leseleitung, welche die Entnahme eines Bits einer adressierten Bitstelle in der Spalte ; ermöglicht. Jede Zeile hat eine einzige Zeilenleitung K, wie die Leitung Y_k für die Zeile A. welche sowohl als Eingangs- wie auch als Ausgangsleitung für alle Speicherzellen in dieser Zeile dient. Daher wird jeder Matrixpunkt von fünf Leitungen bedient, wie weiter unten näher erläutert wird Infolge der Signalverarbeitung innerhalb des Speichermoduls und außerhalb der Speicherzellen, wie sie weiter unten erläutert wird, sind zwei zusätzliche Anschlußleitungen für jede Speicherzelle erforderlich, so daß jede Speicherzelle mit sieben Anschlüssen verschen ist.

Es soll nun der Aufbau einer einzelnen Speicherzelle 10 innerhalb eines Speichermoduls 5 an Hand der

ίο Speicherzelle 10i.fr von Fig.! beschrieben werden. Es sind fünf Eingangsanschlüsse 11, 12, 13. 14 und 15 sowie zwei Ausgangsanschlüsse 16 und 17 für die betreffende Speicherzelle 10,· t vorgesehen. Die Eingangsanschlüsse U, 13 und 14 sind mit den Eingmgsleitungen /f, Wf, bzw. /_,· der Spalte/ verbunden. Der Anschluß 12 ist, gemeinsam mit den entsprechenden An-' Schlüssen der übrigen Speicherzellen der gleichen Spalte, mit einer Leitung verbunden, die ihrerseits mit der Informationsleitung L₁ über ein Nicht-Glied 18 verbunden ist und daher als »komplementäre Informationsleitung t7« bezeichnet werden kann. Der Anschluß 15 ist mit der Zeilenleitung K* der Zeile A' über einen Verstärker 32 verbunden. Der Ausgangsanschluß 17 ist mit der Zeilenleitung Yt über ein Nicht-Glied 31 verbunden, und der Ausgangsanschluß 16 ist, gemeinsam mit den entsprechenden Anschlüssen der übrigen Speicherzellen dergleichen Spalte, mit einer Leitung verbunden, die mit der Leseleitung D, der Spalte / über ein Nicht-Glied 35 verbunden ist, und dementsprechend als »komplementäre Leseleitung 75~« bezeichnet werden kann.

Das zentrale Element jeder Speicherzelle ist ein bistabiles Glied 20, das ein einfaches bistabiles Flipflop sein kann. Das Flipflop 20 befindet sich natürlich stets entweder im gesetzten oder im zurückgesetzten Zustand und es wird angenommen, daß diese Zustände dem Binärwert 1 bzw. dem Binärwert 0 entsprechen. Die Ausgänge des Flipflops 20 sind mit einer aus zwei Und-Gliedcrn 21. 22 bestehenden Vergleichsschaltung und mit einer Lesetorschaltung 23 verbunden, während seine Eingänge mit einer aus zwei NAND-Gliedern 24 und 25 bestehenden Schreibtorschaltung verbunden sind. Folgende Schaltverbindungen sind hergestellt:

Ein Eingang des Und-Gliedes 21 ist an den direkten Ausgang des Flipflops 20 angeschlossen. Zwei weitere Eingänge des Und-Gliedes 21 sind mit den Eingangsanschlüssen 11 bzw. 12 verbunden. Ein Eingang des Und-Gliedes 22 und ein Eingang der Lesetorschaltung 23 sind an den komplementären Ausgang des Füpfiops 20 angeschlossen. Zwei weitere Eingänge des Und-Gliedes 22 sind mit den Eingangsanschlüssenil und 14 verbunden, und ein weiterer Eingang des Und-Gliedes 23 mit dem Eingangsanschluß 15 verbunden. Die Ausgänge der Und-Glieder 21 und 22 sind zur Bildung einer Antivalenzschaltung in einer Oder-Verknüpfung miteinander verbunden; der Ausgang der dadurch gebildeten Vergleichsschaltung ist mit dem Ausgangsanschluß 17 verbunden. Die Vergleichsschaltung 21, 22 wird während eines assoziativen Such-Vorgangs in Bereitschaft gesetzt und vergleicht das über die Informationsleitung Lt auf die Spalte i gegebene Bit mit dem Zustand des Flipflops 20. Der Ausgang der Lesetorschaltung 23 ist mit dem Ausgangsanschluß 16 verbunden. Daher liefert die Lesetor- schaltung 23 ein zu dem Zustand des Flipflops 20 komplementäres Signal zum Anschluß 16, wenn die betreffende Speicherzelle über den mit der Zeilenleitung }'»- verbundenen Anschluß 15 angesteuert wird.

p Die Asso Und-Glieder 21, 22 der Vergleichsschaltung ein Ausgangssignal »1« ab, so daß zum Ausgangsanschluß 17 ein Signal »0« übertragen wird.

Das gleiche Signal »0« gelangt zum Ausgangsanschluß 17, wenn die betreffende Speicherzelle 10«, * nicht an dem Assoziativsuchvorgang teilnimmt, weil dann die Und-Glieder 21, 22 der Vergleichsschaltung durch das Signal »0« auf der Adressierleitung /< gesperrt sind.

Wenn dagegen der Inhalt des Flipflops 20 nicht mit dem Suchbit auf der Informationsleitung Lt übereinstimmt, gibt infolge der Antivalenzverknüpfung entweder das Und-Glied 21 oder das Und-Glied 22 das Ausgangssignal »1« ab, das zum Ausgangsanschluß 17 übertragen wird, vorausgesetzt, daß gleichzeitig das Aktivierungssignal auf der Adressierleitung /( anliegt. Es ist zu erkennen, daß die Und-Glieder 21 und 22 niemals gleichzeitig ein Ausgangssignal »1« abgeben können, da nicht beide Ausgänge des Flipflops 20 gleichzeitig das Signal »1« führen können; die dargestellte Vergleichsschaltung 21, 22 entspricht also tatsächlich einer Antivalenzschaltung.

Der Ausgangsanschluß 17 ist über ein Nicht-Glied 31 mit der Zeilenleitung Yk verbunden. Diese Zeilenleitung Vj- ist sämtlichen Speicherzellen 10 der Zeile k zugeordnet, die zusammen einen Speicherplatz bilden. Wie aus F i g. 1 zu erkennen ist, ist auch der entsprechende Ausgangsanschluß 17 der zweiten, zur gleichen Zeile k gehörenden Speicherzelle 1Of h.a- des dargestellten Speichermoduls 5 mit dem Eingang des gleichen Nicht-Gliedes 31 verbunden. Der Ausgang des Nicht-Gliedes 31 gibt somit nur dann ein Ausgangssignal »1« ab, wenn die Ausgangsanschlüsse 17 der beiden Speicherzellen 10,, a- und 1O_{1 + 1},*- gleichzeitig ial »0« führen während in allen anderen Fällen cht-Glied 31 die Zeiienleitung Yk- auf dem Signalwert »0« hält.

Die Ausgangsanschlüsse 17 aller in der Zeile A liegenden Speicherzellen 10 sind in gleicher Weise

der Weise ab" Das den Assoziativsuchvorgang an- 40 über entsprechende Nicht-Glieder mit der Zeilenzeigende Signal auf der Adressierleitung h wird auf leitung Y_k gekoppelt. Die Vergleichsschaltung 21. 22 den Eingangsanschluß 11 gegeben und dadurch den einer an dem Assoziativsuchvorgang nicht beteiligten beiden Und-Gliedern 21 22 der Vergleichsschaltung Speicherzelle 10 ist außer Bereitschaft, wenn die bezugeführt Nach einer kurzer. Verzögerung, die ins- treffende Adressierleitung/ nicht erregt ist, und sie besondere gewährleisten soll, daß diese Signale in den 45 gibt dementsprechend ein Signal »0« ab. Es ist^ von Und-Gliedern 21, 22 endgültig eingestellt sind, wird
ein den Binärwer» des Suchbits angegebenes Signal auf
die Informationsleitung U gegeben, an welche der
Eingangsanschluß 14 der Speicherzelle angeschlossen
ist. Das Nicht-Glied 18, das zu den Schaltungen ge- 5°
hört, die eine Signalverarbeitung innerhalb des Speimoduls S, aber außerhalb der Speicherzellen 10 durchführen, erzeugt auf der Kompkmentär-Informationsleitung 17 ein Signal, das zu dem Signal auf der Informationsleitung Li komplementär ist; dieses komple- 55

mentäre Signal wird dem Eingangsanschluß 12 der .

^ — Die Zeiienleitung Yk nimmt dann und nur dann den

Signalwert »1« an, wenn sämtliche Ausgangsanschlüsse 17 der zugeordneten Speicherzellen 10 das Signal »0« 60 führen; dies ist nur dann der Fall, wenn alle dem Assoziativsuchvorgang unterworfenen Speicherzellen dieser Zeile hinsichtlich ihres Inhalts mit dem über die entsprechende Informationsleitung L übertragenen

mentärT Ausg^ngssTgnal des Flipflops20 und aas Suchbit übereinstimmen Wenn auch nur bei einer direkt Informationssienal der Informationsleitung U «5 dieser Speicherzellen keine Ubera.nstimmung be-ΪΤ Lu-S*J7mtanddes Flipflopl 20 steht, gibt die Vergleichsschaltung 21, 22 dieser S^K^^sSÄnieMÄ^ Speicherzelle 10 ein Signal .1, ab das dem Nichtleitung L₁ übSnstimmt, gibt keines der beiden Glied 31 zugeführt wird, so daß das Ausgangss.gnal

609635/119

Infolge des Nicht-Gliedes 35 erscheint dann auf der Leseleitung £> < ein den Zustand des Flipflops 20 wiedergegebenes Signal.

Das NAND-Glied 25 der Schreibtotschaltung steuert den Setz-Eingang des Flipflops 20 an. Die drei Eingänge dieses NAND-Gliedes sind mit den Eingangsanschlüssen 12, 13 bzw. 15 verbunden. Das NAND-Glied 24 steuert den Rücksetzeingang des Flipflops 20 an; seine drei Eingänge sind mit den Eingangsanschlüssen 13, 14 bzw. 15 verbunden. Die Schreibsteuerschaltung 24, 25 bewirkt daher ein Setzen oder Zurücksetzen des Flipflops 20, wenn die Schreibsteuerleitung Wi erregt ist und wenn der Speicherplatz A- (d. h. alle mit der Zeilenleitung Y_k verbundenen Speicherzellen 10) angesteuert wird.

Bei dem beschriebenen assoziativen Speicher kann jede Speicherzelle 10 eine doppelte Rolle spielen: Das darin gespeicherte Bit kann entweder ein Suchbit für den assoziativen Suchvorgang oder ein Datenbit sein; die jeweilige Bedeutung ist nicht durch die betreffende Speicherzelle festgelegt, sondern hängt von der Steuerung mittels der Adressierleitung / ab. Die Erregung der Adressierleitung /< zeigt an, daß die Spalte / an dem Assoziativsuchvorgang teilnimmt. ^nip ' ziativsuche besteht darin, daß fesi ' "' Speicherzellen in den am Assozi; nehmenden Spalten Bits speichern, die .... zeitig über die Informationsleitung L der Spalte zugeführten Bits ü' -----'—*^:——~ ergebnis ist für diejenigen _
positiv, in denen den Inhalt sämtlicher Vorgang teilnehmenden Speicherzellen mit den über die zugeordneten Informationsleitungen L übertragenen Suchbits übereinstimmt. Wenn auch nur bei einer der am Suchvorgang teilnehmenden Speicher- 35 das zellen diese Übereinstimmung nicht besteht, ist das das Suchergebnis für die betreffende Zeile negativ.

Unter diesen -Voraussetzungen läuft der Asso-Bedeutung, daß die Vergleichsschaltungen 21. 22 der Speicherzellen 10 jeweils die gleichen Ausgangssignale (nämlich das Ausgangssignal »0«) abgeben, wenn sie

— entweder überhaupt nicht an dem Assoztativsuchvorgang teilnehmen (wobei das Ausgangssignal der Vergleichsschaltung dann unabhängig vom Inhalt der Speicherzelle ist);

— oder an dem Assoziativsuchvorgang teilnehmen und ihr Inhalt mit dem über die Informationsleitung L übertragenen Suchbit übereinstimmt.

SSiSA!; Und-GLd 21 auß;r dem über die Adressierleitung U kommenden A^^WJJs das direkte Ausgangssignal des ^{F 1}P¹¹⁰P^" ""_ions.

komplementäre Informationssigna ^d" ^lnl°X* dem leitung Lt, während das Und-Glied 22 auuer

Aktivierungssignal der Adressierleitung «£as ™mp mentäre Ausgangssignal des _t ^F1'P^floP_t ^s.*" "™ ,

des betreffenden Nicht-Glieds 31 den Signalwert »0« Übertragung les Inhalts ihres Flipflops auf die Lesehat, wodurch die Zeilenleilung Yt auf dem Signalwert leitung A + i geöffnet wird. Allgemeiner ausgedrückt: »0« gehalten wird, und zwar unabhängig davon, ob Die Lesetorschaltung jeder Speicherzelle 10 überdie übrigen Vcrgleichsschaltungen der in der gleichen trägt den Inhalt der betreffenden Speicherzelle zu der Zeile liegenden Speicherzellen 10 Signale »1« oder 5 Leseleitung D, sobald die zugeordnete Zeilenleitung Y Signale »0« abgeben. Dabei nimmt das Ausgangs- den Signalwert »1« annimmt, also dann, wenn das signal des Nicht-Glieds 31 den Signalwert »0« an, so- Suchergebnis für den betreffenden Speicherplatz bald wenigstens einer der beiden mit ihrem Eingang positiv war, und zwar unabhängig davon, ob die beverbundenen Anschlüsse 17 den Signalwcrt »1« führt, treffende Speicherzelle 10 an dem Assoziativsuchunabhängig von dem Signalwert auf dem anderen 10 Vorgang teilnahm oder nicht.
Anschluß 17. Unabhängig von der Durchführung eines Asso-

Mit anderen Worten: Durch die Erregung der ziativsuchvorgangs besteht auch die Möglichkeit, eine Adressierleitungen / wird festgelegt, welche Speicher- Zeilenleitung Y durch äußere Einwirkung auf den zellen 10 einer Zeile an dem Assozialivsuchvorgang Signalwert »1« zu bringen. Dies ermöglicht ein Lesen teilnehmen. Wenn die Inhalte dieser Speicherzellen 15 sämtlicher Speicherzellen, die der betreffenden Zeilenmit den über die zugeordneten InformationsleitungenL leitung Y zugeordnet sind, natürlich vorausgesetzt, übertragenen Suchbits übereinstimmen, nimmt die daß gleichzeitig die übrigen Zeilenleitungen Y der entsprechende Zcilenleitung Y den Signalwert »1« an, Speichermatrix durch äußere Einwirkung auf dem unabhängig von den Inhalten der nicht an dem Signalwert »0« gehalten werden. Dieser Fall wird Assoziativsuchvorgang beteiligten Speicherzellen der 20 weiter unten ausführlicher erläutert,
betreffenden Zeile. Wenn dagegen bei wenigstens einer Es soll nun beschrieben werden, wie ein Inforder am Assoziativsuchvorgang beteiligten Speicher- mationsbit in die Speicherzelle 1Oi₁A.- eingeschrieben zellen keine Übereinstimmung des Inhalts mit dem werden kann. Für die Durchführung eines Schreibüber die entsprechende Informationsleitung/, über- Vorgangs ist es notwendig, daß die Schreibsteuertragenen Suchbit besteht, nimmt die Zcilenleitung )' 25 leitung W_t der entsprechenden Spalte / erregt ist, also den Signalwert »0« an, wiederum unabhängig von den . ein Signal »1« führt. Dieses Signal wird über den An-Inhalten der nicht am Assoziativsuchvorgang be- Schluß 13 den beiden NAND-Gattern 24 und 25 der teiligten Speicherzellen. Schreibtorschaltung zugeführt. Der Schreibvorgang

Wenn die Zeilenleitung >'*■ den Signalwert »1« setzt ferner voraus, daß die zugeordnete Zeilen-

führt (positives Suchergebnis), wird dieses Signal in 30 leitung Y_k den Signalwert »1« führt. Dieser Signalwert

einem Verstärker 32 verstärkt, der ebenfalls zu den kann in einer der beiden zuvor angegebenen Weisen

außerhalb der Speicherzellen liegenden Bauelementen erhalten werden, nämlich entweder infolge eines posi-

des Speichcrmoduls 5 gehört. Die Eingangsanschlüsse tiven Suchergebnisses oder durch eine äußere Ein-

15 der beiden in der betreffenden Zeile liegenden wirkung. In beiden Fällen liefert der Verstärker 32

Speicherzellen 10_t,_A und 10,-.*., sind an den Ausgang ₃₅ ein Signal »1« zu einem Eingang jedes der beiden

dieses Verstärkers 32 angeschlossen. Das Ausgangs- NAND-Glieder 24, 25 der Schreibtorschaüung, wo-

signal des Veratärkcrs 32 wird somit jeweils zu einem durch die Schreibtorschaltung für einen Schreib-

Eingang der Lesetorschaltung 23 und der beiden Vorgang vorbereitet wird.

NAND-Glieder 24, 25 der Schreibtorschaltung jeder Das in die Speicherzelle einzuschreibende Bit wird

der beiden Speicherzellen 10 übertragen. Wie be- 40 anschließend wieder auf die Informationslcitung U

reits erwähnt wurde, empfängt die Lesetorschai- der Spalte ; gegeben. Es liegt also an allen Spcicher-

tung23 außerdem das Ausgangsignal vom korn- zellen dieser Spalte an, wird aber nur in die Speicher-

plementären Ausgang des Flipflops 20. Wenn somit zelle der Zeile eingeschrieben deren Zeilenleitung Y

das Flipflop 20 im Ruhezustand steht, liefert die Lese- erregt ist. Je nach dem Binärwert des über die Infor-

torschaitung 23 ein Signal »1« zum Ausgangsanschluß ₄₅ mationsleitung L, übertragenen Informationsbits führt

16; wenn dagegen das Flipflop 20 im gesetzten Zu- entweder der Anschluß 12 oder der Anschluß 14 das

stand stc'H, liefert die Lesetorschaltung 23 ein Signal Signal »1«, so daß das betreffende NAND-Glied 25

»0« zum Ausgangsanschluß 16. Das Ausgangssignal bzw. 24 ein Ausgangssignal »0« abgibt Das Flipflop 20

der Lesetorschaltung 23 gelangt somit auf die komple- wird dementsprechend gesetzt oder zurückgesetzt,

mentäre Leseleitung D₁, die über das Nicht-Glied 35 50 wodurch das über die Informationsleitung U zu-

mit der Leseleitung A verbunden ist. Somit führt die geführte Informationsbit gespeichert wird

Leseleitung A ein Signal, das dem Zustand des I_n der vorstehenden Beschreibung der Speicherzelle

Flipflops 20 entspricht, sobald der betreffenden Spei- ΙΟ,.* und ihrer Funktionsweise sind bereits verschie-

cherzellelO ein Ausgangssignal vom Verstärker 32 dene Bestandteile des Speichermoduls 5 erwähnt

zugeführt wird. ........ „ · . 55 worden, die mehreren Speicherzellen gemeinsam sind.

Dieser Vorgang erfolgt naturlich fur alle mit der Hierzu gehören das Nicht-Glied 31 und der Vergleichen Zeilenleitung Y verbundenen Speicherzellen stärker 32, die den mit der Zeilenleitung Yt verbungleichzeitig, da sämtliche Verstärker 32 dieser Zeile denen Speicherzellen dieses Speichermoduls gemeingleichzeit.g ein Ausgangssignal abgeben, sobald die sam sind. Entsprechende Nicht-Glieder 311 312,313 Zeilenleitung Y den Signalwert »1« annimmt. Somit 60 und Verstärker 321 322 323 sind für die Zeilenwerden die in den betreffenden Speicherzellen 10 ge- leitungen Y_k+U Y_k+, γ' vorgesehen Das Nichtspe.cherten Bits gleichzeitig parallel an den Lese- Glied 18 ist allen in der Spalte /liegenden Speicherle.tungen A, A ₊ , .. .abgeben Wenn man beispiels- zellen dieses Speichermoduls gemeinsam; dieses Nichtweise annimir.t, daß die Zelle 10, _Mil nicht an dem Glied hat insbesondere den Zweck eine besondere Assoziativsuchvorgang teilnahm, weil die entsprechen- 65 Spaltenleitung einzusparen deren Signal stets zu dem de Adressierleitung /, ₄, nicht erregt war, so empfängt Signal auf der Informationsleitung U komplementär diese Speicherzelle dennoch das Ausgangssignal des ist. Ein entsprechendes Nicht-Glied 19 ist für die Verstärkers 32, so daß ihre Lesctorschaltung zur Speicherzellen in der Spalte i + 1 vorgesehen. Das

Nicht-Glied 35 ist ebenfalls allen in der Spalte / liegenden Speicherzellen des Speichermoduls gemeinsam, und ein entsprechendes Nicht-Glied 36 ist für die in der Spalte; + 1 liegenden Speicherzellen vorgesehen.

Schließlich ist für die Spalte/ ein Nicht-Glied 33 vorgesehen, das die Informationsleitung h mit der Schreibsteuerleitung W_{ dieser Spalte verbindet; ein entsprechendes Nicht-Glied 34 verbindet in der Spalte f" + 1 die Informationsleitung Zi _{+ 1} mit der Schreibsteuerleitung Wi ι,. Das Nicht-Glied 33 häit diese Schreibsteuerleitung Wt auf dem Signalwert »0«. wenn die Adressierleitung Λ den Signalwert»!« führt. Dadurch wird verhindert, daß eine Spalte, die durch Erregung der Adressierleitung / für einen Assoziativversuchvorgang ausgewählt ist, an einem Schreibvorgang teilnimmt, durch den die in dieser Spalte stehenden Bits (die ja gewissermaßen die »Adressenbits« des Assoziativsuchvorgangs bilden) geändert werden könnten. Die automatische Sperrung des Schreibvorgangs für alle am Assoziativsuchvorgang beteiligten Spalten ermöglicht wiederum eine Vereinfachung des Schaltungsaufbaus, denn es ist dann beispielsweise möglich, alle Schreibsteuerleitungen W an eine gemeinsame Steuerquelle (beispielsweise ein einziges Schreibsteuer-Flipflop) anzuschließen, das alle Schreibsteuerleitungen W erregt, soweit diese nicht durch Erregung der entsprechenden Adressierleitung / blockiert sind. Auch ist es dadurch möglich, einen Schreibvorgang durch äußere Erregung aller Schreibsteuerleitungen ohne Durchführung eines Assoziativsuchvorgangs vorzunehmen, dabei aber bestimmte Speicherzellen durch Erregung der betreffenden Adressierleitungen / vom Schreibvorgang auszunehmen.

Schließlich können umgekehrt die in bestimmten Speicherzellen stehenden Datenbits vor einem Schreibvorgang geschützt werden, wenn in andere Speicherzellen die Adressenbits für eine neue assoziative Adresse eingeschrieben werden sollen.

Folgende besondere Situationen sind noch von Interesse: Wenn alle Adressierleitungen/ einer Speichermatrix gleichzeitig das Signal »0« führen, werden alle Zeilenleitungen Y gleichzeitig auf den Signalwert »1« gebracht. Wenn in diesem Fall zusätzlich auf sämtliche Schreibsteuerleitungen W das Signal »1« und auf sämtliche Informationsleitungen L das Signal »0« gegeben wird, werden alle Flipflops zurückgestellt, d. h., daß der gesamte Speicher gelöscht wird. Anders ausgedrückt, durch gleichzeitige Erregung aller Schreibsteuerleitungen W, während gleichzeitig alle Adressierleitungen / auf dem Signalwert »0« gehalten werden, wird in alle Zellen jeder Spalte das Bit eingegeben, das gerade über die Informationsleitung L der betreffenden Spalte übertragen wird.

Die vorstehende Beschreibung läßt erkennen, daß der Assoziativsuchvorgang nicht notwendigerweise stets zu einer eindeutigen Situation führt. Die Suchbedingung kann so gewählt sein, daß mehrere Zeilenleitungen Y gleichzeitig den Signalwert »1« annehmen. Die über die Leseleitangen D ausgegebenen Daten wären dann nicht eindeutig, und bei der Durchführung eines Schreibvorgangs würde die gleiche Information in mehrere Speicherplätze eingeschrieben werden. Um solche Unbestimmtheiten zu vermeiden, sind die Zeilenleitungen Y mit einer Prioritätslogikschaltung 60 verbunden, wie sie nun an Hand von F i g. 2 beschrieben werden soll.

F i g. 2 zeigt, wie ein assoziativer Speicher aus Soeichermodulcn der in F i g. 1 dargestellten Art zusammengebaut werden kann. Jeder Speichermodul hat entsprechend der Darstellung von F i g. 1 acht Bitspeicherstellen, und zwar jeweils zwei Bits von vier verschiedenen Wörtern, die in vier aufeinanderfolgenden Zeilen gespeichert sind. Es sei angenommen, daß der Speicher insgesamt ρ Speicherplätze und q Bitstcllen je Speicherplatz aufweist. Dabei sind ρ und q im allgemeinen positive ganze Zahlen. Für den kleinstmöglichen Speicher, der nur aus einem Speichermodul besteht, gilt /> 4 und q -■- 2 (m - η — 1). Somit muß ρ ein ganzzahliges Vielfaches von 4 und q ein ganzzahliges Vielfaches von 2 sein. Dies ist jedoch keine grundsätzliche Einschränkung, sondern ergibt sich lediglich aus der Verwendung eines Speichermoduls mit 2 · 4 Speicherzellen. Es ist zu beachten, daß in F i g. 2 die Speichermodule 5 gegenüber der Darstellung von Fig.! um 90° gedreht sind, so daß die »Zeilen« vertikal und die »Spalten« horizontal verlaufen. Die Speichermodule 5 sind in F i g. 2 in m horizontalen Reihen (die den Spalten entsprechen) und in η vertikalen Reihen (die den Zeilen entsprechen) angeordnet und mit Indizes versehen, deren erste Ziffer die horizontale Reihe und deren zweite Ziffer die vertikale Reihe bezeichnet. Es gilt also /1 = p/4 und /?i — q/2, und es sind insgesamt qjl ■ p/4 Speichermodule der in F i g. 1 gezeigten Art vorhanden. Aus Platzgründen sind jedoch nur die in den beiden ersten horizontalen Reihen Nr. 1 und Nr. 2 und in der letzten horizontalen Reihe Nr. in liegende Module der ersten vertikalen Reihe Nr. 1 und der letzen vertikalen Reihe Nr. /; liegenden Speichermodule 5,,, S₂₁, 5»» 1 ^ 5_in. 5₂„. 5,„„ dargestellt.

Für diese sechs Speichermodule sind in F i g. 1 die zugehörigen Schreibsteuerleitungen W, Adressierleitungcn /, Informationsleitungen L und Leseleitungen O angedeutet, die jeweils allen in der gleichen horizontalen Reihe liegenden Speichermodulen gemeinsam sind, sowie die Zeilenlcitungen }', die jeweils allen in der gleichen vertikalen Reihe liegenden Speicher-

4» modulcn 5 gemeinsam sind. Für die Speichermodule 5,, und 5, π der ersten (untersten) horizontalen Reihe sind dies die Schreibsteuerleitungen W_x, W₂, die Adressierleitungen Z₁, Z₂, die Informationsleitungen L₁, L₂ und die Lescleitungen D₁, D₂; für die Speicher-

4:5 module 5₂₁ und 5_sf! der zweiten horizontalen Reihe die Schreibsteuerlcitungen H₃. W₁, die Adressierleitungen Z₃, Z₁, die Informationsleitungen L₃, L₄ und die Leseleitungen D.„ Dj; und schließlich für die Speichermodule 5_m, und 5,„„ der letzten horizontalen Reihe die Schreibsteuerleitungen W_q, W_q~_x, die Adressierleitungen Z₇, Z₁₇₁, die Informationsleitungen L₉, L_q- ■ und die Leseleitungen D_q, D_q ,. Für die Speicher module S_n, 5₂₁, 5_ffll der ersten vertikalen Reihe sine die Zeilenleitungen K₁, Y₂, Y₃, Y_t dargestellt, und füi die Speichermodule 5, _n, 5₂ „, 5_mn der letzten vertikaler Reihe die Zeilenieitungen Y_v, Yp~\, Yp z, Yp 3 Alle Zeilenleitungen Y sind mit einer Prioritätslogik schaltung 60 verbunden, die außerdem über eini Leitung 66 ein von außen kommendes Freigabesigna empfängt. Die Prioritätslogikschaltung 60 hat dii Aufgabe, ein gleichzeitiges Ansteuern von zwei ode mehr Speicherplätzen zu verhindern, wenn mehrer Zeilenleitungen Y gleichzeitig den Signalwert »1« füh ren, weil der Assoziativsuchvorgang für die be

«5 treffenden Speicherplätze positiv verlaufen ist.

In der Pnoritätslogikschaltung 60 ist jede Zeilen leitung Y mit dem einen Eingang eines NOR-Gliede verbunden, wie durch die NOR-Glieder 70, 71, 72 fü

13 14

die Zeilenleitungen K₁, K„, Y₃ dargestellt ist. Der Pufferverstärker 93 sowie die weiteren, nicht dar-

zweite Eingang jedes dieser NOR-Glieder empfängt gestellten Pufferverstärker an die Zeilenleitung Y₁

das über die Leitung 66 kommende Freigabesignal. und alle folgenden Zeilenleitungen angelegt, so daß

Der Ausgang jedes NOR-Gliedes 70, 71,72 ... ist mit diese auf dem Signalwert »0« gehalten werden, unab-

dem einen Eingang eines Oder-Gliedes 80, 81, 82 ... 5 hängig von dem Ergebnis des Assoziativsuchvorgangs,

veibunden, dessen zweiter Eingang jeweils an den Aus- Wenn kein Freigabesignal über die Leitung 66

gang des vorhergehenden Oder-Gliedes angeschlossen übertragen wird, ist die Prioritätslogikschaltung 60

ist und beim ersten Oder-Glied 80 dauernd ein dem außer Betrieb gesetzt. Dies ist beispielsweise für den

Signalwert »1« entsprechendes positives Potential emp- zuvor beschriebenen Vorgang des Löschens des

fängt, herner ist der Ausgang jedes Oder-Gliedes 8ß, io ganzen Speichers wichtig, bei dem alle Zeilenleitungen

81, 82 ... über einen Pufferverstärker 91, 92, 93 ... Y₁ bis Yp auf dem Signalwert »lt gehalten werden

mit der folgenden Zeilenleitung K₂, Y₃, K₄ ... ver- müssen. Die Prioritätslogikschaltung 60 muß auch dann

bunden. Die Oder-Glieder 80, 81, 82 ... bilden zu- außer Betrieb gesetzt werden, wenn die gleiche Infor-

sammen mit den Pufferverstärkern 91, 92, 93 ... Ver- mation in mehr als einen Speicherplatz eingeschrieben

riegetüngsschaltungen, weiche die jeweils angeschlos- 15 werden soll. Schließlich können die Zeilenleitungen K₁

sene Zeilenleitung K zwangsläufig auf dem Signal- bis Y_p auch mit einer nicht dargestellten äußeren

wert »0« halten, wenn irgendeine der davorliegenden Adressieranordnung gekoppelt sein, so daß die Spei-

Zeilenleitungen den Signalwert»!« führt,- dadurch cherplätze unabhängig von einem der zuvor beschrie-

wird eine Prioritätsrangfolge festgelegt, wobei die benen Vorgänge angesteuert werden können. Diese

erste Zeilenleitung K₁ die höchste und die letzte Zeilen- 20 Möglichkeit macht die Anordnung noch anpassungs-

leitung Y_p die niedrigste Priorität hat. fähiger, setzt aber ebenfalls voraus, daß die Pnoritäts-

Diese Prioritätslogikschaltung 60 arbeitet in fol- logikschaltung 60 außer Betrieb gesetzt ist.
gender Weise: Es sei angenommen, daß über dieLei- Die Leseleitungen D₁ bis D_q, von denen jede mit tung66 ein Freigabesignal an sämtliche NOR-Glie- allen in der gleichen Spalte liegenden Speicherzellen der 70, 71, 72 angelegt wird. Ferner sei angenommen, 25 verbunden ist, sind an ein Datenaufnahmeresgister 65 daß die erste Zeilenleitung K, infolge des positiven angeschlossen, das q Stufen hat. Die Leseleitung D₁ Ergebnisses eines Assoziativsuchvorgangs den Signal- ist mit der ersten Stufe das Datenaufnahmeregisters 65 wert »1« führt. In diesem Fall gibt das NOR-Glied 70 verbunden, die Leseleitung D₂ mit der zweiten Stufe ein Signal »0« ab, das über sämtliche in Kaskade ge- und schließlich die Leseleitung D₉ mit der q-ten Stufe, schalteten Oder-Glieder 80, 81, 82 ... übertragen wird 30 In das Datenaufnahmeregister 65 werden somit und somit zu den Eingängen aller Pufferverstärker 91, parallel die Bits des Wortes eingegeben, das, in der 92, 93 ... gelangt. Das verstärkte Signal »0« liegt zuvor beschriebenen Weise aus der angesteuerten Zeile somit an sämtlichen Zeilenleitungen K₂, K₃ ... Y_v der Speichermatrix ausgelesen wird. Die Schrei bmit Ausnahme der ersten Zeilenleitung K, an und Steuerleitungen W₁ bis W ₉, von denen jede gleichfalls hält diese Zeilenleitungen auf dem entsprechenden 35 mit allen Speicherzellen der betreffenden Spalte verPotential, und zwar auch dann, wenn die Vergleichs- bunden ist, sind an eine Schreibsteuerschaltung 61 schaltungen der in einer Zeile liegenden Speicherzellen angeschlossen. Diese Schreibsteuerschaltung 61 kann die betreffende Zeilenleitung infolge eines positiven gleichfalls ein Register mit q Stufen sein, von denen Surhergebnisses auf den Signalwert »!« zu bringen jede eine der Schreibsteuerleitungen W ansteuert, suchen. Daher wird nur der Speicherplatz ausgewählt, 40 Dies ist dann der Fall, wenn die Nicht-Glieder zwiwelcher der ersten Zeilenleitung K₁ zugeordnet ist. sehen den Adressierleitungen / und den Schreibsteuer-

Nun wird angenommen, daß das Ergebnis des Asso- leitungen W (wie die Nicht-Glieder 33 und 34 von

ziativsuchvorgangs für die beiden ersten Zeilen negativ F i g. 1) in den Speichermodulen 5 nicht vorhanden

war, so daß die Zeilenleitungen Kj und K₂ auf dem sind oder wenn keine äußere Adressierung möglich

Signalwert »0« bleiben, während das Ergebnis für die 45 ist. Wenn dagegen die erwähnten Nicht-Glieder nach

dritte Zeile positiv war, so daß die Zeilenleitung K₃ Art der Nicht-Glieder 33 und 34 vorhanden sind,

den Signalwert »l·« annimmt. Infolge der Signal- können alle Schreibsteuerleitungen W_x bis W_q direkt

werte »0« auf den Zeilenleitungen K₁ und K₂ behält miteinander verbunden sein, und die Schreibsteuer-

das Ausgangssignal der NOR-Glieder 70 und 71 den schaltung 61 kann dann aus einer einzigen Stufe be-

Signalwert »1«, der auch an den Ausgängen der Oder- 5° stehen, an die alle Schreibsteuerleitungen gemeinsam

Glieder 80, 81 und der Pufferverstärker 91 und 92 angeschlossen sind, und die im Arbeitszustand alle

erscheint. Das am Ausgang des Pufferverstärkers 91 Schreibsteuerleitungen W auf das Potential bringt,

erscheinende Signal »1« bringt aber die Leitung K₂ das angibt, daß ein Schreibvorgang stattfinden

nicht auf den Signalwert »1«, da diese wegen der feh- soll.

!enden Übereinstimmung durch die Vergleichsschal- 55 Die Adressierleitung Z₁ bis I₉, von denen jede tung 21, 22 von wenigstens einer Speicherzelle in der wiederum mit allen Speicherzellen der betreffenden betreffenden Zeile auf dem Signalwert »0« gehalten Spalte verbunden ist, sind an die Ausgänge eines wird. Dagegen führt die Zeilenleitung K₃ den Signal- Adressierregisters 63 angeschlossen. Das Adressierwert »1«, da dieser sowohl von den Vergleichsschal- register 63 kann q Stufen enthalten, mit denen die tungen der zugehörigen Speicherzellen als auch vom 60 Adressierleitungen / getrennt angesteuert werden kön-Pufferverstärker 92 angelegt wird. Der der Zeilen- nen, wenn nicht von vornherein feststeht, daß bestimmte leitung K₃ zugeordnete Speicherplatz wird daher als Bitstellen aller Speicherplätze der Speicheranordnung Ergebnis des Assoziativsuchvorgangs ausgewählt. An- niemals für einen Assoziativsuchvorgang verwendet dererseits ruft der Signalwert »1« auf der Zeilenleitung werden. Zur Durchführung eines Assoziativsuch-K₃ ein Signal »0« am Ausgang des NOR-Gliedes 72 65 Vorgangs empfängt das Adressierregister 63 ein Steuhervor, und dieses Signal »0« wird über die das Oder- erwort, in welchem beispielsweise die Bits »1« angeben, Glied 82 und alle in Kaskade daran angeschlossenen welche Bitstellen des assoziativen Speichers an dem weiteren Oder-Glieder übertragen und über den Assoziativsuchvorgang teilnehmen sollen, d. h., Bits

enthalten, die mit den Suchbits verglichen werden sollen.

Alle Bits »0« in diesem Sleuerwort bezeichnen dann die Speicherzellen, welche nichv an dem Assoziativsuchvorgang teilnehmen rollen. Ein wesentliches Merkmal des beschriebenen assoziativen Speichers besteht darin, daß grundsätzlich keine Bitstelle irgendeines Speicherplatzes durch eine feste Verdrahtung darauf festgelegt ist, daß sie nur Assoziativsuchbits enthält. Eine solche Einschränkung kann für eine be- ίο stimmte Anwendung vorgenommen werden, aber vom Aufbau her ermöglichen die verwendeten Speichermodule grundsätzlich eine freie Wahl in der Weise. daß jede Speicherzelle in jedem Speicherplatz nach Belieben entweder ein Assoziativsuchbit oder ein Datenbit enthalten kann, wobei jeweils durch die Adressierleitungen / bestimmt wird, ob das gespeicherte Bit als Suchbit oder als Datenbit gedeutet wird.

Schließlich enthält der Speicher von F i g. 2 noch ein Informationsregister 64, an dessen Ausgänge die Informationsleitungen L₁ bis L_q angeschlossen sind. Dieses Informationsregister 64 bildet das Informationseingangsre{iister für den Speicher und weist demzufolge q Stufen auf. Die Eingänge des Informationregisiers 64 sind mit der nicht dargestellten Datenverarbeitungsanlage gekoppelt, zu welcher der assoziative Speicher gehört. Das Informationsregisler 64 empfängt sowohl die Suchbits für die Assoziativsuchvorgänge als auch die aufzeichnenden Datenbits. In bestimmten Stufen des Informationsregister 64 enthaltene Bits werden als Assoziativsuchbits gedeutet, wenn die entsprechenden Stufen des Adressierregisters 63 die Binärziffer »1« enthalten. Die Inhalte der übrigen Stufen des Informationsregisters 64, die also Stufen des Adressierregisters 63 entsprechen, in denen Bits »0« stehen. werden als Datenbits gedeutet, falls ein Schreibvorgang durchgeführt wird.

Das Adressierregister 63 kann in verschiedenartiger Weise für die Ansteuerung des Speichers verwendet werden. Die möglichen Ansteuerungen hängen von der Organisation des Speichers ab. Beispielsweise kann jeder Speicherplatz eine besondere Speicherzelle aufweisen, in der ein Bit gespeichert ist, das durch seinen Binärwert den Besetztzustand des Speicherplatzes angibt. Dieses Kennzeichenbit legt also fest, ob in den Speicherplatz unter Löschung des vorherigen Inhalts eingeschrieben werden kann, oder ob der Speicherplatz geschützte Daten enthält, die nicht gelöscht werden dürfen. Eine Möglichkeit der Durchführung des Assoziativsuchvorgangs besteht dann darin, einen Speicherplatz aufzusuchen, welcher infolge seines Kennzeichnungsbits als leer betrachtet werden kann.

In diesem Fall enthält das Adressierregister 63 ein einziges Bit »1« in der Stufe, die der Spalte des Speichers zugeordnet ist, in der alle das Kennzeichnungsbit enthaltenden Speicherzellen liegen; alle übrigen Stufen des Adressierregisters 63 enthalten dagegen Bits »0«. Dadurch ist festgelegt, daß nur eine Spalte des Speichers dem Assoziativsuchvorgang unterworfen ist. Wenn man ferner annimmt, daß ein Kennzeichnungsbit »0« den Besetztzustand und ein Kennzeichnungsbit »1« den Freizustand des Speicherplatzes anzeigt, wird in die entsprechende Stufe des Informationsregisters 64 ein Suchbit »1« eingegeben; der Inhalt der übrigen Stufen des Informationsregisters 64 ist für den Assoziativsuchvorgang unwesentlich. Da aber die Suche nach einem leeren Speicherplatz gewöhnlich zum Zweck eines Sclreibvorgangs durchgeführt wird, enthalten diese übrigen Stufen des Informationsregisters 64 die Bits, die in den gesuchten leeren Speicherplatz eingeschrieben werden sollen. Diese Bits können sowohl Datenbits als auch Adressenbits für Assoziativsuchvorgänge sein.

Mit dem soeben beschriebenen Suchvorgang wird lediglich ein leerer Speicherplatz gesucht. Nachdem ein leerer Speicherplatz gefunden worden ist, wird die Schreibsteuerschaltung 61 aktiviert, wodurch die in den übrigen Stufen des Informationsregiste^s 64 stehenden Daten in den gefundenen Speicherplatz eingeschrieben werden.

Wenn mehr als ein freier Speicherplatz gefunden wird, bestimmt die Pnoritätslogikschaltung 60, falls sie aktiviert ist, daß das Einschreiben nur in den ersten leeren Speicherplatz erfolgt, während die übrigen leeren Speicherplätze gesperrt werden.

Da jeder Assoziativsuchvorgang mit einem Lesevorgang gekoppelt ist, erscheint auf der Leseleiiung D, die den die Kennzeichnungsbits enthaltenden Speicherzellen zugeordnet ist, stets dann ein Signal »1«, wenn wenigstens ein leerer Speicherplatz gefunden worden ist. Das Ausbleiben dieses Signals »1« zeigt an, daß durch den Assoziativsuchvorgang kein leerer Speicherplatz gefunden wurde. Da in diesem Fall der Schreibvorgang nicht durchgeführt werden kann, muß die Datenverarbeitungsanlage entscheiden, was in diesem Fall zu tun ist.

Nach dem Auffinden des leeren Speicherplatzes und das Einschreiben von Informationen in den gefundenen Speicherplatz ist es erforderlich, diesen Speicherplatz als »besetzt« zu kennzeichnen. Dies kann in der folgenden Weise geschehen: Nach der Durchführung des Schreibvorgangs enthält das Informationsregister 64 noch die soeben in den Speicherplatz, eingeschriebenen neuen Adressenbits in bestimmten Stufen. Die entsprechenden Stufen des Adressenregisters / erhalten nunmehr den Inhalt »1«, wogegen die dem Kennzeichnungsbit zugeordnete Stufe des Adressierregisters 63 in den Zustand »0« zurückgestellt wird. Ebenso wird in die dem Kennzeichnungsbit entsprechende Stufe des Informationsregisters 64 das Bit »0« eingebracht. Wenn nun ein neuer Assoziativsuchvorgang mit anschließendem Schreibvorgang ausgelöst wird, wobei nur die dem Kennzeichnungsbit entsprechende Schreibsteuerleitung W erregt wird, ist unmittelbar zu erkennen, daß in den gefundenen Speicherplatz das Kennzeichnungsbit »0<· eingeschrieben wird, wodurch dieser Speicherplatz als «besetzt« gekennzeichnet ist.

Der assoziative Speicher ist an sich einzeln überhaupt nicht adressierbar, wenn nicht eine äußere Adressierung vorgesehen wird, was im Prinzip nicht erforderlich ist. Zur Inbetriebnahme kann der Speicher zweckmäßig in folgender Weise betrieben werden: Die Prioritätslogikschaltung 60 wird zunächst außer Betrieb gesetzt, alle Schreibsteuerleitungen IV sind erregt, das Adressierregister 63 enthält lauter Bits -»Ο«, und in das Informationsregister 64 wird ein Wort eingegeben, das in der den Kennzeichnungsbits entsprechenden Stelle ein Bit»l« und in allen übrigen Stellen ein Bit »0« enthält. Alle Zeilenlcilungen V werden auf den Signalwert »1« gebracht. Dies hat zur Folge, daß in sämtliche Speicherplätze die Kcnnzcichnungsbils >·! * eingeschrieben werden, wodurch die Speicherplätze als »unbesetzt« gekennzeichnet werden,

während alle übrigen Speicherzellen gelöscht werden. Anschlielfend können Schreibvorgänge in der zuvor beschriebenen Weise so durchgeführt werden, daß leweils ein freier Speicherplatz gesucht wird. Die

d dfü dß di

Prioritätslogikschaltung sorgt dann dafür, daß die 5 bits durchgeführt werden.

freien Speicherplätze der Reihe nach belegt werden. Sobald Speicherplätze belegt sind, können außerdem Assoziativsuchvorgänge unter Verwendung der inzwischen in die Speicherplätze eingeschriebenen Suchfh d

Hierzu 2 Blatt Zeichnungen

Claims (3)

Patentansprüche:

1. Assoziativer Speicher mit Speicherzellen für jeweils eine Binärziffer, die in Zeilen und SpaJten zu einer Matrix verdrahtet sind, wobei jede Zeile wenigstens einen Speicherplatz mit mehreren Binärzifferstellen umfaßt und die einander entsprechenden Ziffernstellen zugeordneten Speicherzellen der Speicherplätze in den gleichen Spalten der Matrix liegen, und wobei jede Speicherzelle ein bistabiles Speicherelement, eine Vergleichsschaltung, eine Schreibtorschaltung und eine Lesetorschaltung enthält, mit einem Informationswortregister, an dessen Stufenausgänge liifor- mationsleitungen angeschlossen sind, die jeweils mit den Vergleichsschaltungen aller in einer Spalte liegenden Speicherzellen derart verbunden sind, daß jede Vergleichsschaltung ein die Übereinstimmung bzw. Nichtübereinstimmung zwischen dem Inhalt des zugehörigen Speicherelements und der über die Informalionsleitung übertragenen Binärziffer anzeigendes Signal abgibt, mit einem Adressierregister, an dessen Stufenausgänge Adressierleitungen angeschlossen sind, die jcweii- mit den Steuereingängen der Vergleichsschaltungen aller in einer Spalte liegenden Speicherzellen verbunden sind, mit Zeüenleitungen, die jeweils an die Ausgänge der Vcrgleichsschaltungen der zu einem Speicherplatz gehörenden Speicherzellen derart angeschlossen sind, daß sie dann und nur dann einen die Übereinstimmung anzeigenden Spannungswert führen, wenn in alien dem Vergleich unterworfenen Spalten eine Übereinstimmung besteht, mit Leseleitungen, die jeweils mit den Ausgängcn der Lcselorschaltungen aller in der gleichen Spalte liegenden Speicherzellen verbunden sind, und mit Sclireibsteuerleitungen, von denen jede mit den Stcuereingängen der Schrcibtorschaltungen bestimmter Speicherzellen verbunden ist. dadurch gekennzeichnet, daß die Signaleingänge der Schreibtorschaltungen (24, 25) aller in einer Spalte liegenden Speicherzellen (10) an die dieser Spalte zugeordnete Informationsleitung (L) angeschlossen sind, daß jede Schreibsleuerleitung (W) mit den Steuereingängen der Schreibtorschaltungen (24, 25) aller in einer Spalte liegenden Speicherzellen (10) verbunden ist, daß ein weiterer Steuercingang jeder Schrcibtorschaltung (24, 25) mit der zugehörigen Zeilenleitung ()') vcrbundcn ist, daß der Steuereingang jeder Lesetorschaltung (23) mit der zugehörigen Zcilenleitung ()') verbunden ist und daß der die Übereinstimmung anzeigende Spannungswert auf der Zeilenleitung (Y) als Enlsperrungssignal für die angeschlossencn Lesetorschaltungen (23) und Schreibtorschaltungen (24, 25) wirkt.

2. Assoziativer Speicher nach Anspruch 1, dadurch gekennzeichnet, daß jede Adressierleitung (/) mit der zur gleichen Spalte gehörenden Schreibsteuerleitung (W) über eine Schaltung (33. 34) verbunden ist, welche die Erregung der Schreibstcuerlcitung (U) bei einer Erregung der Adressierleitung (/) verhindert.

3. Assoziativer Speicher nach Anspruch 1 oder 2, bei welchem ein mehrfaches Ansprechen auf die gleiche Assoziativsuchc durch eine Prioritätslogikschaltung geregelt wird, die durch ein besonderes Programmsignal erregbar ist, dadurch gekennzeichnet, daß die Prioritätslogikschaltung (60) eine Kaskade von Verriegelungsschaltungen (70, 71, 72, ...; 80, 81, 82, ...; 90, 91, 92, ...) enthält, die in einer Folge der Reihe nach durch das Programmsignal freigegeben werden und bei jedem Schritt der Folge jeweils eine Zeilenleitung ( Y) zur Annahme des die Übereinstimmung anzeigenden Spannungswertes freigeben und alle übrigen Zeilenleituncen (K) auf einem der scheinbaren Nichtübereinstimmung entsprechenden Spannungswert halten.