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 .
Response to Amendment
This office action is in response to the amendment filed on 09/02/2025. Claims 1-3, 6-7, 9-12,15-18, and 21 are pending. Claims 1-3, 6-7, 9-12, and 15-18 are amended. Claims 4-5, 8, 13-14, and 19-20 are canceled.
Response to Arguments
Applicant's arguments filed 07/16/2025 have been fully considered but they are not persuasive.
On pages 16-17 of the Remarks, Applicant submits:
Applicant believes that Chang does not disclose the target branch instruction and the branch instruction to be predicted as claimed in amended claim 1. It can be seen from step 300 of FIG. 3 in Chang that the branch instruction for prediction is directly loaded, rather than being determined based on the target branch instruction. Therefore, Chang does not disclose the step of "determining a branch instruction to be predicted based on a target branch instruction" as claimed in amended claim 1.
However, this argument is not persuasive because it does not consider that the target branch instruction is mapped to a branch instruction in the program that is loaded at step 300 and that a branch instruction that is to be predicted at step 303 is determined based on the target branch instruction in the loaded program. In other words, step 303 determines a branch instruction to be predicted based on the branch instruction being a target branch instruction in the loaded program.
On page 17 of the Remarks, Applicant submits:
Furthermore, as can be seen from step 302 of FIG. 3 in Chang that the scheme of Chang is based on a sample dataset, while the present application is based on the branch instruction to be predicted, and the branch instruction to be predicted is determined based on the target branch instruction. Therefore, under the premise that Chang does not disclose the step of "determining a branch instruction to be predicted based on a target branch instruction", Chang also fails to disclose the step of "predicting the branch instruction to be predicted based on a plurality of branch prediction methods which are preset, to obtain corresponding prediction results."
However, this argument is not persuasive because the branch instruction to be predicted at step 303 is determined based on a target branch instruction being in the program loaded at step 300 (as explained above). Further, the branch instruction to be predicted is predicted based on a plurality of prediction heuristics at step 303 and the output of each prediction heuristic is obtained at step 305, which discloses “predicting the branch instruction to be predicted based on a plurality of branch prediction methods which are preset, to obtain corresponding prediction results”.
Applicant’s argument on page 17 of the Remarks that “the branch history information in step 303 of Change cannot be equivalent to the branch prediction state in amended claim 1” is moot because the current rejection does not rely on Chang to disclose this feature and explains that this feature is not required under BRI.
Applicant’s argument at the end of page 17 of the Remarks that the original claim 5 has been amended so that it may not be regarded as a conditional limitation is not persuasive because the amended language claim 1 (which appears to include the features of claim 5 that Applicant is referring to) is still conditional. Specifically, the claim 1 limitation “wherein the plurality of branch prediction metho comprises a method for determining a current branch prediction result based on a branch prediction state” is conditional on there being a branch prediction state, and since the claim does not require there to be a branch prediction state, this limitation, as well as the limitations that follow from it, are not required under BRI.
Specification
The title of the invention is not descriptive. A new title is required that is clearly indicative of the invention to which the claims are directed. Examiner suggests “Method for testing the accuracy of multiple branch prediction methods to select the highest accuracy branch prediction method for a target branch instruction”.
Claim Objections
Claims 1-3, 6-7, 9-10, and 15 are objected to because of the following informalities:
Claim 1 line 12- the phrase “the plurality of branch prediction method” is improper, “method” should be --methods--
Claim 1 lines 14-15 appear to have added language without underlining, which is a non-compliant claim amendment
Claim 1, in the fifth line from the bottom of the claim- delete the word “current” to be consistent with references to the branch prediction state.
Claims 9 and 10 include the same limitation and should be corrected similarly
Claim 2 line 2- the phrase “the plurality of branch prediction method” is improper, “method” should be --methods--
Claim 3 line 2- the phrase “the plurality of branch prediction method” is improper, “method” should be --methods--
Claim 6- “representing” should be “represents” in line 3 of page 6
Claim 7- “representing” should be “represents” in line 11 of page 6
Claim 15 should be corrected to depend from claim 1 as claim 5 has been canceled.
Appropriate correction is required.
Claim Rejections - 35 USC § 112
The following is a quotation of the first paragraph of 35 U.S.C. 112(a):
(a) IN GENERAL.—The specification shall contain a written description of the invention, and of the manner and process of making and using it, in such full, clear, concise, and exact terms as to enable any person skilled in the art to which it pertains, or with which it is most nearly connected, to make and use the same, and shall set forth the best mode contemplated by the inventor or joint inventor of carrying out the invention.
The following is a quotation of the first paragraph of pre-AIA 35 U.S.C. 112:
The specification shall contain a written description of the invention, and of the manner and process of making and using it, in such full, clear, concise, and exact terms as to enable any person skilled in the art to which it pertains, or with which it is most nearly connected, to make and use the same, and shall set forth the best mode contemplated by the inventor of carrying out his invention.
Claims 6-7 and 16-17 are rejected under 35 U.S.C. 112(a) or 35 U.S.C. 112 (pre-AIA ), first paragraph, as failing to comply with the written description requirement. The claim(s) contains subject matter which was not described in the specification in such a way as to reasonably convey to one skilled in the relevant art that the inventor or a joint inventor, or for applications subject to pre-AIA 35 U.S.C. 112, the inventor(s), at the time the application was filed, had possession of the claimed invention.
Claim 6 describes further steps of “the method for determining the current branch prediction result based on the branch prediction state” described in claim 1. However, the specification does not disclose a method comprising the steps of claim 1 and claim 6 in the same embodiment. The steps of the method for determining the current branch prediction result based on the branch prediction state recited in claim 1 correspond to Fig. 2 of the Drawings and the steps of the method recited in claim 6 correspond to Fig. 3 of the Drawings. The specification does not disclose Fig. 2 and Fig. 3 as being part of the same method or embodiment.
Claim 7 describes further steps of “the method for determining the current branch prediction result based on the branch prediction state” described in claim 1. However, the specification does not disclose a method comprising the steps of claim 1 and claim 7 in the same embodiment. The steps of the method for determining the current branch prediction result based on the branch prediction state recited in claim 1 correspond to Fig. 2 of the Drawings and the steps of the method recited in claim 7 correspond to Fig. 4 of the Drawings. The specification does not disclose Fig. 2 and Fig. 4 as being part of the same method or embodiment.
Claims 16 and 17 are rejected based on their dependence from claims 6-7.
The following is a quotation of 35 U.S.C. 112(b):
(b) CONCLUSION.—The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the inventor or a joint inventor regards as the invention.
The following is a quotation of 35 U.S.C. 112 (pre-AIA ), second paragraph:
The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the applicant regards as his invention.
Claims 1-3, 6-7, 9-12,15-18, and 21 are rejected under 35 U.S.C. 112(b) or 35 U.S.C. 112 (pre-AIA ), second paragraph, as being indefinite for failing to particularly point out and distinctly claim the subject matter which the inventor or a joint inventor (or for applications subject to pre-AIA 35 U.S.C. 112, the applicant), regards as the invention.
Claim 1 recites “the prediction accuracy with the highest value” in line 8. There is insufficient antecedent basis for this limitation as the claim does not introduce a prediction accuracy with a highest value.
Claims 9 and 10 recite the same limitation and are rejected for the same reasons.
Claim 1 recites “determining that the branch prediction state is a non-jump execution branch instruction of a first-level” in lines 16-17, “determining that the branch prediction state is the non-jump execution branch instruction of the second-level” on page 4 lines 1-2, “determining that the branch prediction state is the jump execution branch instruction of the second-level” on page 4 lines 7-8, and “determining that the branch prediction state is the jump execution branch instruction of the first-level” on page 4 lines 13-14. It is unclear how the branch prediction state can be each of these states at the same time as they appear to be mutually exclusive branch prediction states. The branch prediction state can only be one of the aforementioned states at a time.
Claims 9 and 10 recite the same limitation and are rejected for the same reasons.
Claim 1 recites “determining that… the current branch prediction result is not jump” in line 17 and on page 4 line 2 and also recites “determining that… the current branch prediction result is jump” on page 4 line 8 and on page 4 line 14. It is unclear how the current branch prediction result can be “not jump” and “jump” at the same time as these are mutually exclusive branch prediction results.
Claims 9 and 10 recite the same limitation and are rejected for the same reasons.
Claim 1 recites steps of “the method for determining the current branch prediction result based on the branch prediction state”. It is unclear how the steps may be part of “the method for determining the current branch prediction result based on the branch prediction state” since they describe determining the branch prediction state and determining the current branch prediction result, which is different from determining the branch prediction state based on the current branch prediction result, and the further steps of keeping or adjusting the branch prediction state in response to the current branch prediction being verified to be successful or failed describes determining the branch prediction state based on the current branch prediction result, which is the opposite of determining the current branch prediction result based on the branch prediction state. That is, the method for determining the current branch prediction result based on the branch prediction state is unclear because it does not describe any steps for determining the current branch prediction result based on the branch prediction state.
Claims 9 and 10 recite the same limitation and are rejected for the same reasons.
Claim 2 recites “a jump execution branch instruction” in lines 2-3. It is unclear whether this refers to the same jump execution branch instruction introduced in claim 1 (on page 4 line 5) or if they are different.
Claim 3 recites “a non-jump execution branch instruction in lines 2-3. It is unclear whether this refers to the same non-jump execution branch instruction introduced in claim 1 line 16 or if they are different.
Claim 6 recites “a jump execution branch instruction” in line 5. It is unclear whether this refers to the same jump execution branch instruction introduced in claim 1 or if they are different.
Claim 6 recites “a non-jump execution branch instruction” in the third line from the bottom of page 5. It is unclear whether this refers to the same non-jump execution branch instruction introduced in claim 1 or if they are different.
Claim 6 recites “determining that a cumulative number of prediction results… is 1” in lines 4-5, “determining that the cumulative number of prediction results… is 2” in lines 12-13, and “determining that the cumulative number of prediction results… is 3” in lines 21-22. It is unclear how the cumulative number of prediction results can be 1, 2, and 3 at the same time as these are mutually exclusive results. The cumulative number of prediction results can only be one of the aforementioned results at a time.
Claim 6 recites “determining that… the current branch prediction result is jump” in line 5, lines 13-14, and lines 22-23, and also recites “determining that… the current branch prediction result is not jump” on page 6 line 4, in addition to claim 1 describing that the current branch prediction result is jump and not jump. It is unclear how the current branch prediction result can be “not jump” and “jump” at the same time as these are mutually exclusive branch prediction results.
Claim 6 recites “determining that the branch prediction state represent[s] the non-jump execution branch instruction” on page 6 line 3. It is unclear whether this non-jump execution branch instruction refers to the non-jump execution branch instruction introduced in the third line from the bottom of page 5 or if it refers to the non-jump execution branch instruction introduced in claim 1.
Further, since claim 1 describes determining that the branch prediction state is the jump execution branch instruction, it is unclear how the branch prediction state can also represent the non-jump execution branch instruction at the same time as these are mutually exclusive states.
Claim 6 recites steps of “the method for determining the current branch prediction result based on the branch prediction state”. However, none of the steps recited in claim 6 determine the current branch prediction result based on the branch prediction state. It is thus unclear how the steps recited in claim 6 are part of the method for determining the current branch prediction result based on the branch prediction state.
Claim 7 recites “a non-jump execution branch instruction” in line 5. It is unclear whether this refers to the same non-jump execution branch instruction introduced in claim 1 or if they are different.
Claim 7 recites “a jump execution branch instruction” on page 7 line 6. It is unclear whether this refers to the same jump execution branch instruction introduced in claim 1 or if they are different.
Claim 7 recites “determining that a cumulative number of prediction results… is 1” in lines 4-5, “determining that the cumulative number of prediction results… is 2” in lines 13-14, and “determining that the cumulative number of prediction results… is 3” in lines 22-23. It is unclear how the cumulative number of prediction results can be 1, 2, and 3 at the same time as these are mutually exclusive results. The cumulative number of prediction results can only be one of the aforementioned results at a time.
Claim 7 recites “determining that… the current branch prediction result is not jump” in lines 5-6, lines 14-15, and lines 23-24, and also recites “determining that… the current branch prediction result is jump” on page 7 line 12, in addition to claim 1 describing that the current branch prediction result is jump and not jump. It is unclear how the current branch prediction result can be “not jump” and “jump” at the same time as these are mutually exclusive branch prediction results.
Claim 7 recites “determining that the branch prediction state represent[s] the jump execution branch instruction” on page 7 line 11. It is unclear whether this jump execution branch instruction refers to the jump execution branch instruction introduced on page 7 line 6 or if it refers to the jump execution branch instruction introduced in claim 1.
Further, since claim 1 describes determining that the branch prediction state is the non-jump execution branch instruction, it is unclear how the branch prediction state can also represent the jump execution branch instruction at the same time as these are mutually exclusive states.
Claim 6 steps of “the method for determining the current branch prediction result based on the branch prediction state”. However, none of the steps recited in claim 6 determine the current branch prediction result based on the branch prediction state. It is thus unclear how the steps recited in claim 6 are part of the method for determining the current branch prediction result based on the branch prediction state.
Claim 9 recites “the branch prediction method” on page 8 line 8. It is unclear which of the plurality of branch prediction methods introduced in lines 6-7 this refers to.
Claim 10 recites “the branch prediction method” on page 10 line 1. It is unclear which of the plurality of branch prediction methods introduced in lines 6-7 this refers to.
Claim 17 recites “the branch prediction method” in line 2. It is unclear which of the plurality of branch prediction methods in claim 1 this refers to.
Claim 18 recites “the external” in line 6. There is insufficient antecedent basis for this limitation in the claim. While the claim describes commands input from external to the processor in lines 3-4, the term “external” is used as an adjective in this context and does not provide sufficient antecedent basis for the use of the term “external” as a noun in line 6. Examiner suggests replacing “to the external” with --externally--.
Claim 21 recites “a jump execution branch instruction” in lines 2-3. It is unclear whether this refers to the same jump execution branch instruction introduced in claim 9 (in the fifth line from the bottom of page 8) or if they are different.
Claims dependent on a rejected base claim are further rejected based on their dependence.
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.
Claims 1, 6-7, 11-12, and 15-17 are rejected under 35 U.S.C. 102(a)(1) as being anticipated by Chang US 5,687,360.
Regarding claim 1, Chang teaches:
1. A branch instruction processing method, comprising:
determining a branch instruction to be predicted based on a target branch instruction (step 300 of Fig. 3 loads a program containing branches, see col 8 lines 60-64, and step 303 predicts the branches using prediction heuristics, see col 8 lines 47-53, this indicates that the method of Fig. 3 determines branch instructions to be predicted based on the target branch instructions in the loaded program);
predicting the branch instruction to be predicted based on a plurality of branch prediction methods which are preset, to obtain corresponding prediction results (step 303 predicts the branch instruction based on a plurality of prediction heuristics/methods (which are preset in the sense that the heuristics are set before step 303), see also col 8 lines 52-53, and the prediction results are obtained at step 305, see col 9 lines 7-9);
determining prediction accuracy of each of the plurality of branch prediction methods based on the corresponding prediction results (step 305 determines the accuracy of each of the prediction heuristics/methods);
determining a branch prediction method among the plurality of branch prediction methods corresponding to the prediction accuracy with the highest value as a target branch prediction method (col 9 lines 10-15: by setting the BSEL field in step 308, the method of Fig. 3 determines the prediction heuristic/method with the highest prediction accuracy value as a target prediction method)); and
performing branch prediction on the target branch instruction based on the target branch prediction method (col 6 lines 6-20 describes that the best heuristic is identified before normal execution of the program and col 9 lines 10-15 describe saving the program after setting the BSEL field of each branch, this indicates that the normal execution of the program will perform branch prediction on the target branch instruction based on the target branch prediction method indicated by the BSEL field);
wherein the plurality of branch prediction method comprises a method for determining a current branch prediction result based on a branch prediction state (since the claim does not require there to be a branch prediction state and this limitation is contingent on there being a branch prediction state, this limitation is a contingent limitation that is not required under BRI of a method claim, see MPEP 2111.04 (II));
wherein the method for determining the current branch prediction result based on the branch prediction state comprises… (since this limitation is not required under BRI of a method claim, the steps that this limitation comprises are also not required under BRI).
Regarding claim 6, Chang teaches:
6. The branch instruction processing method according to claim 1,
Claim 6 further describes steps of the method for determining the current branch prediction result based on the branch prediction state. However, since the method for determining the current branch prediction result based on the branch prediction state is not required under BRI, the steps of this method are also not required under BRI.
Regarding claim 7, Chang teaches:
7. The branch instruction processing method according to claim 1,
Claim 7 further describes steps of the method for determining the current branch prediction result based on the branch prediction state. However, since the method for determining the current branch prediction result based on the branch prediction state is not required under BRI, the steps of this method are also not required under BRI.
Regarding claim 11, Chang teaches:
11. The branch instruction processing method according to claim 1, wherein the target branch instruction is a branch instruction actually to be processed by a processor (col 8 lines 55-56 describes executing the branch instruction (i.e., the target branch instruction) to determine a branch decision).
Regarding claim 12, Chang teaches:
12. The branch instruction processing method according to claim 1, wherein the branch instruction to be predicted is a branch instruction used to test an accuracy of the plurality of branch prediction methods subsequently (the branch instruction predicted by the prediction heuristics at step 303 is used to test the accuracy of the prediction heuristics subsequently at step 305, see col 9 lines 4-14).
Regarding claim 15, Chang teaches:
15. The branch instruction processing method according to claim 5, wherein when the current branch prediction is verified to be failed (since this limitation is contingent on the current branch prediction being verified to be failed, it is contingent limitation that is not required under BRI of a method claim), it represents that the current branch prediction result is wrong, and when the current branch prediction is verified to be successful (since this limitation is contingent on the current branch prediction being verified to be successful, it is contingent limitation that is not required under BRI of a method claim), it represents that the current branch prediction result is correct.
Regarding claim 16, Chang teaches:
16. The branch instruction processing method according to claim 6, wherein every time the method for determining the current branch prediction result based on the branch prediction state is applied, the cumulative number of the prediction results for the branch prediction state representing the jump execution branch instruction is initialized to be 1 (since this limitation follows from a contingent limitation (the method for determining the current branch prediction result is a contingent limitation), this limitation is also a contingent limitation that is not required under BRI of a method claim).
Regarding claim 17, Chang teaches:
17. The method according to claim 7, wherein every time the branch prediction method is applied, the cumulative number of the prediction results for the branch prediction state representing non-jump execution branch instruction is initialized to be 1 (since this limitation follows from a contingent limitation (as the cumulative number is introduced in a contingent limitation), this limitation is also a contingent limitation that is not required under BRI of a method claim).
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.
Claims 2-3 and 21 are rejected under 35 U.S.C. 103 as being unpatentable over Chang US 5,687,360 in view of Henry US 6,230,261.
Regarding claim 2, Chang teaches:
2. The branch instruction processing method according to claim 1,
Although Chang teaches that many types of heuristics other than the ones described may be utilized, Chang does not explicitly teach utilizing an always-taken prediction heuristic. That is, Chang does not teach:
wherein the plurality of branch prediction method comprises a method for always predicting a jump execution branch instruction.
However, Henry teaches a method for always predicting a jump execution branch instruction (branches of a first type that fall into the taken subset are always predicted taken, see col 9 lines 23-30 and lines 51-55).
It would have been obvious to one of ordinary skill in the art, before the effective filing date of the claimed invention, to modify Chang to include the always taken prediction method of Henry as one of the prediction heuristics. One of ordinary skill in the art would have been motivated to make this modification to improve branch prediction for branch instructions that are most accurately predicted using an always taken prediction.
Regarding claim 3, Chang teaches:
3. The branch instruction processing method according to claim 1,
Although Chang teaches that many types of heuristics other than the ones described may be utilized, Chang does not explicitly teach utilizing an always-taken prediction heuristic. That is, Chang does not teach:
wherein the plurality of branch prediction method comprises a method for always predicting a non-jump execution branch instruction.
However, Henry teaches a method for always predicting a non-jump execution branch instruction (branches of a second type that fall into the not taken subset are always predicted not taken, see col 9 lines 23-30 and lines 51-55).
It would have been obvious to one of ordinary skill in the art, before the effective filing date of the claimed invention, to modify Chang to include the always not taken prediction method of Henry as one of the prediction heuristics. One of ordinary skill in the art would have been motivated to make this modification to improve branch prediction for branch instructions that are most accurately predicted using an always not taken prediction.
Regarding claim 21, Chang teaches:
21. The device according to claim 9,
Chang does not teach:
Although Chang teaches that many types of heuristics other than the ones described may be utilized, Chang does not explicitly teach utilizing an always-taken prediction heuristic. That is, Chang does not teach:
wherein the operations comprises an operation for always predicting a jump execution branch instruction.
However, Henry teaches an operation for always predicting a jump execution branch instruction (branches of a first type that fall into the taken subset are always predicted taken, see col 9 lines 23-30 and lines 51-55).
It would have been obvious to one of ordinary skill in the art, before the effective filing date of the claimed invention, to modify Chang to include the always taken prediction method of Henry as one of the prediction heuristics. One of ordinary skill in the art would have been motivated to make this modification to improve branch prediction for branch instructions that are most accurately predicted using an always taken prediction.
Claims 9-10 are rejected under 35 U.S.C. 103 as being unpatentable over Chang US 5,687,360.
Regarding claim 9, Chang teaches:
9. A branch instruction processing device, comprising a memory and one or more processors, wherein a computer-readable instruction is stored in the memory, and when executed by the one or more processors, the computer-readable instruction makes the one or more processors execute operations (col 1 lines 9-11 and col 5 lines 18-20 indicates that a microprocessor performs the method of Chang, and microprocessors inherently require instructions stored in memory since microprocessors operate under the control of instructions stored in memory, see also col 8 lines 62-64 disclosing loading a program from memory) comprising:
determining a branch instruction to be predicted based on a target branch instruction (step 300 of Fig. 3 loads a program containing branches, see col 8 lines 60-64, and step 303 predicts the branches using prediction heuristics, see col 8 lines 47-53, this indicates that the method of Fig. 3 determines branch instructions to be predicted based on the target branch instructions in the loaded program);
predicting the branch instruction to be predicted based on a plurality of branch prediction methods which are preset, to obtain corresponding prediction results (step 303 predicts the branch instruction based on a plurality of prediction heuristics/methods (which are preset in the sense that the heuristics are set before step 303), see also col 8 lines 52-53, and the prediction results are obtained at step 305, see col 9 lines 7-9);
determining prediction accuracy of each of the plurality of branch prediction methods based on the corresponding prediction results (step 305 determines the accuracy of each of the prediction heuristics/methods);
determining a branch prediction method among the plurality of branch prediction methods corresponding to the prediction accuracy with the highest value as a target branch prediction method (col 9 lines 10-15: by setting the BSEL field in step 308, the method of Fig. 3 determines the prediction heuristic/method with the highest prediction accuracy value as a target prediction method)); and
performing branch prediction on the target branch instruction based on the target branch prediction method (col 6 lines 6-20 describes that the best heuristic is identified before normal execution of the program and col 9 lines 10-15 describe saving the program after setting the BSEL field of each branch, this indicates that the normal execution of the program will perform branch prediction on the target branch instruction based on the target branch prediction method indicated by the BSEL field);
wherein the branch prediction method comprises a method for determining a current branch prediction result based on a branch prediction state (col 7 line 50-col 8 line 30: each of the heuristics (MLPN, LLPN, etc.) are branch prediction methods that determine a prediction (i.e., a current branch prediction result) based on a branch prediction state);
The current embodiment of Chang does not explicitly teach:
wherein the method for determining the current branch prediction result based on the branch prediction state comprises:
determining that the branch prediction state is a non-jump execution branch instruction of a first-level and the current branch prediction result is not jump; keeping the branch prediction state to be the non-jump execution branch instruction of the first-level in response to a current branch prediction being verified to be successful; and adjusting the branch prediction state to be the non-jump execution branch instruction of a second-level in response to the current branch prediction being verified to be failed;
determining that the branch prediction state is the non-jump execution branch instruction of the second-level and the current branch prediction result is not jump; adjusting the branch prediction state to be the non-jump execution branch instruction of the first-level, in response to the current branch prediction being verified to be successful; and adjusting the branch prediction state to be a jump execution branch instruction of the second-level in response to the current branch prediction being verified to be failed;
determining that the branch prediction state is the jump execution branch instruction of the second-level and the current branch prediction result is jump, adjusting the branch prediction state to be the jump execution branch instruction of the first-level in response to the current branch prediction being verified to be successful, and adjusting the branch prediction state to be the non-jump execution branch instruction of the second-level in response to the current branch prediction being verified to be failed; and
determining that the branch prediction state is the jump execution branch instruction of the first-level and the current branch prediction result is jump, keeping the branch prediction state to be the jump execution branch instruction of the first-level in response to the current branch prediction being verified to be successful, and adjusting the current branch prediction state to be the jump execution branch instruction of the second-level in response to the current branch prediction being verified to be failed;
wherein, an execution probability of the first level is greater than an execution probability of the second level.
However, the Background of Chang teaches:
a method for determining the current branch prediction result based on the branch prediction state (col 3 lines 9-65: the local branch prediction heuristic determines predictions (i.e., the current branch prediction result) based on the prior branch decisions (i.e., the branch prediction state)) comprises:
determining that the branch prediction state is a non-jump execution branch instruction of a first-level and the current branch prediction result is not jump (col 3 lines 22-65: the branch prediction state may be 00 (i.e., a non-jump execution branch of a first level) and the prediction (i.e., the current branch prediction result) is not-taken/not jump since 00 is less than the midpoint threshold of 2); keeping the branch prediction state to be the non-jump execution branch instruction of the first-level in response to a current branch prediction being verified to be successful (col 3 lines 22-65: the count/branch prediction state remains at zero as long as the branch is not taken, which verifies the not taken prediction as successful); and adjusting the branch prediction state to be the non-jump execution branch instruction of a second-level in response to the current branch prediction being verified to be failed (col 3 lines 22-65: the counter is incremented to 01 if the branch is taken, which verifies the not taken prediction as failed);
determining that the branch prediction state is the non-jump execution branch instruction of the second-level and the current branch prediction result is not jump (col 3 lines 22-65: the branch prediction state may be 01 (i.e., a non-jump execution branch of the second level) and the prediction is not-taken since 01 is less than the midpoint threshold of 2); adjusting the branch prediction state to be the non-jump execution branch instruction of the first-level, in response to the current branch prediction being verified to be successful (col 3 lines 22-65: the counter is decremented to 00 if the branch is not taken, which verifies the not taken prediction as successful); and adjusting the branch prediction state to be a jump execution branch instruction of the second-level in response to the current branch prediction being verified to be failed (col 3 lines 22-65: the counter is incremented to 10 (i.e., a jump execution branch of the second level) if the branch is taken, which verifies the not taken prediction to be failed);
determining that the branch prediction state is the jump execution branch instruction of the second-level and the current branch prediction result is jump (col 3 lines 22-65: the branch prediction state may be 10 and the prediction is taken since 10 is greater than or equal to the midpoint threshold of 2), adjusting the branch prediction state to be the jump execution branch instruction of the first-level in response to the current branch prediction being verified to be successful (col 3 lines 22-65: the counter is incremented to 11 if the branch is taken, which verifies the taken prediction as successful), and adjusting the branch prediction state to be the non-jump execution branch instruction of the second-level in response to the current branch prediction being verified to be failed (col 3 lines 22-65: the counter is decremented to 01 if the branch is not taken, which verifies the taken prediction to be failed); and
determining that the branch prediction state is the jump execution branch instruction of the first-level and the current branch prediction result is jump (col 3 lines 22-65: the branch prediction state may be 11 and the prediction is taken since 11 is greater than or equal to the midpoint threshold of 2), keeping the branch prediction state to be the jump execution branch instruction of the first-level in response to the current branch prediction being verified to be successful (col 3 lines 22-65: the counter remains at 11 if the branch is taken, which verifies the taken prediction to be successful), and adjusting the current branch prediction state to be the jump execution branch instruction of the second-level in response to the current branch prediction being verified to be failed (col 3 lines 22-65: the counter is decremented to 10 if the branch is not taken, which verifies the taken prediction to be failed);
wherein, an execution probability of the first level is greater than an execution probability of the second level (col 3 lines 22-65: the execution probability/confidence of the 00 or 11 states (i.e., the first level) is greater than the execution probability/confidence of the 01 or 10 states (i.e., the second level) since 00/11 are based on more confirmed predictions that 01/10).
It would have been obvious to one of ordinary skill in the art, before the effective filing date of the claimed invention, to modify the prediction heuristics of the current embodiment of Chang to include the local prediction heuristic of the Background of Chang. One of ordinary skill in the art would have been motivated to make this modification to improve coverage of the prediction heuristics and to improve performance for scientific/engineering applications (col 2 lines 62-64).
Regarding claim 10, Chang teaches:
10. One or more non-transitory computer-readable storage media storing a computer-readable instruction, wherein the computer-readable instruction, when executed by one or more processors, makes the one or more processors execute operations (col 1 lines 9-11 and col 5 lines 18-20 indicates that a microprocessor performs the method of Chang, and microprocessors inherently require instructions stored in memory (i.e., non-transitory computer readable storage media) since microprocessors operate under the control of instructions stored in memory, see also col 8 lines 62-64 disclosing loading a program from memory) comprising:
determining a branch instruction to be predicted based on a target branch instruction (step 300 of Fig. 3 loads a program containing branches, see col 8 lines 60-64, and step 303 predicts the branches using prediction heuristics, see col 8 lines 47-53, this indicates that the method of Fig. 3 determines branch instructions to be predicted based on the target branch instructions in the loaded program);
predicting the branch instruction to be predicted based on a plurality of branch prediction methods which are preset, to obtain corresponding prediction results (step 303 predicts the branch instruction based on a plurality of prediction heuristics/methods (which are preset in the sense that the heuristics are set before step 303), see also col 8 lines 52-53, and the prediction results are obtained at step 305, see col 9 lines 7-9);
determining prediction accuracy of each of the plurality of branch prediction methods based on the corresponding prediction results (step 305 determines the accuracy of each of the prediction heuristics/methods);
determining a branch prediction method among the plurality of branch prediction methods corresponding to the prediction accuracy with the highest value as a target branch prediction method (col 9 lines 10-15: by setting the BSEL field in step 308, the method of Fig. 3 determines the prediction heuristic/method with the highest prediction accuracy value as a target prediction method)); and
performing branch prediction on the target branch instruction based on the target branch prediction method (col 6 lines 6-20 describes that the best heuristic is identified before normal execution of the program and col 9 lines 10-15 describe saving the program after setting the BSEL field of each branch, this indicates that the normal execution of the program will perform branch prediction on the target branch instruction based on the target branch prediction method indicated by the BSEL field);
wherein the branch prediction method comprises a method for determining a current branch prediction result based on a branch prediction state (col 7 line 50-col 8 line 30: each of the heuristics (MLPN, LLPN, etc.) are branch prediction methods that determine a prediction (i.e., a current branch prediction result) based on a branch prediction state);
The current embodiment of Chang does not explicitly teach:
wherein the method for determining the current branch prediction result based on the branch prediction state comprises:
determining that the branch prediction state is a non-jump execution branch instruction of a first-level and the current branch prediction result is not jump; keeping the branch prediction state to be the non-jump execution branch instruction of the first-level in response to a current branch prediction being verified to be successful; and adjusting the branch prediction state to be the non-jump execution branch instruction of a second-level in response to the current branch prediction being verified to be failed;
determining that the branch prediction state is the non-jump execution branch instruction of the second-level and the current branch prediction result is not jump; adjusting the branch prediction state to be the non-jump execution branch instruction of the first-level, in response to the current branch prediction being verified to be successful; and adjusting the branch prediction state to be a jump execution branch instruction of the second-level in response to the current branch prediction being verified to be failed;
determining that the branch prediction state is the jump execution branch instruction of the second-level and the current branch prediction result is jump, adjusting the branch prediction state to be the jump execution branch instruction of the first-level in response to the current branch prediction being verified to be successful, and adjusting the branch prediction state to be the non-jump execution branch instruction of the second-level in response to the current branch prediction being verified to be failed; and
determining that the branch prediction state is the jump execution branch instruction of the first-level and the current branch prediction result is jump, keeping the branch prediction state to be the jump execution branch instruction of the first-level in response to the current branch prediction being verified to be successful, and adjusting the current branch prediction state to be the jump execution branch instruction of the second-level in response to the current branch prediction being verified to be failed;
wherein, an execution probability of the first level is greater than an execution probability of the second level.
However, the Background of Chang teaches:
a method for determining the current branch prediction result based on the branch prediction state (col 3 lines 9-65: the local branch prediction heuristic determines predictions (i.e., the current branch prediction result) based on the prior branch decisions (i.e., the branch prediction state)) comprises:
determining that the branch prediction state is a non-jump execution branch instruction of a first-level and the current branch prediction result is not jump (col 3 lines 22-65: the branch prediction state may be 00 (i.e., a non-jump execution branch of a first level) and the prediction (i.e., the current branch prediction result) is not-taken/not jump since 00 is less than the midpoint threshold of 2); keeping the branch prediction state to be the non-jump execution branch instruction of the first-level in response to a current branch prediction being verified to be successful (col 3 lines 22-65: the count/branch prediction state remains at zero as long as the branch is not taken, which verifies the not taken prediction as successful); and adjusting the branch prediction state to be the non-jump execution branch instruction of a second-level in response to the current branch prediction being verified to be failed (col 3 lines 22-65: the counter is incremented to 01 if the branch is taken, which verifies the not taken prediction as failed);
determining that the branch prediction state is the non-jump execution branch instruction of the second-level and the current branch prediction result is not jump (col 3 lines 22-65: the branch prediction state may be 01 (i.e., a non-jump execution branch of the second level) and the prediction is not-taken since 01 is less than the midpoint threshold of 2); adjusting the branch prediction state to be the non-jump execution branch instruction of the first-level, in response to the current branch prediction being verified to be successful (col 3 lines 22-65: the counter is decremented to 00 if the branch is not taken, which verifies the not taken prediction as successful); and adjusting the branch prediction state to be a jump execution branch instruction of the second-level in response to the current branch prediction being verified to be failed (col 3 lines 22-65: the counter is incremented to 10 (i.e., a jump execution branch of the second level) if the branch is taken, which verifies the not taken prediction to be failed);
determining that the branch prediction state is the jump execution branch instruction of the second-level and the current branch prediction result is jump (col 3 lines 22-65: the branch prediction state may be 10 and the prediction is taken since 10 is greater than or equal to the midpoint threshold of 2), adjusting the branch prediction state to be the jump execution branch instruction of the first-level in response to the current branch prediction being verified to be successful (col 3 lines 22-65: the counter is incremented to 11 if the branch is taken, which verifies the taken prediction as successful), and adjusting the branch prediction state to be the non-jump execution branch instruction of the second-level in response to the current branch prediction being verified to be failed (col 3 lines 22-65: the counter is decremented to 01 if the branch is not taken, which verifies the taken prediction to be failed); and
determining that the branch prediction state is the jump execution branch instruction of the first-level and the current branch prediction result is jump (col 3 lines 22-65: the branch prediction state may be 11 and the prediction is taken since 11 is greater than or equal to the midpoint threshold of 2), keeping the branch prediction state to be the jump execution branch instruction of the first-level in response to the current branch prediction being verified to be successful (col 3 lines 22-65: the counter remains at 11 if the branch is taken, which verifies the taken prediction to be successful), and adjusting the current branch prediction state to be the jump execution branch instruction of the second-level in response to the current branch prediction being verified to be failed (col 3 lines 22-65: the counter is decremented to 10 if the branch is not taken, which verifies the taken prediction to be failed);
wherein, an execution probability of the first level is greater than an execution probability of the second level (col 3 lines 22-65: the execution probability/confidence of the 00 or 11 states (i.e., the first level) is greater than the execution probability/confidence of the 01 or 10 states (i.e., the second level) since 00/11 are based on more confirmed predictions that 01/10).
It would have been obvious to one of ordinary skill in the art, before the effective filing date of the claimed invention, to modify the prediction heuristics of the current embodiment of Chang to include the local prediction heuristic of the Background of Chang. One of ordinary skill in the art would have been motivated to make this modification to improve coverage of the prediction heuristics and to improve performance for scientific/engineering applications (col 2 lines 62-64).
Claim 18 is rejected under 35 U.S.C. 103 as being unpatentable over Chang US 5,687,360 in view of Levenstein US 2020/0167163.
Regarding claim 18, Chang teaches:
18. The device according to claim 9,
Chang does not teach:
wherein the device further includes:
an input port connected to the processor, configured for transmitting commands input from external to the processor; and
a display unit connected to the processor, configured for displaying a processing result of the processor to the external; wherein the display unit is a display panel or a laser scanning displayer.
However, Levenstein teaches:
an input port connected to the processor (Fig. 6, connection between the processor 612 and bus 622), configured for transmitting commands input from external to the processor ([0070] describes that the processor processes data under control of software 650 and Fig. 6 shows the processor connected to software 650 by the bus 622, which indicates that this connection transmits commands input from software 650 (which is outside the processor) to the processor);
a display unit connected to the processor ([0076]: graphical display devices may be connected to the processor by the I/O interface 626), configured for displaying a processing result of the processor to the external ([0076]: the graphical display devices receive output from the computer system, which indicates that graphical display devices are configured for displaying results of the processor to the outside); wherein the display unit is a display panel or a laser scanning displayer ( [0076]: the display of a graphical display device is a display panel).
It would have been obvious to one of ordinary skill in the art, before the effective filing date of the claimed invention, to modify Chang to include the input port and display unit connected to the processor as taught by Levenstein. One of ordinary skill in the art would have been motivated to make this modification to improve usability of the processor since an input port would allow the processor to be controlled externally and a display unit would allow receive feedback from the processor
Conclusion
Applicant's amendment necessitated the new ground(s) of rejection presented in this Office action. Accordingly, THIS ACTION IS MADE FINAL. See MPEP § 706.07(a). 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 extension fee 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 date of this final action.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to KASIM ALLI whose telephone number is (571)270-1476. The examiner can normally be reached Monday - Friday 9am 5pm.
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, Andrew Caldwell can be reached on (571) 272-3702. 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.
/ANDREW CALDWELL/Supervisory Patent Examiner, Art Unit 2182
/KASIM ALLI/Examiner, Art Unit 2182
Prosecution Insights