(PICTURE)(PICTURE) (PICTURE)Europäi _hes Patentamt
_ (PICTURE) EuroPean Patent offi_e
(PICTURE) Offi_e euroPeen des brevets _ PubIication number . O 3_9 81 _ B1
_ EUROPEA_ PATE_T SPECIFICATlO_
_ Date oF pubI_i_t_ion oF patent spec_ircat_ion .. _ lnt. _l.6 .. _O6F _2JO8
22.__.9_ Bulletin 9_l4l
_ APPlication number . 899o4922._
_ Date of filing . 3o.o3.89
_ lnternationaI appIication number .
PCTIUS89lO_3_4
_ International Publication number .
WO 89lO9444 O_._O.89 Ga_ette 89l24
(PICTURE)
(PICTURE)_ cAcHE wlrH Ar LEAsr rwo FlLL slzEs.
_ NOte . Within nine mOnthS ffOm the pUbliCatiOn Of the mentiOn Of the gfant Of the EUfOpean patent, any
penon may give notice to the European Patent Office of opposition to the European patent granted.
_w Notice oF _pp_sition shaII be rIed in a wri_en reasoned statement. lt shaII not be _eemed to have been
fled until the opposition fee has been paid (Art. 99(1) European patent convention).
(PICTURE)Jouve, 18, rue Saint-Denis, 75OO1 PARIS
1 EP O 3_9 8__ B_ 2
Des_ription plays an important role in optimizing computer oper-
ation. CPU operations are performed with virtual ad-
Field of the Invention dresses. Ifthe computersystem uses a virtually map-
(PICTURE) ped cache it becomes advantageous to couple the
The present invention relates to the field ofdigital _ cache directlytothe CPU. Anytranslation fromvirtual
computers and theirarchitecture. More particularly, it to physical addresses which needs to occur can be
relates to the filling of cache memories used in such accomplished downstream from the cache.
computers. For a number of reasons, such as when a new
program is run, the virtual to physical address trans-
Background of the Invention 1o lation map of a virtually mapped cache changes.
(PICTURE) When this occurs, the cache must be flushed
Modern computer systems require memory de- (cleared) and replaced with a new map.
vices with widely varying performance characteris- After the cache is flushed, it is refilled with new
tics. A memory unit capable of extremely rapid infor- data and instructions. In the prior art, after the cache
mation retrieval and transmission is often required to 1_ was flushed, it was refilled at the same rate that data
supply some modern central Processing units or instructions were fed to the cache when a given
(CPUs) with instructions and data for their operation. program was being run for a long period of time. Ca-
Such memories are available, usually in the form of ches work most efficiently when completely full as
Random Access Memories (RAMs), and are com- fewer attempts to find data or instructions in the
monly called 'cache' memories. These caches are _o cache result in misses that require a search of main
generally small, on the orderofa few thousand bytes, memory. Consequently, when the cache was refilled
in ordertoallowthe rapid retrieval ofdata. Since there at a constant rate after flushing, numerous ''misses''
are few complete programs ordata bases that can be requiring reference to and response from the main
stored in memories of that size, computer systems memory occurred, resulting in inefficient cache utili-
also incorporate memories with larger capacities, but __ zation. On the other hand, if the cache is continually
slower access and retrieval times. These memories refilled or refreshed at a very high rate, other prob-
can include larger RAMs with slowerretrieval speeds, lems occur, such as writing over data or instructions
bubble memories, disc memories ofvarious types and which are still current and useful.
other memories. It is an object ofthis invention to provide a mech-
A commonly used method to optimize computer 3o anism whereby the cache can be filled at at least two
operations is to couple a cache memorydirectlytothe different rates, a fast rate being used immediately af-
CPU and another, larger, memory unit to both the ter the cache has been cleared and a slower rate be-
cache memory and the CPU. In this manner the ing used once the cache has been almost completely
cache can supply the CPU with the instructions and refilled.
data needed immediately ata ratewhich will allow un- 3_
impeded CPU operation. The main memory usually Summary of the Invention
supplies refill data to the cache, keeping it full. If an (PICTURE)
instruction or a required piece of data is not in the This and other objects are achieved in the pres-
cache when the CPU requires it, it can be obtained ent invention which provides methods as claimed in
from the main memory, at the expense of the extra 4o claims 1 , 2 and 3.
time that this requires. Other embodiments of the methods according to
A problem which arises with caches which use present invention are claimed in claims 4 to 1 O.
virtual memory mapping occurs when the cache is An apparatus according to the present invention
cleared or flushed. is claimed in claim 11 . Other embodiments ofthis ap-
A memory can be mapped in at least two ways. 4_ paratus are claimed in claims 12 and 13.
The first is physical mapping where instructions refer
to the actual physical address where the required Brief Description of the Drawings
data is stored. The second way is virtual mapping. (PICTURE)
Here, the instruction refers to a virtual address which FIG. 1 shows the structure ofa data block stored
must be translated in some fashion toobtain the phys- _o in a cache; and
ical address where the data is stored. Virtual mapping FIG. 2 is a block diagram of a computer system
allows better main memory utilization and is Particu- which utilizes a virtually mapped cache.
Iarly useful in multiprogramming environments as the
memory can be allocated without contiguous parti- Detailed Description
tions between the users. Both physically and virtually __ (PICTURE)
mapped caches are currently being used in computer Referring to FIG. 1 , caches generally store infor-
design. mation in blocks of data. Each block, here numbered
The physical location of the cache memory also respectively 1 O, 2O, 3O, 4O, and 5O, contains a valid
2
3 EP O 3_9 8__ B_ 4
bit, a tag field, a Process Identification (PID) field and group ifthe ''missed'' blockfalls within that group. For
a data field. example, if block 2 was found to be invalid, blocks O
The valid bit is used to determine if the informa- to 3 would be fetched.
tion contained in the block is valid. When the cache A second embodiment of this invention relies on
is flushed, all valid bits in each of the data blocks are _ both the PID number and the valid bit and is particu-
set to O, indicating invalid data and allowing the pres- larly useful in a multi-user computer system where a
ent contents of the block to be written over. As new number ofdifferent programs or processes are run at
valid data is supplied to each block the valid bit is nearly the same time. Each PID represents a unique
turned on, indicating that the data contained therein numberwhioh refers to one ofat leastthirty-two proc-
is valid and usable. 1o esses or programs which are running at nearly the
In a multiusercomputer environment each user's same time on a single CPU. In this embodiment, the
program is allowed to run fora certain amountoftime, valid bit is checked after every miss. If the valid bit is
whereupon another program is run. For reasons off, the situation is considered identical to that descri-
which will be discussed later, it is useful to identify bed in the first embodiment -- the area of the cache
each program being run with a unique PID number. In 1_ is empty, and an N block refill occurs. If the valid bit
the present invention a six bit field is used for the PID is on, a second comparison is made, this time be-
number, allowing at least sixty-three different proc- tween the PID ofthe process being run and thatofthe
esses to be tracked. particular block being read. Ifthe two numbers do not
The data field is where the data stored in each match, the program being run is different from that
block is actually located. _o which most recently controlled the CPU and the data
Referring now to FIG. 2, cache 1 OO is virtually or instructions contained in the block are not useful.
mapped and coupled to CPU 12O. Cache 1 OO can be Hence, the miss is refilled with N blocks in this in-
a translation buffer, for example, that caches virtual stance also. Only ifthevalid bit is on and the PID num-
to physical translations. Main memory 16O is coupled bers match is the miss refilled with one block. This
to both cache 1 OO and CPU 12O, as well as a plurality __ avoids writing over data which may still be useful to
of inputloutput devices, not shown. As stated before, the process being run.
virtually mapped caches must be flushed every time A further embodiment stores the address of the
the virtual to physical mapping changes. One in- last miss. When a second miss occurs, the locations
stance of when this occurs is when one running pro- of the two misses are compared. If they occurred in
gram is changed for another in the CPU. 3o the same aligned group of blocks, for example, at
The present invention optimizes the refilling of blocks 2 and 3, it is assumed that the program being
the virtual cache through hardware in the following run has moved to a new area, requiring new data and
manner. In the following description, we assume that instructions, and the miss is refilled with N blocks.
there has been a cache miss, in otherwords, a failure This condition is in addition to those described in the
to find desired data or instructions in the cache. Gen- 3_ previous embodiment.
erally this occurs when the address tag being used for A still further embodiment provides a miss coun-
the search refers to a particular block, but the block ter. Once again, if the valid bit is off andlor the PID
contains different data or invalid data. numbers do not match, the miss is refilled with N
Whenever a miss occurs, a first embodiment of blocks. In addition, the miss counter keeps trackofall
the invention checks to see ifthe valid bit is offor on. 4o the read misses that occur even when the valid bit is
If it is off, it means that no data has been written to on and the PID numbers match. Ifthis count exceeds
this block since the last flush and that therefore the a pre-determined threshold, each miss is refilled with
cache should be refilled at a fast rate equal to N N blocks. In this case it is assumed that the program
blocks at a time. If the valid bit is on, the cache is re- being run has reached some transition andjumped to
filled with one block, based on the assumption that 4_ a new region, requiring a change of the data and in-
useful data already exists and it would waste time to structions. As soon as a hit occurs, the counter is re-
write over useful data. set to zero. With this embodiment, it is alternatively
The principle of spatial locality, which has been contemplated to decrement the counter upon each
discovered to operate in computer environments, hit. Onlywhen the counterdecreases below a second
states that when a given block ofdata or instructions _o pre-determined threshold will a miss be refilled with
is needed, it is very likely that contiguous blocks of one block.
data or instructions will also be required. In all of the A further embodiment examines which block in
discussed embodiments, the number of blocks N is an aligned group ofblocks is being read. As in the last
equal to four. Therefore, four blocks which are natur- two described embodiments, if the valid bit is off
allyaligned toone anotherare used to refill the cache. __ andlor if the PID numbers do not match, misses are
In the embodiments, the blocks are chosen in even refilled with N blocks. Even if the valid bit is on and
naturally aligned group offour blocks; more precisely, the PID numbers match, if the block being examined
block numbers O to 3, 4 to 7, etc. are fetched as a is the first block in the aligned group of blocks, the
3
5 EP O 3_9 8__ B_ 6
miss is refilled with N blocks. This decision is based (_ filling the cache with data blocks at the first
upon the traffic patterns ofcertain programs and data rate ifthe process identification numbers are
sets. other than the same; and
(g) filling the cache with at least one data
_ block at a second rate if the process identifi-
Claims cation numbers are the same, with the at least
one data block including the requested infor-
_. A method of filling a cache in a computer, the mation,
method comprising the steps of. wherein the first rate is fasterthan the second
(a) searching the cache for requested infor- 1o rate.
mation;
(b) generating a miss signal if the requested 3. A method offilling a cache in a computerwith in-
information is absent from the cache; formation; the method comprising the steps of.
(c) determining a status ofa valid bit ofa data a) searching a data block in the cache that
block in the cache that should contain the re- 1_ should contain the requested information and
quested information if a miss signal is gener- generating a miss signal if the requested in-
ated according tostep (b), said valid bit having formation is absent from the cache;
a status indicative of an invalidity condition if (b) storing a count of the miss signals gener-
no data has been written to this block since ated at step (a);
the last flush; _o (c) determining a status of a valid bit of the
(d) filling the cache with data blocks at a first data block which was searched, said valid bit
rate ifthe valid bit has a status indicative ofan having a status indicative ofan invalidity con-
invalidity condition, with the data blocks in- dition if no data has been written to this block
cluding the data block that contains the re- since the last flush;
quested information; and __ (d) filling the cache with data blocks at a first
(e) filling the cache with at least one data rate ifthe valid bit has a status indicative ofan
block at a second rate ifthe valid bit has a sta- invalidity condition, with the data blocks in-
tus indicative of a validity condition, with the cluding a data blockthatcontains the request-
at least one data block including the request- ed information;
ed information, 3o (e) comparing the count of miss signals to a
wherein the first rate is fasterthan the second first threshold number of misses;
rate. (_ filling the cache with data blocks at the first
rate ifthe countofmiss signals exceeds afirst
2. A method offilling a cache in a computerwith in- predetermined number;
formation, the method comprising the steps of. 3_ (g) writing at least one data block to the cache
(a) searching the cache for requested infor- at a second rate ifthe count of miss signals is
mation; less than or equal to the first threshold num-
(b) generating a miss signal if the requested ber and the valid bit has a status that is indi-
information is absent from the cache; cative ofa validity condition, with the first rate
(c) determining a status ofa valid bit ofa data 4o being faster than the second rate and the at
block in the cache that should contain the re- least one data block including the requested
quested information, ifa miss signal is gener- information; and
ated according to step (b) and the requested (h) decrementing the count of miss signals
information is absentfrom the cache, said val- each time a search for a data block results in
id bit having a status indicative ofan invalidity 4_ a hit, and continuing filling the cachewith data
condition if no data has been written to this blocks at the first rate until the count of miss
block since the last flush; signals is below a second predetermined
(d) filling the cache with data blocks at a first number.
rate ifthe valid bit has a status indicative ofan
invalidity condition, with the data blocks in- _o 4. The method of claim 1 , further comprising the
cluding a data blockthat contains the request- step of comparing a process identification num-
ed information; ber of the data block in the cache where request-
(e) if the valid bit has a status indicative of a ed information should be located with a process
validity condition comparing a process identi- identification number of a process being run by
fication number of the data block where the __ the computer, with the cache being filled at the
requested information should be located with second rate ifthe two process identification num-
a process identification number of a process bers are the same.
being run by the computer; 4
7 EP O 3_9 8__ B_ 8
_. The method of claims 1 , 2 or 3, wherein the first during a specified time interval if the valid bit is
rate fills the cache at a rate of 4 data blocks per not on, the N data blocks including a data block
a predetermined time period and the second rate containing the requested information; and
fills the cache at a rate of 1 data block perthe pre- meansforfilling the cachewith P data blocks dur-
determined time period. _ ing said specified time interval if the valid bit is
on, where P is less than N, the P blocks including
6. The method ofclaims 1 , 2 or3 furthercomprising a data block containing the requested informa-
the steps of. tion.
storing a location of a miss when searching the
cache results in the miss signal being generated; 1o _2. The apparatus of claim 11 , further comprising
comparing the stored miss location with a loca- means for comparing a process identification
tion of a next occurring miss; and number of the data block with a process identifi-
filling the cache with data blocks at a first rate if cation numberofa process being run by the com-
the stored miss location is a first block in a group puter, wherein the means forfilling fills the cache
of blocks that are aligned, as determined by the 1_ with different sized blocks based upon the com-
stored miss location with a location of a next oc- parison of the process identification numbers by
curring miss. the means for comparing.
l. The method of claim 3, further comprising the _3. The apparatus of claim 11 , wherein the cache is
step of comparing a process identification num- _o a translation buffer.
ber of the data block which was searched with a
process identification number ofa process being
run by the computer, with the second rate being Patentansprü_he
used to fill the cache if the two process identifi-
cation numbers are the same. __ _. Verfahren zum Auffüllen eines Caches in einem
Computer, wobei das Verfahren folgende Schrit-
8. The method ofclaims 1 , 2 or3 furthercomprising te aufweist.
the steps of. a) Absuchen des Caches nach den angefor-
storing a location ofthe miss when searching the derten Informationen;
cache results in a miss signal being generated; 3o b) Erzeugung eines Fehlversuch-Signals,
comparing the stored miss location with a loca- wenn die angeforderten Informationen sich
tion of a next occurring miss; and nicht im Cache befinden;
filling the cache with data blocks at the first rate c) Ermitteln des Status eines gültigen Bits ei-
ifthe stored miss location and the next occurring nes Datenblocks im Cache, der die angefor-
miss location are within a predetermined number 3_ derten Informationen enthalten sollte, wenn
of data blocks away. entsprechend Schritt b) ein Fehlversuch-Si-
gnal erzeugt wird, wobei der Status des gülti-
9. The method of claim 8, wherein the predeter- gen Bits einen ungültigen Zustand anzeigt,
mined number of data blocks is a same aligned wenn seit der letzten Leerung keine Daten in
group of blocks. 4o diesem Block geschrieben wurden;
d) Auffüllen des Caches mit einer ersten Auf-
_ O. The method of claim 3, wherein step (b) decre- füllrate mit den Datenblöcken, die den Daten-
ments the count to zero each time a search for a block, der die angeforderten Informationen
data block results in a hit. enthält, einschlie_en, wenn das gültige Bit ei-
4_ nen Status hat, der einen ungültigen Zustand
__. An apparatus for filling a cache of a computer anzeigt; und
with information, comprising. e) Auffüllen des Caches miteinerzweiten Auf-
means for searching the cache for requested in- füllrate mit zumindest einem Datenblock, der
formation; die angeforderten Informationen enthält,
means for generating a miss signal when the re- _o wenn das gültige Bit einen Status einnimmt,
quested information is not found; der einen gültigen Zustand anzeigt, wobei die
means for evaluating a valid bit ofa data block in erste Auffüllrate grö_er ist als die zweite Auf-
the cachewhere requested information should be füllrate.
Iocated, when the miss signal is generated, said
valid bit having a status indicative ofan invalidity __ 2. Verfahren zum Auffüllen eines Caches in einem
condition if no data has been written to this block Computer mit Informationen, wobei das Verfah-
since the last flush; ren folgende Schritte aufweist.
means for filling the cache with N blocks of data a) Absuchen des Caches nach der angefor-
_
9 EP O 3_9 8_ _ B_ 1 O
derten Information; Zustand anzeigt;
b) Erzeugung eines Fehlversuch-Signals, e) Vergleichen der Anzahl von Fehlversuch-
wenn die angeforderten Informationen sich Signalen mit einem ersten Grenzwert von
nicht im Cache befinden; Fehlversuchen;
c) Ermitteln des Status eines gültigen Bits ei- _ _ Auffüllen des Caches mit Datenblöcken mit
nes Datenblocks im Cache, der die angefor- der ersten Auffüllrate, wenn die Anzahl von
derten Informationen enthalten sollte, wenn Fehlversuch-Signalen eine erste vordefinier-
entsprechend Schritt b) ein Fehlversuch-Si- te Anzahl überschreitet;
gnal erzeugt wird und die angeforderten Infor- g) Schreiben von mindestens einem Daten-
mationen sich nicht im Cache befinden, wobei 1o block in den Cache mit einer zweiten Auffüll-
das gültige Bit einen Status hat, der einen un- rate, wenn die Anzahl von Fehlversuch-Si-
gültigen Zustand anzeigt, wenn seit der letz- gnalen kleiner oder gleich dem ersten Grenz-
ten Leerung keine Daten in diesem Block ge- wert ist und das gültige Bit einen Status ein-
schrieben worden sind; nimmt, der einen gültigen Zustand anzeigt,
d) Auffüllen des Caches mit einer ersten Auf- 1_ wobei die erste Auffüllrate grö_erals die zwei-
füllrate mit den Datenblöcken, die einen Da- te Auffüllrate ist und der mindestens eine Da-
tenblock, der die angeforderten Informationen tenblock die angeforderten Informationen ein-
enthält, einschlie_en, wenn das gültige Bit ei- schlie_t; und
nen Status einnimmt, der einen ungültigen h) Dekrementieren der Anzahl von Fehlver-
Zustand anzeigt; _o such-Signalen jedesmal dann, wenn ein Ab-
e) Vergleichen einer Proze_identifikations- suchen nach einem Datenblock in einem Tref-
nummer des Datenblocks, in dem sich die an- fer resultiert, und fortgesetztes Auffüllen des
geforderten Informationen befinden sollten, Caches mit Datenblöcken mit der ersten Auf-
mit einer Proze_identifi kationsnummer eines füllrate bis die Anzahl von Fehlversuch-Signa-
Prozesses, der auf dem Computer gerade __ len unter einer zweiten vordefinierten Anzahl
läuft, wenn das gültige Bit einen Status ein- liegt.
nimmt, der einen gültigen Zustand anzeigt;
_ Auffüllen des Caches mit Datenblöcken mit 4. Verfahren nach Anspruch 1 , das weiter den
einerersten Auffüllrate, wenn die Proze_iden- Schritt des Vergleichs einer Proze_identifikati-
tifi kationsnummern nicht gleich sind; und 3o onsnummer des Datenblocks im Cache, in dem
g) Auffüllen des Caches mit einerzweiten Auf- sich angeforderte Informationen befinden soll-
füllrate mit zumindest einem Datenblock, der ten, mit einer Proze_identifikationsnummer ei-
die angeforderten Informationen enthält, nes Prozesses, der gerade auf dem Computer
wenn die Proze_identifikationsnummern die läuft, wobei der Cache mit der zweiten Auffüllrate
gleichen sind, wobei die erste Auffüllrate grö- 3_ gefülltwird, wenn die zwei Proze_identifikations-
_er ist als die zweite Auffüllrate. nummern gleich sind.
3. Verfahren zum Auffüllen eines Caches in einem _. Verfahren nach den Ansprüchen 1 , 2 oder 3, wo-
Computer mit Informationen, wobei das Verfah- bei die erste Auffüllrate den Cache mit einer Rate
ren folgende Schritte aufweist. 4o von vier Datenblöcke je vordefinierter Zeiteinheit
a) Absuchen eines Datenblocks im Cache, und die zweite Auffüllrate mit einer Rate von ei-
der die angeforderten Informationen enthal- nem Datenblock je vordefinierter Zeiteinheit auf-
ten sollte, und Erzeugen eines Fehlversuch- füllt.
Signals, wenn die angeforderten Informatio-
nen sich nicht im Cache befinden; 4_ 6. Verfahren nach den Ansprüchen 1 , 2 oder 3, das
b) Speichern der Anzahl der Fehlversuch-Si- weiterhin folgende Schritte aufweist.
gnale, die bei Schritt a) erzeugt wurden; Speichern des Speicherplatzes eines
c) Ermitteln des Status eines gültigen Bits Fehlversuchs, wenn das Absuchen des Caches
des Datenblocks der abgesucht wurde, wobei in der Erzeugung des Fehlversuch-Signals resul-
das gültige Bit einen Status einnimmt, der ei- _o tiert;
nen ungültigen Zustand anzeigt, wenn seit der Vergleichen des gespeicherten Fehlver-
Ietzten Leerung keine Daten in diesen Block such-Speicherplatzes mit einem Speicherplatz
geschrieben worden sind; eines nächsten auftretenden Fehlversuchs; und
d) Auffüllen des Caches mit einer ersten Auf- Auffüllen des Caches mit Datenblöcken
füllrate mit den Datenblöcken, die einen Da- __ mit einer ersten Auffüllrate, wenn, wie aus dem
tenblock, der die angeforderten Informationen gespeicherten Fehlversuch-Speicherplatz zu-
enthält, einschlie_en, wenn das gültige Bit ei- sammen mit dem Speicherplatz eines nächsten
nen Status einnimmt, der einen ungültigen auftretenden Fehlversuchs festgestellt, der ge-
6
1 1 EP O 3_9 8_ _ B_ 12
speicherte Fehlversuch-Speicherplatz der erste nicht El N ist, wobei die N Datenblöcke einen Da-
Block in einer Gruppe von aneinanderliegenden tenblock einschlie_en, der die angeforderten In-
Blöcken ist. formationen enthält; und
eine Vorrichtung zum Auffüllen des Cache
l. Verfahren nach Anspruch 3, das weiter den 5 mit P Datenblöcken während eines festgelegten
Schritt des Vergleichs einer Proze_identifi kati- Zeitintervalls, wenn das gültige Bit El N ist, wobei
onsnummer des Datenblocks, der abgesucht P kleiner ist als N und die P Blöcke einen Daten-
wurde, mit einer Proze_identifi kationsnummer block einschlie_en, der die angeforderten Infor-
eines Prozesses, der gerade aus dem Computer mationen enthält.
läuft, einschlie_t, wobei die zweite Auffüllrate 1o
verwendet wird, den Cache aufzufüllen, wenn die _ 2. Vorrichtung nach Anspruch 1 1 , die ferner eine
zwei Proze_identifikationsnummern gleich sind. Vorrichtung zum Vergleich einer Proze_identifi-
kationsnummer des Datenblocks mit einer Pro-
8. Verfahren nach den Ansprüchen 1 , 2 oder 3, das ze_identifi kationsnummer eines Prozesses, der
weiter folgende Schritte aufweist. 15 gerade auf dem Computer läuft, einschlie_t, wo-
Speichern eines Speicherplatzes des bei die Vorrichtung zum Auffüllen den Cache mit
Fehlversuchs, wenn das Absuchen des Cache in Blöcken verschiedener Grö_e auffüllt, die auf
der Erzeugung eines Fehlversuch-Signals resul- dem von der Vorrichtung zum Vergleichen ausge-
tiert; führten Vergleich der Proze_identifikationsnum-
Vergleichen des gespeicherten Fehlver- _o mern basiert.
such-Speicherplatzes mit einem Speicherplatz
eines nächsten auftretenden Fehlversuchs; und _ 3. Vorrichtung nach Anspruch 1 1 , bei der der Cache
Auffüllen des Caches mit Datenblöcken ein Adre_umwandlungspuffer ist.
der ersten Auffüllrate, wenn der gespeicherte
Fehlversuch-Speicherplatz und der nächste auf- _5
tretende Fehlversuch-Speicherplatz um eine An- Revend i_ations
zahl von Datenblöcken voneinander entfernt lie-
gen, die innerhalb einer vordefinierten Anzahl _ . Procédé de remplissage d'une antémémoire pré-
liegt. vue dans un ordinateur, ledit procédé comportant
3o les étapes consistant.
9. Verfahren nach Anspruch 8, wobei die vordefi- (a) à rechercher des informations demandées
nierte Anzahl von Datenblöcken durch eine Grup- dans l'antémémoire;
pe von nebeneinanderliegenden Blöcken gege- (b) à générer un signal d'absence si les infor-
ben ist. mations demandées sont absentes de l'anté-
35 mémOlfe;
_ O. Verfahren nach Anspruch 3, wobei Schritt b), je- (c) à déterminer un état d'un bit valide d'un
desmal, wenn ein Absuchen nach einem Daten- bloc de données se trouvant dans l'antémé-
block in einem Treffer resultiert, den Zähler auf O moire qui devrait renfermer les informations
dekrementiert. demandées si un signal d'absence est généré
4o selon l'étape (b), ledit bit valide ayant un état
_ _ . Vorrichtung zum Auffüllen eines Caches eines représentatifd'une condition d'invalidité si au-
Computers mit Informationen, welche umfa_t. cune donnée n'a été introduite dans ledit bloc
eine Vorrichtung zum Absuchen des depuis le dernier vidage;
Caches nach angeforderten Informationen; (d) à remplir l'antémémoire de blocs de don-
eine Vorrichtung zum Erzeugen eines 45 nées suivant un premier débit si le bit valide a
Fehlversuch-Signals, wenn die angeforderten In- un état représentatif d'une condition d'invali-
formationen nicht gefunden werden; dité, les blocs de données comprenant le bloc
eine Vorrichtung zum Auswerten eines de données qui renferme les informations de-
gültigen Bits eines Datenblocks im Cache, in dem mandées; et
sich angeforderte Informationen befinden soll- 5o (e) à remplir l'antémémoire d'au moins un bloc
ten, wenn das Fehlversuch-Signal erzeugt wird, de données suivant un second débit si le bit
wobei das gültige Bit einen Status einnimmt, der valide a un état représentatif d'une condition
einen ungültigen Zustand anzeigt, wenn seit der de validité, au moins un bloc de données
Ietzten Leerung keine Daten in diesen Block ge- comprenant les informations demandées,
schrieben worden sind; 55 dans lequel le premier débit est plus rapide
eine Vorrichtung zum Auffüllen des que le second débit.
Caches mit N Blöcken von Daten während eines
festgelegten Zeitintervalls, wenn das gültige Bit 2. Procédé de remplissage d'informations d'une an-
l
1 3 EP O 3_9 8__ B_ 14
témémoire prévue dans un ordinateur, le procédé (d) à remplir l'antémémoire de blocs de don-
comportant les étapes consistant. nées suivant un premier débit si le bit valide a
(a) à rechercher des informations demandées un état représentatif d'une condition d'invali-
dans l'antémémoire; dité, les blocs de données comprenant un bloc
(b) à générer un signal d'absence si les infor- _ de données qui renferme les informations de-
mations demandées sont absentes de l'anté- mandées;
mémoire; (e) à comparer la valeur de comptage des si-
(c) à déterminer un état d'un bit valide d'un gnaux d'absence à un premier nombre seuil
bloc de données se trouvant dans l'antémé- d'absences;
moire qui devrait renfermer les informations 1o (_ à remplir l'antémémoire de blocs de don-
demandées si un signal d'absence est généré nées suivant un premier débit si la valeur de
selon l'étape (b), et que les informations de- comptage de signaux d'absence dépasse un
mandées sont absentes de l'antémémoire, le- premier nombre prédéterminé;
dit bit valide ayant un état représentatif d'une (g) à introduire au moins un bloc de données
condition d'invalidité si aucune donnée n'a été 1_ dans l'antémémoire suivant un second débit si
introduite dans ledit bloc depuis le dernier vi- la valeur de comptage de signaux d'absence
dage; est inférieure ou égale au premier nombre
(d) à remplir l'antémémoire de blocs de don- seuil et que le bit valide a un état qui est re-
nées suivant un premier débit si le bit valide a présentatif d'une condition de validité, le pre-
un état représentatif d'une condition d'invali- _o mier débit étant plus rapide que le second dé-
dité, les blocs de données comprenant un bloc bit et ledit au moins un bloc de données
de données qui renferme les informations de- comprenant les informations demandées; et
mandées; (h) à décrémenter la valeur de comptage de
(e) si le bit valide a un état représentatif d'une signaux d'absence chaque fois qu'une recher-
condition de validité, à comparer un numéro __ che d'un bloc de données aboutit à la déter-
d'identification de processus du bloc de don- mination d'une présence, et à continuer à
nées dans lequel les informations demandées remplir l'antémémoire de blocs de données
devraient se trouver à un numéro d'identifica- suivant le premier débit jusqu'à ce que la va-
tion de processus d'un processus qui est train leur de comptage de signaux d'absence soit
d'être exécuté par l'ordinateur; 3o inférieur à un second nombre prédéterminé.
(_ à remplir l'antémémoire de blocs de don-
nées suivant le premier débit si les numéros 4. Procédé selon la revendication 1 , comportant en
d'identification de processus sont autres que outre l'étape consistant à comparer un numéro
Ies mêmes; et d'identification de processus du bloc de données
(g) à remplir l'antémémoire d'au moins un bloc 3_ de l'antémémoire dans lequel les informations
de données suivant un second débit si les nu- demandées devraient se trouver à un numéro
méros d'identification de processus sont les d'identification de processus d'un processus qui
mêmes, ledit au moins un bloc de données est en train d'être exécuté par l'ordinateur, l'an-
comprenant les informations demandées, témémoire étant remplie suivant le second débit
dans lequel le premier débit est plus rapide 4o si les deux numéros d'identification de processus
que le second débit. sont les mêmes.
3. Procédé de remplissage d'informations d'une an- _. Procédé selon les revendications 1 , 2 ou 3, dans
témémoire prévue dans un ordinateur, le procédé lequel le premier débit remplit l'antémémoire à
comportant les étapes consistant. 4_ une cadence de 4 blocs de données par période
(a) rechercher un bloc de données de l'anté- de temps prédéterminée et le second débit rem-
mémoire qui devrait renfermer les informa- plit l'antémémoire suivant une cadence de 1 bloc
tions demandées et à générer un signal d'ab- de données par période de temps prédéterminée.
sence si les informations demandées sont ab-
sentes de l'antémémoire; _o 6. Procédé selon les revendications 1 , 2 ou 3,
(b) emmagasiner une valeurde comptage des comportant en outre les étapes consistant.
signaux d'absence générés à l'étape (a); à emmagasiner un emplacement d'une
(c) à déterminer un état d'un bit valide du bloc absence lorsque la recherche dontfait l'objet l'an-
de données qui a fait l'objet de la recherche, témémoire aboutit à la génération du signal d'ab-
Iedit bit valide ayant un état représentatif __ sence;
d'une condition d'invalidité si aucune donnée à comparer l'emplacement d'absence em-
n'a été introduite dans ce bloc depuis le der- magasiné à un emplacement d'une absence se
nier vidage; produisant subséquemment; et
8
1 5 EP O 3_9 8__ B_ 16
à remplir l'antémémoire de blocs de don- dage;
nées suivant un premier débit si l'emplacement des moyens pourremplirl'antémémoire de
d'absence emmagasiné est un premier bloc d'un N blocs de données pendant un intervalle de
groupe de blocs qui sont alignés, comme déter- temps spécifié si le bit valide n'est pas à ''1 '', les
miné par l'emplacement d'absence emmagasiné, _ N blocs de données comprenant un bloc de don-
avec un emplacement d'une absence se produi- nées renfermant les informations demandées; et
sant subséquemment; des moyens pourremplirl'antémémoire de
P blocs de données pendant ledit intervalle de
l. Procédé selon la revendication 3, comportant en temps spécifié si le bit valide est à ''1 '', où P est
outre l'étape consistant à comparer un numéro 1o inférieur à N, les P blocs comprenant un bloc de
d'identification de processus du bloc de données données renfermant les informations deman-
qui a fait l'objet d'une recherche à un numéro dées.
d'identification de processus d'un processus qui
est en train d'être exécuté par l'ordinateur, le se- _2. Appareil selon la revendication 11 , comprenant
cond débit étant utilisé pour remplir l'antémémoi- 1_ en outre des moyens pour comparer un numéro
re si les deux numéros d'identification de proces- d'identification de processus du bloc de données
sus sont les mêmes. à un numéro d'identification de processus d'un
processus qui est en train d'être exécuté par l'or-
8. Procédé selon les revendications 1 , 2 ou 3, dinateur, dans lequel les moyens de remplissage
comportant en outre les étapes consistant. _o remplissent l'antémémoire de blocs de tailles dif-
à emmagasiner un emplacement de l'ab- férentes sur la base de la comparaison des numé-
sence lorsque la recherche dont fait l'objet l'anté- ros d'identification de processus par les moyens
mémoire aboutit à la génération d'un signal d'ab- de comparaison.
SenCe;
à comparer l'emplacement d'absence em- __ _3. Appareil selon la revendication 11 , dans lequel
magasiné à un emplacement d'une absence se l'antémémoire est une mémoire tampon de tra-
produisant subséquemment; et duction.
à remplir l'antémémoire de blocs de don-
nées suivant le premier débit si l'emplacement
d'absence emmagasiné et l'emplacement d'ab- 3o
sence se produisant subséquemment sont dis-
tants de moins d'un nombre prédéterminé de
blocs de données.
9. Procédé selon la revendication 8, dans lequel le 3_
nombre prédéterminé de blocs de données est un
même groupe aligné de blocs.
_ O. Procédé selon la revendication 3, dans lequel
l'étape (b) décrémente la valeurde comptagejus- 4o
qu'à zéro chaque fois qu'une recherche d'un bloc
de données aboutit à la détermination d'une pré-
SenCe.
__. Appareil pour remplir d'informations une antémé- 4_
moire d'un ordinateur, comportant.
des moyens pour rechercher des informa-
tions demandées dans l'antémémoire;
des moyens pour générer un signal d'ab-
sence lorsque les informations demandées ne _o
sont pas trouvées;
des moyens d'évaluer un bit valide d'un
bloc de données se trouvant dans l'antémémoire
dans lequel les informations demandées de-
vraient se trouver, lorsque le signal d'absence est __
généré, ledit bit valide ayant un état représentatif
d'une condition d'invalidité si aucune donnée n'a
été introduite dans ledit bloc depuis le dernier vi- 9
__LIDTi4G PREOPCOE3S_S98,_B,
(PICTURE)
Bl_ FJEL_JD_JV_JFJ_A__JV D___
(PICTURE)
FIG.l
FIG.,,2