Speed efficient cache output selector circuitry based on tag compare and data organization

• US 5,854,943 A
• Filed: 08/07/1996
• Issued: 12/29/1998
• Est. Priority Date: 08/07/1996
• Status: Expired due to Term

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Ziemkowski, Ted B., McBride, John G.
• Primary Examiner(s): Swann, Tod R.
• Assistant Examiner(s): Lee, Felix B.
• Application Number:
  US08/689,173
• Time in Patent Office: 874 Days
• Field of Search: 711/128, 395/871
• US Class Current: 710/51
• CPC Class Codes: G06F 12/0864 using pseudo-associative means, e.g. set-associative or hashing
• CPC Class Codes: G06F 12/0886 Variable-length word access

Abstract

A cache output selector for a multi-way set-associative cache memory which provides for simultaneous access of multiple-word data is presented. The cache memory comprises a plurality of data arrays wherein no two consecutive multiple-word reside in the same data. The cache output selector of the present invention includes, for each data array of the plurality of data arrays, a qualifying multiplexor which receives the respective tag match signals from each of the tag matching circuits as data input and a set selector signal, as selector input, and at least one qualifying signal as qualifying input. The set selector signal indicates which data array a first set of the multi-way set-associative memory resides in during a current read/write cycle. The qualifying multiplexor combines a clock qualifying functionality and a multiplexor functionality to produce a data array output enable signal in only two levels of logic. The cache memory comprises a prefetch buffer path and a bypass path from which the cache output selector selects an addressed multi-word for output. The output path selected circuit includes a pair of qualifying NOR gates. Each qualifying NOR gate combines a clock qualifying functionality and a logical NOR functionality to produce a qualified prefetch buffer path output enable signal and a qualified bypass path output enable signal respectively.

Claims

1. A cache output selector for a multi-way set-associative cache memory, said cache memory for storing a plurality of lines of data, each line data containing a plurality of words of data, and for providing for simultaneous access of words grouped as a multiple-word, said cache memory comprising a plurality of data arrays wherein consecutive multiple-words of each line of data in the plurality of lines of data reside in different data arrays in the plurality of data arrays, said cache memory comprising a switchably selectable output path for outputting an addressed multiple-word either via a pre-fetch buffer path from a set of pre-fetch latches or via a bypass path which bypasses said set of pre-fetch latches said cache output selector comprising:

for each data array of the plurality of data arrays, a tag matching circuit for checking whether an addressed multiple-word resides in the data array and for producing a tag match signal to indicate whether the addressed multiple-word resides in the data array;

a qualifying tag match circuit which receives the respective tag match signals from each of the tag matching circuits and produces respective qualified tag match signals for each of the tag matching signals;

for each data array of the plurality of data arrays, a qualifying multiplexor which receives the respective qualified tag match signals from the qualifying tag matching circuit as data inputs, a set selector signal which selects one of said data inputs for output, and at least one qualifying signal used to qualify when said qualifying multiplexor outputs said selected data input as a qualified data array output enable signal; and

a qualifying output path select circuit which receives said respective tag match signals from each of said tag matching circuits as data input, said at least one qualifying signal as a qualifying input, and an output path select signal as a select input, said qualifying output path select circuit selecting one of said prefetch path or said bypass path from which to output said addressed multiple-word and qualifying an output enable signal.

2. The cache output selector of claim 1, said qualifying tag match circuit comprising a plurality of NAND gates, one each corresponding to each tag match signal and each receiving all of the plurality of tag match signals and wherein the tag match signal corresponding to the NAND gate is inverted before input to the NAND gate, and each NAND gate producing a respective qualified tag match signal of its corresponding tag match signal.

3. The cache output selector of claim 1, said at least one qualifying signal comprising:

a first clock signal; and

a second clock signal.

4. The cache output selector of claim 1, said qualifying multiplexor comprising two levels of logic.

5. The cache output selector of claim 1 said qualifying multiplexor comprising:

a plurality of transfer gates, one each corresponding to each qualifified tag match signal, each transfer gate having a transfer gate input to receive an input signal, a transfer gate output to produce an output signal, and a transfer gate control means to control whether the input signal received at the transfer gate input is transferred to the transfer gate output, and wherein each transfer gate receives its corresponding qualified tag match signal as its input signal;

a selector means responsive to the set selector signal for selecting one selected transfer gate from the plurality of transfer gates, signaling the transfer gate control means of the selected transfer gate to transfer its input signal to its transfer gate output to produce a selected transfer signal;

a NAND gate connected to receive said at least one qualifying signal and to produce a NAND gate output signal; and

a NOR gate connected to receive the selected transfer signal and the NAND gate output signal, which produces said qualified data array output enable signal.

6. The cache output selector of claim 1, said qualifying multiplexor comprising:

a NAND gate connected to receive said at least one qualifying signal and to produce a NAND gate output signal; and

a plurality of NOR gates, one each corresponding to each qualified tag match signal, each NOR gate connected to receive its respective qualified tag match signal and the NAND gate output signal, and each producing a qualified data array output enable signal.

7. The cache output selector of claim 1 said qualifying output path select circuit comprising:

a NAND gate which receives said output path select signal and each of the respective tag match signals from each of the tag matching circuits and produces an output path NAND output signal;

a qualifying NOR gate which receives the output path NAND output signal and said at least one qualifying signal, wherein said qualifying NOR gate combines a clock qualifying functionality and a logical NOR functionality to produce a qualified output select path enable signal.

8. The cache output selector of claim 7, said qualifying NOR gate comprising a speed-critical enable path of one level of logic.

9. The cache output selector of claim 7, said qualifying NOR gate comprising:

a NAND gate connected to receive said at least one qualifying signal, which produces a NAND gate output signal; and

a NOR gate connected to receive the output select path enable signal and the NAND gate output signal, which produces a qualified output select path enable signal.

10. The cache output selector of claim 7, said prefetch buffer path comprising:

a plurality of prefetch buffers, each for storing a multiple-word, and

a prefetch buffer multiplexor connected to receive the contents of each of the plurality of prefetch buffers, for selecting and outputting the contents of one of the plurality of prefetch buffers.

11. The cache output selector of claim 1, said output path select signal comprising a prefetch buffer path select signal and a bypass path select signal, said output path enable signal comprising a prefetch buffer path output enable signal and a bypass path output enable signal, said qualifying output path select circuit comprising:

a first NAND gate connected to receive each of the respective tag match signals from each of the tag matching circuits and said prefetch buffer path select signal, and which produces a prefetch buffer path NAND output signal;

a first qualifying NOR gate connected to receive the prefetch buffer path NAND output signal and said at least one qualifying signal, which produces said qualified prefetch buffer path output enable signal;

a second NAND gate connected to receive each of the respective tag match signals from each of the tag matching circuits and said bypass path select signal, and which produces a bypass path NAND output signal;

a second qualifying NOR gate connected to receive the bypass path NAND output signal and said at least one qualifying signal, which produces said qualified bypass path output enable signal;

wherein said first qualifying NOR gate and said second qualifying NOR gate each combine a clock qualifying functionality and a logical NOR functionality to produce said qualified prefetch buffer path output enable signal and said qualified bypass path output enable signal.

12. The cache output selector of claim 11, wherein:

said first qualifying NOR gate comprises;

a third NAND gate connected to receive said at least one qualifying signal, which produces a third NAND gate output signal; and

a first NOR gate connected to receive the prefetch buffer path output enable signal and the third NAND gate output signal, which produces said qualified prefetch buffer path output enable signal; and

said second qualifying NOR gate comprises;

a fourth NAND gate connected to receive said at least one qualifying signal, which produces a fourth NAND gate output signal; and

a second NOR gate connected to receive the bypass path output enable signal and the fourth NAND gate output signal, which produces said qualified prefetch buffer path output enable signal.

13. The cache output selector of claim 11, said prefetch buffer path comprising a plurality of prefetch buffers, each for storing a multiple-word, and

a prefetch buffer multiplexor having a plurality of inputs connected to receive the contents of each of the plurality of prefetch buffers, a selection input responsive to a selection signal for selecting a selected input from among the plurality of inputs, and a prefetch buffer multiplexor output upon which the selected input is produced as data for the prefetch buffer path.

14. The cache output selector of claim 11, said bypass path comprising a direct bypass line from the input of the prefetch buffer path from which the addressed multiple-word may be selected for output from the cache memory by the cache output selector.

15. A qualifying multiplexor circuit comprising:

a plurality of transfer gates, each coupled to receive a data input signal and each comprising a transfer gate control means for controlling whether its respective data input signal is output as a transfer gate output;

a selector means responsive to a selector signal for selecting one of said plurality of transfer gates and causing said transfer gate control means of said selected transfer gate to transfer its data input signal to its respective transfer gate to produce a selected transfer signal;

a NAND gate connected to receive at least one qualifying signal and which produces a NAND gate output signal; and

a NOR gate connected to receive the selected transfer signal and the NAND gate output signal, which produces the qualified multiplexor output signal.

16. The qualifying multiplexor circuit of claim 15, said at least one qualifying signal comprising:

a first clock signal, a second clock signal, and a qualifier signal.

17. A qualifying NOR circuit, comprising:

a plurality of data inputs, a first clock signal input, a second clock signal input, and a qualifier signal input, said qualifying NOR circuit combining a clock qualifying functionality and a logical NOR functionality to produce a qualified NOR output signal.

18. The qualifying NOR circuit of claim 17, comprising:

a NAND gate connected to receive the first clock signal, the second clock signal, and the qualifier signal, which produces a NAND gate output signal; and

a NOR gate connected to receive the plurality of data input signals and the NAND gate output signal, which produces the qualified NOR output signal.