DE2525287B2

DE2525287B2 - ASSOCIATIVE MEMORY

Info

Publication number: DE2525287B2
Application number: DE19752525287
Authority: DE
Inventors: Gerhard 8000 München Wolf
Original assignee: Siemens AG
Current assignee: Siemens AG
Priority date: 1975-06-06
Filing date: 1975-06-06
Publication date: 1977-03-24
Also published as: DE2525287A1; FR2313738B3; FR2313738A1; BE842604A; NL7606019A

Description

Die Erfindung bezieht sich auf einen Assoziativspeicher nach dem Oberbegriff des Patentanspruchs i. ν >The invention relates to an associative memory according to the preamble of claim i. ν>

Integrierte Bausteine zum Aufbau von Assoziativspeichern sind bereits bekannt (vergleiche Datenblatt TT μL· Memory 93 402 der Firma Fairchild Semiconductor vom Mai 197ί). Der bekannte Baustein hat mit 16 Bit eine vergleichsweise geringe Speicherkapazität. Dem ^ Versuch, die Kapazität zu erhöhen, hat in der Vergangenheit vor allem die Zahl der innerhalb eines Bausteins realisierbaren Verknüpfungs- bzw. Speicherglieder eine Grenze gesetzt. Durch die zunehmende Beherrschung der Integrationstechnik hat sich das im Problem verlagert, so daß die Grenzen mehr und mehr durch die maximale Anzahl der äußeren Anschlüsse gegeben sind. Bekanntlich sind beim Assoziativspeicher wesentlich mehr Anschlüsse als beim linear adressierten Speicher erforderlich, weil zusätzliche Leitungen für die '^ Eingabe der Maske und für die Ausgabe der Treffersignale vorgesehen werden müssen.Integrated modules for setting up associative memories are already known (see data sheet TT μL · Memory 93 402 from Fairchild Semiconductor from May 197). The known module has a comparatively small storage capacity of 16 bits. In the past, the attempt to increase capacity was mainly limited by the number of logic or memory elements that could be implemented within a module. Due to the increasing mastery of integration technology, the problem has shifted, so that the limits are more and more given by the maximum number of external connections. Known more ports than the linear addressed memory are much needed in associative memory because additional lines must be provided for the '^ entering the mask and to output the hit signals.

Zwar kann die Anzahl der äußeren Anschlüsse des Bausteins dadurch verringert werden, daß die Datenleitungen sowohl für die Eingabe als auch für die Ausgabe von Daten benutzt werden, daß die für die Anwahl der Speicherplätze erforderlichen Adressendecodierer innerhalb des Bausteins integriert werden und daß die Maske ebenfalls über die Datenleitungen zugeführt wird. Die zuletzt genannte Maßnahme bedingt die Bereitstellung eines Maskenregisters innerhalb des Bausteins, was jedoch den Schaltungs- und Zeitaufwand erhöht.It is true that the number of external connections of the module can be reduced by the fact that the data lines can be used for both input and output of data, that for the selection of the Memory locations required address decoder are integrated within the module and that the Mask is also supplied via the data lines. The last-mentioned measure requires the Provision of a mask register within the module, which, however, reduces the expenditure on circuit and time elevated.

Ausgehend von der Erkenntnis, daß sich die assoziative Verarbeitung der gespeicherten Daten in den weitaus überwiegenden Fällen nur über Teile des gesamten Inhalts von Speichern mittlerer oder hoher Kapazität erstreckt, liegt der Erfindung die Aufgabe zugrunde. Maßnahmen anzugeben, die es gestatten, die innerhalb eines integrierten Bausteins realisierbare Speicherkapazität zu erhöhen, ohne daß die Anzahl der äußeren Anschlüsse ein tragbares Maß überschreitet.Proceeding from the knowledge that the associative processing of the stored data in the overwhelming majority of cases only extends over parts of the entire contents of medium or high capacity memories, the object of the invention is based. Specify measures which make it possible to increase the storage capacity that can be realized within an integrated module without the number of external connections exceeding an acceptable level.

Gemäß der Erfindung wird diese Aufgabe durch die im kennzeichnenden Teil des Patentanspruchs 1 angegebenen Maßnahmen gelost.According to the invention, this object is achieved by the features set out in the characterizing part of claim 1 specified measures solved.

Neben einem besonders günstigen Verhältnis der in einem einzelnen Speicherbaustein realisierbaren Kapazität zu der An.tahl der erforderlichen äußeren Anijhlüsse bietet der hierarchisch organisierte Assoziativspeicher große Vorteile bei der Verarbeitung unabhängiger Tabellen bzw. Listen, insbesondere beim Sortieren von ungeordneten abgelegten Begriffen. Jede Adres.se des Untergrund-Speichers bildet einen unabhängig assoziierbaren Bereich (vergleiche Patentanmeldung P 25 05 477.7).In addition to a particularly favorable ratio of the capacity that can be realized in a single memory module The hierarchically organized associative memory offers the number of required external connections great advantages when processing independent tables or lists, especially with Sorting of unordered stored terms. Each Adres.se of the underground storage forms one independently associable area (see patent application P 25 05 477.7).

Im folgenden wird die LilinJung anhand eines in der Zeichnung dargestellten Ausführungsbeispiels näher beschrieben. Es zeigtIn the following, the LilinJung is based on one in the Drawing illustrated embodiment described in more detail. It shows

F i g. 1 eine schematische Darstellung zur Erläuterung des Grundprinzips,F i g. 1 a schematic representation to explain the basic principle,

F i g. 2 den inneren Aufbau eines Speicherbausteins.F i g. 2 shows the internal structure of a memory module.

Die Fig. 1 zeigt den Assoziativspeicher gemäß der Erfindung als Block, von dem eine dünne Scheibe 5! abgetrennt und ein wenig nach oben gerückt ist. Diese Scheibe 51 soll die assoziative Oberfläche darstellen. Der restliehe, größere Teil S 2 des Blocks bezeichnet den linear adressierbaren, nHit assoziativen Untergrund-Speicher. FIG. 1 shows the associative memory according to FIG Invention as a block from which a thin slice 5! separated and moved up a little. These Disk 51 is intended to represent the associative surface. The rest of the larger part S 2 of the block is designated the linearly addressable, nHit associative underground memory.

Der gesamte Datenaustausch zwischen dem Assoziativspeicher und seiner Umwelt erfolgt allein über seine Oberfläche. Ein direkter Zugriff zum Untergrund-Speicher ist nicht möglich.The entire data exchange between the associative memory and its environment takes place solely through its own Surface. Direct access to the underground storage is not possible.

Zur Erleichterung des Verständnisses soll zunächst davon ausgegangen werden, daß die Oberfläche durch einen voll assoziativen Speicher gebildet wird, der beispielsweise aus 64 Wortzeilen zu je 8 Byte besteht. Den einzelnen Speicherzellen sind in bekannter Weise Vergleicher zugeordnet, die zeilenweise zusammenwirken und bei Übereinstimmung des Zeileninhaltes mit dem vorgegebenen Suchbegriff ein Treffersignal abgeben. Durch eine veränderbare Maske kann der Assoziationsbereich auf Teile der Wortzeile, gegebenenfalls bis auf ein Bit, eingeengt werden. Für die Eingabe und Ausgabe von Daten können die Zeilen des Oberflächen-Speichers getrennt ausgewählt werden. Bei der Betriebsart »Assoziieren« werden alle Zeilen gleichzeitig erfaßt.To facilitate understanding, it should first be assumed that the surface is through a fully associative memory is formed, which for example consists of 64 word lines of 8 bytes each. The individual memory cells are assigned comparators in a known manner, which interact line by line and emit a hit signal if the content of the line matches the specified search term. Using a changeable mask, the association area can be applied to parts of the word line, if necessary down to a bit. The lines of the Surface memory can be selected separately. In the »Associate« operating mode, all lines captured at the same time.

Jeder Zeile des Oberflächen-Speichers sind 2", beispielsweise 32, durch eine »Untergrund-Adresse« adressierbare Zeilen im Untergrund-Speicher zugeordnet. Die 2" Zeilen bilden einen Untergrund-Speicherbe-Each line of the surface memory is assigned 2 ", for example 32, lines in the underground memory that can be addressed by an" underground address ". The 2" lines form an underground memory area.

reich. Einander entsprechende Zeilen aller Untergrund-Speicherbereiche werden durch gleiche Untergrund-Adressen erfaßt und bilden eine Untergrund-Speicherebene. rich. Corresponding lines of all underground storage areas are registered by the same underground addresses and form an underground storage level.

Über die auf diese Weise geschaffene, sehr breite Schnittstelle zwischen dem Untergrund und der Oberfläche kann in einem Speicherzyiclus der gesamte Inhalt des Oberflächen-Speichers parallel in die adressierte Untergrund-Speicherebene überführt oder umgekehrt von dort übernommen werden.About the very broad interface created in this way between the underground and the The entire surface can be stored in one storage cycle The contents of the surface memory are transferred in parallel to the addressed underground memory level or conversely, can be taken over from there.

Bei der Aufteilung des Gesamtspeichers in einzelne integrierte Bausteine mit möglichst hohem Integrationsgrad ist es zweckmäßig, zur Verringerung der Anzahl der nach außen führenden Anschlüsse die Schnittstelle zwischen der Oberfläche und dem Untergrund in das Innere des Bausteins zu verlegen.When dividing the total memory into individual integrated modules with the highest possible degree of integration it is advisable to use the interface to reduce the number of connections leading to the outside to be laid between the surface and the subsurface in the interior of the building block.

Die Fig. 2 zeigt in schema tische r Darstellung ein vorteilhaftes Ausführungsbeispiel mit einer Kapazität von 1024 Bit (1 K-Bh), wobei die nach der vorher erwähnten Annahme vorhandene Kapazität des Oberflächen-Speichers nicht mitgerechnet ist. Der Baustein enthält 64 Bitelemente AS. die in vier Zeilen zu je 16 Bitelementen angeordnet sind. Die Zeilen, die innerhalb des Bausteins im allgemeinen nur Teilworte des Gesamtspeichers umfassen, sind für Lese- oder Schreibzyklen einzeln wählbar Hierzu wird dem Baustein über die äußeren Anschlüsse 26 und 27 eine binär codierte Oberflächen-Adresse AA zugeführt, die d.irch den Decodierer DA in die Form 1 aus umgewandelt wird. Ein dem Decodierer DA ebenfalls zugeführtes !nhibitsignal IN (Anschluß 25) ermöglicht die Auswahl eines bestimmten Bausteines bzw. einer Gruppe aus 4 Wortzeilen der Oberfläche des Gesamtspeichers.Fig. 2 shows a schematic representation of an advantageous embodiment with a capacity of 1024 bits (1 K-Bh), the existing capacity of the surface memory according to the previously mentioned assumption is not included. The block contains 64 bit elements AS. which are arranged in four lines of 16 bit elements each. The lines that comprise the total memory within the block, in general, only part words are, for read or write cycles individually selectable For this purpose, the block via the external terminals 26 and 27, a binary coded surfaces address AA is supplied to the d.irch the decoder DA is converted into the form 1 from. An inhibit signal IN (connection 25) which is also fed to the decoder DA enables the selection of a specific module or a group of 4 word lines on the surface of the overall memory.

Unter der vorher gemachten Annahme, daß die Oberfläche eine selbständig speicherfähige Anordung darstellt, besteht jedes ihrer Bitelemente aus einem Speicherelement zur Speicherung eines Datenbits und einem Vergleicher zum assoziativen Vergleich des gespeicherten Datenbits mit dem betreffenden Bit des Suchbegriffs. Die Ausgänge der einzelnen Vergleicher einer Zeile werden nach einer UND-Funktion verknüpft. Die Anschlüsse 21 bis 24 dienen zur Ausgabe der Treffersignale TRa. Über die Anschlüsse 17 bis 20 werden die Treffersignale 77?; vorausgehender Bausteine zugeleitet. Läßt die vorgesehene Verknüpfungsschaltung eine verdrahtete UND-Verknüpfung zu. dann können einander entsprechende Treffer-Ausgangsleitungen einfach miteinander verbunden werden und die Treffer-Eingangsleitungen sind entbehrlich. Auf diese Leitungen kann auch dann verzichtet werden, wenn die Treffersignale von allen schließlich zu einer gemeinsamen Wortzeile zusammengefaßten Zeilen der Einzelbausteine durch ein zusätzliches äußeres UND-Glied verknüpft werden.Under the previously made assumption that the surface represents an independently storable arrangement, each of its bit elements consists of a storage element for storing a data bit and a comparator for associative comparison of the stored data bit with the relevant bit of the search term. The outputs of the individual comparators of a line are linked according to an AND function. The connections 21 to 24 serve to output the hit signals TRa. The hit signals 77 ?; are transmitted via the connections 17 to 20; preceding modules. Does the logic circuit provided allow a wired AND operation. then corresponding hit output lines can simply be connected to one another and the hit input lines can be dispensed with. These lines can also be dispensed with if the hit signals from all lines of the individual modules that are finally combined into a common word line are linked by an additional external AND element.

Für je vier Bitelemente mit dem gleichen Stellenwert in den vier Zeilen der Oberfläche in einem Baustein steht ein Anschluß 1 bis 16 für die Eingabe oder Ausgabe von Daten (Bitleitungen) zur Verfügung. Weiterhin sind Anschlüsse 34 bis 49 für die Eingabe der veränderbaren Maske vorgesehen. Die zuletzt genannten Anschlüsse können eingespart werden, wenn dafür in den Baustein ein 16ste!liges Register für die Zwischenspeicherung der veränderbaren Maske integriert wird. Neben dem erhöhten Schaltungsaufwand vergrößert sich dabei auch der für einen Assoziationsvorgang insgesamt benötigte Zeitaufwand, weil in einem ersten Arbeitsschritt die Maske über die Bitleitungen eingespeichertFor every four bit elements with the same value in the four lines of the user interface in one module a connection 1 to 16 is available for the input or output of data (bit lines). Furthermore are Connections 34 to 49 are provided for entering the changeable mask. The last-mentioned connections can be saved if there is a 16-digit register in the block for the intermediate storage of the changeable mask is integrated. In addition to the increased circuit complexity, this increases also the total time required for an association process, because in a first work step the mask is stored via the bit lines

ίο werden muß, mindestens dann, wenn sich ihr Zustand gegenüber dem vorausgehenden Assoziationsvorgang geändert hat.ίο must be, at least when their condition changes has changed compared to the previous association process.

Die binär codierten Anweisungen für die Bestimmung der Arbeitsmodi Lesen, Schreiben oder Assoziieren werden über die Anschlüsse 32 und 33 dem Decodierer DB zugeführt und von diesem entschlüsselt. Die Steuersignale wirken sowohl auf den Oberflächen- als auch auf den Untergrund-Speicher ein.The binary-coded instructions for determining the working modes reading, writing or associating are supplied to the decoder DB via the connections 32 and 33 and are decrypted by the latter. The control signals act on both the surface and the underground memory.

Analog der Zuordnung eines Speicherbereichs mit 2" Analogous to the assignment of a memory area with 2 "

:o Zeilen zu jeder Zeile des Oberflächenspeichers in der Gesamtordnung sind auch innerhalb eines Bausteins jeder Zeile des Oberflächenspeichers 2" Zeilen entsprechender Länge eines Untergrund-Teilspeichers US zugeordnet. Dem in Fig. 2 dargestellten Ausführungsbeispiel sind 16 Speicherzeilen zugrunde gelegt (n = 4). Die für die Adressierung des Untergrund-Speichers i/5 erfordei liehen Untergrund-Adressen UA bestehen demgemäß aus 4 Bit, die an den Anschlüssen 28 bis 31 eingespeist werden. Für die Decodierung der Unter-: o Lines for each line of the surface memory in the overall order are also assigned within a module to each line of the surface memory 2 "lines of corresponding length of an underground sub-memory US . The exemplary embodiment shown in FIG. 2 is based on 16 memory lines (n = 4). The underground addresses UA required for addressing the underground memory i / 5 accordingly consist of 4 bits, which are fed in at the connections 28 to 31. For the decoding of the sub-

<· grund- Adiv.sen IJA ist grundsätzlich nur ein Adressendecodierer je Bauslein notwendig. Zur Einsparung von internen Steuerleitungen kann es jedoch zweckmäßig sein, jedem Speicherbereich oder sogar nur einem Teil eines solchen einen eigenen Adressendecodierer beizuordnen. In der Fig. 2 ist kein Decodierer für die Untergrund-Adresse UA dargestellt.<· Grund- Adiv.sen IJA basically only one address decoder is necessary per module. In order to save internal control lines, however, it can be expedient to assign a separate address decoder to each memory area or even to only part of such a memory area. No decoder for the underground address UA is shown in FIG.

Der Assoziativspeicher gemäß der Erfindung kann mit bipolaren oder mit unpipolaren (MOS) Elementen, insbesondere auch als sogenannter CCD-Speicher hergestellt werden. In all diesen Fällen geben die Speicherelemente nichtflüchtige, d. h. statische oder quasistatische Lesesignale ab. Da der Inhalt einer adressierten Speicherebene des Untergrund-Speichers [JS ohnehin zur Verfügung steht, können die Speicher-The associative memory according to the invention can be produced with bipolar or with unpipolar (MOS) elements, in particular also as a so-called CCD memory. In all these cases, the memory elements emit non-volatile, ie static or quasi-static read signals. Since the content of an addressed storage level of the underground storage [JS is available anyway, the storage

•15 zellen in der Oberfläche entfallen. Die Oberfläche besorgt dann insoweit nur noch die Verbindung zur Außenwelt.• There are no 15 cells on the surface. The surface then only takes care of the connection to the outside world.

Es sei noch erwähnt, daß es zur Ermittlung freier Speicherplätze beim Einschreiben neuer Daten zweckmäßig ist, eine Speicherzelle in jeder Wortzeile des Untergrund-Speichers für die Eintragung eines Belegtbit vorzusehen. Das Belegtbit bleibt erhalten, solange der Inhalt der betreffenden Wortzeile noch aktuell ist. Die Ermittlung freier Speicherplätze erfolgt durch einen assoziativen Suchvorgang, der durch entsprechende Festlegung der Maske auf die Inhalte der betreffenden Speicherzellen in der adressierten Speicherebene beschränkt ist.It should also be mentioned that it is useful to determine free memory locations when writing new data is, a memory cell in each word line of the underground memory for the entry of a busy bit to be provided. The occupied bit is retained as long as the content of the relevant word line is still up-to-date. The determination of free storage spaces is carried out by an associative search process, which is carried out by a corresponding Definition of the mask on the contents of the relevant memory cells in the addressed memory level is limited.

Hierzu 1 Blatt Zeichnungen1 sheet of drawings

Claims

Patent claims:

1. From integrated building blocks, hierarchically organized associative memory with word-by-word (line by line) access and with an association area within the words to be determined by a selectable mask, characterized in that each building block is hierarchically organized in such a way that one ι consists of several lines associative surface is linewise cooperating associative comparators are provided which receive data from the outside or release to the outside or with an each line associated linearly _addressable: cash Substrate (Teii-) memory having 2 "regardless of the rows of the surface selectable rows exchange can and that each module contains a decoder for selecting the lines of the surface (partial) memory and the underground (partial) memory

2. Associative memory according to claim!, Characterized in that the surface has its own Having memory cells.

3. Associative memory according to claim 1 or 2,. '. characterized in that in each building block Means are provided that, when the command »Associate« is present, all lines of the surface or activate the surface (partial) storage tank at the same time. v

4. Associative memory according to claim 3, characterized in that in each building block one on the Data lines loadable mask register is integrated.

5. Associative memory according to one of the preceding claims, characterized in that each word line is assigned a special memory cell, that when a new word is entered, an occupancy bit is set in the special memory cell of the word line in question and that ± free memory locations by an association process can be determined, in which only the special memory cells of the addressed memory planes participate by appropriate masking.