Multiplexed directory for dedicated cache memory system

• US 4,228,503 A
• Filed: 10/02/1978
• Issued: 10/14/1980
• Est. Priority Date: 10/02/1978
• Status: Expired due to Term

• Current Assignee: Sperry Corporation
• Original Assignee: Sperry Corporation
• Inventors: Waite, John C., Baber, David J.
• Primary Examiner(s): Atkinson, Charles E.
• Assistant Examiner(s): Chin, Gary
• Application Number:
  US05/947,791
• Time in Patent Office: 743 Days
• Field of Search: 364/200, 364/900
• US Class Current: 711/121
• CPC Class Codes: G06F 12/0808 with cache invalidating means G06F12/0815 takes precedence

Abstract

Apparatus for avoiding ambiguous data in a multi-requestor computing system of the type wherein each of the requestors has its own dedicated cache memory. Each requestor has access to its own dedicated cache memory for purposes of ascertaining whether a particular data word is present in its cache memory and of obtaining that data word directly from its cache memory without the necessity of referencing main memory. Each requestor also has access to all other dedicated cache memories for purposes of invalidating a particular data word contained therein when that same particular data word has been written by that requestor into its own dedicated cache memory. Requestors and addresses in a particular cache memory are time multiplexed in such a way as to allow a particular dedicated cache memory to service invalidate requests from other requestors without sacrificing speed of reference or cycle time of the particular dedicated cache memory from servicing read requests from its own requestor.

Claims

1. In a computer system including a plurality of requestors, each requestor being a resident requestor to its own dedicated cache memory but a non-resident requestor to the dedicated cache memories of the other requestors of the computer system, the cache memories storing copies of data words that are stored in a main memory, the improvement wherein each of said dedicated cache memories comprises:

data buffer means having a plurality of addressable locations therein for storing a plurality of data words thereat and having a first, relatively slow, memory cycle;

tag buffer means having a plurality of addressable locations therein for storing a data word address and an associated invalidate bit at each of said addressable locations and having a second, relatively fast, memory cycle that is of substantially less duration than that of said first memory cycle;

selector means for alternatively coupling to said tag buffer means a first portion of a resident requestor address or a first portion of a non-resident requestor address for reading out the data word address and associated invalidate bit that are stored in said tag buffer means at the addressed addressable location;

resident requestor comparator means coupled to a second portion of said resident requestor address and to the data word address read out of said tag buffer means for generating a resident requestor match or mismatch signal;

non-resident requestor comparator means coupled to a second portion of said non-resident requestor address and to the data word address read out of said tag buffer means for generating a non-resident requestor match or mismatch signal;

invalidate bit bistable means for generating a data out gate signal upon the coupling thereto of a valid condition invalidate bit and a resident requestor match signal;

data out gating means coupled to said data buffer means and said invalidate bit bistable means for gating out a data word from said data buffer means only if the read out invalidate bit is in a valid condition and said resident requestor comparator means is generating a resident requestor match signal;

control means enabling said resident requestor comparator means to compare, during a first portion of a first one of said first memory cycles, the second portion of said resident requestor address of the data word address read out of said tag buffer means for generating said resident requestor match or mismatch signal, said resident requestor match signal enabling, in turn, said invalidate bit bistable means to gate said data word from said data buffer means through said data out gating means;

said control means enabling said non-resident comparator means to compare, during a second portion of said first one of said first memory cycles, the second portion of said non-resident requestor address to the data word address read out of said tag buffer means for generating said nonresident requestor match or mismatch signal; and

,

said non-resident requestor comparator means match signal conditioning said control means to set, during a second portion of a second, subsequent one of said first memory cycles, the invalidate bit of the addressed addressable location in said tag buffer means to an invalid condition.

2. In a computer system including a plurality of requestors, each requestor being a resident requestor to its own dedicated cache memory but a non-resident requestor to the dedicated cache memories of the other requestors of the computer system, the cache memories storing copies of data words that are stored in a main memory, the improvement wherein each of said dedicated cache memories comprises:

data buffer means having a plurality of addressable locations therein for storing a plurality of data words thereat and having a first, relatively slow, memory cycle;

tag buffer means having a plurality of addressable locations therein for storing a data word address and an associated invalidate bit at each of said addressable locations and having a second, relatively fast, memory cycle that is less than one half that of said first memory cycle;

resident requestor address register means for storing the address of a data word requested by its resident requestor;

non-resident requestor address register means for storing the address of a data word that is requested by a non-resident requestor of said plurality of requestors;

selector means for alternatively coupling to said tag buffer means a first portion of said resident requestor address or a first portion of said non-resident requestor address for reading out the data word address and associated invalidate bit that are stored in said tag buffer means at the tag buffer means addressed addressable location;

resident requestor comparator means coupled to a second portion of said resident requestor address and to the data word address read out of said tag buffer means for generating a resident requestor match or mismatch signal;

non-resident requestor comparator means coupled to a second portion of said non-resident requestor address and to the data word address read out of said tag buffer means for generating a non-resident requestor match or mismatch signal;

invalidate bit gating means for generating a data out gate signal when a valid condition invalidate bit and a resident requestor match signal are coupled thereto;

data out gating means coupled to said data buffer means and said invalidate bit gating means for gating out the data word read out of said data buffer means to said resident requestor only if said data out gate signal is generated by said invalidate bit gating means;

control means enabling said resident requestor comparator means to compare, during the first half of a first one of said data buffer means'"'"' relatively slow first memory cycles, the second portion of said resident requestor address to the data word address read out of said tag buffer means for generating said resident requestor match or mismatch signal;

said control means enabling said non- resident comparator means to compare, during the second half of said first one of said data buffer means'"'"' relatively slow first memory cycles, the second portion of said non-resident requestor address to the data word address read from said tag buffer means for generating said non-resident requestor match or mismatch signal; and

,

said non-match requestor comparator means match signal conditioning said control means to set, during the second half of a second, subsequent one of said data buffer means'"'"' relatively slow first memory cycles, the invalidate bit of the addressed addressable location in said tag buffer means to an invalid condition.

3. In a computer system including a plurality of requestors, each requestor being a resident requestor to its own dedicated cache memory but a non-resident requestor to the dedicated cache memories of the other requestors of the computer system, the cache memories storing copies of data words that are stored in a main memory, the improvement wherein each of said dedicated cache memories comprises:

data buffer means having a plurality of addressable locations therein for storing a plurality of block of data words thereat and having a first, relatively slow, cycle time;

tag buffer means having a plurality of addressable locations therein for storing a plurality of data word addresses and associated invalidate bits thereat and having a second, relatively fast, cycle time that is approximately one half that of said first cycle time;

resident requestor address register means for storing the address of a data word requested by its resident requestor;

non-resident requestor address register means for storing the address of a data word that is requested by one of the other, non-resident, requestors of said plurality of requestors;

selector means for alternatively coupling to said tag buffer means a first portion of said resident requestor address from said resident requestor address register means or a first portion of said non-resident requestor address from said non-resident requestor address register means for reading out the data word address and associated invalidate bit that are stored in said tag buffer means at the tag buffer means addressed addressable location;

resident requestor comparator means coupled to said tag buffer means and said resident requestor address register means for comparing a second portion of said resident requestor address from said resident requestor address register means to the data word address read out of said tag buffer means and generating a resident requestor match or mismatch signal;

non-resident requestor comparator means coupled to said tag buffer means and said non-resident requestor address register means for comparing a second portion of said nonresident requestor address from said non-resident requestor address register means to the data word address read out of said tag buffer means and generating a non-resident requestor match or mismatch signal;

invalidate bit gating means coupled to said resident requestor comparator means and said tag buffer means for generating a data out gate signal upon the coupling thereto of a valid condition invalidate bit from said tag buffer means and a resident requestor match signal from non-resident requestor comparator means;

data out gating means coupled to said data buffer means and said invalidate bit gating means for gating out the data word read out of said data buffer means to said resident requestor only if said data out gate signal is generated by said invalidate bit gating means;

control means enabling said resident requestor comparator means to compare, during the first half of said data buffer means'"'"' relatively slow first cycle time, the second portion of said resident requestor address from said resident requestor address register means to the data word address from said tag buffer means for generating said resident requestor match or mismatch signal;

said control means enabling said non-resident comparator means to compare, during the second half of said data buffer means'"'"' relatively slow first cycle time, the second portion of said non-resident requestor address from said non-resident requestor address register means to the data word address from said tag buffer means for generating said non-resident requestor match or mismatch signal; and

,

said non-resident requestor match signal conditioning said control means to set, during the second half of a subsequent one of said data buffer means'"'"' relatively slow first cycle time, the invalidate bit of the addressed addressable location in said tag buffer means to an invalid condition.

4. In a computer system including a plurality of requestors, each requestor being a resident requestor to its own dedicated cache memory but a non-resident requestor to the dedicated cache memories of the other requestors of the computer system, the cache memories storing copies of data words that are stored in a main memory, the improvement wherein each of said dedicated cache memories comprises:

data buffer means having a plurality of addressable locations therein for storing a plurality of blocks of data words thereat and having a first, relatively slow, cycle time;

tag buffer means having a plurality of addressable locations therein for storing a plurality of data word addresses and associated invalidate bits thereat and having a second, relatively fast, cycle time that is approximately one half that of said first cycle time;

resident requestor address register means for storing the address of a data word requested by its resident requestor;

non-resident requestor address register means for storing the address of a data word that is requested by one of the other, non-resident, requestors of said plurality of requestors;

selector means for alternatively coupling to said tag buffer means a first portion of said resident requestor address from said resident requestor address register means or a first portion of said non-resident requestor address from said non-resident requestor address register means for reading out the data word address and associated invalidate bit that are stored in said tag buffer means at the tag buffer means addressed addressable location;

resident requestor comparator means;

non-resident requestor comparator means;

means coupling said first portion of said resident requestor address from said resident requestor address register means to said data buffer means for reading out the data word stored in said data buffer means at the data buffer means addressed addressable location;

means coupling said read out data word address from said tag buffer means to said resident requestor comparator means and to said non-resident requestor comparator means;

means coupling a second portion of said resident requestor address from said resident requestor address register means to said resident requestor comparator means for comparing the addresses coupled thereto and generating a resident requestor match or mismatch signal;

means coupling a second portion of said non-resident requestor address from said non-resident requestor address register means to said non-resident requestor comparator means for comparing the addresses coupled thereto and generating a non-resident requestor match or mismatch signal;

invalidate bit gating means;

means coupling the resident requestor match or mismatch signal from said resident requestor comparator means to said invalidate bit gating means;

means coupling the invalidate bit read out of said tag buffer means to said invalidate bit gating means for enabling the resident requestor match signal from said resident requestor comparator means to generate a data out gate signal;

data out gating means;

means coupling the read out data word from said data buffer means to said data out gating means;

means coupling the data out gate signal from said invalidate bit gating means to said data out gating means for gating out the read out data word from said data buffer means to said resident requestor;

control means coupling a select resident requestor signal to said selector means during the first half of said data buffer means'"'"' relatively slow first cycle time and enabling said selector means to couple said first portion of the resident requestor address from said resident requestor address register means to said tag buffer means for addressing the associated addressable location in said tag buffer means and coupling the read out resident requestor address to said resident requestor comparator means and coupling the associated invalidate bit to said invalidate bit gating means for enabling said data out gating means to gate out the readout data word from said data buffer means to said resident requestor if said invalidate bit is in a valid condition; and

,

said control means coupling a select non-resident requestor signal to said selector means during the second half of said data buffer means'"'"' relatively slow cycle time and enabling said selector means to couple said first portion of the nonresident requestor address from said non-resident requestor address means to said tag buffer means for addressing the associated addressable location in said tag buffer means and coupling the read out non-resident requestor address to said non-resident requestor comparator means and coupling the nonresident requestor match or mismatch signal to said control means, a non-resident requestor match signal conditioning said control means to enable said non-resident requestor, during the second half of the next subsequent data buffer means'"'"' relatively slow first cycle time of said resident requestor means, to set the invalidate bit of the non-resident requestor addressed addressable location in said data buffer means to an invalid condition.

5. In a computer system including a like plurality of requestors and dedicated cache memories, each requestor being a resident requestor to its own dedicated cache memory but a non-resident requestor to the dedicated cache memories of the other requestors of the computer system, each cache memory storing copies of data words that are stored in a main memory at addressable locations in a data buffer and storing address words and associated invalidate bits at addressable locations in a tag buffer, each of said address words associated with different ones of said data words, the method of preventing an ambiguous data word being accessed by a resident requestor from its dedicated cache memory when such data word is made ambiguous by an operation of a non-resident requestor, comprising:

during a first half of a first one of said resident requestor data buffer'"'"'s memory cycles,

coupling a first portion of a resident requestor address to its tag buffer and to its data buffer for reading out the data word address and its associated invalidate bit from its tag buffer and the data word from its data buffer;

comparing said first portion of said resident requestor address to the data word address that was read out of said tag buffer by said first portion of said resident requestor address;

generating a resident requestor match or mismatch signal from said comparison;

combining the invalidate bit, which was read out of said resident requestor tag buffer by said first portion of said resident requestor address, and said resident requestor match signal for subsequently, during the second half of said first one of said resident requestor data buffer'"'"'s memory cycle, gating out the data word from said resident requestor data buffer that was addressed by said first portion of said resident requestor address only if said combination is affected by a valid condition invalidate bit;

during the second half of said first one of said resident requestor data buffer'"'"'s memory cycles,

coupling a first portion of a non-resident requestor address to said resident requestor tag buffer for addressing the data word address and its associated invalidate bit; and

,

setting said addressed invalidate bit to an invalid condition for preventing the gating out of the data word from said resident requestor data buffer upon the subsequent addressing of the associated data word by the resident requestor address.

6. In a computer system including a like plurality of requestors and dedicated cache memories, each requestor being a resident requestor to its own dedicated cache memory but a non-resident requestor to the dedicated cache memories of the other requestors of the computer system, each cache memory storing copies of data words that are stored in a main memory at addressable locations in a data buffer and storing address words and associated invalidate bits at addressable locations in a tag buffer, each of said address words associated with different ones of said data words, the method of preventing an ambiguous data word from being accessed by a resdident requestor from its dedicated cache memory when such data word is made ambiguous by an operation of a non-resident requestor, comprising:

during a first half of a first one of said resident requestor data buffer'"'"'s memory cycles,

coupling a first portion of a resident requestor address to its tag buffer and to its data buffer for reading out the data word address and its associated invalidate bit from its tag buffer and the data word from its data buffer;

comparing the data word address read from said tag buffer to a second portion of said resident requestor address;

generating a resident requestor match or mismatch signal from said comparison;

combining the invalidate bit which was read out of said resident requestor tag buffer by said first portion of said resident requestor address, and said resident requestor match signal;

during the second half of said first one of said resident requestor data buffer memory cycles,

coupling a first portion of a non-resident requestor address to said resident requestor tag buffer for reading out the data word address and its associated invalidate bit from said resident requestor tag buffer;

comparing a second portion of said non-resident requestor address to the data word address that was read out of said resident requestor tag buffer by said first portion of said non-resident requestor address;

generating a non-resident requestor match or mismatch signal from said comparison;

gating out the data word from said resident requestor data buffer that was addressed by said first portion of said resident requestor address only if said combination of said invalidate bit and said resident requestor match signal is affected by a valid condition invalidate bit;

during a first half of a second one, subsequent to said first one, of said resident requestor data buffer'"'"'s memory cycles,

coupling a first portion of a resident requestor address to its tag buffer and to its data buffer for reading out the data word address and its associated invalidate bit from its tag buffer and the data word from its data buffer;

comparing the data word address read from said tag buffer to a second portion of said resident requestor address;

generating a resident requestor match or mismatch signal from said comparison;

during the second half of said second one of said resident requestor data buffer'"'"'s memory cycles,

coupling said first portion of said non-resident requestor address to said resident requestor tag buffer for addressing the data word address and its associated invalidate bit;

setting said addressed invalidate bit to an invalid condition if said comparison of said second portion of said non-resident requestor address to the data word address that was read out of said resident requestor tag buffer by said first portion of said nonresident requestor address generated said non-resident match signal for preventing the gating out of the data word from said resident requestor data buffer upon subsequent addressing of the associated data word by the resident requestor address.