DETAILED ACTION
Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Claims 1-2 and 4-20 are pending in this office action and presented for examination. Claims 1-2, 4-17, and 20 are newly amended, and claim 3 is newly cancelled, by the response received February 17, 2026.
Claim Rejections - 35 USC § 102
The following is a quotation of the appropriate paragraphs of 35 U.S.C. 102 that form the basis for the rejections under this section made in this Office action:
A person shall be entitled to a patent unless –
(a)(1) the claimed invention was patented, described in a printed publication, or in public use, on sale, or otherwise available to the public before the effective filing date of the claimed invention.
Claim(s) 1-2, 14, and 17 is/are rejected under 35 U.S.C. 102(a)(1) as being anticipated by Shah et al. (Shah) (US 20120290821 A1).
Consider claim 1, Shah discloses an apparatus ([0084], line 3, processor 10) comprising: default prediction hardware circuitry ([0084], line 9, branch predictor 330), responsive to an address associated with a given branch instruction ([0090], lines 3-5, when a CTI is encountered in a group of instructions, the address of that CTI is provided to both predictor 330 and predictor 340; [0087], lines 7-15, fetch address block 320 also provides information (e.g., a key or address) to look up information in branch predictors 330 and 340, discussed below. In one embodiment, the key provided from block 320 to predictor 330 includes the address provided to instruction cache 312, along with an identification of a current thread. In one embodiment, the key provided from block 320 to predictor 340 is a hash of the address provided to instruction cache 312 with the global branch history), to generate a default prediction of a target address for the given branch instruction ([0090], lines 5-9, each predictor generates corresponding branch prediction information for the CTI. Thus, for a particular CTI (e.g., for the same occurrence of a branch instruction), direction and/or target information may be generated by both predictor 330 and predictor 340; [0086], lines 11-14, IFU 310 is configured to use branch prediction information to facilitate the fetching of instructions. In some embodiments, this prediction information may include predicted branch directions, predicted target addresses, etc.); further prediction hardware circuitry ([0084], line 9, branch predictor 340) arranged, when the given branch instruction is a given type of branch instruction ([0084], lines 12-15, determine whether those instructions include a control transfer instruction (non-limiting examples of CTIs include branches, calls, jumps, returns, and trap instructions); [0058], lines 7-11, IFU 200 may be configured to predict the direction and target of CTIs (or, in some embodiments, a subset of the CTIs that are defined for an ISA) in order to reduce the delays incurred by waiting until the effect of a CTI is known with certainty), to generate a further prediction of the target address for the given branch instruction ([0090], lines 5-9, each predictor generates corresponding branch prediction information for the CTI. Thus, for a particular CTI (e.g., for the same occurrence of a branch instruction), direction and/or target information may be generated by both predictor 330 and predictor 340; [0086], lines 11-14, IFU 310 is configured to use branch prediction information to facilitate the fetching of instructions. In some embodiments, this prediction information may include predicted branch directions, predicted target addresses, etc.), wherein the further prediction is generated later than the default prediction ([0091], lines 1-8, in general, one of the predictors (here, predictor 330) is configured to generate its prediction information before the other predictor. Accordingly, the two predictors can be distinguished by making some reference to the relative timing of their prediction outputs. As used herein, the later predictor (340) is referred to in some instances as the "delayed" predictor, although the other predictor (330) could just as easily be referred to as the "early" predictor; [0084], lines 19-23, predictor 330 may be lower latency than 340; accordingly, prediction information determined by predictor 330 can be used to go ahead and fetch a target address while prediction information is still being determined by predictor 340) and is used in place of the default prediction in the event that the further prediction differs from the default prediction ([0102], lines 1-9, the respective prediction information generated by BTC 430 and DBP 460 is presented to branch prediction selection unit 480. In one embodiment, the prediction information generated by DBP 460 controls or trumps the prediction information produced by BTC 430. Thus, if BTC 430 predicted a branch to be taken and DBP 460 predicts that the branch not to be taken, unit 480 selects the DBP 460 outputs as branch prediction output information 482 and conveys it to the IFU; [0084], lines 19-23, predictor 330 may be lower latency than 340; accordingly, prediction information determined by predictor 330 can be used to go ahead and fetch a target address while prediction information is still being determined by predictor 340); and monitoring hardware circuitry responsive to detecting an update condition based on monitoring an observed indication of the target address for multiple occurrences of the given branch instruction, to cause the default prediction hardware circuitry to be updated so as to alter the default prediction generated by the default prediction hardware circuitry for the given branch instruction ([0028], lines 5-8, the predicted program flow and/or information stored in the first branch prediction unit may be updated once the prediction information generated by the second branch prediction unit is generated; [0093], lines 1-8, in one embodiment, IFU 310 includes an update unit 350 that is configured to receive the results of predictors 330 and 340 and update predictor 330 accordingly. Thus, where predictor 330's results are inconsistent with those of predictor 340, information in predictor 330 may be invalidated or updated. In this manner, the output of predictor 330 may be made more consistent with the output of predictor 340 upon a next occurrence of a particular CTI; [0102], lines 9-17, unit 480 also generates branch prediction update information 478 which is conveyed to unit 420 in order to update the tag and data array in the BTC in an appropriate fashion (e.g., by invalidating an entry so that it will no longer produce a hit, or by updating the data in an entry). In one embodiment, BTC 430 is updated so that on a next occurrence of the current CTI, the BTC will generate the results provided by the DBP for the current occurrence of the CTI. In this manner, the performance of the BTC may be improved; [0119], lines 11-14, even if both the first and second branch predictions indicate that a given CTI is predicted to be taken, a BTC update may still occur in step 730 if the respective targets of the predictions differ; [0100], lines 6-7, BTC 430 could generate this information without it first having been previously predicted by DBP 460; [0103], lines 11-12, the target of a predicted-taken CTI will be the same as its prior reference; [0110], lines 1-4, a table 600 is shown that sets forth a list of exemplary update actions that may be taken with respect to BTC 430 based upon the respective branch predictions generated by BTC 430 and DBP 460), wherein the monitoring hardware circuitry is arranged to detect the update condition based on performance of a test to assess, given the observed indication of the target address for multiple occurrences of the given branch instruction, whether an update of the default prediction is expected to improve accuracy of the default prediction ([0116], lines 1-9, as noted above, the set of BTC update actions described in table 600 correspond to only one possible embodiment. This set of actions is designed such that when the BTC produces predictions inconsistent with the DBP for a CTI, the BTC is updated such that it will produce consistent results upon a next occurrence of the CTI (e.g., during the next iteration of a loop). In this manner, incorrect predictions associated with the reduced-latency prediction of the BTC may be minimized; [0028], lines 5-8, the predicted program flow and/or information stored in the first branch prediction unit may be updated once the prediction information generated by the second branch prediction unit is generated; [0093], lines 1-8, in one embodiment, IFU 310 includes an update unit 350 that is configured to receive the results of predictors 330 and 340 and update predictor 330 accordingly. Thus, where predictor 330's results are inconsistent with those of predictor 340, information in predictor 330 may be invalidated or updated. In this manner, the output of predictor 330 may be made more consistent with the output of predictor 340 upon a next occurrence of a particular CTI; [0102], lines 9-17, unit 480 also generates branch prediction update information 478 which is conveyed to unit 420 in order to update the tag and data array in the BTC in an appropriate fashion (e.g., by invalidating an entry so that it will no longer produce a hit, or by updating the data in an entry). In one embodiment, BTC 430 is updated so that on a next occurrence of the current CTI, the BTC will generate the results provided by the DBP for the current occurrence of the CTI. In this manner, the performance of the BTC may be improved; [0119], lines 11-14, even if both the first and second branch predictions indicate that a given CTI is predicted to be taken, a BTC update may still occur in step 730 if the respective targets of the predictions differ; [0100], lines 6-7, BTC 430 could generate this information without it first having been previously predicted by DBP 460; [0103], lines 11-12, the target of a predicted-taken CTI will be the same as its prior reference; [0110], lines 1-4, a table 600 is shown that sets forth a list of exemplary update actions that may be taken with respect to BTC 430 based upon the respective branch predictions generated by BTC 430 and DBP 460).
Consider claim 2, Shah discloses an apparatus as claimed in Claim 1 (see above), wherein: the further prediction hardware circuitry is a history-dependent prediction hardware circuitry that is arranged to generate the further prediction in dependence on a program flow history of a program executed by processing hardware circuitry; and the given type of branch instruction is a polymorphic branch instruction whose target address varies in dependence on the program flow history ([0087], lines 13-15, the key provided from block 320 to predictor 340 is a hash of the address provided to instruction cache 312 with the global branch history; [0101], lines 10-11, DBP target address 468; [0119], lines 11-14, even if both the first and second branch predictions indicate that a given CTI is predicted to be taken, a BTC update may still occur in step 730 if the respective targets of the predictions differ; [0101], lines 11-12, DBP may implement any suitable branch prediction algorithm, methodology, or design structure).
Consider claim 14, Shah discloses an apparatus as claimed in Claim 1 (see above), wherein the observed indication of the target address comprises one of: the further prediction of the target address for the given branch instruction as generated by the further prediction hardware circuitry; an actual target address for the given branch instruction when executed by processing hardware circuitry ([0116], lines 1-9, as noted above, the set of BTC update actions described in table 600 correspond to only one possible embodiment. This set of actions is designed such that when the BTC produces predictions inconsistent with the DBP for a CTI, the BTC is updated such that it will produce consistent results upon a next occurrence of the CTI (e.g., during the next iteration of a loop). In this manner, incorrect predictions associated with the reduced-latency prediction of the BTC may be minimized; [0028], lines 5-8, the predicted program flow and/or information stored in the first branch prediction unit may be updated once the prediction information generated by the second branch prediction unit is generated; [0093], lines 1-8, in one embodiment, IFU 310 includes an update unit 350 that is configured to receive the results of predictors 330 and 340 and update predictor 330 accordingly. Thus, where predictor 330's results are inconsistent with those of predictor 340, information in predictor 330 may be invalidated or updated. In this manner, the output of predictor 330 may be made more consistent with the output of predictor 340 upon a next occurrence of a particular CTI; [0102], lines 9-17, unit 480 also generates branch prediction update information 478 which is conveyed to unit 420 in order to update the tag and data array in the BTC in an appropriate fashion (e.g., by invalidating an entry so that it will no longer produce a hit, or by updating the data in an entry). In one embodiment, BTC 430 is updated so that on a next occurrence of the current CTI, the BTC will generate the results provided by the DBP for the current occurrence of the CTI. In this manner, the performance of the BTC may be improved; [0119], lines 11-14, even if both the first and second branch predictions indicate that a given CTI is predicted to be taken, a BTC update may still occur in step 730 if the respective targets of the predictions differ; [0100], lines 6-7, BTC 430 could generate this information without it first having been previously predicted by DBP 460; [0103], lines 11-12, the target of a predicted-taken CTI will be the same as its prior reference; [0110], lines 1-4, a table 600 is shown that sets forth a list of exemplary update actions that may be taken with respect to BTC 430 based upon the respective branch predictions generated by BTC 430 and DBP 460).
Consider claim 17, Shah discloses a method of generating predictions of a target address of branch instructions ([0090], lines 5-9, each predictor generates corresponding branch prediction information for the CTI. Thus, for a particular CTI (e.g., for the same occurrence of a branch instruction), direction and/or target information may be generated by both predictor 330 and predictor 340; [0086], lines 11-14, IFU 310 is configured to use branch prediction information to facilitate the fetching of instructions. In some embodiments, this prediction information may include predicted branch directions, predicted target addresses, etc.), comprising: identifying an address associated with a given branch instruction of a given type; responsive to the address associated with the given branch instruction ([0084], lines 12-15, determine whether those instructions include a control transfer instruction (non-limiting examples of CTIs include branches, calls, jumps, returns, and trap instructions); [0058], lines 7-11, IFU 200 may be configured to predict the direction and target of CTIs (or, in some embodiments, a subset of the CTIs that are defined for an ISA) in order to reduce the delays incurred by waiting until the effect of a CTI is known with certainty; [0090], lines 3-5, when a CTI is encountered in a group of instructions, the address of that CTI is provided to both predictor 330 and predictor 340; [0087], lines 7-15, fetch address block 320 also provides information (e.g., a key or address) to look up information in branch predictors 330 and 340, discussed below. In one embodiment, the key provided from block 320 to predictor 330 includes the address provided to instruction cache 312, along with an identification of a current thread. In one embodiment, the key provided from block 320 to predictor 340 is a hash of the address provided to instruction cache 312 with the global branch history), generating using default prediction circuitry a default prediction of a target address for the given branch instruction ([0090], lines 5-9, each predictor generates corresponding branch prediction information for the CTI. Thus, for a particular CTI (e.g., for the same occurrence of a branch instruction), direction and/or target information may be generated by both predictor 330 and predictor 340; [0086], lines 11-14, IFU 310 is configured to use branch prediction information to facilitate the fetching of instructions. In some embodiments, this prediction information may include predicted branch directions, predicted target addresses, etc.); generating using further prediction circuitry ([0084], line 9, branch predictor 340) a further prediction of the target address for the given branch instruction ([0090], lines 5-9, each predictor generates corresponding branch prediction information for the CTI. Thus, for a particular CTI (e.g., for the same occurrence of a branch instruction), direction and/or target information may be generated by both predictor 330 and predictor 340; [0086], lines 11-14, IFU 310 is configured to use branch prediction information to facilitate the fetching of instructions. In some embodiments, this prediction information may include predicted branch directions, predicted target addresses, etc.), wherein the further prediction is generated later than the default prediction ([0091], lines 1-8, in general, one of the predictors (here, predictor 330) is configured to generate its prediction information before the other predictor. Accordingly, the two predictors can be distinguished by making some reference to the relative timing of their prediction outputs. As used herein, the later predictor (340) is referred to in some instances as the "delayed" predictor, although the other predictor (330) could just as easily be referred to as the "early" predictor; [0084], lines 19-23, predictor 330 may be lower latency than 340; accordingly, prediction information determined by predictor 330 can be used to go ahead and fetch a target address while prediction information is still being determined by predictor 340) and is used in place of the default prediction in the event that the further prediction differs from the default prediction ([0102], lines 1-9, the respective prediction information generated by BTC 430 and DBP 460 is presented to branch prediction selection unit 480. In one embodiment, the prediction information generated by DBP 460 controls or trumps the prediction information produced by BTC 430. Thus, if BTC 430 predicted a branch to be taken and DBP 460 predicts that the branch not to be taken, unit 480 selects the DBP 460 outputs as branch prediction output information 482 and conveys it to the IFU; [0084], lines 19-23, predictor 330 may be lower latency than 340; accordingly, prediction information determined by predictor 330 can be used to go ahead and fetch a target address while prediction information is still being determined by predictor 340); detecting an update condition based on monitoring an observed indication of the target address for multiple occurrences of the given branch instruction ([0028], lines 5-8, the predicted program flow and/or information stored in the first branch prediction unit may be updated once the prediction information generated by the second branch prediction unit is generated; [0093], lines 1-8, in one embodiment, IFU 310 includes an update unit 350 that is configured to receive the results of predictors 330 and 340 and update predictor 330 accordingly. Thus, where predictor 330's results are inconsistent with those of predictor 340, information in predictor 330 may be invalidated or updated. In this manner, the output of predictor 330 may be made more consistent with the output of predictor 340 upon a next occurrence of a particular CTI; [0102], lines 9-17, unit 480 also generates branch prediction update information 478 which is conveyed to unit 420 in order to update the tag and data array in the BTC in an appropriate fashion (e.g., by invalidating an entry so that it will no longer produce a hit, or by updating the data in an entry). In one embodiment, BTC 430 is updated so that on a next occurrence of the current CTI, the BTC will generate the results provided by the DBP for the current occurrence of the CTI. In this manner, the performance of the BTC may be improved; [0119], lines 11-14, even if both the first and second branch predictions indicate that a given CTI is predicted to be taken, a BTC update may still occur in step 730 if the respective targets of the predictions differ; [0100], lines 6-7, BTC 430 could generate this information without it first having been previously predicted by DBP 460; [0103], lines 11-12, the target of a predicted-taken CTI will be the same as its prior reference; [0110], lines 1-4, a table 600 is shown that sets forth a list of exemplary update actions that may be taken with respect to BTC 430 based upon the respective branch predictions generated by BTC 430 and DBP 460), wherein the update condition is detected based on performance of a test to assess, given the observed indication of the target address for multiple occurrences of the given branch instruction, whether an update of the default prediction is expected to improve accuracy of the default prediction ([0116], lines 1-9, as noted above, the set of BTC update actions described in table 600 correspond to only one possible embodiment. This set of actions is designed such that when the BTC produces predictions inconsistent with the DBP for a CTI, the BTC is updated such that it will produce consistent results upon a next occurrence of the CTI (e.g., during the next iteration of a loop). In this manner, incorrect predictions associated with the reduced-latency prediction of the BTC may be minimized; [0028], lines 5-8, the predicted program flow and/or information stored in the first branch prediction unit may be updated once the prediction information generated by the second branch prediction unit is generated; [0093], lines 1-8, in one embodiment, IFU 310 includes an update unit 350 that is configured to receive the results of predictors 330 and 340 and update predictor 330 accordingly. Thus, where predictor 330's results are inconsistent with those of predictor 340, information in predictor 330 may be invalidated or updated. In this manner, the output of predictor 330 may be made more consistent with the output of predictor 340 upon a next occurrence of a particular CTI; [0102], lines 9-17, unit 480 also generates branch prediction update information 478 which is conveyed to unit 420 in order to update the tag and data array in the BTC in an appropriate fashion (e.g., by invalidating an entry so that it will no longer produce a hit, or by updating the data in an entry). In one embodiment, BTC 430 is updated so that on a next occurrence of the current CTI, the BTC will generate the results provided by the DBP for the current occurrence of the CTI. In this manner, the performance of the BTC may be improved; [0119], lines 11-14, even if both the first and second branch predictions indicate that a given CTI is predicted to be taken, a BTC update may still occur in step 730 if the respective targets of the predictions differ; [0100], lines 6-7, BTC 430 could generate this information without it first having been previously predicted by DBP 460; [0103], lines 11-12, the target of a predicted-taken CTI will be the same as its prior reference; [0110], lines 1-4, a table 600 is shown that sets forth a list of exemplary update actions that may be taken with respect to BTC 430 based upon the respective branch predictions generated by BTC 430 and DBP 460); and responsive to detecting the update condition, causing the default prediction circuitry to be updated so as to alter the default prediction generated by the default prediction circuitry for the given branch instruction ([0028], lines 5-8, the predicted program flow and/or information stored in the first branch prediction unit may be updated once the prediction information generated by the second branch prediction unit is generated; [0093], lines 1-8, in one embodiment, IFU 310 includes an update unit 350 that is configured to receive the results of predictors 330 and 340 and update predictor 330 accordingly. Thus, where predictor 330's results are inconsistent with those of predictor 340, information in predictor 330 may be invalidated or updated. In this manner, the output of predictor 330 may be made more consistent with the output of predictor 340 upon a next occurrence of a particular CTI; [0102], lines 9-17, unit 480 also generates branch prediction update information 478 which is conveyed to unit 420 in order to update the tag and data array in the BTC in an appropriate fashion (e.g., by invalidating an entry so that it will no longer produce a hit, or by updating the data in an entry). In one embodiment, BTC 430 is updated so that on a next occurrence of the current CTI, the BTC will generate the results provided by the DBP for the current occurrence of the CTI. In this manner, the performance of the BTC may be improved; [0119], lines 11-14, even if both the first and second branch predictions indicate that a given CTI is predicted to be taken, a BTC update may still occur in step 730 if the respective targets of the predictions differ; [0100], lines 6-7, BTC 430 could generate this information without it first having been previously predicted by DBP 460; [0103], lines 11-12, the target of a predicted-taken CTI will be the same as its prior reference; [0110], lines 1-4, a table 600 is shown that sets forth a list of exemplary update actions that may be taken with respect to BTC 430 based upon the respective branch predictions generated by BTC 430 and DBP 460).
Claim Rejections - 35 USC § 103
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
Claim(s) 4-5, 8-13, and 15-16 is/are rejected under 35 U.S.C. 103 as being unpatentable over Shah as applied to claim 1 above, and further in view of Kothari et al. (Kothari) (US 20130311760 A1).
Consider claim 4, Shah discloses an apparatus as claimed in Claim 1 (see above), but does not disclose that the monitoring hardware circuitry is arranged to maintain a test counter for the given branch instruction, whose value is altered in dependence on the observed indication of the target address for multiple occurrences of the given branch instruction, and the test comprises determining whether the test counter has at least reached a predetermined value indicating presence of the update condition.
On the other hand, Kothari discloses monitoring hardware circuitry is arranged to maintain a test counter for a given branch instruction, whose value is altered in dependence on an observed indication of a target address for multiple occurrences of the given branch instruction, and a test comprises determining whether the test counter has at least reached a predetermined value indicating presence of a condition that a predicted target address of a first level predictor is not likely to be correct ([0027], lines 1-9, a confidence counter, such as confidence counter 326, is allocated for each entry of first level predictor 56 to help determine the difference between simple and polymorphic branches. The confidence counter is an X-bit saturating counter (where X is usually 2 or 3) that counts up or down based on the prediction accuracy of first level predictor 56. The lower saturation value of the counter is 0 and the upper saturation value is 2.sup.X-1. For example, a 2-bit counter can have a value from 0 to 3; [0028], lines 1-10, as an example, given a 2-bit confidence counter with an initial value of Y=2, when first level predictor 56 predicts the branch correctly, the counter is incremented and saturates to the high value mark (i.e. 3). A correct prediction means that the target address stored in first level predictor 56 for the PC was the correct target address. Similarly, when first level predictor 56 predicts the branch incorrectly, the counter is decremented (i.e. to 1). An incorrect prediction means that the target address stored in first level predictor 56 for the PC was not the correct target address; [0029], lines 1-5, when the counter reaches a value of Z (e.g. Z=0), it means there is no confidence in the ability of first level predictor 56 to predict that particular branch correctly. This means that the branch is not a "simple" indirect branch, but is rather a "polymorphic" indirect branch).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to combine the teaching of Kothari with the invention of Shah in order to result in more accurate and simpler prediction of simple branches via use of a confidence value to facilitate prediction of simple branches using a first level predictor when the first level predictor is likely to be correct. Note that Kothari’s teaching of monitoring hardware circuitry is arranged to maintain a test counter for a given branch instruction, whose value is altered in dependence on an observed indication of a target address for multiple occurrences of the given branch instruction, and a test comprises determining whether the test counter has at least reached a predetermined value indicating presence of a condition that a predicted target address of a first level predictor is not likely to be correct, when applied to the invention of Shah wherein a condition that a default prediction is not likely to be correct results in an updated prediction based on a further prediction circuitry, results in the overall claim limitation that the monitoring hardware circuitry is arranged to maintain a test counter for the given branch instruction, whose value is altered in dependence on the observed indication of the target address for multiple occurrences of the given branch instruction, and the test comprises determining whether the test counter has at least reached a predetermined value indicating presence of the update condition.
Consider claim 5, the overall combination entails an apparatus as claimed in Claim 4 (see above), wherein the monitoring hardware circuitry is arranged, for the given branch instruction, to store an indication of the default prediction of the target address generated by the default prediction hardware circuitry, to use the test counter to track occurrences of divergence of the observed indication of the target address from the default prediction, and to detect the update condition when the test counter reaches the predetermined value, wherein the predetermined value indicates that a mismatch threshold has been reached (Kothari, [0027], lines 1-9, a confidence counter, such as confidence counter 326, is allocated for each entry of first level predictor 56 to help determine the difference between simple and polymorphic branches. The confidence counter is an X-bit saturating counter (where X is usually 2 or 3) that counts up or down based on the prediction accuracy of first level predictor 56. The lower saturation value of the counter is 0 and the upper saturation value is 2.sup.X-1. For example, a 2-bit counter can have a value from 0 to 3; [0028], lines 1-10, as an example, given a 2-bit confidence counter with an initial value of Y=2, when first level predictor 56 predicts the branch correctly, the counter is incremented and saturates to the high value mark (i.e. 3). A correct prediction means that the target address stored in first level predictor 56 for the PC was the correct target address. Similarly, when first level predictor 56 predicts the branch incorrectly, the counter is decremented (i.e. to 1). An incorrect prediction means that the target address stored in first level predictor 56 for the PC was not the correct target address; [0029], lines 1-5, when the counter reaches a value of Z (e.g. Z=0), it means there is no confidence in the ability of first level predictor 56 to predict that particular branch correctly. This means that the branch is not a "simple" indirect branch, but is rather a "polymorphic" indirect branch; Shah, [0028], lines 5-8, the predicted program flow and/or information stored in the first branch prediction unit may be updated once the prediction information generated by the second branch prediction unit is generated; [0093], lines 1-8, in one embodiment, IFU 310 includes an update unit 350 that is configured to receive the results of predictors 330 and 340 and update predictor 330 accordingly. Thus, where predictor 330's results are inconsistent with those of predictor 340, information in predictor 330 may be invalidated or updated. In this manner, the output of predictor 330 may be made more consistent with the output of predictor 340 upon a next occurrence of a particular CTI; [0102], lines 9-17, unit 480 also generates branch prediction update information 478 which is conveyed to unit 420 in order to update the tag and data array in the BTC in an appropriate fashion (e.g., by invalidating an entry so that it will no longer produce a hit, or by updating the data in an entry). In one embodiment, BTC 430 is updated so that on a next occurrence of the current CTI, the BTC will generate the results provided by the DBP for the current occurrence of the CTI. In this manner, the performance of the BTC may be improved; [0119], lines 11-14, even if both the first and second branch predictions indicate that a given CTI is predicted to be taken, a BTC update may still occur in step 730 if the respective targets of the predictions differ; [0100], lines 6-7, BTC 430 could generate this information without it first having been previously predicted by DBP 460; [0103], lines 11-12, the target of a predicted-taken CTI will be the same as its prior reference; [0110], lines 1-4, a table 600 is shown that sets forth a list of exemplary update actions that may be taken with respect to BTC 430 based upon the respective branch predictions generated by BTC 430 and DBP 460).
Consider claim 8, the overall combination entails an apparatus as claimed in Claim 5, wherein the monitoring hardware circuitry is arranged, on determining that the mismatch threshold has been reached, to trigger an update of the default prediction hardware circuitry such that an altered default prediction will be generated, to update the stored indication of the default prediction to match the altered default prediction, to reset the test counter, and to then track occurrences of divergence of the observed indication of the target address from the altered default prediction (Kothari, [0027], lines 1-9, a confidence counter, such as confidence counter 326, is allocated for each entry of first level predictor 56 to help determine the difference between simple and polymorphic branches. The confidence counter is an X-bit saturating counter (where X is usually 2 or 3) that counts up or down based on the prediction accuracy of first level predictor 56. The lower saturation value of the counter is 0 and the upper saturation value is 2.sup.X-1. For example, a 2-bit counter can have a value from 0 to 3; [0028], lines 1-10, as an example, given a 2-bit confidence counter with an initial value of Y=2, when first level predictor 56 predicts the branch correctly, the counter is incremented and saturates to the high value mark (i.e. 3). A correct prediction means that the target address stored in first level predictor 56 for the PC was the correct target address. Similarly, when first level predictor 56 predicts the branch incorrectly, the counter is decremented (i.e. to 1). An incorrect prediction means that the target address stored in first level predictor 56 for the PC was not the correct target address; [0029], lines 1-5, when the counter reaches a value of Z (e.g. Z=0), it means there is no confidence in the ability of first level predictor 56 to predict that particular branch correctly. This means that the branch is not a "simple" indirect branch, but is rather a "polymorphic" indirect branch; Shah, [0028], lines 5-8, the predicted program flow and/or information stored in the first branch prediction unit may be updated once the prediction information generated by the second branch prediction unit is generated; [0093], lines 1-8, in one embodiment, IFU 310 includes an update unit 350 that is configured to receive the results of predictors 330 and 340 and update predictor 330 accordingly. Thus, where predictor 330's results are inconsistent with those of predictor 340, information in predictor 330 may be invalidated or updated. In this manner, the output of predictor 330 may be made more consistent with the output of predictor 340 upon a next occurrence of a particular CTI; [0102], lines 9-17, unit 480 also generates branch prediction update information 478 which is conveyed to unit 420 in order to update the tag and data array in the BTC in an appropriate fashion (e.g., by invalidating an entry so that it will no longer produce a hit, or by updating the data in an entry). In one embodiment, BTC 430 is updated so that on a next occurrence of the current CTI, the BTC will generate the results provided by the DBP for the current occurrence of the CTI. In this manner, the performance of the BTC may be improved; [0119], lines 11-14, even if both the first and second branch predictions indicate that a given CTI is predicted to be taken, a BTC update may still occur in step 730 if the respective targets of the predictions differ; [0100], lines 6-7, BTC 430 could generate this information without it first having been previously predicted by DBP 460; [0103], lines 11-12, the target of a predicted-taken CTI will be the same as its prior reference; [0110], lines 1-4, a table 600 is shown that sets forth a list of exemplary update actions that may be taken with respect to BTC 430 based upon the respective branch predictions generated by BTC 430 and DBP 460).
Consider claim 9, the overall combination entails an apparatus as claimed in Claim 4 (see above), wherein the monitoring hardware circuitry is arranged, for the given branch instruction, to maintain a record of a last observed indication of the target address, to use the test counter to track when a current observed indication of the target address matches the last observed indication, and to detect the update condition when the test counter at least reaches the predetermined value, wherein the predetermined value indicates that an update usefulness threshold has been met (Kothari, [0027], lines 1-9, a confidence counter, such as confidence counter 326, is allocated for each entry of first level predictor 56 to help determine the difference between simple and polymorphic branches. The confidence counter is an X-bit saturating counter (where X is usually 2 or 3) that counts up or down based on the prediction accuracy of first level predictor 56. The lower saturation value of the counter is 0 and the upper saturation value is 2.sup.X-1. For example, a 2-bit counter can have a value from 0 to 3; [0028], lines 1-10, as an example, given a 2-bit confidence counter with an initial value of Y=2, when first level predictor 56 predicts the branch correctly, the counter is incremented and saturates to the high value mark (i.e. 3). A correct prediction means that the target address stored in first level predictor 56 for the PC was the correct target address. Similarly, when first level predictor 56 predicts the branch incorrectly, the counter is decremented (i.e. to 1). An incorrect prediction means that the target address stored in first level predictor 56 for the PC was not the correct target address; [0029], lines 1-5, when the counter reaches a value of Z (e.g. Z=0), it means there is no confidence in the ability of first level predictor 56 to predict that particular branch correctly. This means that the branch is not a "simple" indirect branch, but is rather a "polymorphic" indirect branch; Shah, [0028], lines 5-8, the predicted program flow and/or information stored in the first branch prediction unit may be updated once the prediction information generated by the second branch prediction unit is generated; [0093], lines 1-8, in one embodiment, IFU 310 includes an update unit 350 that is configured to receive the results of predictors 330 and 340 and update predictor 330 accordingly. Thus, where predictor 330's results are inconsistent with those of predictor 340, information in predictor 330 may be invalidated or updated. In this manner, the output of predictor 330 may be made more consistent with the output of predictor 340 upon a next occurrence of a particular CTI; [0102], lines 9-17, unit 480 also generates branch prediction update information 478 which is conveyed to unit 420 in order to update the tag and data array in the BTC in an appropriate fashion (e.g., by invalidating an entry so that it will no longer produce a hit, or by updating the data in an entry). In one embodiment, BTC 430 is updated so that on a next occurrence of the current CTI, the BTC will generate the results provided by the DBP for the current occurrence of the CTI. In this manner, the performance of the BTC may be improved; [0119], lines 11-14, even if both the first and second branch predictions indicate that a given CTI is predicted to be taken, a BTC update may still occur in step 730 if the respective targets of the predictions differ; [0100], lines 6-7, BTC 430 could generate this information without it first having been previously predicted by DBP 460; [0103], lines 11-12, the target of a predicted-taken CTI will be the same as its prior reference; [0110], lines 1-4, a table 600 is shown that sets forth a list of exemplary update actions that may be taken with respect to BTC 430 based upon the respective branch predictions generated by BTC 430 and DBP 460).
Consider claim 10, the overall combination entails an apparatus as claimed in Claim 9 (see above), wherein each time the current observed indication of the target address matches the last observed indication of the target address the monitoring hardware circuitry is arranged to increment the test counter by an increment value (Kothari, [0027], lines 1-9, a confidence counter, such as confidence counter 326, is allocated for each entry of first level predictor 56 to help determine the difference between simple and polymorphic branches. The confidence counter is an X-bit saturating counter (where X is usually 2 or 3) that counts up or down based on the prediction accuracy of first level predictor 56. The lower saturation value of the counter is 0 and the upper saturation value is 2.sup.X-1. For example, a 2-bit counter can have a value from 0 to 3; [0028], lines 1-10, as an example, given a 2-bit confidence counter with an initial value of Y=2, when first level predictor 56 predicts the branch correctly, the counter is incremented and saturates to the high value mark (i.e. 3). A correct prediction means that the target address stored in first level predictor 56 for the PC was the correct target address. Similarly, when first level predictor 56 predicts the branch incorrectly, the counter is decremented (i.e. to 1). An incorrect prediction means that the target address stored in first level predictor 56 for the PC was not the correct target address; [0029], lines 1-5, when the counter reaches a value of Z (e.g. Z=0), it means there is no confidence in the ability of first level predictor 56 to predict that particular branch correctly. This means that the branch is not a "simple" indirect branch, but is rather a "polymorphic" indirect branch).
Consider claim 11, the overall combination entails an apparatus as claimed in Claim 10 (see above), wherein each time the current observed indication of the target address differs from the last observed indication of the target address, the monitoring hardware circuitry is arranged to decrement the test counter by a decrement value and to update the record of the last observed indication of the target address to indicate the current observed indication (Kothari, [0027], lines 1-9, a confidence counter, such as confidence counter 326, is allocated for each entry of first level predictor 56 to help determine the difference between simple and polymorphic branches. The confidence counter is an X-bit saturating counter (where X is usually 2 or 3) that counts up or down based on the prediction accuracy of first level predictor 56. The lower saturation value of the counter is 0 and the upper saturation value is 2.sup.X-1. For example, a 2-bit counter can have a value from 0 to 3; [0028], lines 1-10, as an example, given a 2-bit confidence counter with an initial value of Y=2, when first level predictor 56 predicts the branch correctly, the counter is incremented and saturates to the high value mark (i.e. 3). A correct prediction means that the target address stored in first level predictor 56 for the PC was the correct target address. Similarly, when first level predictor 56 predicts the branch incorrectly, the counter is decremented (i.e. to 1). An incorrect prediction means that the target address stored in first level predictor 56 for the PC was not the correct target address; [0029], lines 1-5, when the counter reaches a value of Z (e.g. Z=0), it means there is no confidence in the ability of first level predictor 56 to predict that particular branch correctly. This means that the branch is not a "simple" indirect branch, but is rather a "polymorphic" indirect branch; Shah, [0028], lines 5-8, the predicted program flow and/or information stored in the first branch prediction unit may be updated once the prediction information generated by the second branch prediction unit is generated; [0093], lines 1-8, in one embodiment, IFU 310 includes an update unit 350 that is configured to receive the results of predictors 330 and 340 and update predictor 330 accordingly. Thus, where predictor 330's results are inconsistent with those of predictor 340, information in predictor 330 may be invalidated or updated. In this manner, the output of predictor 330 may be made more consistent with the output of predictor 340 upon a next occurrence of a particular CTI; [0102], lines 9-17, unit 480 also generates branch prediction update information 478 which is conveyed to unit 420 in order to update the tag and data array in the BTC in an appropriate fashion (e.g., by invalidating an entry so that it will no longer produce a hit, or by updating the data in an entry). In one embodiment, BTC 430 is updated so that on a next occurrence of the current CTI, the BTC will generate the results provided by the DBP for the current occurrence of the CTI. In this manner, the performance of the BTC may be improved; [0119], lines 11-14, even if both the first and second branch predictions indicate that a given CTI is predicted to be taken, a BTC update may still occur in step 730 if the respective targets of the predictions differ; [0100], lines 6-7, BTC 430 could generate this information without it first having been previously predicted by DBP 460; [0103], lines 11-12, the target of a predicted-taken CTI will be the same as its prior reference; [0110], lines 1-4, a table 600 is shown that sets forth a list of exemplary update actions that may be taken with respect to BTC 430 based upon the respective branch predictions generated by BTC 430 and DBP 460).
Consider claim 12, the overall combination entails an apparatus as claimed in Claim 9 (see above), wherein the monitoring hardware circuitry is arranged, responsive to determining that the update usefulness threshold has been met, to cause an update of the default prediction hardware circuitry such that an altered default prediction will be generated, and to apply an adjustment to the test counter value (Kothari, [0027], lines 1-9, a confidence counter, such as confidence counter 326, is allocated for each entry of first level predictor 56 to help determine the difference between simple and polymorphic branches. The confidence counter is an X-bit saturating counter (where X is usually 2 or 3) that counts up or down based on the prediction accuracy of first level predictor 56. The lower saturation value of the counter is 0 and the upper saturation value is 2.sup.X-1. For example, a 2-bit counter can have a value from 0 to 3; [0028], lines 1-10, as an example, given a 2-bit confidence counter with an initial value of Y=2, when first level predictor 56 predicts the branch correctly, the counter is incremented and saturates to the high value mark (i.e. 3). A correct prediction means that the target address stored in first level predictor 56 for the PC was the correct target address. Similarly, when first level predictor 56 predicts the branch incorrectly, the counter is decremented (i.e. to 1). An incorrect prediction means that the target address stored in first level predictor 56 for the PC was not the correct target address; [0029], lines 1-5, when the counter reaches a value of Z (e.g. Z=0), it means there is no confidence in the ability of first level predictor 56 to predict that particular branch correctly. This means that the branch is not a "simple" indirect branch, but is rather a "polymorphic" indirect branch; Shah, [0028], lines 5-8, the predicted program flow and/or information stored in the first branch prediction unit may be updated once the prediction information generated by the second branch prediction unit is generated; [0093], lines 1-8, in one embodiment, IFU 310 includes an update unit 350 that is configured to receive the results of predictors 330 and 340 and update predictor 330 accordingly. Thus, where predictor 330's results are inconsistent with those of predictor 340, information in predictor 330 may be invalidated or updated. In this manner, the output of predictor 330 may be made more consistent with the output of predictor 340 upon a next occurrence of a particular CTI; [0102], lines 9-17, unit 480 also generates branch prediction update information 478 which is conveyed to unit 420 in order to update the tag and data array in the BTC in an appropriate fashion (e.g., by invalidating an entry so that it will no longer produce a hit, or by updating the data in an entry). In one embodiment, BTC 430 is updated so that on a next occurrence of the current CTI, the BTC will generate the results provided by the DBP for the current occurrence of the CTI. In this manner, the performance of the BTC may be improved; [0119], lines 11-14, even if both the first and second branch predictions indicate that a given CTI is predicted to be taken, a BTC update may still occur in step 730 if the respective targets of the predictions differ; [0100], lines 6-7, BTC 430 could generate this information without it first having been previously predicted by DBP 460; [0103], lines 11-12, the target of a predicted-taken CTI will be the same as its prior reference; [0110], lines 1-4, a table 600 is shown that sets forth a list of exemplary update actions that may be taken with respect to BTC 430 based upon the respective branch predictions generated by BTC 430 and DBP 460).
Consider claim 13, the overall combination entails an apparatus as claimed in Claim 9 (see above), wherein whilst the update condition is determined to be present, the monitoring hardware circuitry is arranged to implement an update procedure comprising one of: - causing the default prediction hardware circuitry to be updated such that the default prediction is altered whenever the monitoring hardware circuitry detects a change in the observed indication of the target address; or - causing the default prediction hardware circuitry to be updated such that the default prediction is altered once every N executions of the given branch instruction (Kothari, [0027], lines 1-9, a confidence counter, such as confidence counter 326, is allocated for each entry of first level predictor 56 to help determine the difference between simple and polymorphic branches. The confidence counter is an X-bit saturating counter (where X is usually 2 or 3) that counts up or down based on the prediction accuracy of first level predictor 56. The lower saturation value of the counter is 0 and the upper saturation value is 2.sup.X-1. For example, a 2-bit counter can have a value from 0 to 3; [0028], lines 1-10, as an example, given a 2-bit confidence counter with an initial value of Y=2, when first level predictor 56 predicts the branch correctly, the counter is incremented and saturates to the high value mark (i.e. 3). A correct prediction means that the target address stored in first level predictor 56 for the PC was the correct target address. Similarly, when first level predictor 56 predicts the branch incorrectly, the counter is decremented (i.e. to 1). An incorrect prediction means that the target address stored in first level predictor 56 for the PC was not the correct target address; [0029], lines 1-5, when the counter reaches a value of Z (e.g. Z=0), it means there is no confidence in the ability of first level predictor 56 to predict that particular branch correctly. This means that the branch is not a "simple" indirect branch, but is rather a "polymorphic" indirect branch; Shah, [0028], lines 5-8, the predicted program flow and/or information stored in the first branch prediction unit may be updated once the prediction information generated by the second branch prediction unit is generated; [0093], lines 1-8, in one embodiment, IFU 310 includes an update unit 350 that is configured to receive the results of predictors 330 and 340 and update predictor 330 accordingly. Thus, where predictor 330's results are inconsistent with those of predictor 340, information in predictor 330 may be invalidated or updated. In this manner, the output of predictor 330 may be made more consistent with the output of predictor 340 upon a next occurrence of a particular CTI; [0102], lines 9-17, unit 480 also generates branch prediction update information 478 which is conveyed to unit 420 in order to update the tag and data array in the BTC in an appropriate fashion (e.g., by invalidating an entry so that it will no longer produce a hit, or by updating the data in an entry). In one embodiment, BTC 430 is updated so that on a next occurrence of the current CTI, the BTC will generate the results provided by the DBP for the current occurrence of the CTI. In this manner, the performance of the BTC may be improved; [0119], lines 11-14, even if both the first and second branch predictions indicate that a given CTI is predicted to be taken, a BTC update may still occur in step 730 if the respective targets of the predictions differ; [0100], lines 6-7, BTC 430 could generate this information without it first having been previously predicted by DBP 460; [0103], lines 11-12, the target of a predicted-taken CTI will be the same as its prior reference; [0110], lines 1-4, a table 600 is shown that sets forth a list of exemplary update actions that may be taken with respect to BTC 430 based upon the respective branch predictions generated by BTC 430 and DBP 460).
Consider claim 15, Shah discloses an apparatus as claimed in Claim 1 (see above), wherein: the monitoring hardware circuitry is arranged to maintain one or more entries ([0096], lines 1-2, tag array 440 and a data array 450, each of which has N entries), where each entry has an identifier field used to identify a branch instruction of the given type associated with that entry ([0096], lines 8-10, in one embodiment, the key is a portion (i.e., certain bits) of the current fetch address; [0098], lines 13-14, tag that matches the key), and a target address comparison field to maintain a value of the target address against which a subsequent observed indication of the target address is compared in order to determine adjustment ([0100], lines 10-11, target address found at the hit index within data array 450); and each entry further comprises a replacement policy field used to maintain metadata used by the monitoring hardware circuitry when implementing a replacement policy to determine when the entry is available for reallocation to another branch instruction of the given type, wherein the replacement policy is arranged to bias use of the one or more entries for monitoring of more frequently occurring branch instructions of the given type within a program flow history of a program executed by processing hardware circuitry ([0097], lines 4-5, recent access information (e.g., for a replacement algorithm); [0105], lines 4-15, the used bit allows the BTC to implement an entry replacement policy. Many different replacement policies are possible and contemplated. In one implementation, the used bit is set on each access to a particular entry, and, when adding a new entry to the BTC, the BTC writes to its "lowest-order" entry that does not have the used bit set. Thus, if the BTC includes entries 0-31, and entries 0-3 currently have the used bit set, and the used bit is not set for entry 4, upon the need to write a new BTC entry, entry 4 will be used. In one embodiment, upon the used bit being set for every entry in the BTC, all used bits may be cleared, allowing used bits to be set again upon further access).
However, Shah does not disclose a counter field used to maintain a test counter value for the branch instruction associated with the entry, and the adjustment is of the test counter value.
On the other hand, Kothari discloses a counter field used to maintain a test counter value for a branch instruction associated with an entry, and a target address comparison field to maintain a value of a target address against which a subsequent observed indication of the target address is compared in order to determine adjustment of the test counter value ([0027], lines 1-9, a confidence counter, such as confidence counter 326, is allocated for each entry of first level predictor 56 to help determine the difference between simple and polymorphic branches. The confidence counter is an X-bit saturating counter (where X is usually 2 or 3) that counts up or down based on the prediction accuracy of first level predictor 56. The lower saturation value of the counter is 0 and the upper saturation value is 2.sup.X-1. For example, a 2-bit counter can have a value from 0 to 3; [0028], lines 1-10, as an example, given a 2-bit confidence counter with an initial value of Y=2, when first level predictor 56 predicts the branch correctly, the counter is incremented and saturates to the high value mark (i.e. 3). A correct prediction means that the target address stored in first level predictor 56 for the PC was the correct target address. Similarly, when first level predictor 56 predicts the branch incorrectly, the counter is decremented (i.e. to 1). An incorrect prediction means that the target address stored in first level predictor 56 for the PC was not the correct target address; [0029], lines 1-5, when the counter reaches a value of Z (e.g. Z=0), it means there is no confidence in the ability of first level predictor 56 to predict that particular branch correctly. This means that the branch is not a "simple" indirect branch, but is rather a "polymorphic" indirect branch).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to combine the teaching of Kothari with the invention of Shah in order to result in more accurate and simpler prediction of simple branches via use of a confidence value to facilitate prediction of simple branches using a first level predictor when the first level predictor is likely to be correct.
Consider claim 16, the overall combination entails an apparatus as claimed in Claim 15 (see above), wherein: the monitoring hardware circuitry is arranged, for each entry, to maintain a replacement counter in the replacement policy field that is adjusted in a first direction each time the branch instruction associated with that entry is observed by the monitoring hardware circuitry, and is adjusted in a second direction each time the monitoring hardware circuitry, on observing a branch instruction of the given type not yet allocated to an entry of the monitoring hardware circuitry, has no available entry to allocate for that branch instruction; and the monitoring hardware circuitry is arranged to identify a given entry as an available entry for allocation when the replacement counter in the replacement policy field of that given entry has a predetermined value (Shah, [0097], lines 4-5, recent access information (e.g., for a replacement algorithm); [0105], lines 4-15, the used bit allows the BTC to implement an entry replacement policy. Many different replacement policies are possible and contemplated. In one implementation, the used bit is set on each access to a particular entry, and, when adding a new entry to the BTC, the BTC writes to its "lowest-order" entry that does not have the used bit set. Thus, if the BTC includes entries 0-31, and entries 0-3 currently have the used bit set, and the used bit is not set for entry 4, upon the need to write a new BTC entry, entry 4 will be used. In one embodiment, upon the used bit being set for every entry in the BTC, all used bits may be cleared, allowing used bits to be set again upon further access).
Claim(s) 6-7 is/are rejected under 35 U.S.C. 103 as being unpatentable over Shah and Kothari as applied to claim 5 above, and further in view of Pedley et al. (Pedley) (US 20060242517 A1).
Consider claim 6, the combination thus far entails an apparatus as claimed in Claim 5 (see above), wherein each time the observed indication of the target address for an occurrence of the given branch instruction differs from the default prediction the monitoring hardware circuitry is arranged to decrement the test counter by a decrement value (Kothari, [0027], lines 1-9, a confidence counter, such as confidence counter 326, is allocated for each entry of first level predictor 56 to help determine the difference between simple and polymorphic branches. The confidence counter is an X-bit saturating counter (where X is usually 2 or 3) that counts up or down based on the prediction accuracy of first level predictor 56. The lower saturation value of the counter is 0 and the upper saturation value is 2.sup.X-1. For example, a 2-bit counter can have a value from 0 to 3; [0028], lines 1-10, as an example, given a 2-bit confidence counter with an initial value of Y=2, when first level predictor 56 predicts the branch correctly, the counter is incremented and saturates to the high value mark (i.e. 3). A correct prediction means that the target address stored in first level predictor 56 for the PC was the correct target address. Similarly, when first level predictor 56 predicts the branch incorrectly, the counter is decremented (i.e. to 1). An incorrect prediction means that the target address stored in first level predictor 56 for the PC was not the correct target address; [0029], lines 1-5, when the counter reaches a value of Z (e.g. Z=0), it means there is no confidence in the ability of first level predictor 56 to predict that particular branch correctly. This means that the branch is not a "simple" indirect branch, but is rather a "polymorphic" indirect branch).
However, the combination thus far does not entail, in the context of the claim, incrementing by an increment value, rather than decrementing by a decrement value.
On the other hand, Pedley discloses incrementing by an increment value as an alternative to decrementing by a decrement value ([0049], lines 1-4, although in this embodiment, the counter is set to a predetermined value and counts down it would be clear to a skilled person that this does not have to happen and in fact it could count up to a predetermined value).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to combine the teaching of Pedley with the combination of Shah and Kothari, as this modification merely entails simple substitution of one known element (decrementing by a decrement value) for another (incrementing by an increment value) to obtain predictable results (the combination of Shah and Kothari, wherein the test counter is incremented, rather than decremented, upon a mismatch, such that for a 2-bit confidence counter, the value of “3” reflects low confidence, rather than high confidence), which is an example of a rationale that may support a conclusion of obviousness as per MPEP 2143.
Consider claim 7, the overall combination entails an apparatus as claimed in Claim 6 (see above), wherein each time the observed indication of the target address for an occurrence of the given branch instruction matches the default prediction the monitoring hardware circuitry is arranged to decrement the test counter by a decrement value (Kothari, [0027], lines 1-9, a confidence counter, such as confidence counter 326, is allocated for each entry of first level predictor 56 to help determine the difference between simple and polymorphic branches. The confidence counter is an X-bit saturating counter (where X is usually 2 or 3) that counts up or down based on the prediction accuracy of first level predictor 56. The lower saturation value of the counter is 0 and the upper saturation value is 2.sup.X-1. For example, a 2-bit counter can have a value from 0 to 3; [0028], lines 1-10, as an example, given a 2-bit confidence counter with an initial value of Y=2, when first level predictor 56 predicts the branch correctly, the counter is incremented and saturates to the high value mark (i.e. 3). A correct prediction means that the target address stored in first level predictor 56 for the PC was the correct target address. Similarly, when first level predictor 56 predicts the branch incorrectly, the counter is decremented (i.e. to 1). An incorrect prediction means that the target address stored in first level predictor 56 for the PC was not the correct target address; [0029], lines 1-5, when the counter reaches a value of Z (e.g. Z=0), it means there is no confidence in the ability of first level predictor 56 to predict that particular branch correctly. This means that the branch is not a "simple" indirect branch, but is rather a "polymorphic" indirect branch; Pedley, [0049], lines 1-4, although in this embodiment, the counter is set to a predetermined value and counts down it would be clear to a skilled person that this does not have to happen and in fact it could count up to a predetermined value).
Claim(s) 18-19 is/are rejected under 35 U.S.C. 103 as being unpatentable over Shah as applied to claim 1 above, and further in view of Sturcken (US 6734538 B1).
Consider claim 18, Shah discloses a system comprising: the apparatus of claim 1 (see above), but does not disclose that the apparatus is implemented in at least one packaged chip; at least one system component; and a board, wherein the at least one packaged chip and the at least one system component are assembled on the board.
On the other hand, Sturcken discloses a system comprising: an apparatus, implemented in at least one packaged chip; at least one system component; and a board, wherein the at least one packaged chip and the at least one system component are assembled on the board (col. 1, lines 20-45, for example).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to combine the teaching of Sturcken with the invention of Shah in order to create packaging efficiencies (Sturcken, col. 1, line 23). Alternatively, this modification merely entails combining prior art elements (the teaching of Shah cited above, and the teachings of Sturcken cited above) according to known methods (Examiner submits that chips, packages, system components, boards, and so forth, were known, as reflected by Sturcken) to yield predictable results (the invention of Shah, implemented in the manner cited in Sturcken), which is an example of a rationale that may support a conclusion of obviousness as per MPEP 2143.
Consider claim 19, the overall combination entails a chip-containing product comprising the system of claim 18 (see above), wherein the system is assembled on a further board with at least one other product component (Sturcken, col. 1, lines 20-45, for example).
Claim(s) 20 is/are rejected under 35 U.S.C. 103 as being unpatentable over Shah as applied to claim 1 above, and further in view of Abhishek Raja (US 20220300329 A1).
Consider claim 20, Shah discloses the apparatus of Claim 1 (see above), but does not disclose a non-transitory computer-readable medium storing computer-readable code for fabrication of the apparatus.
On the other hand, Abhishek Raja discloses a non-transitory computer-readable medium storing computer-readable code for fabrication of the apparatus ([0139]-[0143]).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to combine the teaching of Abhishek Raja with the invention of Shah in order to facilitate fabrication. Alternatively, this modification merely entails combining prior art elements (the apparatus of claim 1 of Shah above, and the non-transitory computer-readable medium storing computer-readable code for fabrication of an apparatus of Abhishek Raja as cited above) according to known methods (Examiner submits fabrication via hardware description languages was known) to yield predictable results (the invention of Shah, fabricated via a non-transitory computer-readable medium storing computer-readable code), which is an example of a rationale that may support a conclusion of obviousness, as per MPEP 2143.
Response to Arguments
Applicant on page 10 argues: “The suggestion regarding page 1, line 20 has been adopted. A new more detailed title is provided: DETERMINING WHEN TO UPDATE A DEFAULT PREDICTION OF A TARGET ADDRESS OF A BRANCH INSTRUCTION. Approval is requested.”
In view of the aforementioned amendment, the previously presented objections to the title and body of the specification are withdrawn.
Applicant on page 10 argues: “Claim amendments have been made as suggested by the Examiner.”
In view of the aforementioned claim amendments, the previously presented objections to the claims are withdrawn.
Applicant on page 10 argues: ‘Claim 5 is amended to recite "detect the update condition when the test counter reaches the predetermined value, wherein the predetermined value indicates that a mismatch threshold has been reached," as interpreted by the Examiner in section 13 of the OA.’
In view of the aforementioned amendment, the associated previously presented indefinite rejection is withdrawn.
Applicant on page 10 argues: ‘Claim 9 is amended to recite "to detect the update condition when the test counter at least reaches the predetermined value, wherein the predetermined value indicates that an update usefulness threshold has been met," as interpreted by the Examiner in section 14.’
In view of the aforementioned amendment, the associated previously presented indefinite rejection is withdrawn.
Applicant on page 10 argues: ‘In section 15 of the OA, the Examiner raises an objection against claim 13 regarding the grouping of alternatives. Claim 13 describes that the update procedure comprises one of two alternatives. Claim 13 does not, as the Examiner has suggested, describe that the update procedure is selected from a list or group "comprising" two alternatives, which would then leave open the possibility that the update procedure is not limited to the two options of claim 13. The structure of claim 13 instead requires that the update procedure requires at least one of the two claimed alternatives, and the scope of claim 13 is limited by at least one of the alternatives. The same comments apply to claim 14.’
In view of Applicant’s arguments, the associated previously presented indefinite rejections are withdrawn.
Applicant on page 11 argues: ‘The term "hardware" is included for each instance of circuitry in claims 1-16. Claim 20 now recites a 'non-transitory' computer-readable medium. Withdrawal of this rejection is requested.’
In view of the aforementioned amendments, the previously presented rejections under 35 USC 101 are withdrawn.
Applicant on page 11 argues: ‘Claim 17 is amended in a corresponding way as claim 1 and is further amended to explicitly recite the steps of 'identifying an address associated with a given branch instruction of a given type,' and 'detecting an update condition...,' to avoid any contingent feature interpretation for the method.’
Examiner greatly appreciates the proactive amendment to avoid any contingent feature interpretation for the method.
Applicant on page 12 argues: “However, amended independent claims 1 and 17 update the default prediction in a way not described by Shah. The claimed default prediction for a given branch instruction is updated in response to an update condition detected based on a test that is based on multiple occurrences of the given branch instruction. Although examples are described on page 6, lines 4-28 of the specification, in general, the decision whether to update the default prediction is made based on multiple occurrences of the given branch instruction.” Applicant on page 12 further argues: “Accordingly, Shah does not teach detecting an update condition, for deciding whether to update the default prediction, based on a test assessed over multiple occurrences of the given branch instruction.” Applicant across pages 13-14 additionally argues: “There is no longer term assessment as to whether changing the default prediction is expected to improve accuracy (let alone basing the assessment on observing multiple occurrences of the branch instruction). Shah's approach of updating the default prediction based on a single observed instance of a given branch instruction is discussed on page 4, lines 28-37 of Applicant's specification and is contrasted with the claimed approach of updating the default prediction based on observing multiple occurrences of the given branch instruction. Shah provides no teaching or suggestion of deciding whether to update the default prediction based on observing multiple occurrences of a branch instruction. Thus, Shah fails to disclose or suggest multiple features recited in claim 1. Corresponding features are recited in independent claim 17. The rejections based on Shah should be withdrawn.”
However, Examiner submits that the relevant claim language, under the broadest reasonable interpretation, is taught by Shah.
For example, claim 1 recites “detecting an update condition based on monitoring an observed indication of the target address for multiple occurrences of the given branch instruction” in lines 10-12, and the limitation “detect the update condition based on performance of a test to assess, given the observed indication of the target address for multiple occurrences of the given branch instruction, whether an update of the default prediction is expected to improve accuracy of the default prediction” in lines 15-18.
Even if the claim necessitated multiple occurrences of the given branch instruction—Examiner notes that the “for multiple occurrences of the given branch instruction” limitation may be an intended use limitation—Examiner submits that the limitations would nevertheless still encompass a first scenario in which a) there are multiple occurrences of the given branch instruction; and b) for each of the aforementioned occurrences, there is an associated instance of detecting an update condition based on monitoring an observed indication of the target address associated with that occurrence. Additionally, Examiner submits that the limitations would nevertheless still encompass a second scenario in which a) there are multiple occurrences of the given branch instruction; and b) an [overall] update condition (e.g., whether the default prediction is updated at all, across the multiple occurrences) is based on monitoring an observed indication of the target address for each occurrence. Examiner submits that Shah (as cited by Examiner and further summarized by Applicant in the remarks) teaches each of these scenarios and, as such, teach the relevant claim language, even if the overall inventive concept of the instant application and Shah diverge.
Applicant on page 13 argues: “Shah also does not disclose a test to assess whether the update of the default prediction is expected to improve accuracy of the default prediction. As shown in the table of Figure 6, Shah instead compares a single DBP prediction to a previous default prediction and updates the default prediction when they differ.”
However, Examiner submits Shah’s comparison explained above reflects such a test; a comparison that results in a determination of inequality reflects the aforementioned update being expected to improve accuracy of the default prediction.
Conclusion
THIS ACTION IS MADE FINAL. Applicant is reminded of the extension of time policy as set forth in 37 CFR 1.136(a).
A shortened statutory period for reply to this final action is set to expire THREE MONTHS from the mailing date of this action. In the event a first reply is filed within TWO MONTHS of the mailing date of this final action and the advisory action is not mailed until after the end of the THREE-MONTH shortened statutory period, then the shortened statutory period will expire on the date the advisory action is mailed, and any nonprovisional extension fee (37 CFR 1.17(a)) pursuant to 37 CFR 1.136(a) will be calculated from the mailing date of the advisory action. In no event, however, will the statutory period for reply expire later than SIX MONTHS from the mailing date of this final action.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to KEITH E VICARY whose telephone number is (571)270-1314. The examiner can normally be reached Monday to Friday, 9:00 AM to 5:00 PM.
Examiner interviews are available via telephone, in-person, and video conferencing using a USPTO supplied web-based collaboration tool. To schedule an interview, applicant is encouraged to use the USPTO Automated Interview Request (AIR) at http://www.uspto.gov/interviewpractice.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, Jyoti Mehta can be reached at (571)270-3995. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of published or unpublished applications may be obtained from Patent Center. Unpublished application information in Patent Center is available to registered users. To file and manage patent submissions in Patent Center, visit: https://patentcenter.uspto.gov. Visit https://www.uspto.gov/patents/apply/patent-center for more information about Patent Center and https://www.uspto.gov/patents/docx for information about filing in DOCX format. For additional questions, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/KEITH E VICARY/Primary Examiner, Art Unit 2183