DE2630323A1

DE2630323A1 - Datenspeichereinrichtung

Info

Publication number: DE2630323A1
Application number: DE19762630323
Authority: DE
Inventors: Peter Leo Lawrence Desyllas; John Austin Jones; Brian John Procter
Original assignee: Fujitsu Services Ltd
Current assignee: Fujitsu Services Ltd
Priority date: 1975-07-09
Filing date: 1976-07-06
Publication date: 1977-02-03
Also published as: FR2317731A1; SE416500B; AU497095B2; US4086629A; CS222228B2; SE7607814L; FR2317731B1; JPS5651429B2; DE2630323B2; GB1515376A; NL181150C; ZA763978B; AU1557076A; DE2630323C3; HU175243B; JPS5210639A; NL7607479A; NL181150B

Description

INTERNATIONAL COMPUTERS LIMITED, ICL House, Putney, London SoW. 15, England

Datenspeichereinrichtung

Die Erfindung bezieht sich auf Datenspeichereinrichtungen, insbesondere Datenspeichereinrichtungen mit einem Hauptspeicher, einem HilfsSpeicher geringerer Größe, jedoch höherer Zugriffszeit als der Hauptspeicher, wobei Datenausdrücke im Hilfsspeicher in Abhängigkeit von einem Satz von Speicherzugriffsbefehlen zugänglich sind, und einer Vorausschaulogik, zum Einführen von Datenausdrücken aus dem Hauptspeicher in den Hilfsspeicher, bevor sie benötigt werden.

Für einen gegebenen Datenspeicher stehen sich im allgemeinen hohe Zugriffsgeschwindigkeit und hohe Speicherkapazität unvereinbar gegenüber. Dies bedeutet, daß die räumlichen Abstände, die die Signale zu durchlaufen haben, umso größer werden und somit die Zugriffsgeschwindigkeit umso langsamer wird, je größer ein Datenspeicher wird. Hochgeschwindigkeitsspeichereinrichtungen sind im allgemeinen wesentlich teuerer und aufwendiger als Niedriggeschwindigkeitseinrichtungen, und es ist deshalb oft unwirtschaftlich, eine große Datenverarbeitungsanlage nur unter Verwendung von Hochgeschwindigkeitsspeichern auszulegen.

609885/0784

Konto: Bayerische Vereinsoani: (BLZ 750 2OQ 73) 5 804248 Postscheckkonto München 893 63 - 801

Gerichtsstand Regensburg

263Π3

2.7.1976 W/He - 2 - I/p 8590

Eine Möglichkeit,um diese Schwierigkeit zu umgehen, ist die Verwendung eines hierarchischen Speichersystems. Derartige Systeme sind beispielsweise im Aufsatz von CJ. Conti in Computer Group News, März 1969, Seite 9 unter dem Titel "Concepts for Buffer Storage" beschrieben.

Grundsätzlich weist ein hierarchisches Speichersystem einen großen, verhältnismäßig langsam arbeitenden Hauptspeicher und einen kleineren, aber rascher arbeitenden Hilfsspeicher(der manchmal als Pufferspeicher bezeichnet wird) auf. Wenn ein Speicherzugriff aufgerufen wird, wird dies zuerst im Hilfsspeicher versucht, und nur dann, wenn dies nicht erfolgreich ist (d.h. wenn der zugegriffene Datenausdruck im Hilfsspeicher nicht vorhanden ist) wird der Zugriff aus dem Hauptspeicher vorgenommen. Auf diese Weise wird die effektive mittlere Zugriffszeit für das System im allgemeinen kleiner als die des Hauptspeichers und wird im Idealfall gleich der des Hilfsspeichers.

Die Leistungsfähigkeit eines solchen Systems hängt von dem Algorithmus ab, der zum Fortschreiben des Hilfsspeichers verwendet wird. Ein leistungsfähiger Algorithmus gewährleistet, daß der Hilfsspeicher nur mit Daten gefüllt ist, die eine hohe Wahrscheinlich besitzen, daß sie in kürzerer Zeit zugegriffen werden.

Allgemein besteht das Grundprinzip der Algorithmen für das Fortschreiben des Hilfsspeichers darin, daß Datenausdrücke, die aus dem Hauptspeicher zugegriffen werden, in den Hilfsspeicher eingeschrieben werden, da kurz vorher zugegriffene Ausdrücke im allgemeinen eine hohe Wahrscheinlich bieten, daß sie wieder benötigt werden. Darüber hinaus können Daten im Hauptspeicher in Blöcken angeordnet sein; wenn Daten in einem bestimmten Block zugegriffen werden, kann der ganze Block in den Hilfsspeicher eingeführt werden, da eine hohe Wahrscheinlichkeit dafür besteht, daß andere Daten in diesem Block

60988 5/078 4

ORIGINAL INSPECTED

2.7.1976 W/He - 3 - I/p 8590

ebenfalls innerhalb kürzerer Zeit benötigt werden.

Es wurde auch bereits vorgeschlagen, Datenblöcke vorab abzurufen, bevor sie benötigt werden, u. zwar wie folgt: Wenn Daten häufig aus dem Block N zugegriffen werden, ist eine hohe Wahrscheinlichkeit gegeben, daß der Block N + 1 in naher Zukunft benötigt wird. Deshalb wird Block U + 1 aus dem Hauptspeicher vorab abgerufen und in den Hilfsspeicher eingeführt. Diese Technik ist jedoch verhältnismäßig unwirksam, da sie eine große Anzahl von unnötigen Abrufungen ergibt.

Ziel vorliegender Erfindung ist eine Speichereinrichtung, bei der Daten vorab abgerufen werden, wobei jedoch die Anzahl von nicht notwendigen Vorabrufungen reduziert werden kann.

Gemäß der Erfindung weist eine Speichereinrichtung einen Hauptspeicher und einen Hilfsspeicher geringerer Größe, jedoch rascherer Zugriffszeit als der Hauptspeicher auf; Datenausdrücke im Hilfsspeicher sind in Abhängigkeit von einem Satz von Spexcherzugrif fssystemen zugänglich, und es ist eine Vorausschau— logik zum Einführen von Datenausdrücken aus dem Hauptspeicher in den HilfsSpeicher vorgesehen, bevor sie erforderlich werden, wobei die Vorausschaulogik nur im Hinblick auf eine Untergruppe der Speicherzugriffsbefehle betätigt werden kann.

Die Einrichtung weist zwei Klassen von Speicherzugriffsbefehlen auf, deren einer eine Vorausschauwirkung ergibt, und deren anderer nicht. Befehle der ersteren Klasse sollen nur in Fällen verwendet werden, in denen es wahrscheinlich ist, daß der gerade zugegriffene Datenausdruck einen Teil einer Folge bildet (z.B. zum Zugriff von Instruktionen, die üblicherweise sequentiell gespeichert sind). Somit versetzt die Einrichtung den Programmierer in die Lage, zu spezifizieren, ob eine Vorausschauwirkung erforderlich ist oder nicht, und dies ist von großem Wert für die Verringerung der Anzahl von nicht erforderlichen Vorauss ch a uz uπrif f svo rgang en.

60988 5/0784

ORIGINAL INSPECTED

2.7.1976 W/He - 4 - I/p 8590

Vorzugsweise ist gewährleistet, daß der vorab aufgerufene Datenausdruck im Hilfsspeicher vorhanden ist, indem zuerst geprüft wird, ob er bereits im Hilfsspeicher vorhanden ist, und, wenn dies nicht der Fall ist, er aus dem Hauptspeicher abgerufen und in den Hilf sspeicher eingeführt wird. Dies vermeidet einen Zeitverlust beim Abrufen von Datenausdrücken, die bereits imHilfsspeicher vorhanden sind.

Ferner wird mit vorliegender Erfindung eine Einrichtung vorgeschlagen, die Datenausdrücke vorab abrufen kann, welche einen Teil einer Folge bilden, in der es nicht von vorneherein bekannt ist, in welcher Richtung die Folge wahrscheinlich enthalten ist (d.h., ob es eine Folge aufsteigender oder absteigender Adressen ist).

In weiterer Ausgestaltung der Erfindung weist eine Datenspeichereinrichtung einen Hauptspeicher, einen Hilfsspeicher kleinerer Größe, jedoch rascherer Zugriffszeit als der Hauptsspeicher, und eine Vorausschaulogik zum Einführen von Datenausdrücken aus dem Hauptspeicher in den Hilfsspeicher, bevor sie notwendig werden, auf, wobei die Vorausschaulogik die Richtung einer möglichen Folge von Datenausdrücken, einschließlich eines Ausdruckes, das aus dem Speicher zugegriffen wird, gewährleistet und eine Vorausschauwirkung in dieser Richtung ergibt, so daß sichergestellt ist, daß ein nachfolgender Datenausdruck dieser möglichen Folge in den Hilfsspeicher eingeführt wird.

Die Richtung der möglichen Folge der Datenausdrücke kann dadurch festgelegt werden, daß geprüft wird, ob ein Ausdruck oder eine Gruppe von Ausdrücken eine Adresse aufweist, die in einer ersten Richtung gegenüber der des gerade zugegriffenen Ausdruckes im Hilfsspeicher vorhanden ist; ist dies nicht der Fall, kann angenommen werden, daß die Folge in dieser ersten Richtung verläuft, während dann, wenn der Ausdruck vorhanden ist, die Folge als in der entgegengesetzten Richtung verlaufend angenommen wird.

609885/0784

2.7.1976 W/He - 5 - I/p 8590

Die Datenausdrücke sind vorzugsweise im Hauptspeicher in Gruppen (z.B. Wortpaaren) angeordnet, und wenn die Vorausschaulogik sicherstellt, daß ein Datenausdruck im Hilfsspeieher vorhanden ist, stellt sie auch sicher, daß der oder jeder andere Ausdruck in der gleichen Gruppe im Hilfsspeicher vorhanden ist.

Nachstehend wird die Erfindung in Verbindung mit derZeichnung anhand eines Ausführungsbeispieles erläutert. Die Figuren zeigen:

Fig. 1 ein Blockschaltbild des gesamten Datenverarbeitungssystems,

Fig. 2 eine Speicherzugriffseinheit, die einen Teil des Datenverarbextungssystems bildet,

Fig. 3 eine Schaltung der Vorausschaulogik, und Fig. 4 eine Folgesteuerschaltung«

Nach Fig. 1 weist das Datenverarbeitungssystem einen Hauptspeicher 10, eine mikroprogrammierte Verarbeitungseinheit 11, einen Scheduler 12 und eine Speicherzugriffseinheit (SAU) 13 auf.

Der Hauptspeicher 10 hält verschiedene Arten von Daten einschließlich Instruktionen zur Ausführung von Operanden und Deskriptoren durch das System. Typischerweise besitzt der Speicher eine Kapa-

in
zität der Größenordnung von 256 K Wörtern und eine Zugriffszeit von etwa 840 NanoSekunden. Der Speicherzugriffspfad 14 besitzt eine Breite von zwei Wörtern, was bedeutet, daß jeder Zugriff ein Paar von Wörtern aus dem Speicher rückführt.

Die SAU wirkb als eine Zwischeneinrichtung zwischen der Verarbeitungseinheit 11 und dem Scheduler 12 einerseits und dem Hauptspeicher 10 andererseits, in-dem Speicherzugriffsbefehle aus der Verarbeitungseinheit und dem Scheduler aufgenommen und sie in der entsprechenden Weise gewartet werden, wobei je nach Erforderiis-, ein Lese- oder Schreibzugriff zum Hauptspeicher vorgenommen

609885/0784" "

2.7.1376 W/He - 6 - I/p. 8590

wird. Diese Befehle können echte oder virtuelle Adressen enthalten, und die SAU enthält einen Adressenumsetzer zur Umwandlung virtueller Adressen in echte Adressen, v/o dies erforderlich ist.

Ferner enthält die SAU einen Datenhilfsspeicher. Dien ist ein kleiner, schneller Speicher, der virtuell adressierte Daten hält, die wahrscheinlich in Kürze für einen Zugriff benötigt werden.

Das Grundprinzip der Arbeitsweise des Hilfsspeichers besteht darin, daß ein in den Hauptspeicher durch einen virtuell adressierten Befehl eingeschrj ebener Datenausdruck auch in den Hilfsspeicher eingeschrieben wird, und in ähnlicher Weise ein Ausdruck, der von einem virtuell adressierten Befehl aus dem Hauptspeicher ausgelesen wird, in den Hilfsspeieher kopiert wird. Dieses Prinzip kann für bestimmte Befehle modifiziert werden, der generelle Effekt besteht jedoch darin, daß vor kurzem zugegriffene Ausdrücke im Hilfsspeicher zur Verfügung stehen. Im Falle eines nachfolgenden Lesebefehles können sie somit automatisch aus dem Hilfsspeicher ohne die Verzögerung, die durch einen Hauptspeicherzugriff auftritt, zugegriffen v/erden.

Bestimmte virtuell adressierte Lesebefehle zeigen der SAU an, daß der laufende Zugriff wahrscheinlich eine aus einer Folge von fortlaufenden Adressen ist. Die SAU behandelt diese Befehle so, daß zuerst das adressierte Wort in der normalen Weise aus dem Hilfsspeicher (falls es dort vorhanden ist) oder derr. Hauptspeicher zugegriffen wird und daß dann gewährleistet wird, daß der Hilfsspeicher mit dem nächsten Paar von Wörtern in der möglichen Folge (als das Vorausschau-Wortpaar bezeichnet) gefüllt v/ird. Zu diesem Zweck wird ein Test durchgeführt, um zu bestimmen, ob das Vorausschau-Wortpaar bereits im Hilfsspeicher vorhanden ist; wenn dies nicht der Fall ist, wird dieses Wortpaar aus dem Hauptspeicher geholt und in den Hilfsspeicher eingeführte Dies v/ird als Vorausschaufunktion bezeichnet. Im Falle einiger

609885AO784

BAD ORIGINAL

2.7.1976 W/He - 7 - I/_P 8590

Befehle weist die Vorausschaufunktion eine Entscheidung in bezug auf die wahrschein] iche Richtungder Folge auf.

Die grundlegende Funktion des Schedulers besteht darin, Instruktionen zur Ausführung durch die Verarbeitungseinheit vorher abzurufen, ehe sie benötigt werden, indem Lesebefehle in die SAU eingegeben werden. Der Scheduler decodiert auch jede Instruktion, während die -.vorausgehende Instruktion gerade durchgeführt wire¹, und gibt auf Anfrage einen Satz von Parametern, die die Aufgaben definieren, welche durch die Verarbeitungseinheit durchgeführt werden sollen, um die Ausführung der Instruktion zu vervollständigen, in die Verarbeitungseinheit. Eine Instruktion wird normalerweise in zwei Aufgaben (in Ausnahmen eine oder drei) durchgeführt, und die Parameter, die in die Verarbeitungseinheit für jede Aufgabe eingeführt werden, v/eisen normalerweise eine Mikroprogrammstartadresse, eine Aufgabenlä-ngenanzeigevorrichtung, eine Kopie der Instruktion und andere Kennzeicheneinstellungs- und Schleifenzählinformation auf.

Sprunginstruktionen werden durch das Mikroprogramm in der Verarbeitungseinheit in gleicher Weise wie andere Instruktionen bewertet, wenn jedoch eine Änderung der Folge angezeigt wird, beginnt das Mikroprogramm mit dem Abrufen der Sprungbestimmungsinstruktion, bevor die Ausführung der laufenden Instruktion abgeschlossen ist. Alle vorher vorabgerufenen Instruktionen im Scheduler werden beseitigt.

Die Verarbeitungseinheit ist eine mikroprogrammierte Universaleinheit mit einem Arbeitsspeicher mit 256 Wörtern mit einer¹ Zykluszeit von 125 Nanosekunden, einem Stapelspeicher mit 32 Wörtern mit einer Zykluszeit von 62,5 Nanosekunden und einem Mikroprogrammspeicher, der 8-16K Wörter hält. Mikroprogramminstrufctionen werden normalerweise mit der Geschwindigkeit von einer Instruktion., je 125 Nanosekunden ausgeführt, die Zeit- . steuerung kann jedoch aufgehalten werden, damit eine Synchronisierung anderer Einhei-fmöglich ist (insbesondere, um auf Daten

609885/07Ö4

2.7.1976 W/He - 8 - I/p 8590

aus der SAU zu warten).
Speicherzuqriffseinheit (SAU)

In Fig. 2 nimmt die SAU bei jedem Speicherzugriffsbefehl aus dem

Scheduler oder der Verarbeitungseinheit eine Adresse von 30 Bits

über einen Multiplexer 20 auf. Die ersten 28 Bits (0-27) dieser Adresse können als die Adresse eines bestimmten, aus vier Wörtern

bestehenden Abschnittes des Speichers betrachtet v/erden, während

Bit 28 ein Wortpaar in diesem Abschnitt auswählt und Bit 29 ein Wort des ausgewählten Paares spezifiziert.

Diese Adresse wird in ein Adressenregister 21 übernommen, dessen Bits mit ADO bis AD29 in der Reihenfolge abnehmender Bedeutung bezeichnet sind.

Der Inhalt des Adressenregisters wird einer Adressenumsetzungseinheit (ATU) 22 aufgegeben, die virtuelle Adressen in entsprechende echte Adressen umwandelt, und sie dem Hauptspeicher aufgibt. Zu diesem Zweck enthält die ATU eine Anzahl von laufenden Seitenregistern, die die echten Basisadressen von Seiten halten, die gerade von dem System verwendet werden, wobei eine Seite als ein Teil mit 256 Worten des virtuellen Speichers festgelegt wird. Um somit eine virt^uelle Adresse in eine echte Adresse umzuwandeln, wird zuerst das entsprechende laufende Seitenregister ausgewählt und dann die in diesem Register enthaltene Basisadresse einem Verschiebungsteil der virtuellen Adresse hinzugefügt. Wenn die erforderliche Basisadresse in Wirklichkeit nicht in einem der laufenden Seitenregister vorhanden ist, wird ein Unterbrechungssyignal in die Verarbeitungseinheit gegeben und leitet eine Mikroprogrammfolge zum Fortschalten der laufenden Seitenregister ein.

Fig. 2 zeigt auch den Daten-hilfsspeicher 23 der SAU. Der Hilfsspeicher ist ein Speicher mit direktem Zugriff, der eine Zugriffszeit von 45 Nanosekunden besitzt und der insgesamt 256 Wörter

609885/0784

2.7.1976 W/He - 9 - I/p 8590

hält, die in 64 Zellen mit jeweils vier Wörtern unterteilt sind. Zu einem bestimmten Zeitpunkt ist jede aktive Zelle einem bestimmten Abschnitt aus vier Wörtern des virtuellen Speichers zugeordnet und einzelne beliebige, alle oder keine dieser Wörter können gültige Daten enthalten. Jedem Wort im Hilfsspeicher ist deshalb ein Gültigkeitsbit zugeordnet, damit angezeigt wird, ob es gültige Daten enthält. Jede aktive Zelle enthält auch die virtuelle Adresse des Abschnittes mit vier Wörtern des virtuellen Speichers, dem sie zugeordnet ist.

Wenn die SAU einen virtuell adressierten Befehl aufnimmt, wird eine Kontrolladresse mit fünf Bits in einer Kontrollcodierschaltung 24 aus ausgewählten Bits der virtuellen Adresse im Adressenregister 21 gebildet, und zwar wie folgt:

Kontrollbit Ableitung

0 ADO

1 (AD24) = (ADl2)

2 (AD25) Ξ (ADl3)

3 AD26

4 AD27

wobei das Symbol = die Äquivalenz der beiden Bits bezeichnet.

Diese Kontrolladresse wird dem Adresseneingang des Hilfsspeichers aufgegeben, so daß ein Paar von Zellen ausgewählt wird. Dann wird ein Vergleich zwischen der virtuellen Adresse, die in jeder dieser Zellen gespeichert ist, und den Inhalten des Adressenregisters vorgenommen. Wird für eine dieser Stellen eine Übereinstimmung festgestellt, wird eine Prüfung durchgeführt, ob das adressierte Wort in dieser Zelle gültig ist. Wenn dies der Fall ist, wird die gewünschte Fortsehreibung oder der Lesezugriff zu dem Wort vorgenommen, ist das Wort nicht gültig, wird ein erforderlicher Hauptspeicherzugriff zur Korrektur vorgenommen. Wenn andererseits keine Zelle des Paares den Inhalten des Adressenregisters ent-

609885/0784

2.7.1976 W/He - 10 - I/p 8a59O

spricht, wird die Zelle des zuletzt verwendeten Paares ausgewählt und der neuen virtuellen Adresse wieder zugeordnet= Diese Zelle wird dann in der erforderlichen Weise fortgeschrieben, indem ein Zugriff zum Hauptspeicher vorgenommen wird.

Da der Zugriffspfad zum Hauptspeicher eine Breite von zwei Wörtern besitzt, wird immer dann, wenn ein Wort aus dem Hauptspeicher zugegriffen wird, das andere Wort des Paares auch in die SAU zurückgeführt und in den Hilfsspeicher eingeschrieben.

Es wird jedoch nur das adressierte Wort des Paares in die Verarbeitungseinheit oder den Scheduler zurückgeführt.

Jede Zelle im Hilfsspeicher enthält auch Kennzeichen, die angeben, ob die Daten in dieser Zelle zum Lesen, Schreiben oder zum Durc-hführen einer Instruktion oder einer Kombination dieser Vorgänge zur Verfügung stehen. Diese Kennseichen werden in die entsprechenden Zustände gesetzt, wenn die Zelle zugeteilt wird, und werden für Zugriffszulassungsprüfungen verwendet, wenn die Zelle zugegriffen wird·

Der Hilfsspeicher erzeugt auch zwei Ausgangssignale AWPV und OWPV zur Verwendung bei der Vorausschau—Aktion. AXtfPV (adressiertes Wortpaar gültig) ist "echt", wenn beide Wörter des adressierten Wortpaares (d.h. das Wortipaar, das das adressierte Wort enthält} gültig sind, während OWPV (anderes Wortpaar gültig) "echt" ist, wenn beide Wörter des anderen Paares inder gleichen Zelle gültig sind.

SAU-Punktionen

Die SAU kann eine Vielzahl von Funktionen in Abhängigkeit von Speicherzugriffsbefehlen aus dem Scheduler oder der Verarbeitungseinheit ausführen.

609885/0784

2.7.1976 W/He - 11 - Ι/ρ. 8590

Jede dieser Funktionen beginnt mit einer Folge von Arbeitsvorgängen, die als die Anfangszugriffsfolge bezeichnet ist, in welcher das durch das Adressenregister 21 spezifizierte Wort zum Auslesen oder Fortschreiben zugegriffen und in den Scheduler und/oder die Verarbeitungseinheit zurückgeführt wird. An diese Folge können sich in manchen Fällen ein oder mehrere weitere Folgen zur Durchführung der Vorausschaufunktion anschließen.

Xm Falle eines Befehls aus der Verarbeitungseinheit wird die spezielle Funktion, die durchgeführt werden soll, durch einen Funktionscode mit fünf Bits in dem Befehl spezifiziert. Einige dieser Funktionen können eine Vorausschaufunktion enthalten, während andere eine solche Funktion nicht enthalten.

Zwei Beispiele für Funktionen, die keine Vorausschaufunktion enthalten, sind folgende:

RV Virtuelles Auslesen. Dies ist die Grundfunktion zum Auslesen eines Wortes aus dem virtuellen Speicher. Das Wort wird aus dem Hilfsspeicher oder aus dem Hauptspeicher ausgelesen, wie oben beschrieben. Es wird eine Auslesezugriffszulässigkeitsprüfung durchgeführt und das Wort wird, wenn diese Prüfung erfolgreich ist, in die Verarbeitungseinheit geführt.

RJ Auslesesprungbestimmung. Diese Funktion wird zur Einleitung einer Änderung der Instruktionsfolge verwendet. Die Funktion bewirkt, daß ein Wort aus dem virt/^uellen Speicher wie in RV ausgelesen wird. Es wird eine Ausführungszugriffzulässigkeitsprüfung durchgeführt und das Wort, wenn diese Prüfung erfolgreich ist, sowohl der Verarbeitungseinheit als auch dem Scheduler als die Sprungbestimmungsinstruktion zugeführt. Die virtuelle Adresse des Wortes wird in den Scheduler als die Sprungadresse eingeführt.

609885/0784

2.7.1976 W/He - 12 - Ι/ρ 8590

Eine vollständige Liste von ilicht-Vorausschau-Punktionen ist nicht aufgeführt, da sie für das Verständnis der Erfindung nicht wesentlich ist. Es sei jedoch darauf hingewiesen, daß andere solche Funktionen Schreibfunktionen wie auch Lesefunktionen enthalten, und einige dieser Funktionen eine echte Adressierung anstelle einer virtuellen Adressierung umfassen.

nachstehend werden die Funktionen angegeben, die durch die Verarbeitungseinheit erzeugt werden und die zu einer Vorausschau führen.

RVLl Virtuelles Auslesen mit Vorausschau (ein Wort). Diese Funktion dient zum Auslesen eines Ausdruckes einer Folge von Einzelwortausdrücken, die wahrscheinlich an benachbarten Adressen auftreten, von denen jedoch nicht bekannt ist, ob sie in aufsteigender oder absteigender Folge vorliegen. Dies ist ähnlich der RV-Funktion, kann jedoch eine Vorausschaufunktion enthalten, die weiter unten beschrieben wird. .

RVL2 Virtuelles Auslesen mit Vorausschau (Doppelwort). Diese Funktion dient zum Auslesen des höher adressierten Wortes eines Ausdruckes einer Folge von Doppelwortausdrücken, die an aufeinanderfolgenden Adressen vorhanden sind (in absteigender oder aufsteigender Reihenfolge). Dies ist ähnlich RVLI, jedoch mit einer unterschiedlichen Vorausschauaktion.

RVM Virtuelles Auslesen, Mehrfachwort. Diese Funktion dient zur Verwendung dort, wo eine Folge von Lesezugriffen in einer aufsteigenden Reihe von fortschreitenden Adressen vorgenommen werden. Grundsätzlich ist diese Funktion ähnlich RV, enthält jedoch eine Vorausschau.

RVMF Virtuelles Lesen, Mehrfachwort, zuerst. Diese Funktion dient zum Vorbereiten des Datenhilfsspeichers für eine Folge

60988 5/0784

2.7.1976 W/He - 13 - I/p 8590

von RVM-Funktionen. Grundsätzlich ist diese Funktion die gleiche wie RVM,mit der Ausnahme, daß sie eine doppelte Vorausschau-Funktion darstellt.

RJL Lesesprungbestimmung mit Vorausschau. Diese ist grundsätzlich die gleiche wie RJ, kann jedoch eine Vorausschau enthalten.

Im Falle eines Speicherzugriffsbefehles aus dem Scheduler in SAU wird die folgende Funktion durchgeführt:

RVLS Virtuelles Lesen mit Vorausschau; Scheduler. Diese Funktion wird von dem Scheduler verwendet, um Instruktionen zur Ausführung vorab zu rufen. Sie kann nicht durch die Verarbeitungseinheit

vji rd
erzeugt werden. Ein Wort aus dem virtuellen Speicher ausgelesen, wie in RV, in diesem Fall jedoch wird eine Ausführungszugriffszulässigkeitsprüfung durchgeführt. Ist die Prüfung erfolgreich, wird das Wort in den Scheduler zurückgeführt. Daran kann sich eine Vorausschau-Funktion anschließen.

Die VorausSchau-Funktion kann deshalb nur durch sechs unterschiedliche Funktionen angerufen werden, von denen fünf aus der Verarbeitungseinheit und eine aus dem Scheduler kommen.

In allen Fällen umfaßt die Vorausschau-Funktiorveinen Test, um zu bestimmen, ob das Vorausschau-Wortpaar (d.h. das nächstmögliche Wortpaar in der Folge) im Hilfsspeicher vorhanden ist. Ist es dort nicht vorhanden, wird dieses Wortpaar aus dem Hauptspeicher abgerufen und in den Hilfesspeicher eingeführt. Im Frlle von RWIF wird das nächste, mögliche Wortpaar wieder geprüft und abgerufen, falls dies erforderlich ist.

Die Funktionen RVM und RVMF werden, wie oben erwähnt, verwendet, um Folgen von Daten bei aufsteigenden Adressen auszulesen, während die Funktionen RJL und RVLS verwendeb werden, um Instruktionen auszulesen, von denen angenommen wird, daß sie in aufsteigender Folge gespeichert sind» Deshalb, erfolgt die Vorausschau-Funktion für diese vier Funktionen stets in der Vorwärtsrichtung. 609885/0784

Die Funktionen RVLl und RVL2 andererseits dienen zum Auslesen von Folgen, bei denen nicht bekannt ist, ob die Adressen aufsteigend oder absteigend sind« Die Vorausschau für diese Funktionen schließt deshalb eine Entscheidung mit ei-';, nut der die wahrscheinliche Richtung der Folge festgelegt wird. Die erste Vorausschau einer Folge kann auf diese Weise in der falschen Richtung erfolgen und somit umsonst sein, anschließende Zugriffe haben jedoch dann die korrekte Vorausschau.

Wenn einmal eine Vorausschaufunktion festgelegt worden ist, erhält sie eine höhere Priorität als eine neue Funktionsanfrage.

Vorausschaulogik

Nach Fig. 2 weist die SAU eine logische Vorausschauschaltune auf, die die Vorausschaufunktion steuert. Diese Schaltung steuert die Arbeitsweise einer Adcierschaltung 27, die die acht Bits AD22-2S geringster Bedeutung des Adressenregisters um O, +2, -2, +4 oder -4 anheben kann, so daß die Adresse des Vorausschauwortpaares erzeugt wird. Die erhöhte Adresse kann in das Adressenregister über den Multiplexer 20 eingeschrieben werden. Wenn ein Überlauf aus dieser Addition eintritt, der anzeigt, daß die Grenze einer 256 Worte umfassenden Seite gekreuzt worden ist, wird die Vorausschaufunktion aufgehoben. Somit kann keine Vorausschau an den Grenzen von Seiten erfolgen.

In Fig. 3 weist die logische Vorausschauschaltung drei Verriegelungen (bistabile Schaltungen) 30-32 und einen Satz von UND-Gliedern 40-5 3 auf.

Die logische Schaltung nimmt Eingangssignale RVLl, RVL2, RVH, RVMF, RJL und RVLS während der anfänglichen Zugriffsfolgen dieser Funktionen auf und kann eines von fünf Zuwachssignalen 0, +2, -2, +4, und -4 ezeugen_o Diese Zuwachssignale v/erden der Addierschaltung 2 7 (FIg. 2) aufgegeben, so daß die Adresse im Adressenregister um den entsprechenden Betrag erhöht wird.

609885/0784

BAD ORIGINAL

2.7.1976 W/He - 15 - I/p 8590

Am Ende einer jeden Aufangszugriffsfolge werden die Zustände der Verriegelungen 30, 31 geprüft. Wenn die Verriegelung 30 gesetzt wiri, wird eine weitere Folge, die als DOLA (Vorausschauerü-Folge bezeichnet wird, eingeführt, während dann, wenn die Verriegelung 31 gesetzt wire, eine Folge, die als TRYLA (Versuch einer Vorausschau)-Folge bezeichnet wird, eingeführt wird. Am Ende einer jeden TRYLA-FoIge werden die Verriegelungen 31 wieder geprüft, und wenn die Verriegelung30 gesetzt ist, wird eine DOLA-Folge eingeleitet, während dann, wenn die Verriegelung 31 gesetzt wird, eine andere TRYLA-FoIge eingeleitet wird« Am Ende einer jeden DOLA-Folge wird die Verriegelung 31 geprüft und, wenn sie gesetzt wird, wird eine TRYLA-FoIge eingeleitet.

Die Verriegelung 30 wird während einer jeden anfänglichen- Zugriffsfolge und einer TRYLA-FoIge getaktet. Die Verriegelung 31 wird normalerweise nur während der anfänglichen Zugriffsfolge getaktet, wird jedoch im Falle einer RVMF-Funktion auch während der DOLA- und TRYLA-FoIgen getaktet. Die Verriegelung 32 wird nur während der TRYLA-Folgen getaktet.

Die Arbeitsweise der Vorausschaulogik ist grundsätzlich folgende: Während der Anfangszugriffsfolge wird, wenn die Logik feststellt, daß das Vorausschau-Wortpaar im gleichen Vier-Wort-Abschnitt des Speichers wie das laufend, adressierte Wort ist, das entsprechende Wortpaar im Hilfsspeicher auf Gültigkeit geprüft.

Wenn das Wortpaar nicht gültig ist (d.h. eines oder beide Wörter nicht gültig sind) , wird ein Signal der Verriegelung 30 aufgegeben, das bewirkt, daß die Verklinkung gesetzt wird, wenn sie getaktet ist. Eine DOLA-Folge schließt sich somit an.

In der DOLA-Folge wird die erhöhte Adresse aus der Addierschaltung 27 (die die Adresse des Vorausschau-Wortpaares darstellt) in das Adressenregister 21 getaktet, und es wird dann ein Hauptspeicherzugriff vorgenommen, um das Vqrausschau-Wortpaar abzurufen

609885/0784
BADOFlIGiNAL

2.7.1976 W/He - 16 - I/n 8590

und es in den Hilfsspeicher einzuführen. Andererseits wird während der Anfangszugriffsfolge, wenn die Logik feststellt, daß das Vorausschau-Wortpaar in einem anderen Vier-Wort-Abschnitt des Speichers in Hinblick auf das laufend adressierte Wort vorhanden ist, ein Signal der Verriegelung 31 aufgegeben, das bewirkt, daß die Verriegelung gesetzt wird, wenn sie getaktet ist. Deshalb schließt sich eine TRYLA-Folge an.

In der TRYLA-Folge wird die Adresse des Vorausschau-Wortpaares in das Adressenregister getaktet, so daß die entsprechende Zelle des Hilfsspeichers adressiert wird. Gleichzeitig wird ein Signal einem Eingang des UND-Gatters Λ0 aufgegeben. Wenn das adressierte Wortpaar im Hilfsspeicher nicht gültig ist (d.h.AWFV = 0), wird dieses Gatter wirksam gemacht, wodurch ein NULL-Zuwachεsignal erzeugt und eine Eingabe der Verriegelung 30 aufgegeben wird, wodurch die Verriegelung gesetzt wird, wenn sie getaktet ist. Es schließt sich deshalb eine DOLA-Folge an, damit das Vorausschau-Wortpaar abgerufen wird, wie vorstehend beschrieben«

Es ergibt sich somit, daß die Vorausschau-Logik stets prüft, ob das Vorausschau-Wortpaar im HilfsSpeicher vorhanden ist; ist es nicht vorhanden, wird eine DOLA-Folge eingeleitet, damit das V/ortpaar aus dem Hauptspeicher abgerufen wird. Wenn das Vorausschau-Wortpaar im gleichen Vier-Wort-Abschnitt wie das anfänglich adressierte Wort sich befindet, kann die Prüfung unmittelbar vorgenommen v/erden, da der Zugriff zur entsprechenden Zelle des Hilfsspeichers bereits erfolgt. Wenn andererseits das Vorausschau-Wortpaar in einem anderen Vier-Wort-Abschnitt vorhanden ist, kann die Prüfung nicht unmittelbar vorgenommen werden, so daß eine TRYLA-Folge eingeleitet wird, in der ein Zugriff _zur entsprechenden Zelle des Hilfsspeichers vorgenommen wird. Die einzige Ausnahme hierbei ist die RVMF-Funktion, wie weiter unten noch erläutert wird.

609885/0784

2.7.19 76 W/He - 17 - I/p 3590

Die Arbeitsweise der Vorausschaulogik wird nachstehend im einzelnen für jede Vorausschaufunktion der Reihe nach in Verbindung mit Fig. 3 beschrieben. Zweckmäßig er v/ei se werden die vier Wörter in der Zelle, die während der Anfangszugriffsfolge adressiert werden, als Wörter O bis 3 bezeichnet, während die Wörter in den Zellen, die den beiden aufeinanderfolgenden Abschnitten des virtuellen Speichers zugeordnet sind, als Wörter -4 bis -1 und 4-7 bezeichnet sind.

Für diese Funktion ist keine Vorausschau notwendig, wenn das adressierte Wort 0 oder 2 ist, da das nächste Wort in der (aufsteigend angenommenen) Folge bereits im Hilfsspeicher vorhanden ist.

Wenn das Wort 1 adressiert wird (d.h. AD28=O, AD29=1), und wenn das Wortpaar 2, 3 nicht gültig ist (d.h. OWPV=O), wird das UND-Glied 41 wirksam gemacht. Dies erzeugt ein +2 Signal und setzt auch die Verriegelung 30. Somit wird eine DOLA-Folge eingeleitet, in der das Adressenregister um +2 erhöht wird und auf Wort 3 hinweist. Das .Wortpaar 2, 3 wird auf diese Weise aus dem Hauptspeicher abgerufen.

Wenn das Wort 3 adressiert wird, wird das UND-Gatter 49 wirksam gemacht, es wird +2 erzeugt und die Verriegelung 31 gesetzt. Auf diese Weise wird eine TRYLA-Folge eingeleitet, in der das Adressenregister um +2 erhöht wird, so daß es auf Wort 5 weist (d.h. das zweite Wort in der nächsten Zelle). Wenn das Wortpaar 4, 5 nicht gültig ist, wird das UND-Glied 40 wirksam gemacht unddie Verriegelung 30 eingestellt. Somit wird eine DOLA-Folge eingeleitet, damit dieses Wortpaar aus dem Hauptspeicher abgerufen wird.

609885/0784

2ο7.1976 W/He - 18 - I/r 8590

Diese Vorgänge werden nachstehend in einer Tabelle zusammengestellt:

AD 28, 29 OWt-V Glied Erhöhung Folge

1 G 41 +2 DCLA

3 _49 +2 TRYLA

Wie vorstehend erwähnt, wird diese Funktion verwendet, wenn nicht bekannt ist, ob die Folge von Adressen aufsteigend oder absteigend ist. Eine Prüfung ist deshalb in diese Funktion eingeschlossen, um die wahrscheinliche Richtung der Folge auf der Basis der verfügbaren Evidenz zu bestimmen. Wenn beispielsweise das Wort 0 adressiert ist und das Wortpaar 2, 3 gültig ist, wird angenommen, daß die Folge absteigend ist, während dann, wenndas Wortpaar 2, 3 nicht gültig ist, die Folge als aufsteigend angenommen wird.

Die Vorausschau dieser Funktion wird in der folgenden Tabelle zu s ammeng ef aß t:

AD 28, 29	OWPV	Glied	Erhöhung	Folge
0	1	46	-2	TRYLA
1	0	41	+2	DOLA
2	0	44	-2	DOLA
3	1	48	+ 2	TRYLA
RVL2

Diese Funktion umfaßt eine Prüfung in bezug auf die wahrscheinliche Richtung der Folge. Die Prüfung trägt der Tatsache Rechnung, daß das Anfangs adressierte Wort als das höher adressierte Wort eines Doppelwortausdruckes angenommen wird.

609885/0784

2.7.1976 W/He

I/p 8590

Die folgende Tabelle zeigt die Vorausschau dieser Funktion:

AD 28, 29	OWFV	Glied	Erhöhung	Folge
0	0	42	+ 2	DOLA
0	1	53	-4	TRYLA
1	0	42	+ 2	DOLA
1	1	47		TRYLA
r_	-	50	+ 2	TRYLA
	0	4 5		DOLA
3	1	48	+ 2	TRYLA
RVLS

Da diese Funktion sich nur mit aufsteigenden Folgen befaßt, ist keine Vorausschau notwendig, wenn das Wort 0 oder 2 adresc-ijffrert wird.

Die- Vorausschau-Funktion ist folgende:

AD 28, 29

OWPV Glied

Erhöhung

Folge

41

+ 2

DOLA

45

+ 2

TRYLA

Diese Funktion leitet stets eine TRYLA-Folge ein, wobei die Adresse um +4 erhöht wird.

RVMF

Diese Funktion macht das UND-Glied 52 wirksam und ergibt eine TRYLA-Folge, wobei die Adresse um +2 erhöht wird. Während der TRYLA-FoIge wird die Verriegelung,„getaktet und damit gesetzt,

609885/0784

2c7.1976 W/He - 20 - I/p 8590

so daß RVMFl nunmehr "echt" ist.

Während der TRYLA-Folge wird, wenn das adressierte Wortpaar (d.h. das V/ortpaar an der erhöhten Adresse) nicht gültig ist, das UND-

wird
Glied 40 wirksam gemacht, und es/exne DOLA-Folge eingeleitet, um dieses V/ortpaar abzurufen. Während der DOLA-Folge wird das UfJD-Glied 51 wirksam gemacht und dies egibt eine zweite TRYLA-Folge, wobei die Adresse weiter um +2 erhöht wird. Andererseits wird, wenn das adressierte Wortpaar während der ersten TRYLA-Folge gültig ist, das UND-Glied 51 wirksam gemacht, und die zweite TRYLA-Folge beginnt unmittelbar anschließend daran, ohne daß eine DOLA-Folge zwischengeschaltet wird.

Während der zweiten TRYLA-Folge wird, wenn das adressierte Wortpaar (d.h. das Wortpaar an der zweifach erhöhten Adresse) nicht gültig ist, das UND-Gatter wirksam gemacht, wodurch eine DOLA-Folge eingeleitet wird, um dieses Wortpaar abzurufen.

Die Verriegelung wird wieder während dieser zweiten TRYLA-Folge getaktet, und die Verriegelung 32 wird rückgesetzt, da RVMF nun in "falsch" umgewandelt worden ist.

Zusammenfassend ergibt sich, daß die RVMF-Funktion gewährleistet, daß zwei Vorausschau-Wortpaare im Hilfsspeicher vorhanden sind. Wenn beispielsweise der Anfangszugriff bei Wort 2 erfolgt, prüft die Vorausschau, ob die Wortpaare 4, 5 und 6, 7 ebenfalls vorhanden sind, und wenn eines von beiden nicht vorhanden ist, wird dieses Paar aus dem Hauptspeicher abgerufen.

Folgesteuerlogik

In Fig. 4 ist die Folgesteuerlogxk zur Steuerung der verschiedenen Folgen, die von der SAU durchgeführt werden, gezeigt.

Drei Schieberegister 51-5 3 sind zur Steuerung der Anfangszugriffsfolge, der DOLA-Folge und der TRYLA-Folgen vorgesehen. Wenn eine

609885/07 84

2.7„IS76 W/He - 21 - Ι/ρ 8590

dieser Folgen angefordert wird, wird eine binäre "1" in das linke Ende des entsprechenden Registers eingeführt, und diese "1" wird dann längs des rechten Endes des Registers getaktet, indejm eine Serie von Steuersignalen für die SAU erzeugt wErden. Wenn die "1" das rechte Ende des Registers erreicht hat, leitet sie eine Prüfung ein, um festzulegen, welche Folge als nächste eingeleitet wird, und zwar wie folgt:

Am Ende einer Anfangszugriffsfolge wird, wenn die Verriegelung 30 gesetzt ist, das UND-Glied 64 wirksam gemacht und bewirkt, daß eine "1" in das linke Ende des DOLA-Registers 52 eingeführt wird und somit eine DOLA-Folge eingeleitet wird· Wenn andererseits die Klinke 31 gesetzt wird, wird das UND-Glied 61 wirksam gemacht und bewirkt, daß eine "1" in das TRYLA-Register 5 3 eingeführt und somit eine TRYLA-Folge eingeleitet wird.

Am Ende einer DOLA-Folge wird, wenn die Verriegelung 31 gesetzt ist, das UND-Glied 63 v/irksam gemacht, und damit eine TRYLA-Folge eingeleitet»

Am Ende einer TRYLA-Folge wird, wenn die Verriegelung 30 gesetzt ist, das UND-Glied 65 wirksam gemacht, so daß eine DOLA-Folge eingeleitet wird, wahrend dann, wenn die Verriegelung 31 gesetzt ist, das UND-Glied 62 wirksam gemacht und damit eine TRYLA-Folge eingeleitet wird.

Wenn alle Folgen abgeschlossen sind, kann eine neue Funktion eingeleitet werden, indem eine "1" in das linke Ende des Registers 51 eingeführt wird, so daß eine neue Anfangszugriffsfolge gestartet wird.

609885/0784

Claims

2.7ol976 W/He - 22 - l/p 8590

Patentansprüche:

Datenspeichereiririchtung mit einem Hauptspeicher, einem Hilf f. speicher geringerer Größe, jectoch höherer Zugriffszeit sir, der Hauptspeicher, wobei Datenausdrücke irr; KiIfsspeicher in Abhängigkeit von einem Satz von Sreicherzugriffsbefehlen zugänglich sind, und einer Vorausschaulogik, zum Einführen von Dateriausdrücken aus dem Hauptspeicher in den Hilf sspeicher, bevor sie ber-cti gt v/erden, dadurch gekennzeichnet₇ daß die Vorausschaulogik (26) nur in bezug auf eine Untergruppe der Speieherzugriffsbefehle wirksam ist.

2. Datenspeichereinrichtung mit einem Hauptspeicher, einem Hilfsspeicher geringerer Größe, jedoch höherer Zugriffszeit als der Hauptspeicher, und einer Vorausschaulogik zum Einführen von Datenausdrücken aus dem Hauptspeicher in den Hilfsspeicher, bevor sie benötigt werden, dadurch gekennzeichnet, daß die Vorausschaulogik (26) so arbeitet, daß sie die Richtung einer möglichen Folge von Datenausdrücken einschließlich eines Ausdruckes, der gerade aus den Speichern (10, 23) zugegriffen wird, gewährleistet und eine Vorausschauwirkung in dieser Richtung durchführt, so daß sichergestellt ist, daß ein nachfolgender Datenausdruck dieser möglichen Folge in denHilfsspeicher (23) eingeführt wird.

3. Datenspeichereinrichtung nach Anspruch 2, dadurch gekennzeichnet, daß die Richtung der möglichen Folge dadurch festgestellt wird, daß geprüft wird, ob ein Ausdruck, der in einer ersten Richtung gegenüber dem laufend zugegriffenen Ausdruck verschoben ist, im Hilfsspeicher (23) vorhanden ist, und daß dann, wenn dies nicht der Fall ist, die Folge in der ersten Richtung angenommen wird, während dann, wenn sie vorhanden ist,

die Folge in der entg%engesetzten Richtung angenommen wird»

4. Einrichtung nach einem der Ansprüche 1-3, dadurch gekennzeichnet, daß die Vorausschaulogik (26)"so ausgelegt ist, daß ein Datenausdruck aus dem Hauptspeicher (10) in den Hilfsspeicher (23) nur dann eingeführt wird, wenn er nicht bereits im Hilfsspeicher (23) vorhanden ist. _609885/0784

BAD ORIGINAL

Leerseite