Method and apparatus for fast memory access in a computer system

A method and apparatus for fast memory access in a computer system employing a high-speed associative memory for storing extracts that each include an address and an associated information component. Each extract is associated with a presence indicator and a reference indicator, their respective states being changed when an extract is used. According to the method of the invention, the state of each reference indicator can be changed only if the number of extracts present is at least equal to a threshold value. The invention also relates to apparatus for implementing the method. The invention can be applied to cache memories and to translations of virtual addresses to real addresses.

FIELD OF THE INVENTION 
The invention relates to computers and more particularly to facilitating 
access to information contained in a memory system of a computer. 
BACKGROUND OF THE INVENTION 
The central subsystem of a computer generally comprises three types of 
units: processors, memory modules forming the main memory, and 
input-output controllers. Usually the processors communicate with the 
memory modules through a bus that allows addressing and transfer of data 
between the processors and the main memory. To execute a program 
instruction, its operands must be located in the main memory. The same is 
true for successive instructions of the program to be executed. In the 
case of a multiprocessing system, the memory must be partitioned to allow 
multiplexing between programs. For this purpose, virtual addressing is 
generally used in conjunction with a pagination mechanism which includes 
dividing the addressable space, or "virtual space," into zones of a fixed 
size called "pages." In a system of this kind, a program being executed 
addresses a virtual space that corresponds to a real portion of the main 
memory. Thus, a logical or virtual address is associated with a physical 
or real address of the main memory. 
An instruction that requires addressing contains information that enables 
the processor executing it to obtain a real address. In general, this 
virtual address is segmented, i.e., it is composed of a segment number, a 
page number, and a shift i.e., displacement within the referenced page. 
The segment number in turn can be subdivided into a segment table number 
and a shift within this table. 
In order to access an item of information in memory associated with this 
segmented address, several memory accesses are necessary. It is first 
necessary to access an address space table allocated to the process 
(program being executed). From this table, using a segment table number, 
the real address of the corresponding segment table is then obtained. 
Next, as a function of the shift in the segment table, a segment 
descriptor is accessed which makes it possible to calculate the real 
address of a page table. Eventually a real page address is found, using a 
function of the page number defining the shift within this page table, 
thereby making it possible to address the memory. The real address of a 
word or particular byte [8-bit byte] is obtained by concatenation of the 
real page address with the shift within this page defined by the least 
significant bits of the virtual address. 
A memory access is relatively time consuming, due primarily to the use of a 
bus that is common to both the processors and the memory module. To 
improve system performance, the successive memory accesses typically 
required to obtain a real address are avoided as much as possible. Most 
processes have a locality property according to which, during a given 
phase of its execution, the number of pages used by a process is very 
small relative to the total number of pages allocated to that process. 
The locality property can be used to facilitate the translation of a 
virtual address into a real address by the use of "extracts". Each extract 
includes a virtual address and an associated real address, and is used by 
the program during a single execution phase. A plurality of extracts are 
stored in high-speed memory or in registers. To perform a translation of a 
virtual address into a real address, a high-speed associative memory is 
accessed to determine whether the virtual address to be translated is 
already present in the high-speed memory. If it is, the real address is 
obtained directly without accessing the main memory. 
The locality property motivates the use of cache memories composed of 
small, high-speed memories in which the pages most recently referenced are 
stored. The probability that a new reference will relate to an item of 
information already present in cache memory is high, so the effective 
access time is reduced. In a manner analogous to the translation of the 
virtual address into a real address, a cache memory comprises a table 
containing the real addresses of the pages present in the cache memory. 
This table, called a directory, can be consulted in an associative fashion 
to determine whether the information associated with a given real address 
is contained in the cache memory. If it is, a word or byte is obtained by 
addressing the cache memory by means of the least significant bits of the 
virtual address of the word or octet. 
Issues related to the translation of addresses will now be discussed, it 
being understood that the same considerations may apply to cache memories. 
In both cases, the issue is that of rapidly obtaining information 
associated with a page address. In the case of translation of an address, 
the page address is a virtual address and the associated information is 
the corresponding real address, while in the case of cache memory, the 
page address is a real address and the associated information includes all 
the data contained in the page. 
As previously discussed, the high-speed translation memory is an 
associative memory. The memory comprises a given number of registers, or 
more generally, locations, each capable of storing one extract. Each 
extract can be accompanied by additional information such as 
right-of-access indicators or indicators reporting that a write access has 
been effected in the page associated with the extract. Moreover, each 
extract is associated with a presence indicator which, for a given logic 
state, indicates that the associated extract is valid. These presence 
indicators are, for example, set to zero at initialization, i.e., each 
time a process is activated in a particular processor. Thus, as the 
process uses new pages, the associated extracts are loaded into 
associative memory and the respective presence indicators are 
simultaneously set to 1. When a memory access must be executed, the 
virtual address is compared with the virtual address of each extract 
stored in associative memory. If there is a match between the virtual 
address being sought and one of the virtual addresses of an extract stored 
in the memory while its associated presence indicator is set to 1, the 
corresponding real address can be obtained directly by simply reading the 
register that contains the real address. 
In order for this translation mechanism to be practical, the associative 
memory must be of limited size. Consequently, for processes with many 
pages, the associative memory cannot store all the extracts corresponding 
to these pages. When associative memory is full, the only way to store a 
new extract therein is to erase an old extract. It is therefore necessary 
to provide a method for eradicating an old extract and storing a new 
extract in its place. To accomplish this, a replacement algorithm is used 
that decides which old extract is to be replaced by a new extract. Many 
algorithms have already been proposed, for example: 
the FIFO ("first in, first out") algorithm, in which the oldest extract is 
replaced; 
the RAND ("random choice") algorithm, in which the extract to be replaced 
is chosen at random; 
the LFU ("least frequently used") algorithm, in which the least frequently 
used extract is replaced; and 
the LRU ("least recently used") algorithm, in which the least recently used 
extract is replaced. The LRU algorithm theoretically gives good results, 
but in practice it is preferable to use a simplified version, called the 
"pseudo-LRU." To generate n extracts, a true LRU requires the presence and 
management of log.sub.2 (n) bits per extract to maintain an ordered 
history of the uses of the extracts. On the other hand, a pseudo-LRU 
requires only a single bit per extract, called a reference bit or 
indicator. 
According to the pseudo-LRU algorithm, the reference bit is set to a first 
logic state (1 for example) when its associated extract is used. When the 
associative memory is full, all the presence indicators are set to 1, and 
a new extract must be loaded. The extract to be replaced is the first 
extract encountered with a reference bit set to 0 according to the 
chronological order of filling. When saturation is reached, i.e., when all 
but one of the reference bits are set at 1, the extract whose reference 
bit is at 0 is replaced by the new extract, and all the reference bits are 
then reset to 0. Resetting all the reference bits obliterates the history 
of the use of the extracts. 
The loss of the history upon saturation results in a decrease in the 
efficiency of the algorithm. Moreover, a freshly loaded extract may very 
likely be reused immediately after being loaded, again resulting in 
saturation upon the loading of the fresh extract. 
To assess the consequences of this loss of history, it is useful to perform 
simulations of populations consisting of specific processes relating to 
applications normally handled by the system. It is found, for example, 
that for a certain population of processes, in 65% of the cases, only 32 
extracts are required. This means that 65% of the processes do not require 
use of the replacement algorithm. On the contrary; the algorithm will be 
used at least once by 35% of the processes. This means that a loss of 
history will occur at least once in 35% of the cases. 
During a simulation, it has also been found in 90% of the cases, that at a 
given moment, a program will access one of the last seven extracts called. 
This result confirms the phenomenon of locality mentioned above. Thus, 
after the reference bits are reset to 0 after saturation, the only 
criterion for selecting the extract to be replaced is the position of the 
extract in the associative memory. However, the location of an extract 
provides no indication of the time of its last use; it only provides an 
indication of its first use. Thus, it is quite possible that pages used at 
the start of the process will be used again a short time before 
saturation. In this case, after resetting the reference bits to 0, these 
pages will be eliminated first, even though they have a high probability 
of being reused very soon thereafter. 
SUMMARY OF THE INVENTION 
One aspect of the invention is a method for rapid access to information 
stored in the main memory of a computer system, a component of information 
being located by an address, that component of information and its 
associated address together being called an "extract". The system includes 
a high-speed associative memory that includes a plurality of memory 
locations, each location being capable of storing one extract. Each 
extract is associated with a presence indicator and a reference indicator 
initialized to a first logic state, the presence indicator assuming a 
second logic state when the corresponding extract is present in the 
high-speed memory. Access to an item of information is accomplished by 
associatively searching for the extract present in the high-speed memory 
whose address matches the address of the information sought. The reference 
indicators undergo a change of state upon use of their respective 
extracts, the state change being detected and processed by an algorithm 
for replacing old extracts with new extracts that are being sought and are 
not yet present in the high-speed memory. The reference indicators are 
maintained at their initial logic state while the number of extracts 
present in the high-speed memory is less than a given threshold value. A 
reference indicator is forced to a second logic state when the associated 
extract is used, but only if the number of extracts present is at least 
equal to said threshold value. 
Provision is made for the reference indicators to be maintained at their 
initial states (for example at 0) during the early stages of execution of 
a process, and for as long as the number of extracts present remains less 
than a given threshold value. Once the threshold value has been reached, 
updating the reference indicators takes place normally. Thus, when the 
associative memory is full, only the extracts used during an execution 
phase corresponding to the end of filling can have their reference 
indicators set to a logic state (1 for example) that indicates their use. 
As a result, on average, a larger number of processes will escape the loss 
of history due to saturation. 
The threshold value is chosen so that the difference between the number of 
extracts and the number n of locations in the high-speed memory results in 
a history of sufficient scope to optimize the performance of an intended 
application. 
According to one preferred embodiment of the process of the invention, a 
rank is assigned to each location in the high-speed memory. Extracts are 
initially loaded in chronological order into locations of increasing rank. 
The state of the presence indicator whose rank is equal to the threshold 
value provides an indication that the threshold value has been reached. 
In another aspect of the process of the invention, when an information item 
being sought cannot be found in the high-speed memory, the information is 
then sought in the main memory and the corresponding extract is loaded 
into the high-speed memory at a location whose rank is determined by the 
loading algorithm. The associated presence indicator is forced to a second 
logic state in conjunction with the loading. A new associative search for 
the desired information is then performed. 
According to yet another aspect of the process of the invention, the 
loading algorithm includes the steps of searching, in increasing order, 
the rank of the first extract whose presence indicator is at a first logic 
state or, failing that, of the first extract whose reference indicator is 
at the first logic state. 
A further aspect of the invention is an apparatus for implementing the 
process of the invention. The apparatus includes processing means for 
accessing "extracts" that each include an address and an associated 
information component. An extract is accessed by addressing a main memory 
included in the apparatus. The processing means also includes a high-speed 
associative memory that has a plurality of locations, each location being 
capable of storing an extract. Each location is associated with a presence 
flip-flop and a reference flip-flop, each being initially set to a first 
logic state. The presence flip-flop is placed at a second logic state when 
an extract is loaded into the associated location. The high-speed memory 
cooperates with a comparison means that delivers, for each location, a 
coincidence signal having a first logic value when the address of an item 
of sought information coincides with the address of an extract present in 
the location. The apparatus also includes threshold detection means for 
furnishing a threshold signal whose logic value indicates whether the 
number of extracts present in said high-speed memory is at least equal to 
a given threshold value. For each extract that is present, the state of 
the associated reference flip-flop is controlled by a management circuit 
for forcing the reference flip-flop to a second logic state when the 
coincidence signal indicates a match while the threshold signal indicates 
that the threshold has been reached.

DETAILED DESCRIPTION OF THE INVENTION 
With reference to FIG. 1, a high-speed associative memory 1 is connected so 
as to communicate with a controller 2 and with a portion of the circuitry 
3 of a processor. In traditional fashion, the processor and its circuitry 
3 is connected to the main memory (not shown). In particular, the 
circuitry 3 is a portion of the processor that relates to address 
translation, and includes an address development unit, generally 
microprogrammed for calculating the virtual addresses VA of the 
information sought. The firmware that controls the circuitry 3 executes 
searches in translation tables to obtain the real addresses as a function 
of the virtual addresses. This address translation is speeded up by the 
associative memory that includes a number n of virtual address registers 
VAR and the same number of real address registers RAR. The associative 
memory 1 also has a set of n flip-flops BPR associated respectively with 
the virtual address registers and real address registers. The combination 
of a virtual address VA.sub.i contained in the virtual address register 
with rank i and a real address RA.sub.i contained in the real address 
register of the same rank, constitutes an extract i. This extract i is 
associated with a presence indicator PR.sub.i whose logic state 
corresponds to the state of the corresponding presence flip-flop. A 
comparator 4 is connected to outputs VA.sub.i of virtual address registers 
VAR and receives from the firmware of circuitry 3 the virtual address VA 
to be translated. Comparison circuit 4 is validated by output signals 
PR.sub.i from the presence flip-flops BPR. Circuit 4 provides coincidence 
signals HIT.sub. i whose logic values represent equality between the 
virtual address sought and one of the virtual addresses contained in 
registers VAR. The HIT.sub.i signals are provided to a validation circuit 
8 that furnishes an address validation signal ADVAL to the firmware of 
circuitry 3, indicating whether address translation was successful. 
In the event of a failure, the ADVAL signal initiates a micro-program that 
searches within the tables for the real address. Once a search has been 
done, the virtual address VA.sub.e and its associated real address 
RA.sub.e are applied respectively to input interfaces 5, 6 of the virtual 
and real address registers. The virtual and real addresses are then 
written in one of these registers under the control of write command 
signals WVR.sub.i and WRR.sub.i, respectively. If translation is 
successful, coincidence signals HIT.sub.i authorize, via interface 7, 
reading of the real address register containing the translation sought. 
Controller 2 comprises a set of reference flip-flops BRF associated 
respectively with the locations of memory 1, and with the extracts stored 
within those locations. The state RF.sub.i of the flip-flops BRF is 
determined by a control circuit 9 which receives coincidence signals 
HIT.sub.i and which is connected to the outputs RF.sub.i of the reference 
flip-flops BRF. A selection circuit 10 connected to the outputs of 
presence flip-flop BPR and the reference flip-flops BRF delivers selection 
signals S.sub.i which are applied to a load control circuit 11 that 
delivers the above-mentioned WVR.sub.i and WRR.sub.i signals. Selection 
signals S.sub.i determine the virtual and real address registers into 
which a new extract not present in the table must be loaded. The write 
commands WVR.sub.i and WRR.sub.i are determined by the load control 
circuit 11 as a function of the selection signals S.sub.i and common write 
command signals WRR, WVR that are delivered by the circuitry 3 under 
control of firmware. The firmware controlling the circuitry 3 also 
furnishes a signal RS that controls the resetting of the presence and 
reference flip-flops. 
The device in FIG. 1 operates as follows. When a virtual address VA is to 
be translated, the microsoftware controlling the circuitry 3 places the 
virtual address at the input of the comparator 4. In the event of a match, 
the HIT.sub.i signals validate the real address register containing the 
translation sought and circuit 8 validates this address by the ADVAL 
signal. Control circuit 9 reupdates the state of the latter flip-flops as 
a function of the coincidence signals HIT.sub.i, the number of extracts 
present in the high-speed memory, and the previous state RF.sub.i of the 
reference flip-flops. Selection circuit 10 reupdates selection signals 
S.sub.i according to the new state RF.sub.i of these flip-flops and the 
presence indicators PR.sub.i, to determine which new registers will 
receive the next extract. 
In the event of a translation failure, the ADVAL signal triggers the 
microprogram that searches in the tables. Once the search has been 
executed, the corresponding extract VA.sub.e, RA.sub.e is presented to the 
inputs of interfaces 5, 6. Control circuit 11 then locates the extract 
according to the write signals WRR, WVR and selection signals S.sub.i. 
Once the extract has been loaded into the selected registers, the 
microsoftware controlling the circuitry 3 makes a new attempt to translate 
the virtual address to be translated. 
According to one feature of this embodiment, control circuit 9 takes into 
account the number of extracts present in the memory. As long as this 
number is less than a given threshold value t, reference indicators 
RF.sub.i are kept unchanged and thus preserve the initial state (e.g., 0) 
which was imposed on them by the RS signal at the beginning of the 
process, for example, after a dispatch. As soon as the number of extracts 
present reaches or exceeds the value t, indicators R.sub.i can be modified 
according to the classical pseudo-LRU algorithm. It will be shown below 
how this threshold can be detected in practice. 
The value of the threshold is determined by searching for the optimum value 
of the number n-t which corresponds to the number of extracts loaded 
between the time the threshold is reached and the time when the 
associative memory is full. To accomplish this, use can be made of 
statistical data relating to, in particular, the number of extracts used 
by the processes between two dispatches and the age of the reused pages. 
Another solution consists of making system operation simulations with 
characteristic programs, varying the value of the threshold. 
As a non-limiting example, for a universal computer of the multiprocessor 
type with n=32, t may be chosen to equal 24. 
FIG. 2 shows the part of memory 1 associated with one of the extracts. The 
virtual and real addresses of an extract i assumed to be loaded are 
contained in virtual address register VAR.sub.i and real address register 
RAR.sub.i, respectively. The parallel output VA.sub.i of virtual address 
register VAR.sub.i is connected to a first input of a comparison circuit 
14 of comparator 4 whose second input receives the virtual address to be 
translated VA that is furnished by register R.sub.c. A presence flip-flop 
BPR.sub.i is connected at its output PR.sub.i to the validation input of 
circuit 14. Output PR.sub.i is also connected to controller 2. The output 
of circuit 14 is connected to the controller 2 to the input of a 
synchronization gate 17. Gate 17 is synchronized by the first phase CK1 of 
a clock signal. 
The parallel output of real address register RAR.sub.i is connected to the 
input of an amplifier 18B validated by output signal RD.sub.i from 
synchronization gate 17. Signal RD.sub.i also validates amplifier 18A 
which receives at its input a voltage corresponding to logic value 1. The 
signals ADVAL and RA.sub.i from amplifiers 18A and 18B are sent to the 
firmware controlling circuitry 3. 
The virtual and real addresses VA.sub.e and RA.sub.e that are to be loaded 
into the registers are initially placed in an output register R.sub.e of 
the firmware. The parallel output of register R.sub.e is connected to the 
parallel inputs of register VAR.sub.i and RAR.sub.i via amplifiers 15 and 
16, respectively. Amplifiers 15 and 16 are validated respectively by 
signals WVR.sub.i and WRR.sub.i furnished by controller 2. 
The circuit of FIG. 2 operates as follows. A clock (not shown) furnishes a 
clock signal with two phases CK1 and CK2. During phase CK2, the firmware 
of circuitry 3 places the virtual address to be translated VA in register 
R.sub.c. During the next phase CK1, this address is compared in circuit 15 
to the virtual address VA.sub.i contained in register VAR.sub.i. If 
addresses VA and VA.sub.i are different, or if presence indicator PR.sub.i 
is at 0, coincidence signal HIT.sub.i will assume a value of 0. As a 
result, during phase CK1 amplifiers 18A and 18B are maintained in a state 
of high impedance. 
If, on the other hand, addresses VA and VA.sub.i are identical while 
presence indicator PR.sub.i is at 1, coincidence signal HIT.sub.i assumes 
a value of 1. Thus, during phase CK1, real address RA.sub.i contained in 
register RAR.sub.i is transmitted to the firmware of circuitry 3 by means 
of amplifier 18B. Simultaneously, the ADVAL signal is at 1, thus 
indicating the success of translation. Note that amplifiers 18A associated 
with the various memory extracts execute a wired OR function that can 
advantageously be accomplished by means of a precharged line during phase 
CK2 and selectively unloaded by one of the signals RD.sub.i during phase 
CK1. 
To load a new extract into the high-speed memory, the microsoftware of 
circuitry 3 first places the virtual address VA.sub.e of the extract in 
register R.sub.e and activates the virtual address write control signal 
WVR of FIG. 1. If register VAR.sub.i is selected, loading circuit 11 of 
controller 2 furnishes a WVR.sub.i signal which validates amplifier 15. 
Likewise, the corresponding real address RA.sub.e is then placed in output 
register R.sub.e and the WRR.sub.i signal validates amplifier 16. 
FIG. 3 shows reference flip-flops BRF and their control circuit 9 in 
greater detail. Control circuit 9 is composed of a common control circuit 
19B and an assembly of flip-flop BRF management circuits 19A. With the 
locations (pairs of registers) of the associative memory being referenced 
by the subscripts 1, 2, . . . , i, . . . , n, they are associated 
respectively with flip-flops BRF.sub.1, BRF.sub.2, . . . , BRF.sub.i, . . 
. , BRF.sub.n. Each flip-flop BRF.sub.i is controlled by a signal 
WRF.sub.i furnished by an associated management circuit GRF. Outputs 
RF.sub.1, RF.sub.2, . . . , RF.sub.i, . . . , RF.sub.n are connected to 
common control circuit 19B which furnishes to each management circuit GRF 
a prepositioning signal V for setting to 1 and a prepositioning signal CL2 
for setting to 0. Circuit 19B also receives coincidence signals HIT.sub.1, 
HIT.sub.2, . . . , HIT.sub.i, . . , HIT.sub.n. Each management circuit GRF 
receives a signal HL.sub.i which is the coincidence signal HIT.sub.i 
latched by a flip-flop BHL upon each phase CK1. 
The operation of the circuit in FIG. 3 will be explained with the reference 
to FIGS. 4 and 5 which represent detailed forms of common control circuit 
19B and management circuit GRF, respectively. By convention, the 
explanations will be given in positive logic. Common control circuit 19B 
of FIG. 3 includes an evaluation circuit 19C, a flip-flop BCL, and a 
synchronization circuit 19D. Evaluation circuit 19C has an evaluation line 
CL whose state indicates whether the saturation condition of the 
high-speed memory has been reached. Circuit 19C consists of a complex 
logic gate in CMOS technology whose line CL is precharged during phase CK2 
by means of PMOS transistors P1 and P2. Line CL is evalutated as a 
function of signals HIT.sub.i * and RF.sub.i *, respectively, which are 
the complements of the coincidence signal HIT.sub.i and the reference 
signal RF.sub.i associated with the extracts contained in the high-speed 
memory. The state of line CL is latched by the flip-flop BCL upon phase 
CK1. The flip-flop BCL then provides a latched evaluation signal CL1 at 
its output. 
Line CL is connected to ground VSS via a common NMOS transistor N3 and, for 
each extract, via the series arrangement including two NMOS transistors N1 
and N2 whose gates receive respectively the signals RF.sub.i * and 
HIT.sub.i * from the associated extract. This arrangement allows the 
following logic function (evaluated during phase CK1) to be implemented: 
EQU CL=+* (RF.sub.i *.HIT.sub.i *) 
where +* is the NOR function applied to the set of logical products 
RF.sub.i *.HIT.sub.i *, for all values of i. Transistor N3, blocked during 
phase CK2, contributes to precharging of line CL. 
Thus, from the beginning of operation of the associative memory, when all 
the indicators are initialized at 0, line CL is unloaded at each 
evaluation phase provided that the saturation condition is not reached. 
The saturation condition corresponds to the case where all the reference 
indicators are at 1 except for the indicator that represents a coincidence 
event. If the saturation condition is reached, line CL retains logic value 
1 during the evaluation phase, thereby reporting that the saturation 
condition is reached. 
Synchronization circuit 19D includes an AND gate 21 with three inputs. A 
first input of the gate 21 receives the latched evaluation signal CL1, a 
second input receives phase CK2, and the third input receives an 
authorization-to-operate signal USE. The signal USE is a command signal 
furnished by the microsoftware of the circuitry 3. 
Circuit 19D also has a NAND gate 20 with three inputs receiving, 
respectively, clock signal CK2, the command signal USE, and a threshold 
signal PR.sub.t which assumes logic value 1 when the high-speed memory 
loading threshold is reached. Gate 20 generates a signal V* which is the 
complement of the prepositioning signal V that sets to 1. Provided the 
locations are loaded in a given order, the threshold signal can be 
obtained simply by reading flip-flop BPR.sub.t whose rank is equal to the 
value of threshold t and that which was chosen. 
FIG. 5 represents reference flip-flop BRF.sub.i and its associated 
management circuit GRF. Flip-flop BRF.sub.i is composed simply of two 
inverters mounted head-to-tail which furnish reference indicator RF.sub.i 
and its complement RF.sub.i *. The state RF.sub.i of flip-flop BRF.sub.i 
is controlled by line WRF.sub.i. Line WRF.sub.i can be unloaded via the 
series arrangement formed of two NMOS transistors N4, N5 or via an NMOS 
transistor N6. Transistors N4, N5 and N6 receive at their respective gates 
the HL.sub.i * signal which is the complement of the HL.sub.i signal, the 
CL2 signal, and the RS signal. As a result, line WRF.sub.i is unloaded 
when the RS signal is at 1 or when the CL2 signal is at 1 while the 
HL.sub.i signal is at 0. Thus, flip-flop BRF.sub.i is forced to 0 when the 
saturation condition is detected while the virtual address contained in 
the associated register does not match the virtual address to be 
translated. 
Line WRF.sub.i may be placed at logic value 1 via the series arrangement 
formed of two PMOS transistors P3, P4 that receive the signals HL.sub.i * 
and V* at their respective gates. As a result of this arrangement, 
flip-flop BRF.sub.i is forced to 1 when signals V and HL.sub.i are at 1, 
i.e., when the virtual address sought matches the virtual address 
contained in the register, provided that the threshold is reached. 
The full operation of the circuits of FIGS. 3, 4 and 5 will now be 
explained in relation to the timing diagram of FIG. 6. This diagram 
represents the changes in state over time of the signals CL, CL1, CL2, and 
V generated by the common control circuit 19B of FIGS. 3 and 4, as well as 
the signals HIT.sub.i, HL.sub.i, and RF.sub.i associated with extract i of 
the associative memory 1 of FIG. 3. It is assumed that extract i is 
present, i.e., indicator PR.sub.i is at 1. It is also assumed that the 
threshold has already been reached, i.e., the signal V is at 1 during 
phase CK2, hence the signal V* is at 0 during this phase. Finally, it is 
assumed that at initial time t.sub.0, the reference indicator RF.sub.i and 
the latched evaluation signal CL1 are both at 0. 
Precharging of line CL of circuit 19C starts at time t.sub.0 during phase 
CK2. Starting at time t.sub.1, during the following phase CK1, coincidence 
signal HIT.sub.i, assumed to have value 1, is evaluated. During this 
phase, signal HIT.sub.i is held by flip-flop BHL whose state HL.sub.i goes 
to 1. At the same time, line CL is evaluated. Assuming that saturation is 
not reached, signal CL goes to 0 and signals CL1 and CL2 also remain at 0. 
During the next phase CK2, starting at time t.sub.2, line CL is once more 
precharged. Also, with coincidence signal HL.sub.i and validation signal V 
at 1, transistors P3 and P4 of management circuit GRF conduct, and line 
WRF.sub.i is charged to a positive voltage, thus forcing indicator 
RF.sub.i to 1. 
During the next phase CK1 after time t.sub.3, assuming that there is no 
match, coincidence signal HIT.sub.i goes to 0 thus forcing signal HL.sub.i 
to 0. Still assuming that the saturation condition is not reached, line CL 
is set to 0 during this phase and signals CL1 and CL2 remain at 0. As a 
result, during the next phase CK2 after time t.sub.4, signal CL2 at 0 
keeps transistor N5 in a blocked state, thus preventing flip-flop 
BRF.sub.i from being reset to 0. 
During the next phase CK1, after time t.sub.5, we have assumed that the 
threshold condition was reached and signal HIT.sub.i was at 0. As a 
result, line CL remains high, thereby setting the state CL1 of flip-flop 
BCL to 1. Thus, during the next phase CK2 after time t.sub.6, the 
prepositioning zero-resetting signal CL2 goes to 1, making transistor N5 
conduct. Since signal HL.sub.i is at 0, transistor N4 also conducts and 
line WRF.sub.i is unloaded and indicator RF.sub.i is reset to 0. The above 
description shows that the associative memory always operates in 
accordance with two clock phases, even when the reference indicators must 
be reset to 0. 
FIG. 7 represents selection circuit 10 of FIG. 1. We find presence 
flip-flops BPR1, BPR2, . . . , BPR.sub.i, . . . , BPR.sub.n, and reference 
flip-flops BRF1.sub.1, BRF.sub.2, . . . , BRF.sub.i, . . . , BRF.sub.n, 
associated respectively with extracts of rank 1, 2, . . . , i, . . . , n 
from the associative memory. Each extract i has associated with it a 
selection cell SC and two propagation circuits PC that propagate a request 
signal, associated respectively with extract presence and reference 
flip-flops. Each propagation circuit PC furnishes a request signal 
VP.sub.i or RP.sub.i, and receives indicator PR.sub.i or RF.sub.i, of the 
associated flip-flop, as well as request signal VP.sub.i-1 or RP.sub.i-1 
from the upstream propagation circuit. 
Output VP.sub.n of propagation circuit PC associated with presence 
flip-flop BPR.sub.n of the last extract of rank n is applied to the 
request input of the propagation circuit associated with reference 
flip-flop BRF.sub.i of the first extract. In addition, the request input 
of propagation circuit PC associated with presence flip-flop BPR.sub.1 of 
the first extract continuously receives a signal representing the 
existence of a request. In the example shown, we assumed that a request 
was present when the associated request signal was at 1. Alternatively, 
the reverse convention could be chosen without thereby departing from the 
framework of the invention. 
Each propagation circuit is designed to deliver a request signal VP.sub.i, 
or RP.sub.i, that represents the existence of a request when the upstream 
request signal VP.sub.i-1 or RP.sub.i-1 indicates the existence of a 
request while indicator PR.sub.i or RF.sub.i is at 1. Moreover, selection 
cell SC furnishes a selection signal S.sub.i representing the selection of 
an extract i when one of the upstream request signals VP.sub.i-1 or 
RP.sub.i-1 reports the existence of a request when the associated 
flip-flop BPR.sub.i or BRF.sub.i is at 0. 
The circuit in FIG. 7 operates as follows. As a function of the state of 
the presence and reference flip-flops, the request signal permanently 
applied to the input of the propagation circuit associated with first 
presence flip-flop BPR1 propagates stepwise, in increasing extract order, 
via propagation circuits associated first with the presence flip-flops, 
then via propagation circuits associated with the reference flip-flops. 
Propagation of the request signal stops at the propagation circuit that is 
associated with a presence flip-flop or reference flip-flop which is at 0. 
The selection cell associated with this extract then places selection 
signal S.sub.i at a specific logic value, indicating that a new extract 
must be written in the associated registers. 
Thus, the circuit of FIG. 7 always allows the location of the associative 
memory that is to receive a new extract to be pinpointed. The loading 
algorithm employed by this circuit thus consists of searching, in 
ascending order according to the ranks assigned to the locations, the 
first location containing no extract (the first whose presence indicator 
PR.sub.i is set at 0), then the second extract which has not been used 
recently (the first whose reference indicator RF.sub.i is set at 0). 
According to this arrangement, updating of selection signals S.sub.i is 
automatically controlled by the change in state of the presence and 
reference flip-flops. 
Due to the cascade arrangement of a propagation circuit, its reaction time 
is fairly long. Fortunately, the selection signals are not utilized until 
after the search in the tables for a new extract to be loaded, which is 
also a fairly lengthy operation. However, the slowness of the selection 
circuit may become cumbersome if the associative memory has a large number 
of extracts. Thus, to overcome this slowness, and according to one 
advantageous embodiment of the invention , optimization of the selection 
cells and propagation circuits is employed to reduce the number of layers 
of these circuits, thereby increasing operating speed. Accordingly, two 
different types of cells are provided, each type respectively associated 
with either odd or even rank locations. 
FIG. 8 shows selection cell SCI and propagation circuits PCI associated 
with an odd-ranked location. Propagation circuits PCI each consist of a 
NAND gate receiving, at a first input, associated indicator RF.sub.i, 
PR.sub.i and at a second input, upstream request signal RP.sub.i-1, 
VP.sub.i-1. The PCI gates deliver at their outputs the request signal 
complements RP.sub.i *, VP.sub.i *. The SCI cell is a complex logic gate 
which receives at the input the upstream request signals RP.sub.i-1, 
VP.sub.i-1 and complements RF.sub.i *, PR.sub.i * of indicators RF.sub.i, 
PR.sub.i. The SCI gate implements the equation: 
EQU S.sub.i *=(RF.sub.i *.RP.sub.i-1 +PR.sub.i * VP.sub.i-1)* 
To obtain signal S.sub.i, the output S.sub.i * of the SCI gate is connected 
to an inverter. 
FIG. 9 shows a selection cell SCP and propagation circuits PCP associated 
with an even-ranked location. The propagation cells PCP are implemented by 
NOR gates that receive, at a first input, the complement of associated 
indicator RF.sub.i, PR.sub.i and at a second input, the complement 
RP.sub.i-1 *, VP.sub.i-1 * of request signal RP.sub.i-1, VP.sub.i-1 coming 
from the preceding odd stage. Selection cell SCP is a complex gate 
receiving at its input indicators RF.sub.i, PR.sub.i and complements of 
associated request signals RP.sub.i-1, VP.sub.i-1. The SCP gate delivers 
selection signal S.sub.i verifying the preceding logical equation. Cells 
SCI, SCP, and gates SCI, PCP can easily implemented in CMOS technology. 
Finally, FIG. 10 represents the circuit for generating write command 
signals WVR.sub.i and WRR.sub.i associated with registers VAR.sub.i and 
RAR.sub.i respectively as a function of control signals WVR, WRR and 
selection signal S.sub.i. The circuit in FIG. 10 is made with AND logic 
gates allowing transmission of common signals for controlling the writing 
of virtual address WVR or real address WRR, validated by selection signal 
S.sub.i and synchronized by clock phase CK2. 
Other modifications and implementations will occur to those skilled in the 
art without departing from the spirit and the scope of the invention as 
claimed. Accordingly, the above description is not intended to limit the 
invention except as indicated in the following claims.