Method and apparatus for resolving probes in multi-processor systems which do not use external duplicate tags for probe filtering

A computing apparatus for multiplexing a full probe with a plurality of tag-only probes, comprising:

• a clock producing a plurality of clock cycles;
• a cache comprising:
• a tag structure which in response to a probe transfers tag information in a clock cycle;
• a data structure which in response to a probe transfers data during multiple clock cycles of the plurality of clock cycles;
• an input stream configured to accept a plurality of probes directed to cache;
• a selector configured to designate each one of the plurality of probes in the input stream to be one of a full probe and a tag-only probe;
• a multiplexer configured to access the data structure with one of the probes designated a full probe to transfer data during the multiple clocks cycles, and the multiplexer further configured to access the tag structure with one or more of the probes designated tag-only probes during the multiple clock cycles, each one of the tag-only probes accessing the tag structure to transfer tag information during a respective one of the multiple clock cycles;
• a probe queue for storing probes;
• and
• wherein the selector designates the proben from the input stream in two stages wherein in the first stage the selector designates the probe the input stream to be a tag-only probe, and, if the probe in response to an access to the tag structure returns tag information indicating a cache hit, the probe is put on a probe queue, and in the second stage the selector further designates the probe from the probe queue to be a full probe so that the multiplexer accesses the data structure with the probe.

A computing apparatus for multiplexing a full probe with a plurality of tag-only probes, comprising:

• a clock producing a plurality of clock cycles;
• a cache comprising:
• a tag structure which in response to a probe transfers tag information in a clock cycle;
• a data structure which in response to a probe transfers data during multiple clock cycles of the plurality of clock cycles;
• an input stream configured to accept a plurality of probes directed to cache;
• a selector configured to designate each one of the plurality of probes in the input stream to be one of a full probe and a tag-only probe;
• and
• a multiplexer coupled to said cache via independent tag structure and data structure select signals and configured to access the data structure with one of the probes designated a full probe to transfer data during the multiple clocks cycles, and the multiplexer further configured to access the tag structure with one or more of the probes designated tag-only probes during the multiple clock cycles, each one of the tag-only probes accessing the tag structure to transfer tag information during a respective one of the multiple clock cycles;
• wherein the multiple clock cycles equals four;
• the selector is configured to designate one probe in the input stream to be a full probe and three probes in the input stream to be tag-only probes;
• and
• the multiplexer is configured to access the data structure corresponding to the full probe to transfer data during the four clocks, and the multiplexer is further configured to access the tag structure in a clock cycle of the multiple clock cycles corresponding to each of one of the tag-only probes during three clock cycles of the four clock cycles.

A computing apparatus for multiplexing a full probe with a plurality of tag-only probes, comprising:

• a clock producing a plurality of clock cycles;
• a cache comprising:
• a tag structure which in response to a probe transfers tag information in a clock cycle;
• a data structure which in response to a probe transfers data during multiple clock cycles of the plurality of clock cycles;
• an input stream configured to accept a plurality of probes directed to cache;
• a selector configured to designate each one of the plurality of probes in the input stream to be one of a full probe and a tag-only probe;
• and
• a multiplexer configured to access the data structure with one of the probes designated a full probe to transfer data during the multiple clocks cycles, and the multiplexer further configured to access the tag structure with one or more of the probes designated tag-only probes during the multiple clock cycles, each one of the tag-only probes accessing the tag structure to transfer tag information during a respective one of the multiple clock cycles;
• a tag bus receiving a tag stream of tag information from the tag structure in responese to the corresponding plurality of probes;
• and
• a probe history counter having values 0 through 3 and wherein upon detecting a cache hidt from the tag stream the probe history counter is set to the value 3 and upon detecting a miss from the tag stream the probe history counter is determined by 1 and if a miss is detected while the probe history counter has value 0 then the probe history counter remains at 0;
• amd
• wherein the selector selects a probe to be a tag-only probe if the probe history counter is 0 and a full probe if the probe history counter is other than 0.

A method of probing a cache having a tag structure and data structure, comprising:

• forming an input stream of a plurality of probes directed to the cache;
• selecting each one of the plurality of probes in the input stream to be one of a full probe and a tag-only probe;
• accessing the data structure with one of the probes designated a full probe to transfer data during multiple clocks cycles of a clock;
• and
• accessing the tag structure with one or more of the probes designated tag-only probes during the multiple clock cycles, each one of the tag-only probes accessing the tag structure to transfer tag information during one of the multiple clock cycles;
• wherein each one of the plurality of probes from the input stream are designated as tag-only probes and after accessing the tag structure if the response for the one of the probes indicates a cache hit;
• then
• further comprising:
• storing the one of the probes indicating a cache hit on a probe queue;
• selecting each one of the probes on the probe queue to be a full probe;
• and
• accessing the data structure with each one of the probes on the probe queue.

A method of probing a cache having a tag structure and data structure, comprising:

• forming an input stream of a plurality of probes directed to the cache;
• selecting each one of the plurality of probes in the input stream to be one of a full probe and a tag-only probe;
• accessing the data structure with one of the probes designated a full probe to transfer data during multiple clocks cycles of a clock;
• and
• accessing the tag structure with one or more of the probes designated tag-only probes during the multiple clock cycles, each one of the tag-only probes accessing the tag structure to transfer tag information during one of the multiple clock cycles;
• receiving a tag stream of tag information responses from the tag structure in response to the corresponding plurality of probes;
• setting a counter upon detecting a cache hit from one of the responses of the tag stream to the value of 3 and upon detecting a miss from one of the responses of the tag stream decrementing the counter by 1 and if a miss is detected while the counter has a value 0 then keeping the counter at 0;
• and
• wherein in the selecting step a probe from the input stream is selected to be a tag-only probe if the counter is 0 and a full probe if the counter is not 0.

A multiprocessor system for resolving probes, comprising:

• a main memory configured to store information;
• memory controller, coupled to the main memory;
• and
• a plurality of processors, each processor coupled to the memory controller, a first one of the processors including:
• a clock producing a plurality of clock cycles;
• a cache comprising:
• a tag structure which in response to a probe transfers tag information in a clock cycles;
• a data structure which in response to a probe transfers data during multiple clock cycles of the plurality of clock cycles;
• an input stream configured to accept a plurality of probes directed to the cache;
• a selector configured to designate each one of the plurality of probes in the input stream to be one of a full probe and a tag-only probe;
• and
• a multiplexer configured to access the data structure with one of the probes designated a full probe to transfer data during the multiple clocks cycles, and the multiplexer further configured to access the tag structure with one or more of the probes designated tag-only probes during the multiple clock cycles, each one of the tag-only probes accessing the tag structure to transfer tag information during a respective one of the multiple clock cycles;
• wherein the selector selects the probe from the input stream in two stages wherein in the first stage the selector selects the probe to be a tag-only probe and only if the probe returns tag information indicating a cache hit the selector in the second stage selects the probe to be a full probe.

A multiprocessor system for resolving probes, comprising:

• a main memory configured to store information;
• memory controller, coupled to the main memory;
• and
• a plurality of processors, each processor coupled to the memory controller, a first one of the processors including:
• a clock producing a plurality of clock cycles;
• a cache comprising:
• a tag structure which in response to a probe transfers tag information in a clock cycles;
• a data structure which in response to a probe transfers data during multiple clock cycles of the plurality of clock cycles;
• an input stream configured to accept a plurality of probes directed to the cache;
• a selector configured to designate each one of the plurality of probes in the input stream to be one of a full probe and a tag-only probe;
• and
• a multiplexer configured to access the data structure with one of the probes designated a full probe to transfer data during the multiple clocks cycles, and the multiplexer further configured to access the tag structure with one or more of the probes designated tag-only probes during the multiple clock cycles, each one of the tag-only probes accessing the tag structure to transfer tag information during a respective one of the multiple clock cycles;
• wherein the first processor further comprises:
• a tag bus receiving a tag stream of tag information from the tag structure in response to the corresponding plurality of probes;
• and
• a probe history counter having values 0 through 3 and wherein upon detecting a cache hit from the tag stream the probe history counter is set to the value 3 and upon detecting a miss from the tag stream the probe history counter is decremented by 1 and if a miss is detected while the probe history counter has value 0 then the probe history counter remains at 0;
• and
• wherein the selector selects a probe to be a tag-only probe if the probe history counter is 0 and a full probe if the probe history counter is not 0.