Cache memory utilizing a two-phase synchronization signal for controlling saturation conditions of the cache

A device for accessing information stored in a main memory of a computer system, wherein said device is coupled to the main memory through an address translation processor wherein the address translation processor includes an address development unit for calculating a virtual address of information sought, said device comprising:

• (a) an associative memory having a plurality of memory locations, each of said memory locations for storing an extract, said associative memory comprising:
• (i) a plurality of virtual address registers;
• (ii) a comparison circuit, coupled to said plurality of virtual address registers and coupled to the address translation processor, said comparison circuit for receiving a virtual address to be translated from the address translation processor and for comparing the received virtual address with virtual addresses in the plurality of virtual address registers and for providing a plurality of coincidence signals, each of said coincidence signals having a first logic value in response to a virtual address of an information item sought matching one of the virtual addresses stored in the plurality of virtual address registers;
• (iii) a plurality of presence flip-flops coupled to said comparison circuit, each of said presence flip-flops for receiving a real address write command signal and for providing a presence indicator output signal to said comparison circuit, wherein the presence indicator output signal has a logic value indicative of a state of the corresponding presence flip-flop;
• and
• (b) a controller, coupled to said associative memory and to the address translation processor, for receiving the coincidence signals and the presence indicator signals from said associative memory and for providing the real address write command signal to the presence flip-flops of said associative memory wherein said controller comprises:
• (i) a plurality of reference flip-flops, wherein each of said reference flip-flops are coupled to said associative memory, and wherein each of said presence flip-flops and reference flip-flops are initially set to a logic value 0, and a first one of the plurality of presence flip-flops is set to a logic value 1 in response to an extract being stored in a corresponding one of said plurality of memory locations;
• and
• (ii) a control circuit, coupled to said reference flip-flops, said control circuit for receiving each of said coincidence signals from said comparison circuit, for receiving a reference indicator signal from said reference flip-flops and for updating a logic state of the reference flip-flops in response to the values of the coincidence signals and the reference indicator signals and wherein said control circuit further provides an evaluation signal during a first phase of a two-phase synchronization signal, wherein the evaluation signal has a value determined by a logic state of said reference flip-flops and said coincidence signals, said evaluation signal having a first value when said associative memory is in a saturation state and having a second different value when said associative memory is not in a saturation state and wherein the evaluation signal indicates a saturation state in response to the following conditions being concurrently met;
• (a) each of the reference flip-flops but a last reference flip-flop have a logic value of 1;
• and
• (b) a coincidence signal corresponding to the last reference flip-flop and having a logic value of 0 is about to be set to 1;
• and wherein when such conditions are detected during the first phase of the two-phase synchronization signal, each of the reference flip-flops except for the last reference flip-flop are reset to 0 and during the second phase of the two-phase synchronization signal the last reference flip-flop is set to 1.

A method of allowing execution of an associative read and a corresponding updating of an indicator regardless of a logical state of the indicator during a single clock cycle having two clock phase, said method comprising the steps of:

• during a first phase of a two-phase clock signal performing the steps of:
• (a) comparing a virtual address to be translated with each virtual address included in an associative memory having a plurality of memory locations wherein each of said memory locations are coupled to one of a like plurality of reference flip-flops;
• (b) evaluation a saturation condition of the associative memory;
• (c) providing an evaluation signal for each of said memory locations, wherein each evaluation signal is provided having a first value selected in response to said evaluating step, and wherein said evaluation signals indicate a saturation state of said associative memory;
• (d) storing each evaluation signal in a corresponding one of a like plurality of reference flip-flops as a latched evaluation signal;
• (e) detecting the following conditions;
• each of the plurality of reference flip-flops except a last reference flip-flop are placed in a first logic state the last reference flip-flop is placed in a second different logic state;
• and
• the last reference flip-flop in the second logic state is about to be placed in the first logic state, wherein an evaluation signal is provided having a value to indicate a saturation state of said associative memory in response to said conditions being concurrently met;
• and
• during a second phase of the two-phase clock signal performing the steps of:
• (a) updating a reference indicator in response to a value of a latched coincidence signal and the latched evaluation signal;
• (b) performing the following step in response to the conditions in said detecting step being met:
• placing the plurality of reference flip-flops in the second logic state;
• and
• placing the last reference flip-flop in the first logic state.