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/16/2025. Claims 1-8, 10-15, and 17-22 are pending. Claims 1-2, 5, 8, 12, 15, 19, and 21-22 are amended.
Response to Arguments
Applicant's arguments filed 09/16/2025 have been fully considered but they are not persuasive.
On pages 7-8 of the Remarks, Applicant submits:
It is respectfully noted that the claims do not recite a "retirement branch history", and that "copy of a global branch history" is explicitly shown in Figs. 6 and 7. The Office Action has not cited any statute or regulation indicating that features of the invention may not be shown in a flow diagram that illustrates a method. Applicant also notes that, as outlined in MPEP 608.02, the statutory requirement for showing the claimed invention only requires that the "applicant shall furnish a drawing where necessary for the understanding of the subject matter to be patented..." (See 35 U.S.C. 113; see also 37 CFR §1.81(a)). In the present application, Applicant respectfully submits that an express illustration of the feature "copy of a global branch history" is not necessary for understanding by one of ordinary skill in the art of the subject matter to be patented, particularly in light of the fact that "global branch history 206" is shown in Figure 2, and a copy of such a global branch history would be understood by persons of ordinary skill in the art. Accordingly, reconsideration and withdrawal of this objection are respectfully requested.
However, this argument is not persuasive because the copy of the global branch history is a claimed feature that is required to be shown in the Drawings. Figs. 6 and 7 do not explicitly show the copy of the global branch history, these figures merely show steps involving the copy of the global branch history. The copy of the global branch history is a structural detail that is essential for proper understanding of the invention. It is not clear whether the global branch history 206 is the copy that is referenced in the claims and in Figs. 6-7 or if they are separate.
On page 9-10 of the Remarks, Applicant submits:
The Office Action indicates that Levitan teaches "updating one or more TAGE tables based on the copy of the global branch history responsive to storing the copy of the global branch history, including updating one or more TAGE table entries respectively corresponding to one or more indexes generated based on the copy of the global branch history", citing Levitan at paras. 0016, 0019, 0022, and 0041-0043. (Office Action at pages 7-8). Levitan discloses that "[t]he GHV and the predictor table can be continually updated based upon whether or not conditional branches have been taken." (Levitan at para. 0016). Levitan discusses modifying the predictor tables in paras. 0045 and 0046 and Fig. 6. This disclosure indicates that, in the event of a misprediction, the folded GHVs and predictor tables may no longer be acceptable and may be discarded and recreated. (See, e.g., Levitan at para. 0044). Levitan discloses that, in another embodiment, old prediction history may be stored in the predictor tables, which may require additional memory, and then when new history data is available, new predictor table entries may be added. (See, e.g., Levitan at para. 0045). Thus, Levitan discloses that the tables are updated by discarding and recreating the tables or adding new predictor table entries. Levitan does not teach or suggest updating one or more table entries respectively corresponding to one or more indexes generated based on the copy of the global branch history and an address of a branch instruction being retired, as recited in the independent claims.
In the Response to Arguments section, the Office Action argued that Applicant's argument "references Fig. 6 of Levitan but the rejection relies on the embodiment of Fig. 5." (Office Action at page 4). It is respectfully noted that Applicant's argument relates to updating the TAGE tables, and Levitan at Fig. 5 and corresponding description do not appear to include any disclosure regarding updating the predictor tables. In contrast, Levitan at Fig. 6 and corresponding description do discuss updating the predictor tables, and indicate that the tables are updated by discarding and recreating the tables or adding new predictor table entries. The Response to Arguments section of the Office Action also cited Levitan at para. 0017, and stated that Levitan teaches "where the GHVs of different lengths are used to create indexes into the predictor tables". (Office Action at page 4). It is respectfully noted that this cited portion of Levitan relates to creating indexes to perform a prediction, and does not include any disclosure regarding generating indexes for updating predictor table entries. Levitan fails to teach or suggest updating one or more TAGE tables based on a copy of a global branch history that has been stored based the detection of an end of a predefined interval of performing branch predictions, as recited in the independent claims. Levitan also fails to teach or suggest updating one or more TAGE table entries respectively corresponding to one or more indexes generated based on such a copy of the global branch history and an address of a branch instruction being retired, as recited in the independent claims.
Examiner notes that the first part of this argument was previously responded to on page 4 of the previous Non-Final Rejection (dated 06/03/2025) and the second part of this argument is with respect to that response. Applicant’s arguments with respect to Fig. 6 are irrelevant because the rejection does not rely on the embodiment of Fig. 6; Fig. 6 and Fig. 5 are directed to different embodiments for handling mispredictions and the rejection relies on the embodiment of Fig. 5 in the context of the rest of Levitan to teach the updating limitation. Applicant’s argument that the embodiment of Fig. 5 does not disclose updating the predictor tables is not persuasive because the rejection does not rely solely on the disclosure with respect to Fig. 5 to teach this feature. Applicant’s argument that [0017] relates to creating indexes for performing a prediction and not for updating predictor table entries is not persuasive because one of ordinary skill in the art would understand that the manner in which an entry of a predictor table is accessed does not depend on what the access is for- in either case an index would be created from the GHV and PC to access an entry.
On pages 10-11 of the Remarks, Applicant submits:
In addition, the Office Action acknowledged that Levitan fails to teach "detecting an end of a predefined interval of performing branch predictions; storing the copy based on the detection of the end of the predefined interval". (Office Action at page 8) (bold in original). The Office Action further stated that "[h]owever, Reinhardt teaches generating checkpoints at predetermined intervals, see [0071]." (Office Action at page 8). Reinhardt discusses periodically checkpointing architectural register files and logs in a multi-threaded environment so that if an error occurs, the processor can reload the state from the last checkpoint. (See, e.g., Reinhardt at para. 0026). Reinhardt does not discuss branch prediction or storing a copy of a global branch history at a checkpoint. Reinhardt does not discuss a predefined interval of performing branch predictions. Reinhardt does not discuss detecting an end of a predefined interval of performing branch predictions, and does not suggest any action that might be taken based on such a detection. Thus, like the Levitan reference, Reinhardt also clearly fails to teach or suggest "detecting an end of a predefined interval of performing branch predictions" and "storing, by a TAGE branch predictor and based on the detection of the end of the predefined interval, a copy of a global branch history". In addition, Reinhardt never uses the periodically saved information unless an error occurs. In contrast, claim 1 recites "updating one or more TAGE tables based on the copy of the global branch history responsive to storing the copy of the global branch history".
In the Response to Arguments section, the Office Action argued that "the office action modifies Levitan in view of Reinhardt to periodically store its GHV." (Office Action at page 5). However, there is no disclosure in Reinhardt that teaches or suggests periodically storing a GHV, and one of ordinary skill in the art would not have been motivated to do so based on the teaching of Reinhardt. It is respectfully noted that Reinhardt discusses storing specific information (e.g., architectural register values and logs in a redundant multi-threaded (RMT) system) for a specific purpose (e.g., to detect hardware faults and provide hardware recovery). (See, Reinhardt at paras. 0024-0026). Reinhardt does not teach or suggest storing a copy of a global branch history at a checkpoint. Like the Levitan reference, Reinhardt also does not teach or suggest detecting an end of a predefined interval of performing branch predictions, and does not teach or suggest any action that might be taken based on such a detection.
In the Response to Arguments section, the Office Action argued that "[i]n this combination, Levitan will detect the end of a predefined interval, at which point it will save the GHV, and since Levitan teaches performing branch predictions, the predefined interval of the combination is an interval of performing branch predictions." (Office Action at page 5). The Office Action acknowledged that Levitan fails to teach "detecting an end of a predefined interval of performing branch predictions". (Office Action at page 8) (bold in original). Applicant respectfully agrees that Levitan fails to teach or suggest this subject matter. Reinhardt also fails to teach or suggest this subject matter. The disclosure in Reinhardt, which discusses periodically storing architectural register values and logs in a redundant multi-threaded (RMT) system to detect hardware faults and provide hardware recovery, fails to teach or suggest modifying Levitan to detect an end of a predefined interval of performing branch predictions.
Examiner notes that the first paragraph of this argument was previously responded to on page 5 of the previous Non-Final Rejection (dated 06/03/2025) and paragraphs 2-3 of this argument is with respect to that response. Applicant’s argument that Reinhardt does not teach storing a GHV or that Levitan does not teach detecting an end of a predefined interval is not persuasive because they attack the references individually without considering without considering the combination, the rejection relies on the combination of Levitan and Reinhardt to teach these features. Applicant’s argument that one of ordinary skill in the art would not have been motivated to periodically store the GHV based on the teaching of Reinhardt is not persuasive because it does not consider the motivation provided on page 8 of the rejection- that modifying Levitan to periodically store the GHV would enable recovering from faults while limiting the amount of data that may be lost.
On page 12 of the Remarks, Applicant submits:
The dependent claims are also further distinguishable from the cited references. For example, amended dependent claim 2 recites "updating the one or more TAGE tables is in response to retirement of the branch instruction, and wherein updating the one or more TAGE table entries includes incrementing a counter for a taken branch or decrementing a counter for a non-taken branch". Levitan discloses that the predictor tables are updated by discarding and recreating the tables or adding new predictor table entries (See, e.g., Levitan at paras. 0044-0045), and fails to teach or suggest the table updating subject matter recited in amended independent claim 2.
However, this argument is moot because the new ground of rejection does not rely on Levitan to teach this feature.
On page 12 of the Remarks, Applicant submits:
Amended dependent claim 5 recites "wherein the predefined interval comprises a number of branch instructions for which a prediction is to be generated". In the rejection of dependent claim 5, the Office Action at page 9 relies on Reinhardt for teaching or suggesting "wherein the predefined interval comprises a number of prediction cycles." Reinhardt describes the interval as being a fixed time interval - not as being a number of branch instructions for which a prediction is to be generated, as claimed. It is noted that the time to generate predictions for a number of branch instructions, such as 10 branch instructions, may vary for every set of 10 branch instructions for which predictions are generated. The cited references fail to teach or suggest the subject matter of dependent claim 5.
However, this argument is not persuasive because the BRI of this limitation would include a fixed time interval during which a prediction is generated for any number of branch instructions, which is taught by the combination of Levitan and Reinhardt. Specifically, the combination would generate predictions for branch instructions (as taught by Levitan) during the predefined interval (as taught by Reinhardt).
On page 13 of the Remarks, Applicant submits:
Amended dependent claim 21 recites "updating the copy of the global branch history in response to retirement of the branch instruction after updating the one or more TAGE tables in response to retirement of the branch instruction". The Office Action stated that "in the combination, the GHV of Levitan is periodically checkpointed (as taught by Reinhardt) .. ." (Office Action at page 20). As discussed above, Reinhardt does not teach periodically checkpointing a GHV, and does not even mention a GHV. The Office Action further stated that "since the GHV is updated periodically, a checkpoint of the GHV (which updates the copy of the GHV) will occur after updating the TAGE tables, see Levitan [0016]". (Office Action at page 20). Amended dependent claim 21 recites that both the copy of the global branch history and the one or more TAGE tables are updated in response to retirement of the same branch instruction, and that the copy of the global branch history in this situation is updated after the one or more TAGE tables. Levitan and Reinhardt fail to teach or suggest this subject matter, and as acknowledged in the Office Action, fail to teach or suggest any updating "in response to retirement of a branch instruction." (See, Office Action at page 20). Olson fails to cure the deficiencies of Levitan and Reinhardt. The Office Action indicated that Olson teaches "updating a non-speculative global history with the resolution of a branch operation, and correcting speculative history with the non-speculative history if the branch prediction is incorrect." (Office Action at page 20). The cited portion of Olson does not appear to mention anything about updating TAGE tables, updating TAGE tables in response to retirement of a branch instruction, or updating a copy of a global branch history after such updating of the TAGE tables.
However, this argument is this argument is moot because the current grounds of rejection no longer relies on Olson. The current combination of Levitan in view of Natarajan and Reinhardt teaches the limitation in claim 21 since the current combination teaches updating the TAGE tables and the GHV in response to retirement of the branch instruction, where the update to the copy of the GHV is also in response to the retirement of the branch instruction that updated the GHV since the copy is updated based on checkpointing the GHV, which would occur at the predetermined interval after the TAGE table is updated.
Drawings
The drawings are objected to under 37 CFR 1.83(a). The drawings must show every feature of the invention specified in the claims. Therefore, the copy of the global branch history must be shown or the feature(s) canceled from the claim(s). Examiner notes that Figures 6 and 7 do not show the copy of the global branch history or retirement branch history, Figures 6 and 7 only show steps of a method. No new matter should be entered.
Corrected drawing sheets in compliance with 37 CFR 1.121(d) are required in reply to the Office action to avoid abandonment of the application. Any amended replacement drawing sheet should include all of the figures appearing on the immediate prior version of the sheet, even if only one figure is being amended. The figure or figure number of an amended drawing should not be labeled as “amended.” If a drawing figure is to be canceled, the appropriate figure must be removed from the replacement sheet, and where necessary, the remaining figures must be renumbered and appropriate changes made to the brief description of the several views of the drawings for consistency. Additional replacement sheets may be necessary to show the renumbering of the remaining figures. Each drawing sheet submitted after the filing date of an application must be labeled in the top margin as either “Replacement Sheet” or “New Sheet” pursuant to 37 CFR 1.121(d). If the changes are not accepted by the examiner, the applicant will be notified and informed of any required corrective action in the next Office action. The objection to the drawings will not be held in abeyance.
Claim Rejections - 35 USC § 112
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 8, 10-15, 17-20 and 22 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 8 recites “a branch instruction” in line 14. It is unclear whether this is the same branch instruction introduced in line 9 or if they are different.
Claim 10 recites “the branch instruction” in line 3. It is unclear which branch instruction in claim 8 this refers to.
Claim 15 recites “a branch instruction” in line 14. It is unclear whether this is the same branch instruction introduced in line 9 or if they are different.
Claim 17 recites “the branch instruction” in line 3. It is unclear which branch instruction in claim 15 this refers to.
Claim 22 recites “the branch instruction” in line 5. It is unclear which branch instruction in claim 8 this refers to.
Claims dependent on a rejected base claim are further rejected based on their dependence.
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 1-2, 5-6, 8, 12-13, 15, and 19-22 are rejected under 35 U.S.C. 103 as being unpatentable over Levitan US 2015/0331691 in view of Natarajan US 2020/0104137 (cited in 892 dated 06/03/2025) and Reinhardt US 2005/0050307.
Regarding claim 1, Levitan teaches:
1. A method of enforcing consistency across redundant tagged geometric (TAGE) branch histories, the method comprising:
storing, by a TAGE branch predictor (Fig. 1 branch prediction logic 110 is a TAGE branch predictor since it includes a TAGE unit, see also [0023]), a copy of a global branch history (the branch prediction logic uses a stored version/copy of the entire GHV, see [0022], which is stored by the branch prediction logic, see [0043]); and
updating one or more TAGE tables based on the copy of the global branch history responsive to storing the copy of the global branch history, including updating one or more TAGE table entries respectively corresponding to one or more indexes generated based on the copy of the global branch history and an address of a branch instruction (upon misprediction, the folded GHVs are recreated based on the copy of the full GHV and the branch prediction circuit is enabled once the folded GHVs are available, see [0041]-[0043]; since the prediction table is updated based on whether the branches are taken or not taken, see [0016], and since a hash of the branch PC (i.e., an address of a branch instruction) and the folded GHVs (the GHVs of respective lengths) are used to generate indices into the prediction table, see [0019], [0022], and [0026], this indicates that, after enabling the prediction circuit after a misprediction, entries in the TAGE tables are updated using a hash of a branch PC and the folded GHVs to generate the indexes into the predictor tables, which are generated based on and responsive to the stored full GHV, and the entries that are updated correspond to indexes generated based on the branch PC and the stored full GHV (since the folded GHVs that are used to generate the indexes are recreated from the stored full GHV when there is a misprediction)).
Levitan does not teach:
updating the TAGE table entries based on an address of a branch instruction being retired;
detecting an end of a predefined interval of performing branch predictions;
storing the copy based on the detection of the end of the predefined interval;
However, Natarajan teaches updating TAGE table entries based on an address of a branch instruction being retired ([0058]-[0059] teaches that the predictor tables are updated at instruction retirement time by recording the resolved direction of a branch instruction at retirement time and [0076] teaches using the IP/address of the branch instruction to index an entry in the TAGE for updating, which indicates that the address of a branch being retired is used to select an entry in the TAGE table to update).
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 TAGE predictor of Levitan to be updated based on the address of a branch instruction being retired as taught by Natarajan. One of ordinary skill in the art would have been motivated to make this modification to ensure accuracy of the TAGE tables, as the results of a branch being retired are known to be accurate.
The combination of Levitan and Natarajan does not teach:
detecting an end of a predefined interval of performing branch predictions;
storing the copy based on the detection of the end of the predefined interval;
However, Reinhardt teaches generating checkpoints at predetermined intervals, see [0071].
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 TAGE predictor of Levitan to store the full GHV by checkpointing it at predetermined intervals as taught by Reinhardt. In this combination, the TAGE predictor will determine the end of a predefined interval of cycles of the predictor (i.e., branch prediction cycles) so that it may checkpoint the GHV in response to the predefined interval occurring. One of ordinary skill in the art would have been motivated to make this modification to enable recovering from faults, see Reinhardt [0071], while limiting the amount of data that may be lost to data generated in the predetermined interval.
Regarding claim 2, Levitan in view of Natarajan and Reinhardt teaches:
2. The method of claim 1, wherein updating the one or more TAGE tables is in response to retirement of the branch instruction (Natarajan [0059]: the prediction table is updated with the resolved direction of the branch instruction at retirement time, which is in response to retirement of the branch instruction), and the TAGE table entries including a counter (Levitan [0025]: each entry includes a signed counter prediction element).
Levitan in view of Natarajan and Reinhardt does not teach:
wherein updating the one or more TAGE table entries includes incrementing a counter for a taken branch or decrementing a counter for a non-taken branch.
However, Natarajan [0068] further teaches that the prediction tables (analogous to the TAGE tables of Levitan) include a prediction counter that is incremented when a taken/not taken prediction was correct or decremented when incorrect.
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 counters of Levitan to be updated by incrementing the counter for a correctly predicted taken branch or decrementing the counter for an incorrectly predicted non-taken branch as taught by Natarajan. One of ordinary skill in the art would have been motivated to make this modification to appropriately update the counters according to the branch outcomes, which would ensure accuracy of the predictions based on the counters.
Regarding claim 5, Levitan in view of Natarajan and Reinhardt teaches:
5. The method of claim 1, wherein the predefined interval comprises a number of branch instructions for which a prediction is to be generated (Reinhardt [0071]: the predetermined checkpoint interval may be a designated period of time, and the combination predicts branch instructions during the interval (i.e., the interval comprises a number of branch instructions for which a prediction is to be generated)).
Regarding claim 6, Levitan in view of Natarajan and Reinhardt teaches:
6. The method of claim 1, wherein the predefined interval comprises a time interval (Reinhardt [0071]: the predetermined checkpoint interval may be a designated period of time).
Regarding claim 8, Levitan teaches:
8. A TAGE branch predictor Fig. 1 branch prediction logic 110 is a TAGE branch predictor since it includes a TAGE unit, see also [0023]) for enforcing consistency across redundant TAGE branch histories, comprising:
a global branch history (the GHV at the time the stored version of the GHV is stored, see [0021]-[0022] which teaches an old version of the GHV used to make predictions and a stored version of the GHV that may be used to recreate the folded history upon misprediction (when the old GHV is invalid), this indicates that the stored version of the GHV is stored from a previously valid GHV); and
a copy of the global branch history ([0022] and [0043]: the stored version of the GHV in the branch prediction logic);
wherein the TAGE branch predictor configured to:
store the copy of the global branch history (the branch prediction logic uses a stored version/copy of the entire GHV, see [0022], which is stored by the branch prediction logic, see [0043]); and
update, in response to retirement of a branch instruction, one or more TAGE tables based on the copy of the global branch history responsive to storing the copy of the global branch history, including updating one or more TAGE table entries respectively corresponding to one or more indexes generated based on the copy of the global branch history and an address of a branch instruction (upon misprediction, the folded GHVs are recreated based on the copy of the full GHV and the branch prediction circuit is enabled once the folded GHVs are available, see [0041]-[0043]; since the prediction table is updated based on whether the branches are taken or not taken, see [0016], and since a hash of the branch PC (i.e., an address of a branch instruction) and the folded GHVs (the GHVs of respective lengths) are used to generate indices into the prediction table, see [0019], [0022], and [0026], this indicates that, after enabling the prediction circuit after a misprediction, entries in the TAGE tables are updated using a hash of a branch PC and the folded GHVs to generate the indexes into the predictor tables, which are generated based on and responsive to the stored full GHV, and the entries that are updated correspond to indexes generated based on the branch PC and the stored full GHV (since the folded GHVs that are used to generate the indexes are recreated from the stored full GHV when there is a misprediction))
Levitan does not teach:
update the TAGE table entries based on an address of a branch instruction being retired;
detect an end of a predefined interval of performing branch predictions;
storing the copy based on detection of the end of the predefined interval
However, Natarajan teaches updating TAGE table entries based on an address of a branch instruction being retired ([0058]-[0059] teaches that the predictor tables are updated at instruction retirement time by recording the resolved direction of a branch instruction at retirement time and [0076] teaches using the IP/address of the branch instruction to index an entry in the TAGE for updating, which indicates that the address of a branch being retired is used to select an entry in the TAGE table to update).
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 TAGE predictor of Levitan to be updated based on the address of a branch instruction being retired as taught by Natarajan. One of ordinary skill in the art would have been motivated to make this modification to ensure accuracy of the TAGE tables, as the results of a branch being retired are known to be accurate.
The combination of Levitan and Natarajan does not teach:
detect an end of a predefined interval of performing branch predictions;
storing the copy based on detection of the end of the predefined interval
However, Reinhardt teaches generating checkpoints are predetermined intervals, see [0071].
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 TAGE predictor of Levitan to store the full GHV by checkpointing it at predetermined intervals as taught by Reinhardt. In this combination, the TAGE predictor will determine the end of a predefined interval of cycles of the predictor (i.e., branch prediction cycles) so that it may checkpoint the GHV in response to the predefined interval occurring. One of ordinary skill in the art would have been motivated to make this modification to enable recovering from faults, see Reinhardt [0071], while limiting the amount of data that may be lost to data generated in the predetermined interval.
Regarding claim 12, Levitan in view of Natarajan and Reinhardt teaches:
12. The TAGE branch predictor of claim 8, wherein the predefined interval comprises a number of branch instructions for which a prediction is to be generated (Reinhardt [0071]: the predetermined checkpoint interval may be a designated period of time, and the combination predicts branch instructions during the interval (i.e., the interval comprises a number of branch instructions for which a prediction is to be generated)).
Regarding claim 13, Levitan in view of Natarajan and Reinhardt teaches:
13. The TAGE branch predictor of claim 8, wherein the predefined interval comprises a time interval (Reinhardt [0071]: the predetermined checkpoint interval may be a designated period of time).
Regarding claim 15, Levitan teaches:
15. An apparatus for enforcing consistency across redundant TAGE branch histories, comprising:
computer memory (Fig. 1 102); and
a processor operatively coupled to the computer memory (Fig. 1 components except for 102 form a processor, see also [0018] describing Fig. 1 as a processor circuit), the processor comprising a TAGE branch predictor (Fig. 1 branch prediction logic 110 is a TAGE branch predictor since it includes a TAGE unit, see also [0023]) configured to:
store a copy of a global branch history (the branch prediction logic uses a stored version/copy of the entire GHV, see [0022], which is stored by the branch prediction logic, see [0043]); and
update, in response to retirement of a branch instruction, one or more TAGE tables based on the copy of the global branch history responsive to storing the copy of the global branch history, including updating one or more TAGE table entries respectively corresponding to one or more indexes generated based on the copy of the global branch history and an address of a branch instruction (upon misprediction, the folded GHVs are recreated based on the copy of the full GHV and the branch prediction circuit is enabled once the folded GHVs are available, see [0041]-[0043]; since the prediction table is updated based on whether the branches are taken or not taken, see [0016], and since a hash of the branch PC (i.e., an address of a branch instruction) and the folded GHVs (the GHVs of respective lengths) are used to generate indices into the prediction table, see [0019], [0022], and [0026], this indicates that, after enabling the prediction circuit after a misprediction, entries in the TAGE tables are updated using a hash of a branch PC and the folded GHVs to generate the indexes into the predictor tables, which are generated based on and responsive to the stored full GHV, and the entries that are updated correspond to indexes generated based on the branch PC and the stored full GHV (since the folded GHVs that are used to generate the indexes are recreated from the stored full GHV when there is a misprediction)).
Levitan does not teach:
update the TAGE table entries based on an address of a branch instruction being retired;
detect an end of a predefined interval of performing branch predictions;
storing the copy based on detection of the end of the predefined interval
However, Natarajan teaches updating TAGE table entries based on an address of a branch instruction being retired ([0058]-[0059] teaches that the predictor tables are updated at instruction retirement time by recording the resolved direction of a branch instruction at retirement time and [0076] teaches using the IP/address of the branch instruction to index an entry in the TAGE for updating, which indicates that the address of a branch being retired is used to select an entry in the TAGE table to update).
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 TAGE predictor of Levitan to be updated based on the address of a branch instruction being retired as taught by Natarajan. One of ordinary skill in the art would have been motivated to make this modification to ensure accuracy of the TAGE tables, as the results of a branch being retired are known to be accurate.
The combination of Levitan and Natarajan does not teach:
detect an end of a predefined interval of performing branch predictions;
storing the copy based on detection of the end of the predefined interval
However, Reinhardt teaches generating checkpoints are predetermined intervals, see [0071].
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 TAGE predictor of Levitan to store the full GHV by checkpointing it at predetermined intervals as taught by Reinhardt. In this combination, the TAGE predictor will determine the end of a predefined interval of cycles of the predictor (i.e., branch prediction cycles) so that it may checkpoint the GHV in response to the predefined interval occurring. One of ordinary skill in the art would have been motivated to make this modification to enable recovering from faults, see Reinhardt [0071], while limiting the amount of data that may be lost to data generated in the predetermined interval.
Regarding claim 19, Levitan in view of Natarajan and Reinhardt teaches:
19. The apparatus of claim 15, wherein the predefined interval comprises a number of branch instructions for which a prediction is to be generated (Reinhardt [0071]: the predetermined checkpoint interval may be a designated period of time, and the combination predicts branch instructions during the interval (i.e., the interval comprises a number of branch instructions for which a prediction is to be generated)).
Regarding claim 20, Levitan in view of Reinhardt teaches:
20. The apparatus of claim 15, wherein the predefined interval comprises a time interval (Reinhardt [0071]: the predetermined checkpoint interval may be a designated period of time).
Regarding claim 21, Levitan in view of Natarajan and Reinhardt teaches:
21. The method of claim 1, and further comprising:
updating the copy of the global branch history in response to retirement of the branch instruction after updating the one or more TAGE tables in response to retirement of the branch instruction (Natarajan [0055] and [0058]-[0059] teaches updating the branch history (i.e., the GHV of the combination) and the predictor tables (i.e., the TAGE tables of the combination) in response to retirement of a branch instruction; further, the combination updates the copy of the GHV by periodically checkpointing the GHV (as taught by Reinhardt), and since the GHV is updated in response to retirement of a branch instruction, the update of the GHV copy (which occurs after updating the GHV and the predictor tables) is also responsive to the retirement of the branch instruction).
Regarding claim 22, Levitan in view of Natarajan and Reinhardt teaches:
22. The TAGE branch predictor of claim 8, wherein the TAGE branch predictor is further configured to:
update the copy of the global branch history in response to retirement of the branch instruction after updating the one or more TAGE tables in response to retirement of the branch instruction (Natarajan [0055] and [0058]-[0059] teaches updating the branch history (i.e., the GHV of the combination) and the predictor tables (i.e., the TAGE tables of the combination) in response to retirement of a branch instruction; further, the combination updates the copy of the GHV by periodically checkpointing the GHV (as taught by Reinhardt), and since the GHV is updated in response to retirement of a branch instruction, the update of the GHV copy (which occurs after updating the GHV and the predictor tables) is also responsive to the retirement of the branch instruction).
Claims 3-4, 10-11, and 17-18 are rejected under 35 U.S.C. 103 as being unpatentable over Levitan US 2015/0331691 in view of Natarajan US 2020/0104137, Reinhardt US 2005/0050307 and Col US 6,189,091.
Regarding claim 3, Levitan in view of Natarajan and Reinhardt teaches:
3. The method of claim 2,
Levitan in view of Natarajan and Reinhardt does not explicitly teach updating the copy of the global branch history based on a prediction for the branch instruction,
However, Col teaches updating a copy of a global branch history based on a prediction for a branch instruction (col 7 lines 9-20: a global history buffer is copied to a temp register and if a branch prediction was incorrect the GHB is restored from the copy and the copy is updated in the GHB to reflect the branch outcome).
It would have been obvious to one of ordinary skill in the art, before the effective filing date of the claimed invention, to modify Levitan in view of Natarajan Reinhardt to use the stored GHV to restore the GHV and to update the restored GHV (i.e., update the copy in the GHV) to reflect the branch outcome as taught by Col. In this combination, the stored copy of the GHV will be restored to the GHV and the copy of the stored GHV will be updated by updating the restored GHV to reflect the branch outcome based on the prediction for the branch instruction being incorrect. One of ordinary skill in the art would have been motivated to make this modification to efficiently recover from mispredictions since restoring the GHV from the stored GHV would enable updating the GHV after recovering from a misprediction while also enabling recovering from further mispredictions using the stored GHV (as opposed to implementations which do not restore the GHV from the stored GHV).
Regarding claim 4, Levitan in view of Natarajan, Reinhardt, and Col teaches:
4. The method of claim 3, wherein the prediction is based on the copy of the global branch history (Levitan [0043] teaches after recreating the folded GHV using the stored GHV (restored into the GHV in the combination with Col), enabling the prediction circuit to generate a branch prediction (see also claim 7 of Levitan), where this branch prediction is based on the copy of the GHV (restored in the GHV), see also Levitan [0019] describing using the GHV to index into a prediction table to generate a prediction).
Regarding claim 10, Levitan in view of Natarajan and Reinhardt teaches:
10. The TAGE branch predictor of claim 8,
Levitan in view of Natarajan and Reinhardt does not explicitly teach update the copy of the global branch history based on a prediction for the branch instruction,
However, Col teaches updating a copy of a global branch history based on a prediction for a branch instruction (col 7 lines 9-20: a global history buffer is copied to a temp register and if a branch prediction was incorrect the GHB is restored from the copy and the copy is updated in the GHB to reflect the branch outcome).
It would have been obvious to one of ordinary skill in the art, before the effective filing date of the claimed invention, to modify Levitan in view of Reinhardt to use the stored GHV to restore the GHV and to update the restored GHV (i.e., update the copy in the GHV) to reflect the branch outcome as taught by Col. In this combination, the stored copy of the GHV will be restored to the GHV and the copy of the stored GHV will be updated by updating the restored GHV to reflect the branch outcome based on the prediction for the branch instruction being incorrect. One of ordinary skill in the art would have been motivated to make this modification to efficiently recover from mispredictions since restoring the GHV from the stored GHV would enable updating the GHV after recovering from a misprediction while also enabling recovering from further mispredictions using the stored GHV (as opposed to implementations which do not restore the GHV from the stored GHV).
Regarding claim 11, Levitan in view of Natarajan, Reinhardt and Col teaches:
11. The TAGE branch predictor of claim 10, wherein the prediction is based on the copy of the global branch history (Levitan [0043] teaches after recreating the folded GHV using the stored GHV (restored into the GHV in the combination with Col), enabling the prediction circuit to generate a branch prediction (see also claim 7 of Levitan), where this branch prediction is based on the copy of the GHV (restored in the GHV), see also Levitan [0019] describing using the GHV to index into a prediction table to generate a prediction).
Regarding claim 17, Levitan in view of Natarajan and Reinhardt teaches:
17. The apparatus of claim 15,
Levitan in view of Natarajan and Reinhardt does not explicitly teach the processor to update the copy of the global branch history based on a prediction for the branch instruction,
However, Col teaches updating a copy of a global branch history based on a prediction for a branch instruction (col 7 lines 9-20: a global history buffer is copied to a temp register and if a branch prediction was incorrect the GHB is restored from the copy and the copy is updated in the GHB to reflect the branch outcome).
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 processor of Levitan in view of Reinhardt to use the stored GHV to restore the GHV and to update the restored GHV (i.e., update the copy in the GHV) to reflect the branch outcome as taught by Col. In this combination, the stored copy of the GHV will be restored to the GHV and the copy of the stored GHV will be updated by updating the restored GHV to reflect the branch outcome based on the prediction for the branch instruction being incorrect. One of ordinary skill in the art would have been motivated to make this modification to efficiently recover from mispredictions since restoring the GHV from the stored GHV would enable updating the GHV after recovering from a misprediction while also enabling recovering from further mispredictions using the stored GHV (as opposed to implementations which do not restore the GHV from the stored GHV).
Regarding claim 18, Levitan in view of Natarajan, Reinhardt and Col teaches:
18. The apparatus of claim 17, wherein the prediction is based on the copy of the global branch history (Levitan [0043] teaches after recreating the folded GHV using the stored GHV (restored into the GHV in the combination with Col), enabling the prediction circuit to generate a branch prediction (see also claim 7 of Levitan), where this branch prediction is based on the copy of the GHV (restored in the GHV), see also Levitan [0019] describing using the GHV to index into a prediction table to generate a prediction).
Claims 7 and 14 are rejected under 35 U.S.C. 103 as being unpatentable over Levitan US 2015/0331691 in view of Natarajan US 2020/0104137, Reinhardt US 2005/0050307, and Eickemeyer US 2015/0032997.
Regarding claim 7, Levitan in view of Natarajan and Reinhardt teaches:
7. The method of claim 1,
Levitan in view of Natarajan and Reinhardt does not teach:
wherein the global branch history and the copy of the global branch history are each implemented as a circular buffer.
However, Eickemeyer teaches:
global branch history implemented as a circular buffer ([0021] and [0044]: the global history vector is implemented as a circular buffer)
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 global branch history in Levitan to be implemented as a circular buffer as taught by Eickemeyer. One of ordinary skill in the art would have been motivated to make this modification to enable more efficient updates of the global history.
The combination of Levitan in view of Reinhardt and Eickemeyer does not teach the copy of the global branch history implemented as a circular buffer.
However, Col teaches restoring a GHB from a stored GHB in response to a misprediction, see col 7 lines 9-20.
It would have been obvious to one of ordinary skill in the art, before the effective filing date of the claimed invention, to modify Levitan in view of Reinhardt to use the stored GHV to restore the GHV. In this combination, the stored copy of the GHV will be restored to the GHV in response to a misprediction and the copy of the GHV will be implemented as a circular buffer (as taught by Eickemeyer) when it is restored to the GHV. One of ordinary skill in the art would have been motivated to make this modification to efficiently recover from mispredictions since restoring the GHV from the stored GHV would enable updating the GHV after recovering from a misprediction while also enabling recovering from further mispredictions using the stored GHV (as opposed to implementations which do not restore the GHV from the stored GHV).
Regarding claim 14, Levitan in view of Natarajan and Reinhardt teaches:
14. The TAGE branch predictor of claim 8,
Levitan in view of Natarajan and Reinhardt does not teach:
wherein the global branch history and the copy of the global branch history are each implemented as a circular buffer.
However, Eickemeyer teaches:
global branch history implemented as a circular buffer ([0021] and [0044]: the global history vector is implemented as a circular buffer)
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 global branch history in Levitan to be implemented as a circular buffer as taught by Eickemeyer. One of ordinary skill in the art would have been motivated to make this modification to enable more efficient updates of the global history.
The combination of Levitan in view of Reinhardt and Eickemeyer does not teach the copy of the global branch history implemented as a circular buffer.
However, Col teaches restoring a GHB from a stored GHB in response to a misprediction, see col 7 lines 9-20.
It would have been obvious to one of ordinary skill in the art, before the effective filing date of the claimed invention, to modify Levitan in view of Reinhardt to use the stored GHV to restore the GHV. In this combination, the stored copy of the GHV will be restored to the GHV in response to a misprediction and the copy of the GHV will be implemented as a circular buffer (as taught by Eickemeyer) when it is restored to the GHV. One of ordinary skill in the art would have been motivated to make this modification to efficiently recover from mispredictions since restoring the GHV from the stored GHV would enable updating the GHV after recovering from a misprediction while also enabling recovering from further mispredictions using the stored GHV (as opposed to implementations which do not restore the GHV from the stored GHV).
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 th