DE2305583A1 - Speichereinrichtung - Google Patents

Description

Die Erfindung bezieht sich auf eine Speichereinrichtung mit mehreren, eine Vielzahl von Speicherplätzen umfassenden Speicherbänken, die jeweils in einen durch einen Teil (Vorsilbe) des Assoziationsbegriffs adressierbaren assoziativen Abschnitt, dessen Inhalt mit dem Assoziationsbegriff oder mit einem inaskierbaren Teil desselben verglichen wird, um Auskunft über das Vorhandensein eines Begriffs zu erhalten, und in einen nicht assoziativen Abschnitt zur Aufnahme eines beigeordneten Begriffs gegliedert sind.

Der Aufwand für einen reinen Assoziativspeicher, bei dem der gesamte Inhalt gleichzeitig mit dem Suchbegriff verglichen v/ird, beträgt ein Mehrfaches des Aufwands für einen nichtassoziativen Speicher gleicher Kapazität, weil jeder Speicherzelle ein Vergleicher beigegeben werden muß, wenn man nicht die einzelnen Speicherplätze nacheinander abfragen will, was sehr viel Zeit in Anspruch nehmen würde. Heine Assoziativspeicher werden deshalb im Verhältnis zu anderen Speichersystemen immer teuer sein. Zudem haben reine Assoziativspeicher, die nur eine inhalts—

adressierte Suche mit dem Ergebnis JA oder NEIN ermöglichen, ein verhältnismäßig kleines Anwendungsgebiet. Man kann sie beispielsweise zum Sortieren benutzen. In der Regel ist es zweckmäßiger, dem eigentlichen assoziativen (inhaltsadressierten) Teil einen nichtassoziativen Teil

VPA 9/210/2034 She/Pdl

-2-

409835/0401

zuzuordnen, der vom assoziativen Teil angesteuert wird, wenn der gesuchte Begriff in diesem enthalten ist.

Ein derart aufgeteilter Assoziativspeicher ermöglicht echte assoziative Verknüpfungen. Er.läßt sich beispielsweise für verschiedenartige Zuordnungs- und Übersetzungsaufgaben, für die Sortierung und Listenbearbeitung, für die der menschlichen Denkweise ähnliche Bildung'von Assoziationsketten und vieles mehr einsetzen-. Eine Anwendung als Schnellzugriffsspeicher zwischen einem relativ langsamen Arbeitsspeicher und einem schnellen Prozessor ist durch die DT-OS 1 4-99 182 gekannt geworden.

Auch solche Assoziativspeicher bedingen einen sehr beträchtlichen Mehraufwand gegenüber speicherplatzadressierten Speichern, weshalb ihr Einsatz in größerem Umfang trotz günstiger sonstiger Eigenschaften bisher nicht erfolgte. Bekanntlich wird aber jeder Speicher mit Speicherplatzadressierung zum Assoziativspeicher, wenn man die Adressen als Assoziationsmittel benützt. Dabei wird der Assoziationsbegriff selbst nicht in den Speicher eingeschrieben, vielmehr dient er weiterhin zur direkten Auswahl eines bestimmten Speicherplatzes. In den Speicherplatz wird jedoch ein "Beschrieben-Bit" eingetragen, dessen Vorhandensein bzw. NichtVorhandensein Auskunft darüber gibt, ob der gesuchte Begriff im Speicher zu finden ist oder nicht. Die übrigen Bitzellen des Speicher- platzes stehen dann für die Eintragung eines beigeordneten Begriffes zur Verfügung.

Ein entscheidender Nachteil dieses Verfahrens ist die zumeist schlechte Ausnutzung des Speichers, weil in der Regel nur ein kleiner Bruchteil all der Begriffe auftaucht, die durch die Adressenbit dargestellt werden können.

VPA 9/210/2054 -3-

409835/0401

Wesentlich günstiger ist ein Verfahren, bei dem der Assoziationsbegriff in zwei Teile aufgespalten wird. Der eine Teil dient zur Adressierung eines Speicherplatzes, der andere Teil wird dessen Inhalt. Wenn hier wie im folgenden vom Inhalt des Speichers oder eines Speicherplatzes die Rede ist, so bezieht sich das auf den assoziativen Teil. In der Regel wird jedoch zusätzlich ein nichtassoziativer Speicherteil zur Eintragung von beigeordneten Begriffen vorhanden sein. Der nichtassoziative Speicherteil wird nicht mehr besonders erwähnt werden.

Um festzustellen, ob ein gesuchter Begriff in dem Speicher enthalten'ist, wird dieser Begriff in derselben Art wie beim Einschreibvorgang in zwei Teile zerlegt. Der eine Teil wird wieder zur Adressierung benutzt, der andere Teil wird mit gelesenen Speicherinhalt verglichen. Dieser Vergleich ergibt, ob der gesuchte Begriff tatsächlich in der ausgewählten Speicherzelle enthalten war (Treffer oder kein Treffer). Da für den Vergleich nur der jeweils adressierte Speicherplatz infrage kommt, ist der nun benötigte Aufwand an Vergleichsmitteln entsprechend gering.

Zum leichteren Verständnis des Weiteren ist in der Pig. 1 das Prinzip eines solchen Speichers dargestellt. Der vollständige Assoziationsbegriff möge aus den Bit a bis h bestehen. Die Bit a, b c (Vorsilbe) dienen zur Anwahl eines Speicherplatzes im Speicher SP, in den die restlichen Bit d bis h eingeschrieben werden.

Ergibt sich bei der Suche nach einem bestimmten Begriff, daß die Bit d bis h des Assoziationsbegriffs mit den Bit d .bis h in dem durch die Bit a, b, c ausgewählten Speicherplatz übereinstimmen, so liefert der Vergleicher VR ein

VPA 9/210/2034 -4-

409835/0401

Signal (Treffer), das "die Torschaltungen Ga bis Gh öffnet. Der ganze Assoziationsbegrxff, gegebenenfalls gleichzeitig mit einem beigeordneten Begriff, steht dann, am Ausgang wieder, zur Verfugung. Es besteht auch die Möglichkeit, nur den beigeordneten Begriff zusammen mit einem Treffersignal auszugeben, da der Assoziationsbegrxff ohnehin schon vorliegt.

Das geschilderte Verfahren mit der Aufspaltung des Assoziationsbegriffs in Adressen- und Inhaltsteil weist neben dem Vorteil des relativ geringen Aufwands jedoch den Nachteil auf, daß der Speicher jeweils nur einen Begriff aus einer Gruppe von Begriffen mit gleicher Vorsilbe aufnehmen kann. Bei einer zufälligen Häufung solcher ähnlicher Begriffe, die sich insbesondere bei Sortieraufgaben und Listenbearbeitung ergeben4cann, lassen sich dann weitere ähnliche Begriffe nicht mehr im Speicher unterbringen.

Es wurde bereits in einem anderen Zusammenhang (Patentanmeldung P 22 61 586.7) eine Speichereinrichtung mit einem assoziativen Teil (Adressenteil) und mit mehreren nicht assoziativen Speicherteilen nach Art des SpeicherieLls in Pig. 1 vorgeschlagen. Damit ergibt sich auch eine Verminderung der Gefahr der Blockierung des Speichers bei einer Häufung gleicher oder ähnlicher Begriffe. In η derartigen "Speicherbänken" lassen sich nämlich maximal η gleiche oder ähnliche Begriffe (mit gleichen Vorsilben) unterbringen. Die gleichen oder ähnlichen Begriffe stehen dann in einer Zeile, die durch die als Adresse dienende Vorsilbe ausgewählt wurde. Eine solche Maßnahme bringt indes noch keine ausreichende Lösung des Häufungsproblems.

VPA 9/210/2034 -5-

409835/040Ϊ

Der Erfindung liegt die Aufgabe zugrunde, eine Speichereinrichtung anzugeben, die nach außen hin alle Eigenschaften eines echten Assoziativspeichers aufweist, aber nur einen Bruchteil des für einen solchen benötigten Aufwands erfordert (hardware-Simulation eines echten Assoziativspeichers). Die Speichereinrichtung soll dabei so ausgebildet sein, daß auch bei dichter Belegung die Gefahr der Blockierung ihrer Aufnahmefähigkeit durch ein gehäuftes Auftreten gleicher oder ähnlicher Begriffe auf ein erträgliches Maß reduziert ist.

Ausgehend von einer Speichereinrichtung der eingangs genannten Art löst die Erfindung die Aufgabe dadurch, daß jeder Speicherbank Mittel zugeordnet sind, die die Ableitung der Adressen aus dem Assoziationsbegriff in definierter, in sich jeweils gleichbleibender, jedoch von Speicherbank zu Speicherbank unterschiedlicher Weise mit pseudo-statistischer Verteilung bewirken.

Vorteilhafte Weiterbildungen der Erfindung sind durch die Unteransprüche gekennzeichnet. Die Erfindung wird nachstehend anhand der Zeichnung näher erläutert werden.

Es zeigt darin

Pig. 1 die schon eingangs beschriebene Speichereinrichtung mit einem assoziativen Abschnitt, in den ein Teil des Assoziationsbegriffs zur Adressierung des betreffenden Speicherplatzes dient,

Pig. 2 eine schematische Darstellung zur Erklärung der Speicherplatzverteilung in der Speicheranordnung gemäß der Erfindung,

Pig. 3 eine Speichereinrichtung gemäß einer Weiterbildung der Erfindung und

Pig. 4 eine der Pig. 2 ähnliche Darstellung zur Erläuterung des "Verdrängungsverfahrens".

-6-409835/0401

Zui* Vermeidung ton Mißverständnissen ist vorab anzumerken,

daß unter dem Ausdruck "Vorsilbe" immer der zur Adressierung van Speicherplätzen im assoziativen Abschnitt verwendete Teil des Assoziat.ionsbegriffs zu verstehen ist, unabhängig davon, ob dieser Teil eine zusammenhängende Bit- " folge am Anfang, am Ende oder an einer anderen Stelle des Assoziationsbegriffs oder eine Auswahl beliebiger Bit aus dem Assoziationsbegriff ist.

Weiterhin sei für das folgende vorausgesetzt, daß Speichereinrichtung mehrere, beispielsweise acht Speicher-"bänke besitzt. Jede Speicherbank enthält wiederum eine Vielzahl von Speicherplätzen, z. B. 64 bis 256. Der Übersichtlichkeit wegen sind in der Zeichnung jeweils nur wenige Speicherplätze dargestellt.

Bei einem ersten Ausführungsbeispiel der · Speichereinrichtung gemäß der Erfindung werden zur Adressierung der Speicher- " platze für jede Speicherbank verschiedene, jedoch jeweils gleich viele Bitstellen aus dem Assoziationsbegriff verwendet. Nimmt man beispielsweise die Bereitstellung von 256 Speicherplätzen je Speicherbank an, so werden für derem. Adressierung 8 Bit benötigt. Diese 8 Bit werden dem gesamten Assoziationsbegriff, der beispielsweise 24 Bit umfassen möge, für jede Speicherbank an anderer Stelle entnommen. Die Auswahl soll möglichst regellos erfolgen. Es kann dabei auch d-ie Reihenfolge einzelner Bit vertauscht werden.

Die angegebene Art der Adressenbildung bewirkt, daß durch ei nen bestimmten Assoziationsbegriff in den verschiedenen Speicherbänken Speicherplätze mit ganz unterschiedliehen Nummern bezeichnet werden. Verbindet man die so adressier-

VPA 9/210/2034 -7-

409835/0401

ten Speicherplätze jeweils benachbarter Speicherbänke gedanklich untereinander, so entsteht eine "Vorsilbenlinie¹¹, die als unregelmäßige Zickzacklinie durch den Speicher führt. Ein anderer Assoziationsbegriff erzeugt eine andere zickzackförmige Vorsilbenlinie, die aber mit der ersten gemeinsame Punkte aufweisen kann.

Die Fig. 2 stellt zur Erläuterung dieser Verhältnisse einen Speicher mit acht Speicherbänken BjZf bis BS zu je acht Speicherplätzen 70 bis P8 dar, in den drei Vorsilbenlinien entsprechend den Vorsilben A, B und X eingezeichnet sind.

Allein schon durch die beschriebene Ableitung der Speicherplatzadressen wird die Häufungsgefahr, insbesondere bei Sortiervorgängen, schon wesentlich vermindert. Vor allem aber bietet sie eine Grundlage für die Anwendung eines wirkungsvollen Verfahrens zur Beg^iung des Häufungsproblems durch nachträgliche Korrektur der Ablageplätze. Auf dieses Verfahren soll an späterer Stelle noch näher eingegangen werden.

Eine weitere Verminderung der Häufungsgefahr (ohne die Verwendung des erwähnten Verfahrens) ergibt sich gemäß einer Weiterbildung der Erfindung durch den Einsatz spezieller Adresswandler für die Adressenbildung. An sie sind folgende Forderungen zu stellen: a) der Adresswandler soll eine Datenreduktion aus dem angebotenen Assoziationsbegriff durchführen. Er soll aus möglichst vielen Bit des Assoziationsbegriffs eine Adresse mit einer dem Adressenumfang bzw. der Anzahl der Speicherplätze einer Speicherbank entsprechenden Bitzahl bilden.

VPA 9/21/2034 -8-

409835/0401

b) Die gebildeten Adressen müssen in einem festen reproduzierbaren Zusammenhang zu dem angebotenen Assoziationsbegriff stehen.

c) Die gebildeten Adressen sollen beim Auftreten von Zählfolgen eine pseudo-statistische Verteilung aufweisen.

Die Pig. 3 zeigt schematisch eine Speichereinrichtung unter Verwendung eines Adresswandlers. Abweichend von der Darstellung in Pig. 1 ist hier der Speicher SP für die Aufnahme des ganzen Assoziationsbegriffs mit den Bit a bis h (und gegebenenfalls des zugeordneten Begriffs) ausgebildet. Dementsprechend muß auch der Vergleicher VE in der Lage sein, den Vergleich über alle Bit a bis h zu erstrecken.

Ein im Beispiel nach Pig. 3 die Bit a bis f umfassender Teil - die Vorsilbe - des Assoziationsbegriffs wird dem Eingang des Adresswandlers ADW zugeführt. Der Adresswandler formt daraus die Adresse x, y, ζ für die Ansteuerung eines bestimmten Speicherplatzes, in den - sofern er noch nicht belegt ist - beim Schreibvorgang der Assoziationsbegriff eingeschrieben wird bzw. dessen Inhalt beim Lesevorgang gelesen und dem Vergleicher VR angeboten wird, der bei Übereinstimmung mit dem vorliegenden Assoziationsbegriff ein Treffersignal auf der Leitung T abgibt. Wie schon anhand der Pig. 1 beschrieben wurde, öffnet das Treffersignal beispielsweise die Torschaltungen Ga bis Gh, so daß der gesuchte Speicherinhalt nunmehr für eine weitere Verwendung zur Verfügung steht.

Würde man für den ganzen Speicher, d. h. für alle Speicherbänke nur einen Adresswandler vorsehen, so würden alle Vorsilbenlinien geradlinig verlaufen. Da aufgrund der

VPA 9/210/2034 -9-r

409835/0401

Datenreduktion im Adresswandler auch verschiedene Vorsilben auf gleiche Adressen führen können, wurden durch die einzelnen Speicherzeilen stets mehrere gerade Vorsilbenlinien verlaufen. Aber auch in einem solchen Pail würde insbesondere beim Auftreten von Zählfolgen eine wesentliche Verringerung der Zahl der Kollisionsfälle eintreten, wenn der Adresswandler die vorher genannten Forderungen erfüllt, für deren Durchführung neben den weniger empfehlenswerten Prioritätsnetzwerken Paritätsgeneratoren, Gattertafeln und ROM-Komplexe mit statistisch verteilten Bitmustern zur Verfügung stehen. Günstiger ist es jedoch, vor allem auch im Hinblick auf das im Zusammenhang mit dem ersten Ausführungsbeispiel der Erfindung schon kurz erwähnte Verfahren zur nachträglichen Korrektur der Ablageplätze, jeder Speicherbank einen eigenen Adresswandler zuzuordnen. Selbstverständlich ist eine solche Maßnahme nur sinnvoll, wenn alle Adresswandler nach verschiedenen Übersetzüngsalgorithmen arbeiten. Es wird damit erreicht, daß Einträge von Assoziationsbegriffen mit gleicher Vorsilbe statistisch verteilt erscheinen.

Die Vorsilbenlinien, die die Speicherplätze für gleiche Vorsilben in den verschiedenen Speicherbänken verbinden, stellen nunmehr wieder unregelmäßige Zickzacklinien dar, wie dies schon in Pig. 2 gezeigt wurde. Verschiedene Vorsilben führen jetzt nicht mehr im ganzen Speicherbereich, sondern höchstens innerhalb einer Speicherbank auf die gleiche Adresse.

Grundsätzlich ist bei freien Speicherbänken die Ablage eingehender Begriffe in jeder beliebigen Speicherbank möglich. Bei teilweiser Belegung muß jedoch jeweils zunächst geprüft werden, in welchen Speicherbänken unter

VPA 9/210/2034 -10-

409835/0AO1

-io-

den von den Adresswandlern gelieferten Adressen noch, freie Äblageplätze vorhanden sind. Das ist beispielsweise auf . einfache Weise dadurch möglich, daß jedem Speicherplatz noch eine Bitstelle zugeordnet wird, in der ein Belegt-' Bit gesetzt wird, wenn und solange der Speicherplatz belegt ist. Bei jedem Aufruf der Speicherplätze zum Zweck eines Neueintrags, bei dem alle Speicherbänke von den zugehörigen Adresswandlern angesteuert werden, wird das Vorhandensein bzw. Fehlen der Belegt-Bit überprüft. Dabei erhält man eine Liste von Speicherbänkeni die für- den einzuschreibenden Begriff noch zugänglich sind. Aus diesen kann an sich eine beliebige Speicherbank ausgewählt werden.

In der Praxis muß jedoch eine Auswahlvorrichtung benutzt werden, welche die Speicherbankauswahl nach bestimmten Algorithmen festlegt. Hierbei kommt ein zyklisch umlaufender Verteiler, die prioritive Verteilung in Richtung niederwertiger Speieherbanknummern und die statistische Verteilung infrage.

Der zyklisch umlaufende Verteiler füllt alle Speicherbänke annähernd gleichmäßig auf, desgleichen ein statistischer Verteilungsmechanismus. Die prioritive Verteilung, die voraussichtlich vorzuziehendst, fördert dagegen eine Konzentration in Richtung der niederwertigen Speicherbänke, wenn der Speicherbank 0 die höchste Priorität zukommt. Das heißt also, daß die Speicherbänke mit den niedrigsten Nummern zuerst voll werden, die weiteren Speicherbänke mit abnehmender Dichte gefüllt werden und die Speicherbänke mit den höchsten Nummern zunächst ganz frei bleiben.

Die bisher beschriebenen, gemäß der Erfindung vorgeschlagenen Maßnahmen verringern die Gefahr der Blockierung des Speichers durch Käufungskollisionen ganz wesentlich.

VPA 9/210/2034 -11-

409835/0401

Ihr besonderer Vorteil wird vor allem dann sichtbar, wenn die in den Speicher einzutragenden Begriffe insgesamt oder gruppenweise einer gewissen Systematik unterliegen, beispielsweise also Zählfolgen darstellen.

Trotzdem läßt sich weder durch eine pseudo-statistische Auswahl von Bitstellen aus dem Assoziationsbegriff zur Adressenbildung gemäß dem ersten Ausführungsbeispiel der Erfindung noch durch Bereitstellung spezieller Adresswandler die Häufungsgefahr völlig beseitigen. Aufgrund der Tatsache, daß auch verschiedene Vorsilben auf gleiche Adressen führen können, kann es in ungünstigen Fällen vorkommen, daß alle vorhandenen Speicherbänke unter einer bestimmten Adresse bereits gefüllt sind, obgleich erst wenige Einträge von Begriffen mit gleicher Vorsilbe erfolgten und im Speicher insgesamt noch viele Speicherplätze frei sind.

Wenn auch eine Blockierung des Speichers für den Eintrag von Begriffen mit einer bestimmten Vorsilbe unter den angegebenen Voraussetzungen nur mit geringer Wahrscheinlichkeit eintritt ., steigt die Blockierungsgefahr naturgemäß mit zunehmender Füllung des Speichers. Eine Möglichkeit zur Abhilfe besteht in der nachträglichen Korrektur der Ablageplätze. In Verbindung mit der Fig. 4 soll dieses Verfahren an einem Beispiel im folgenden näher erklärt werden.

Unabhängig von der angewandten Methode zur Auswahl der Speicherbänke für Neueinträge, die immer nur aufgrund statistischer Überlegungen festgelegt werden kann, kann sich im Einzelfall ein Eintrag auf einem bestimmten

VPA 9/210/2034 -12-

409835/0401

-12-Speicherplatz nachträglich als unzweckmäßig erweisen.

In dem Speicher nach Pig. 4 mit den Speicherbänken bis B8 und den Speicherplätzen Έ0 bis P8 je Speicherbank sind zwei Vorsilbenlinien, die Α-Linie und die D-Linie eingezeichnet. Kleine Kreise in den von diesen Vorsilbenlinien berührten Speicherplätzen bedeuten freie Plätze, während die Eintragungen von Doppelbuchstaben belegte Speicherplätze kennzeichnen. Datei bedeuten ijrt-e~~in~S!-ig--.^44 der erste Buchstabe die Vorsilbe und der zweite Buchstabe die Restsilbe der eingeschriebenen Begriffe.

Nach der der Pig. 4 zugrundeliegenden Annahme sind alle _e auf der Vorsilbenlinie D liegenden Speicherplätze bereits besetzt, aber nur teilweise durch Einträge mit der Vorsilbe D. Die übrigen Speicherplätze enthalten Begriffe mit anderen Vorsilben. Diese Begriffe sollen im folgenden als "artfremde Begriffe" bezeichnet werden. Die Existenz solcher artfremder Begriffe ist dadurch bedingt, daß praktisch jeder Speicherplatz ein Schnitt- oder Berührungspunkt verschiedener Vorsilbenlinien ist. Es ist daher zu beachten, daß die Bezeichnung artfremd nur in bezug auf die gerade interessierende Vorsilbenlinie, hier die Vorsilbenlinie D, keineswegs aber im Hinblick auf die diesen Begriffen eigenen Vorsilbenlinien gilt.

Soll nun ein weiterer Begriff mit der Vorsilbe D, beispielsweise der Begriff DV in den Speicher eingeschrieben werden, so findet sich zunächst auf der Vorsilbenlinie und somit im Speicher für ihn kein Platz mehr. Gemäß einer Weiterbildung der Erfindung wird einer der in bezug auf die Vorsilbenlinie D artfremden Begriffe aus dem VPA 9/210/2034 -13-

A09835/0401

Speicher entfernt und in einem Hilfsregister HR aufbewahrt. In den so freigemachten Speicherplatz wird der zur Eintragung anstehende Begriff DV eingeschrieben.

Für den im Beispiel nach Pig. 4 verdrängten und im Hilfsspeicher HR zwischengespeicherten Begriff AC muß nun ein neuer Platz auf der Vorsilbenlinie A gesucht werden. Ein solcher findet sich mit dem Speicherplatz P2 in der Speicherbank B5, der bisher noch frei war. Der Begriff AC wird vom Hilfsregister auf diesen Speicherplatz übernommen.

Da die Möglichkeit besteht, daß für den zuerst verdrängten Begriff ein freier Speicherplatz zunächst nicht zu finden ist un<J&aher gegebenenfalls mehrere Verdrängungszyklen aufeinanderfolgen müssen, ist es notwendig, zwei Hilfsregister zur Zwischenspeicherung verdrängter Begriffe vorzusehen bzw. das Hilfsregister für die Aufnahme von zwei Begriffen auszulegen.

Sofern auf einer Vorsilbenlinie mehrere artfremde Begriffe vorhanden sind, die für eine Verdrängung infrage kommen, kann beispielsweise die Auswahl des für die Verdrängung bestimmten Begriffs nach einer der schon erwähnten Regeln für die Auswahl einer Speicherbank für Neueinträge erfolgen. Vorteilhafter ist es jedoch, vor einer Verdrängung die Vorsilbenlinien aller verdrängbaren artfremden Begriffe auf freie Speicherplätze, etwa mit Hilfe der ebenfalls schon erwähnten Belegt-Bit, zu überprüfen. Es ist leicht einzusehen, daß auf diese Weise mit höherer Wahrscheinlichkeit sofort freie Speicherplätze zu finden sind, die einen verdrängten Inhalt aufnehmen können. Mehrfache Verdrängungszyklen werden dann kaum mehr erforderlich werden, es sei denn, daß der Speicher schon einen sehr hohen Püllungsgrad erreicht hat.

VPA 9/210/2034 -14-

409835/0401

Bei dem beschriebenen Verdrängungsverfahren oder Verfahren zur nachträglichen Korrektur der Ablageplätze gelten somit folgende Grundsätze:

a) von einer angewählten Vorsilbenlinie können nur artfremde Begriffe verdrängt werden,

b) die Verdrängung darf nur entlang der Vorsilbenlinie des zu verdrängenden Eintrags erfolgen,

c) auf einer Vorsilbenlinie können nicht mehr Einträge vorgenommen werden, als Speicher blanke vorhanden sind.

Die zuletzt genannte Einschränkung könnte zu der Annahme verleiten, daß die Speichereinrichtung gemäß der Erfindung keine Vorteile gegenüber der in der Patentanmeldung P 22 61 586.7 vorgeschlagenen Anordnung bietet. Das trifft jedoch nicht zu, was sich am einfachsten durch einen Vergleich mit der Ausfuhrungsform mit -^.dresswandlern erkennen läßt.

Es sei einmal angenommen, daß die Assoziationsbegriffe jeweils 24 Bit umfassen und daß jede Speicherbank 256 Speicherplätze enthält. Die Adressen für die Bestimmung der Speicherplätze müssen dann aus 8 Bit bestehen. Da nun gemäß dem älteren Vorschlag Vorsilben und Adressen identisch sind, ergeben sich maximal 2 gleiche Vorsilben. Nimmt man nun weiter an, daß die gemäß der Erfindung eingesetzten Adresswandler eine Eingangsbreite von 16 Bit besitzen, so umfaßt auch der Vorsilbenbereich 16 Bit. Demnach führen

maximal nur noch 2 Assoziatio'nsbegriffe zu gleichen Vorsilben. Zwar ergeben sich gleiche Adressen auch auch verschiedenen Vorsilben, doch ist diese Übereinstimmung jeweils nur auf eine Speicherbank beschränkt und für die endgültige Belegung einer Vorsilbenlinie sind nur gleiche

VPA 9/210/2034 -15-

409835/0401

Yorsilben maßgebend. Die statistische Wahrscheinlichkeit für eine vollständige Belegung einer Yorsilbenlinie und damit für eine Blockierung der Aufnahmefähigkeit des Speichers durch eine Häufung wird somit um den Paktor 256 verkleinert.

4 Figuren

10 Patentansprüche.

VPA 9/210/2034 -16-

409835/0401

Claims (10)

1. -16-Patenta η sprüche

   ί1 / Speichereinrichtung mit mehreren, eine Vielzahl von Speicherplätzen umfassenden Speicherbänken, die jeweils in einen durch einen Teil (Vorsilbe) des Assoziationsbegriffs adressierbaren assoziativen Abschnitt, dessen Inhalt mit dem Assoziationsbegriff oder mit einem maskierbaren Teil desselben verglichen wird, um Auskunft über das Vorhandensein eines Begriffs zu erhalten, und in einen nicht assoziativen Abschnitt zur Aufnahme eines beigeordneten Begriffs gegeliedert sind, dadurch gekennzeichnet, daß jeder Speicherbank Mittel zugeordnet sind, die die Ableitung der Adressen aus dem Assoziationsbegriff in definierter, in sich jeweils gleichbleibender, jedoch von Speicherbank zu Speicherbank unterschiedlicher Weise mit pseudo-statistischer Verteilung bewirken.
2. 2. Speichereinrichtung nach Anspruch !,dadurch ge kennzeichnet, daß zur Adressierung der Speicherplätze für jede Speicherbank gleich viele, aber unterschiedliche Bitstellen des Assoziationsbegriffs verwendet werden.
3. 3· Speicherbank nach Anspruch 1 oder 2, dadurch gekennze lehne t, daß jeder Speicherbank ein Adress· iwandler zugeordnet ist, der eine Adresse mit einer dem Adressenumfang der Speicherbank entsprechenden Bitstellenzahl aus einer höheren Bitstellenzahl des Assoziationsbegriffs bildet.
4. 4» Speichereinrichtung nach Anspruch 3, dadurch gekennzei ohne t, daß die zur Adressen-

   VPA 9/210/2034 -17-

   40983 5/0401

   bildung verwendeten Ubersetzungsalgorithmen in jedem Adrees wandler verschieden sind.
5. 5. Speichereinrichtung nach einem der Ansprüche 1 bis 4, dadurch gekennzeichnet, daß für einen Neueintrag unter den Speicherbänken, die unter den jeweils gebildeten Adressen noch freie Speicherplätze aufweisen, die Speicherbank mit der (relativ) niedrigsten Nummer ausgewählt wird.
6. 6. Speichereinrichtung nach einem der Ansprüche 1 bis 4, dadurch gekennzeichnet, daß die Auswahl einer bestimmten Speicherbank für einen Neueintrag unter den Speicherbänken, die unter den jeweils gebildeten Adressen noch freie Speicherplätze aufweisen, durch einen zyklisch umlaufenden Verteiler erfolgt.
7. 7. Speichereinrichtung nach einem der Ansprüche 1 bis 4, dadurch gekennzeichnet, daß die Auswahl einer bestimmten Speicherbank für einen Neueintrag unter den Speicherbänken, die unter den jeweils gebildeten Adressen noch freie Speicherplätze aufweisen, nach einer statistischen Verteilung erfolgt.
8. 8. Verfahren zur Beseitigung einer Häufungskollision bei der Eingabe in die Speichereinrichtung nach einem der vorhergehenden Ansprüche, insbesondere nach Anspruch 2 oder 4, die sich ergibt, wenn ein neuer Begriff gemäß seiner Vorsilbe in einem bereits durch einen Begriff mit anderer Vorsilbe (artfremder Begriff) besetzten Speicherplatz abgelegt werden soll, dadurch g e kemnzeichne t, daß der artfremde Begriff entfernt wird und einen seiner eigenen Vorsilbe ent-

   VPA 9/210/2034 -18-

   409835/0401

   sprechenden Speicherplatz in einer anderen Speicherbank zugewiesen erhält und daß der neue Begriff in den freigemachten Speicherplatz eingeschrieben wird»
9. 9. Verfahren nach Anspruch 8,dadurch gekennzeichnet, daß die Vorsilbenlinien aller auf der

   Vorsilbenlinie des men einzutragenden Begriffs vorhandenen artfremden Einträge auf freie Speicherplätze überprüf twerden und solange solche zu finden sind, nur diejenigen artfremden Einträge verdrängt werden, für die auf den eig enen Vorsilbenlinien freie Speicherplätze vorhanden sind.
10. 10. Speichereinrichtung zur Durchführung 'des Verfahrens

    nach Anspruch 8, dadurch gekennzeichnet, daß dem Assoziationsspeicher mindestens ein Hilfsregister zur Aufnahme eines Assoziationsbegriffs sowie gegebenenfalls eines beigeordneten Begriffs zugeordnet ist.

    VPA 9/210/2034

    40983 5/0401