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 .
Priority
Acknowledgment is made of applicant’s claim for foreign priority under 35 U.S.C. 119 (a)-(d). The certified copy of JP 2024-095190 was received on July 7, 2025
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, determining if updating is to be performed on the updating TAGE table must be shown or the feature(s) canceled from the claim(s). No new matter should be entered.
The drawings are objected to because of the following informalities:
Fig 2, “RSA”, “RSE”, and all other words/numbers similarly rotated should be rotated to be aligned with words such as “instruction buffer”, “register renaming”, etc. See MPEP 37 CFR 1.84(i). Similarly, the sheet numbers must be at the top(one of the shorter sides of the sheet) and larger than the numbers used as reference characters. See MPEP 37 CFR 1.84(f) and 1.84(t).
Fig 3 has the same sheet numbering issues as Fig 2
Fig 4, S4-S6: the “Yes” and “No” cases are the reverse of what is described in the specification. The examiner recommends changing S4 from “Don’t reading” to “Do reading” for clarity, and swapping the positions of “Yes” and “No” on the figure, as well as the descriptions for the steps in paragraphs [073] and [074]
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.
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.
The disclosure is objected to because of the following informalities:
Abstract: Line 14, “the predetermined branch instruction” has an antecedent basis issue as multiple predetermined branch instructions were mentioned (lines 4-5 and line 13)
Par. [003]: “tagged geometric history length branch prediction (TAGE) branch prediction” should be corrected to “tagged geometric history length (TAGE) branch prediction”
Par. [073] and [074]: “(Step S4: Positive)” and “(Step S4: Negative)” are reversed, in the same manner as the drawing objection to Figure 4
Appropriate correction is required.
The lengthy specification has not been checked to the extent necessary to determine the presence of all possible minor errors. Applicant’s cooperation is requested in correcting any errors of which applicant may become aware in the specification.
Additional Remarks:
Par. [008]:
is “once read” meant to mean “read once” or something else here?
is “a reading port for prediction and a reading port for updating” correct here, or should it be “a writing port for updating”?
Par. [052] and [053]: TAGE prediction uses multiple tables with differing history lengths indexing each. However, the updating and prediction table RAM only ever mention one table. Is each storage holding one singular table, or multiple in the manner of TAGE?
Par. [053]: is “The updating TAGE table is a table that is used to determine whether the updating TAGE table will be updated” correct here? Should the second “updating” be “prediction”?
Claim Objections
Claims 1,2, and 4-6 are objected to because of the following informalities:
Claim 1
line 16: “information of the first table” should be corrected to “information registered in the first table” for consistency
Claim 2
Line 2, “performs” should have a colon inserted after
Lines 3-4, “notification of the predetermined branch instruction” should be updated to either “notification” or “notification of the completion information relating to the predetermined branch instruction” for consistency
Claim 4
Line 1,”wherein” should have a colon inserted after
Claim 5
Line 3 should be appended to the end of line 2 (“wherein the processor includes”)
Same issue as claim 1, : “information of the first table” should be corrected to “information registered in the first table” for consistency
Appropriate correction is required.
Claim Interpretation
The following is a quotation of 35 U.S.C. 112(f):
(f) Element in Claim for a Combination. – An element in a claim for a combination may be expressed as a means or step for performing a specified function without the recital of structure, material, or acts in support thereof, and such claim shall be construed to cover the corresponding structure, material, or acts described in the specification and equivalents thereof.
The following is a quotation of pre-AIA 35 U.S.C. 112, sixth paragraph:
An element in a claim for a combination may be expressed as a means or step for performing a specified function without the recital of structure, material, or acts in support thereof, and such claim shall be construed to cover the corresponding structure, material, or acts described in the specification and equivalents thereof.
The claims in this application are given their broadest reasonable interpretation using the plain meaning of the claim language in light of the specification as it would be understood by one of ordinary skill in the art. The broadest reasonable interpretation of a claim element (also commonly referred to as a claim limitation) is limited by the description in the specification when 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, is invoked.
As explained in MPEP § 2181, subsection I, claim limitations that meet the following three-prong test will be interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph:
(A) the claim limitation uses the term “means” or “step” or a term used as a substitute for “means” that is a generic placeholder (also called a nonce term or a non-structural term having no specific structural meaning) for performing the claimed function;
(B) the term “means” or “step” or the generic placeholder is modified by functional language, typically, but not always linked by the transition word “for” (e.g., “means for”) or another linking word or phrase, such as “configured to” or “so that”; and
(C) the term “means” or “step” or the generic placeholder is not modified by sufficient structure, material, or acts for performing the claimed function.
Use of the word “means” (or “step”) in a claim with functional language creates a rebuttable presumption that the claim limitation is to be treated in accordance with 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph. The presumption that the claim limitation is interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, is rebutted when the claim limitation recites sufficient structure, material, or acts to entirely perform the recited function.
Absence of the word “means” (or “step”) in a claim creates a rebuttable presumption that the claim limitation is not to be treated in accordance with 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph. The presumption that the claim limitation is not interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, is rebutted when the claim limitation recites function without reciting sufficient structure, material or acts to entirely perform the recited function.
Claim limitations in this application that use the word “means” (or “step”) are being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, except as otherwise indicated in an Office action. Conversely, claim limitations in this application that do not use the word “means” (or “step”) are not being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, except as otherwise indicated in an Office action.
This application includes one or more claim limitations that do not use the word “means,” but are nonetheless being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, because the claim limitation(s) uses a generic placeholder that is coupled with functional language without reciting sufficient structure to perform the recited function and the generic placeholder is not preceded by a structural modifier. Such claim limitation(s) is/are:
“a branch instruction processing unit that determines...” in claims 1, 5, and 6
“a controller that performs…” in claim 2
Because this/these claim limitation(s) is/are being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, it/they is/are being interpreted to cover the corresponding structure described in the specification as performing the claimed function, and equivalents thereof.
The examiner is interpreting “a branch instruction processing unit that determines”
If applicant does not intend to have this/these limitation(s) interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, applicant may: (1) amend the claim limitation(s) to avoid it/them being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph (e.g., by reciting sufficient structure to perform the claimed function); or (2) present a sufficient showing that the claim limitation(s) recite(s) sufficient structure to perform the claimed function so as to avoid it/them being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph. For the purposes of examination, and due to the lack of support from the specification as will be described in the Claim Rejections section, the examiner is interpreting the limitations as follows:
“a branch instruction processing unit that determines...” in claims 1, 5, and 6 is being interpreted with the BRI of branch prediction circuitry capable of performing the functions listed
“a controller that performs…” in claim 2 is being interpreted with the BRI of control circuitry capable of performing the claimed functions
At least one claim is identified as including a non-limiting contingent limitation. “The broadest reasonable interpretation of a method (or process) claim having contingent limitations requires only those steps that must be performed and does not include steps that are not required to be performed because the condition(s) precedent are not met.” “The broadest reasonable interpretation of a system (or apparatus or product) claim having structure that performs a function, which only needs to occur if a condition precedent is met, requires structure for performing the function should the condition occur. The system claim interpretation differs from a method claim interpretation because the claimed structure must be present in the system regardless of whether the condition is met and the function is actually performed.” See MPEP 2111.04(II).
The method claim, claim 6, contains the contingent limitations of “in a case where writing for updating is not being performed on a second table…” and “in a case where it has been determined that updating will be performed…”. Since there is a case where writing is being performed and thus the first limitation is not met, and/or where updating is determined not to be performed and thus the second limitation is not met, the prior art is not required to teach these contingent limitations in order to read on the method.
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 1 and 2 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. The disclosure does not provide adequate structure to implement the functionality of the branch instruction processing unit or the controller, as will be described below and in the next section
Regarding the branch instruction processing unit, the specification discloses a reservation station coupled with a queue as the structure, which is adequate for holding instructions. However, a reservation station and a queue is not an adequate structure for functionality of detecting branch mispredictions, determining taken branches, or completing the predetermined branch instruction
Regarding the controller, the specification discloses a “control unit”. This does not amount to any specific structure
The specification does not demonstrate that applicant has made an invention that achieves the claimed function because the invention is not described with sufficient detail such that one of ordinary skill in the art can reasonably conclude that the inventor had possession of the claimed invention.
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-6 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.
Regarding claim 1, claim limitation “branch instruction processing unit that determines…detects… and completes ” invokes 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph. However, the written description fails to disclose the corresponding structure, material, or acts for performing the entire claimed function and to clearly link the structure, material, or acts to the function. The claim discloses a branch instruction processing unit that performs the functions of:
Determining whether a branch has been taken in response to a predetermined branch instruction in execution of the instruction in the pipeline
Detecting a branch misprediction
Completing a predetermined branch instruction
Several steps to perform the functions are mentioned in paragraphs [046]-[049], as well as a Reservation Station(RSBR 140) including a queue(Par. [027], “respective reservation stations, such as the RSA 110, the RSE 120, the RSF 130, and the RSBR 140, are mechanisms that hold an instruction until the instruction becomes executable. Each of the RSA 110, the RSE 120, the RSF 130, and the RSBR 140 has a queue”) as the structure to complete the claimed functions; However, a reservation station as a mechanism that holds an instruction and including a queue is not adequate to perform the claimed functions, such as detecting a branch misprediction, determining if a branch has been taken, etc. Therefore, the claim is indefinite and is rejected under 35 U.S.C. 112(b) or pre-AIA 35 U.S.C. 112, second paragraph. For purposes of examination, the examiner is interpreting these limitations with the BRI of a branch prediction circuitry capable of performing said functions.
Applicant may:
(a) Amend the claim so that the claim limitation will no longer be interpreted as a limitation under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph;
(b) Amend the written description of the specification such that it expressly recites what structure, material, or acts perform the entire claimed function, without introducing any new matter (35 U.S.C. 132(a)); or
(c) Amend the written description of the specification such that it clearly links the structure, material, or acts disclosed therein to the function recited in the claim, without introducing any new matter (35 U.S.C. 132(a)).
If applicant is of the opinion that the written description of the specification already implicitly or inherently discloses the corresponding structure, material, or acts and clearly links them to the function so that one of ordinary skill in the art would recognize what structure, material, or acts perform the claimed function, applicant should clarify the record by either:
(a) Amending the written description of the specification such that it expressly recites the corresponding structure, material, or acts for performing the claimed function and clearly links or associates the structure, material, or acts to the claimed function, without introducing any new matter (35 U.S.C. 132(a)); or
(b) Stating on the record what the corresponding structure, material, or acts, which are implicitly or inherently set forth in the written description of the specification, perform the claimed function. For more information, see 37 CFR 1.75(d) and MPEP §§ 608.01(o) and 2181.
Claim 1 also recites the limitation "the instruction" in lines 6-7. There is insufficient antecedent basis for this limitation in the claim. Claim 1 recites “an instruction” on line 2 and “a predetermined branch instruction” on lines 5-6. It is unclear which is being referred to here, and as such, the claim is indefinite. Similarly, claim 1 also recites the limitation “the branch instruction”. The claim recites both “a predetermined branch instruction” on lines 5-6 and “a branch instruction” on line 11, so it’s unclear which is being referred to here as well. As such, there is insufficient antecedent basis for this limitation in the claim.
Claims 5 and 6 are method and apparatus claims similar to claim 1 and recite the same language as mentioned in the rejections above, and as such are rejected as they have the same issues as claim 1. Claims 2-4 are rejected for dependency on claim 1.
Regarding claim 2, claim limitation “a controller that performs” invokes 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph. However, the written description fails to disclose the corresponding structure, material, or acts for performing the entire claimed function and to clearly link the structure, material, or acts to the function. The claim discloses a controller that performs the functions of:
receiving the notification of the predetermined branch instruction from the branch instruction processing unit
storing the completion information relating to the predetermined branch instruction in a temporary storage,
reading the completion information relating to the predetermined branch instruction from the temporary storage
determining whether the writing for the updating is being performed on the second table
notifying the updating determination circuit of the completion information relating to the predetermined branch instruction, in a case where the writing for the updating is not being performed on the second table.
However, there is no mention of the specific structure beyond a generic control unit. Therefore, the claim is indefinite and is rejected under 35 U.S.C. 112(b) or pre-AIA 35 U.S.C. 112, second paragraph. For purposes of examination, the examiner is interpreting these limitations with the broadest reasonable interpretation of control circuitry capable of performing the claimed functions.
Applicant may:
(a) Amend the claim so that the claim limitation will no longer be interpreted as a limitation under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph;
(b) Amend the written description of the specification such that it expressly recites what structure, material, or acts perform the entire claimed function, without introducing any new matter (35 U.S.C. 132(a)); or
(c) Amend the written description of the specification such that it clearly links the structure, material, or acts disclosed therein to the function recited in the claim, without introducing any new matter (35 U.S.C. 132(a)).
If applicant is of the opinion that the written description of the specification already implicitly or inherently discloses the corresponding structure, material, or acts and clearly links them to the function so that one of ordinary skill in the art would recognize what structure, material, or acts perform the claimed function, applicant should clarify the record by either:
(a) Amending the written description of the specification such that it expressly recites the corresponding structure, material, or acts for performing the claimed function and clearly links or associates the structure, material, or acts to the claimed function, without introducing any new matter (35 U.S.C. 132(a)); or
(b) Stating on the record what the corresponding structure, material, or acts, which are implicitly or inherently set forth in the written description of the specification, perform the claimed function. For more information, see 37 CFR 1.75(d) and MPEP §§ 608.01(o) and 2181.
The term “similar to” in claims 1, 5 and 6 is a relative term which renders the claim indefinite. The term “similar to” is not defined by the claim, the specification does not provide a standard for ascertaining the requisite degree, and one of ordinary skill in the art would not be reasonably apprised of the scope of the invention. There is no explanation of what constitutes the second table being “similar to” the first, and as such the scope of this claim limitation is indefinite. Claims 2-4 are dependent on claim 1 and are rejected for inheriting the same deficiencies.
The term “near” in claim 4 is a relative term which renders the claim indefinite. The term “near” is not defined by the claim, the specification does not provide a standard for ascertaining the requisite degree, and one of ordinary skill in the art would not be reasonably apprised of the scope of the invention. Similar to claim 1, there is no definition of what constitutes a storage being “near” a fetch or branch instruction processing unit, and as such the scope of this claim limitation is indefinite.
Claim 6 is 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 6 recites a method for controlling a processor. However, claim 6 does not describe any steps for controlling said processor, instead only describing the structure and functionality of the processor. Therefore, the scope of the claim is unclear, and the claim is indefinite.
Claim 6 also recites the limitation "the information of the second table" in line 25. There is insufficient antecedent basis for this limitation in the claim. The claim recites both “acquiring information relating to the predetermined branch instruction from the second table ” on lines 15-16 and “information relating to a branch instruction being registered in the second table” on lines 19-20, and it is unclear which is being referred to as both are “information of the second table”
Claim Rejections - 35 USC § 103
Claim(s) 6 is/are rejected under 35 U.S.C. 103 as being unpatentable over US 10678551 B2 Levitan et al in view of US 20240095034 A1 Dundas et al, referred to as Levitan and Dundas, respectively.
Regarding claim 6, under an interpretation in which the contingent limitations of the method claim are not required to be taught by prior art(as described in the Claim Interpretation section above), Levitan teaches a method(Figs. 4 and 5) for controlling a processor comprising:
a branch instruction processing unit that determines whether a branch has been taken in response to a predetermined branch instruction in execution of the instruction in the pipeline, detects a branch misprediction, and completes the predetermined branch instruction; (Col. 7, line 33 “Branch execution unit may receive information from both the effective address table and one or more of the executions slices and provide the instruction fetch unit with information regarding branches taken by instructions that have been executed, where the instruction fetch unit may use the information received from the branch execution unit, in conjunction with information from the TAGE, to determine instructions to fetch next.” Col. 7, line 61“The instruction from the instruction fetch unit may also be provided to an execution slice, where the execution slice may—in executing one or more previous instructions—determine that a branch is to be taken or not. Further, information regarding taken or not taken branches may be provided from the execution slices back to the branch execution unit.” Col. 5, line 47 “Flush and recovery operations may be carried out for many reasons, including missed branch predictions…” : the instruction fetch and branch execution units pass information relating to whether or not to take a branch as well whether or not a branch has been taken between each other, and fetch the next instruction to be completed in response. This allows detecting a misprediction and completing a predetermined instruction. Further, the flush and recovery operation is performed in response to mispredictions, which requires the detection of said mispredictions.) and
a first storage(Fig. 3, “Effective Address Table 312”; tables are stored in storage) and
a second storage(Fig. 3, “TAGE Update Table 310”)
However, Levitan does not teach a pipeline in which an instruction is fetched and executed
Dundas teaches a pipeline in which and instruction is fetched and executed(Par. [028] “In this example, the pipeline stages include a fetch stage 6 for fetching instructions from an instruction cache 8; a decode stage 10 for decoding the fetched program instructions to generate micro-operations to be processed by remaining stages of the pipeline;… an execute stage 16 for executing data processing operations corresponding to the micro-operations”)
It would have been obvious to one of ordinary skill in the art, prior to the effective filing date of the claimed invention, to combine the teachings of Levitan and Dundas, in the same manner as follows in claim 1, to provide a method for controlling the processor of Levitan including the pipeline of Dundas, for the purpose of increasing the throughput of the processor.
Claim(s) 1 and 4-6 is/are rejected under 35 U.S.C. 103 as being unpatentable over US 10678551 B2 Levitan et al in view of US 20240095034 A1 Dundas et Al and US 20100031011 A1 Chen et al, referred to as Levitan, Dundas, and Chen, respectively.
Regarding claim 1, Levitan teaches a processor comprising:
a branch instruction processing unit that determines whether a branch has been taken in response to a predetermined branch instruction in execution of the instruction, detects a branch misprediction, and completes the predetermined branch instruction; (Col. 7, line 33 “Branch execution unit may receive information from both the effective address table and one or more of the executions slices and provide the instruction fetch unit with information regarding branches taken by instructions that have been executed, where the instruction fetch unit may use the information received from the branch execution unit, in conjunction with information from the TAGE, to determine instructions to fetch next.” Col. 7, line 61“The instruction from the instruction fetch unit may also be provided to an execution slice, where the execution slice may—in executing one or more previous instructions—determine that a branch is to be taken or not. Further, information regarding taken or not taken branches may be provided from the execution slices back to the branch execution unit.” Col. 5, line 47 “Flush and recovery operations may be carried out for many reasons, including missed branch predictions…” : the instruction fetch and branch execution units pass information relating to whether or not to take a branch as well whether or not a branch has been taken between each other, and fetch the next instruction to be completed in response. This allows detecting a misprediction and completing a predetermined instruction. Further, the flush and recovery operation is performed in response to mispredictions, which requires the detection of said mispredictions.)
a first storage that stores a first table, information relating to a branch instruction being registered in the first table, the first table being used in branch prediction for fetch;(Col. 7, line 12 “Effective address table (312) may include entries (312a-312m) that store effective addresses for currently active instructions.”; Col. 7, line 33 “ Branch execution (308) unit may receive information from both the effective address table (312) and one or more of the executions slices (204a, 204b-204n) and provide the instruction fetch (302) unit with information regarding branches taken by instructions that have been executed” Col 8, lines 42-45 “Updating (406) the TAGE (306) may be carried out by the TAGE (306)—in dependence upon the effective address table (312) providing effective address information for the branch instruction…”; This describes a table storing information related to branch prediction and being used in fetch; tables are stored in storage. The effective address table stores the addresses of branches and is primarily used for instruction fetch, with some use also for updating the predictor alongside the updating table)
a second storage that stores a second table, information relating to the branch instruction that is similar to the information of the first table being registered in the second table; (Col. 7, lines 19-22: “TAGE update table may include entries such that each entry is aligned, or mapped to, a corresponding effective address entry within the effective address table”; Col 8, lines 55-61“ the TAGE update table (310) may provide, for a particular entry, one or more of: a valid bit, a branch effective address, an indication as to whether a TAGE entry was hit, a TAGE component, a TAGE prediction, a TAGE usefulness indication, an alternative component, an alternative predication, a next component, and a next usefulness indication.”; This describes a TAGE updating table used for updating and holding information that is similar to the effective address table, e.g. “branch effective address” )
and;
an updating determination circuit that, in a case where writing for updating is not being performed on the second table, receives, from the branch instruction processing unit, notification of completion information relating to the predetermined branch instruction, acquires information relating to the predetermined branch instruction from the second table,… and updates the first table and the second table (Col. 8, line 1 ” responsive to the branch instruction being taken, updating the effective address table and the TAGE update table to indicate the branch instruction being taken.” Fig. 4 steps 402 -406; this describes receiving notification of a branch being taken(i.e. completion information) and updating an update table and address table in response. Additionally, figure 4 shows acquiring information related to a branch instruction from the first and second table, for the purpose of updating the predictor. Further, the update determination circuit itself makes no determination of if updating is currently being performed, as the controller makes that determination in Par. [058] of the instant application and only gives notification in the case that it is not. As such, any circuit that receives the notification, acquires information, determines updating and updates will necessarily do so in the case where writing updating is not being performed.)
However, Levitan does not teach a pipeline in which an instruction is fetched and executed, or determin(ing) whether the updating will be performed.
Dundas teaches a pipeline in which and instruction is fetched and executed(Par. [028] “In this example, the pipeline stages include a fetch stage 6 for fetching instructions from an instruction cache 8; a decode stage 10 for decoding the fetched program instructions to generate micro-operations to be processed by remaining stages of the pipeline;… an execute stage 16 for executing data processing operations corresponding to the micro-operations”)
It would have been obvious to one of ordinary skill in the art, prior to the effective filing date of the claimed invention, to combine the teachings of Levitan and Dundas in order to have the components of Levitan form a pipeline in the manner of Dundas, for the purpose of increasing the throughput of the processor.
The combination thus far still does not teach determin(ing) whether the updating will be performed
Chen teaches determin(ing) whether the updating will be performed(Par. [032] ,“The branch instruction is executed at step 318 at which time the branch outcome is known, which is used to determine if the original branch prediction was correct or not and the update logic 222 determines if an update is required.”; Par. [033], “If the branch prediction was correct, the process proceeds to step 322, where update logic 222 may perform X consecutive write attempts to branch prediction array 210. If the branch prediction was mispredicted, the process proceeds to step 324, where update logic 222 may perform Y consecutive write attempts to branch prediction array 210. In an embodiment of the invention, branch prediction array 210 is a branch history table as stated above.”; this teaches first determining if an update is necessary before updating a branch history table)
It would have been obvious to one of ordinary skill in the art, prior to the effective filing date of the claimed invention, to combine the processor thus far with the updating logic of Chen, in order to determine if the updating is necessary for the effective address and TAGE updating tables before updating them, thus ensuring the accuracy of the tables and, by extension, the prediction.
Regarding claim 4, the combination thus far teaches the processor according to claim 1.
Levitan further teaches wherein the first storage is disposed near an instruction fetch mechanism included in the pipeline, and the second storage is disposed near the branch instruction processing unit. (Figure 3: “Effective Address Table 312” is coupled to “Instruction Fetch 302” and “TAGE Update table 310” is coupled to “Tagged Geometric History Length Branch Prediction Unit 306”)
Regarding claim 5, the combination thus far teaches a processor… wherein the processor includes:
a pipeline in which an instruction is fetched and executed;
a branch instruction processing unit that determines whether a branch has been taken in response to a predetermined branch instruction in execution of the instruction in the pipeline, detects a branch misprediction, and completes the predetermined branch instruction;
a first storage that stores a first table, information relating to a branch instruction being registered in the first table, the first table being used in branch prediction for fetch;
a second storage that stores a second table, information relating to the branch instruction that is similar to the information of the first table being registered in the second table; and
an updating determination circuit that, in a case where writing for updating is not being performed on the second table, receives, from the branch instruction processing unit, notification of completion information relating to the predetermined branch instruction, acquires information relating to the predetermined branch instruction from the second table, determines whether the updating will be performed, and updates the first table and the second table in a case where it has been determined that the updating will be performed, as shown above.
Levitan further teaches an information processing apparatus comprising a processor and a memory(Fig. 1, “Computer 152”, “Multi-slice Processor 156”, and “RAM 168”)
Claim 6 is a method claim corresponding to claim 1, and is rejected on the same grounds
Claim(s) 2 is/are rejected under 35 U.S.C. 103 as being unpatentable over Levitan in view of Dundas and Chen as applied to claim 1 above, and further in view of CN 113535237 A Macdonald, referred to hereout as Macdonald.
Regarding claim 2, the combination thus far teaches the processor according to claim 1
However, the combination does not teach further including a controller that performs
receiving the notification of the predetermined branch instruction from the branch instruction processing unit, and storing the completion information relating to the predetermined branch instruction in a temporary storage, reading the completion information relating to the predetermined branch instruction from the temporary storage,
determining whether the writing for the updating is being performed on the second table and
notifying the updating determination circuit of the completion information relating to the predetermined branch instruction, in a case where the writing for the updating is not being performed on the second table
Macdonald teaches a controller that performs receiving the notification of the predetermined branch instruction from the branch instruction processing unit(Page 11, Par. 4 “The dual branch updating system 76 includes a write logic 78A; 78B, the write logic from branch unit IU1
26A and IU2 26B receiving branch execution output (e.g., error prediction signal and branch tag) (e.g., the address of the branch in BOT, which allows access to other branch information…))”: this teaches a write control that receives information related to branch prediction), and
storing the completion information relating to the predetermined branch instruction in a temporary storage(Page 2, Par. 4 “writing two updates to a respective first write queue and a second write queue at each clock cycle based on the information”),
reading the completion information relating to the predetermined branch instruction from the temporary storage(Page 12, Par. 2 “ In one embodiment, the update to BTAC table 84 involves reading two (2) updates from queue 80 and/or 82”)
determining whether the writing for the updating is being performed on the second table, and
notifying the updating determination circuit of the completion information relating to the predetermined branch instruction, in a case where the writing for the updating is not being performed on the second table(Page 3, Par. 8 “In one embodiment, the write queue only issues a single update under the condition of expected conflict… In the case where no collision is expected, the write queues each allow a plurality of updates for a given clock cycle”; This teaches updating with multiple values and when a conflict is not expected(i.e. writing is not being performed), only allowing the writing after it has passed. This necessitates determining whether writing is being performed.)
It would have been obvious to one of ordinary skill in the art, prior to the effective filing date of the claimed invention, to further modify the combination thus far by including the controller of Macdonald, in order to control the writing to the updating table and update the table only in a case where writing for updating is not already being performed, thus preventing memory conflicts and the latency associated with such conflicts.
Claim(s) 3 is/are rejected under 35 U.S.C. 103 as being unpatentable over Levitan in view of Dundas, Chen, and Macdonald, and further in view of US 5507028 A Lishing, referred to as Lishing hereout.
Regarding claim 3, the combination thus far teaches the processor according to claim 2
The combination does not teach wherein, in a case where it has been determined that the updating will be performed, the updating determination circuit inhibits the controller from reading the information from the temporary storage
Lishing teaches, the updating determination circuit inhibits the controller from reading the information from a history table(Col 8, lines 8-13 “ In an implementation that allows only one access (Read or Write) per cycle to the history table 43, priority needs to be provided between concurrent accesses. For example, update to the history table 43 due to signal 56 from correction logic 41 may delay the read access for a new prediction.”: this teaches giving priority to writing to the table by inhibiting the reading temporarily while writing is being performed. In our combination thus far, where reading the information from the table is preceded by the controller reading information from the controller queue, this would include blocking reading from the queue. )
It would have been obvious to one of ordinary skill in the art, prior to the effective filing date of the claimed invention, to further apply the teachings of Lishing to the combination thus far, by inhibiting the reading from the queue, to give priority to the former in the same manner as Lishing, in order to ensure updating determinations are made with the most recent information, thereby improving the prediction accuracy.
Conclusion
The prior art made of record and not relied upon is considered relevant to the applicant’s disclosure.
Relevant art:
CN 111459549 A Gong et al: A branch predictor including multiple memories that can be used in branch prediction
CN 122111501 A BOUZGUARROU et al: A branch predictor with a table updating circuit similar to the instant application
André Seznec, Pierre Michaud. A case for (partially) tagged geometric history length branch prediction. The Journal of Instruction-Level Parallelism, 2006, 8, pp.23. ⟨hal-03408381⟩: the original published paper for TAGE branch prediction
Any inquiry concerning this communication or earlier communications from the examiner should be directed to JUSTIN T KYZAR whose telephone number is (571)270-1463. The examiner can normally be reached 7:30a.m. - 5:00p.m. M-F ET.
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, Joyti Mehta can be reached at 5712703995. 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.
/J.T.K./Examiner, Art Unit 2183
/David J. Huisman/Primary Examiner, Art Unit 2183
Prosecution Insights