DETAILED ACTION
Claims 1-20 have been examined.
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 .
Specification
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.
The substitute disclosure submitted on April 30, 2026, is objected to because of the following informalities:
Where the examples starting on page 33, line 15, include similar issues as the claims as pointed out in the previous action, please make appropriate corrections. For instance:
Example 23 on p.37 should be amended similarly to claim 2.
Example 25 on p.38 should be amended similarly to claim 4.
Example 31 on pp.38-39 should be amended similarly to claim 10.
In example 37, last line, insert --that-- before “exceeds”
Claim Recommendations
In claim 2, lines 2 and 5, and in claim 3, the examiner recommends that applicant claim the prediction as a/the first prediction, so as to more clearly distinguish from any prediction in the last paragraph of claim 1.
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-6, 10-12, 15-16, and 19 are rejected under 35 U.S.C. 103 as being unpatentable over Yeh et al. (“Increasing the Instruction Fetch Rate via Multiple Branch Prediction and a Branch Address Cache”).
Referring to claim 1, Yeh has taught an apparatus comprising:
prediction storage circuitry (FIG.3 and, optionally, section 3.2, Branch Address Cache (BAC)) configured to store a plurality of prediction entries (from FIG.3 and the description thereof, the pattern history table (PHT) stores predictions. The three accessed locations in the example of FIG.3 make up a single prediction entry), each prediction entry indicative of whether a respective branch instruction is predicted to be taken or not taken (from FIG.3 and its description, the accessed entry includes a 2-bit counter that indicates a T/NT prediction for the primary branch (e.g. see FIG.2, which shows a primary branch in the top level of the tree)), wherein at least one prediction entry supports an encoding of a multi-taken entry indicating that the respective branch instruction and at least one subsequent branch instruction are each predicted to be taken (from FIGs.2-3, not only is the primary branch predicted, but a secondary branch is also predicted by the entry. The entry will basically store TT, TN, NT, or NN predictions (e.g. where TT stands for a predicted-taken primary branch and a predicted-taken secondary branch, which would correspond to the left branch of the tree of FIG.2)), wherein the at least one subsequent branch instruction is on an execution path following a taken outcome of the respective branch instruction (from FIG.2, when the predicted branch is taken, the left secondary (subsequent) branch is encountered because it is on the taken path); and
prediction resumption circuitry configured to identify a prediction resumption address in response to a flush signal, the prediction resumption address being an address in respect of which at least one prediction is to be generated after the flush signal (from section 3.1, incorrection predictions, i.e., mispredictions, are possible. As is known with branch prediction, this causes a flush of any mispredicted path and prediction will resume down the correct path. As an example, assume the primary branch of FIG.2 is encountered, and that an associated lookup in the predictor (FIG.3) results in a TT prediction, meaning the primary branch is predicted taken and the secondary branch along the taken path is predicted taken. In other words, the system predicts to follow the leftmost path in the tree. If, however, the primary branch prediction is wrong, both the primary and secondary paths must be flushed because the system should have instead proceeded down the right half of the tree. Processing will be resumed at an address on the correct path, i.e., a prediction resumption address. Then the system will perform predictions based on that address).
Yeh has not explicitly taught that the prediction resumption address is identified based on stored information dependent on the multi-taken entry. That is, even though the system will need to obtain the prediction resumption address, as is known with branch misprediction recovery, Yeh does not explain where to obtain the correct address from. However, Yeh teaches that a BAC entry associated with a primary branch already stores both taken and not-taken addresses for that branch and that the BAC directs the flow to those addresses (section 3.2). For the primary branch, when the predictor predicts TT, the addresses in Taddr and TTaddr fields are used to fetch the next two blocks. However, if that primary branch was mispredicted, Naddr should have been used instead of Taddr. Since Naddr (prediction resumption address) is already available in this entry, one of ordinary skill in the art would have been motivated to simply obtain it from the entry and use it to recover from the misprediction. One reason to do so is to make use of information already present and not have to separately calculate and/or store this resumption address elsewhere, redundantly. As a result, it would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to modify Yeh such that the prediction resumption address is identified based on stored information dependent on the multi-taken entry.
Referring to claim 2, Yeh, as modified, has taught the apparatus of claim 1, comprising prediction circuitry configured to perform a lookup in the prediction storage circuitry to generate a prediction in respect of a given branch instruction (see, for instance, the last paragraph in the left column on p.71. Generally, when a miss occurs in the prediction storage, there is no prediction for a primary branch (respective branch instruction). Thus, one must be generated. As described, generating a prediction for a primary branch also involves generating a prediction for a secondary branch (given branch)); and
the prediction circuitry is configured to generate and store the stored information in a prediction resumption cache in response to generating the prediction in respect of the given branch instruction (generating the prediction for a primary branch includes generating and storing the prediction for the secondary (given) branch in the fields of the resumption cache (BAC) (NNaddr, NTaddr, TNaddr, etc.) (left column on p.71)).
Referring to claim 3, Yeh, as modified, has taught the apparatus of claim 2, wherein the flush signal is indicative of the prediction being incorrect (again, when a prediction is incorrect, a flush must occur to rid the system of the incorrect instructions).
Referring to claim 4, Yeh, as modified, has taught the apparatus of claim 2, wherein the given branch instruction is different from the respective branch instruction associated with the multi-taken entry (the primary (respective) and secondary (given) branches are different).
Referring to claim 5, Yeh, as modified, has taught the apparatus of claim 2, wherein the prediction circuitry is configured to generate the prediction and the stored information in a single lookup in the prediction storage circuitry (obtaining the predictions (FIG.3) and predicted addresses corresponding to those predictions (from the BAC) is considered a single lookup).
Referring to claim 6, Yeh, as modified, has taught the apparatus of claim 1, comprising:
history tracking circuitry configured to maintain a program flow history based on predicted branch instructions satisfying a program flow history update condition (see FIG.3, global history register (GHR), which tracks the outcomes of previously-encountered branches (each branch updates a bit of the history));
wherein the prediction storage circuitry comprises at least one set-associative storage structure, in which the at least one set-associative storage structure comprises sets indexed by a portion of the program flow history that is independent of information relating to a most recently predicted branch instruction satisfying the program flow history update condition (see FIG.3 and the MGAs scheme (p.70, left column). There are multiple PHTs (set-associative storage structure) that are addressed by bits in the GHR, at least some of which make up a portion not including the rightmost bit, which relates to the most-recently predicted branch (p.70, last paragraph). That is, as shown in FIG.3, all k bits of the GHR are used to access multiple PHT sets (for MGAs). These k bits includes the leftmost (k-1)-bit portion that is independent of the rightmost GHR bit).
Referring to claim 10, Yeh, as modified, has taught the apparatus of claim 6, wherein:
the at least one storage structure comprises a plurality of set-associative storage structures (again, there are multiple PHTs);
the plurality of set-associative storage structures comprise at least a long-history storage structure associated with a long history length (each PHT is accessed as shown in FIG.3. An entry accessed by all k bits is a long history storage structure) and a short-history storage structure associated with a short history length (an entry accessed by k-1 bits is a short history storage structure); and
in response to a given program flow history, the branch prediction circuitry is configured to identify one or more prediction entries associated with the given program flow history in the long-history storage structure or the short-history storage structure (the history in GHR identifies a prediction amongst the long/short structures).
Referring to claim 11, Yeh, as modified, has taught the apparatus of claim 1, comprising:
flow tracking circuitry configured to maintain program flow information indicative of one or more observed paths after a candidate branch instruction (a branch predictor tracks whether a taken or not-taken path is more likely in the future for a given branch); and
wherein in a case where a prediction is to be generated in respect of the candidate branch instruction, the flow tracking circuitry is configured to cause the stored information to be stored in response to the multi-taken entry indicating a program flow corresponding to one of the one or more observed paths (when the flow-tracking circuitry is to generate the taken path, the stored information is stored in the predictor).
Referring to claim 12, Yeh, as modified, has taught the apparatus of claim 11, wherein the one or more observed paths comprise information identifying at least one subsequent branch instruction encountered after the candidate branch instruction (again, see FIG.2, where sequences of branches are discovered and predicted).
Referring to claim 15, Yeh, as modified, has taught the apparatus of claim 1, wherein the prediction storage circuitry is configured to store a multi-taken entry specifying an unconditional branch instruction as one of the at least one subsequent branch instruction (again, in the left column on p.71, the branches tracked by the BAC may be any of the types, including unconditional. Thus, the primary branch may be conditional, and a secondary may be unconditional (this is one of the possible permutations encompassed by Yeh). In such a case, the possible outcomes are TT or NT since the unconditional branch is always taken).
Referring to claim 16, Yeh, as modified, has taught the apparatus of claim 1, wherein the prediction storage circuitry is configured to store a multi-taken entry specifying, as one of the at least one subsequent branch instruction, a conditional branch instruction which is predicted to be taken and has an associated confidence value exceeds a threshold (any conditional branch that is predicted is predicted based on a 2-bit saturating counter (see section 2.1 and the text under the FIG.3 caption. As known, the counter values can be 00, 01, 10, and 11, with the higher order bit indicating the prediction (0 = not-taken; 1 = taken). When the counter is 11, that means the branch has been taken enough times to increment the counter all the way to 11. A value of 11 indicates highest taken confidence (it exceeds a value of 10, which is lower taken confidence)).
Claim 19 is the method performed by the apparatus of claim 1 and, thus, is rejected for similar reasoning as claim 1.
Claims 13, 17-18, and 20 are rejected under 35 U.S.C. 103 as being unpatentable over Yeh and the examiner’s taking of Official Notice.
Referring to claim 13, Yeh, as modified, has taught the apparatus of claim 11, wherein:
the flow tracking circuitry is configured to enforce a maximum limit for a number of subsequent conditional branch instructions in each of the one or more observed paths (from the left column on p.71, “[i]f the number of basic blocks predicted and fetched per cycle is limited to 2” (this means you can only predict a primary and secondary branch at the same time)); and
wherein the flow tracking circuitry is configured to support at least one observed path comprising a number of conditional branch instructions corresponding to the maximum limit (because two conditional branches can be predicted at once, a path including two branches will be supported by the prediction structure).
Yeh has taught unconditional branches (column 71, left column “type fields”), but has not taught that the supported at least one observed path of the two conditional branch instructions is followed by at least one unconditional branch instruction. However, Official Notice is taken that an unconditional branch following a conditional branch was well known in the art before applicant’s invention. Different branches of different types may appear anywhere in a program depending on the functionality desired by the programmer. As a result, it would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to modify Yeh such that the supported at least one observed path of the two conditional branch instructions is followed by at least one unconditional branch instruction.
Referring to claim 17, Yeh, as modified, has taught a system comprising:
the apparatus of claim 1, implemented in at least one packaged chip (section 3.3 refers to a chip);
Yeh has not taught that the system comprises at least one system component; and a board, wherein the at least one packaged chip and the at least one system component are assembled on the board. However, Official Notice is taken that such components and the combination thereof were well known in the art before applicant’s invention. Such allows for convenient integration of components in a computing system (e.g. processor, memory, etc.) on a single portable board. As a result, it would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to modify Yeh’s system to include at least one system component; and a board, wherein the at least one packaged chip and the at least one system component are assembled on the board.
Referring to claim 18, Yeh, as modified, has taught a chip-containing product comprising the system of claim 17, but has not taught wherein the system is assembled on a further board with at least one other product component. However, Official Notice is taken that such components and the combination thereof were well known in the art before applicant’s invention. Different boards and various components can be combined together to realize additional functions and computing power. As a result, it would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to modify Yeh such that the system is assembled on a further board with at least one other product component.
Claim 20 is mostly rejected for similar reasoning as claim 1. Yeh has not taught a non-transitory computer-readable medium storing computer-readable code for fabrication of an apparatus. However, Official Notice is taken that storing a hardware description language representation (e.g. Verilog, VHDL, etc.) of a processor on a non-transitory medium was well known in the art before applicant’s invention. Such a medium realizes portability for a processor design, allowing it to be moved to different workstations (for instance, to allow multiple users to view the design separately). HDL also allows for simulation of a design and ultimate fabrication of a design. Finally, HDL, being a software implementation, is easier to change should an error be noticed. In contrast, an error in a physical design may require re-fabricating, which is more expensive. As a result, it would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to modify Yeh to include a non-transitory computer-readable medium storing computer-readable code for fabrication of an apparatus.
Allowable Subject Matter
Claims 7-9 and 14 are objected to as being dependent upon a rejected base claim, but would be allowable if rewritten in independent form including all of the limitations of the base claim and any intervening claims.
Response to Arguments
Regarding the argument of the 112 rejection of claim 3, the examiner has withdrawn the rejection because the claim is reasonably clear based on applicant’s explanation. However, the examiner still recommends the slight rewording proposed above.
The examiner agrees with applicant’s argument that Ishii has not taught the new limitation added to the independent claims. Thus, the rejection has been withdrawn, and any remaining argument with respect to Ishii is moot and not responded to herein.
Conclusion
The following prior art made of record and not relied upon is considered pertinent to applicant's disclosure:
Seznec et al. has taught “Multiple-Block Ahead Branch Predictors” (e.g. see FIG.3 and sections 5+).
Applicant's amendment necessitated the new ground(s) of rejection presented in this Office action. Accordingly, THIS ACTION IS MADE FINAL. See MPEP § 706.07(a). Applicant is reminded of the extension of time policy as set forth in 37 CFR 1.136(a).
A shortened statutory period for reply to this final action is set to expire THREE MONTHS from the mailing date of this action. In the event a first reply is filed within TWO MONTHS of the mailing date of this final action and the advisory action is not mailed until after the end of the THREE-MONTH shortened statutory period, then the shortened statutory period will expire on the date the advisory action is mailed, and any nonprovisional extension fee (37 CFR 1.17(a)) pursuant to 37 CFR 1.136(a) will be calculated from the mailing date of the advisory action. In no event, however, will the statutory period for reply expire later than SIX MONTHS from the mailing date of this final action.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to David J. Huisman whose telephone number is 571-272-4168. The examiner can normally be reached on Monday-Friday, 9:00 am-5:30 pm.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, Jyoti Mehta, can be reached at 571-270-3995. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of published or unpublished applications may be obtained from Patent Center. Unpublished application information in Patent Center is available to registered users. To file and manage patent submissions in Patent Center, visit: https://patentcenter.uspto.gov. Visit https://www.uspto.gov/patents/apply/patent-center for more information about Patent Center and https://www.uspto.gov/patents/docx for information about filing in DOCX format. For additional questions, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/David J. Huisman/Primary Examiner, Art Unit 2183
Prosecution Insights