DETAILED ACTION
Claims 1-20 are pending.
Claims 10-20 have been withdrawn.
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 .
Election/Restrictions
Applicant’s election without traverse of Group I, claims 1-9, in the reply filed on September 29, 2025, is acknowledged.
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 disclosure is objected to because of the following informalities:
In paragraph 10, replace the 2nd instance of “CIS” with --CS--.
In paragraph 11, “entry…is a tag” appears to be incorrect. If an entry is an entire row in a directory in FIG.7, then the entry would include a tag, or be associated with a tag.
In paragraph 11, it appears that applicant should insert --contents of-- before “a function call stack”. A stack is a data structure comprising hardware for storing contents. Thus, the hash isn’t hashing the hardware per se, but the contents of the stack.
Appropriate correction is required.
Drawings
All FIGs are objected to for failing to comply with 37 CFR 1.84(a)(1) and 37 CFR 1.84(l), which requires the drawings be in black, and that all drawings be made by a process which will give them satisfactory reproduction characteristics. Every line, number, and letter must be durable, clean, solid black (except for color drawings), sufficiently dense and dark, and uniformly thick and well-defined. The weight of all lines and letters must be heavy enough to permit adequate reproduction. This requirement applies to all lines however fine, to shading, and to lines representing cut surfaces in sectional views. The drawings are pixelated, likely because applicant did not use black (RGB = 000), despite the drawings appearing black to the naked eye. This has been confirmed by the examiner via color inspection of applicant’s submitted pdf file. In such a case, the dithering used to convert applicant's grayscale image to black and white will add white pixels to try to estimate applicant's "gray" color, and the final drawings may not print properly or may print with reduced quality. Therefore, applicant must be sure to use only black and white. Applicant may try the following process to correct the color content:
1. Open the drawings PDF file with Adobe Acrobat (a similar Adobe product may work, but the examiner has only tested this in Adobe Acrobat);
2. Click “File” and then click “Print”;
3. Select “Adobe PDF” as the printer. If not available, “Microsoft Print to PDF” may also work, though this has not been tested. If neither option is available, this process may not be applicable, and applicant should try to find an alternate way to print in only black and white.
4. Uncheck “Print in grayscale (black and white)”;
5. Uncheck “Save ink/toner”;
6. Click “Advanced”;
7. Under “Color Management”, for the “Color Profile” field, select “Black & White” near the bottom of the list. The examiner also had “Treat grays as K-only grays” checked, and “Preserve Black” checked.
8. Click “OK” and then click “Print”. The resulting PDF should comprise only black and white drawings. Please review the final drawings for potential unintended consequences of this process.
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. The figure or figure number of an amended drawing should not be labeled as “amended.” 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 Objections
Claim 2 is objected to because of the following informalities:
In line 3, replace “CIS” with --CS-- to match claim 1, which sets forth an association between the second processing unit and a CS indicator.
Claim 3 is objected to because of the following informalities:
In line 2, the examiner asserts that “is” should be replaced with --associated
with-- based on paragraph 49 of the specification, which states “Each entry may be associated with a respective CIS indirect branch by a tag 703”. The examiner’s understanding is that the entry is not a tag per se (as claimed), because, if it were, a target identifier couldn’t be of the entry (as required by claim 1).
Claim 4 is objected to for similar reasoning as claim 3.
Claim 5 is objected to because of the following informalities:
In line 2, it appears that applicant should insert --contents of-- before “a function call stack”. A stack is a data structure comprising hardware for storing contents. Thus, the hash isn’t hashing the hardware per se, but the contents of the stack.
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. 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.
Such claim limitations are:
In claim 1, “at an electronic device…receiving…an instruction…”, which, under one reasonable interpretation, constitutes an electronic device for performing the receiving. From paragraphs 59-60, this device is interpreted to encompass a computer (FIG.12) or CPU/GPU 1210 (and equivalents thereof). These components are deemed sufficient structure because receiving an instruction is something all processors/computers do without special programming. In other words, receiving an instruction is a co-extensive function for which disclosure of a processor is sufficient (MPEP 2181(II)(B)).
In claim 1, “at an electronic device…generating…a respective instant entry”. From paragraph 53 of the specification, and FIG.8, at 805/807, applicant only generically discloses a fill mechanism to generate an entry. However, no specific structure is disclosed for this mechanism and, therefore, the claim cannot be properly interpreted according to the specification for purposes of 112(f). As such, broadest reasonable interpretation (BRI) will be taken and 112(a)/(b) rejections appear below.
In claim 2, “determining, at the first processing unit when the instruction indicates CIS, whether the respective directory has the respective existing entry corresponding to the instruction”. From paragraph 48, the first processing unit corresponds to FIG.7, 701. The structure that performs the actual determining, while not explicitly disclosed, corresponds to implied comparison circuitry that compares the output of 704 to a tag 703 to determine if there is a match/hit (paragraph 49). Thus, the claimed first processing unit encompasses at least a hardware comparator (and equivalents thereof).
In claim 2, “determining, at the second processing unit when the instruction indicates CIS, whether the respective directory has the respective existing entry corresponding to the instruction”. From paragraph 48, the second processing unit corresponds to FIG.7, 702. The structure that performs the actual determining, while not explicitly disclosed, corresponds to implied comparison circuitry that compares the output of 704 to a tag 703 to determine if there is a match/hit (paragraph 50). Thus, the claimed second processing unit encompasses at least a hardware comparator (and equivalents thereof).
In claim 6, “a fill mechanism to complete the respective instant entry…”. The examiner has been unable to find sufficient structure corresponding to this mechanism in the specification. As such, BRI will be taken and 112(a)/(b) rejections appear below.
In claim 9, the first processing unit and the second processing unit executing instructions to implement the claimed method steps. The examiner notes that FIG.7, 701 is labeled as the first processing unit and FIG.7, 702 is labeled as the second processing unit (paragraph 48). However, from FIG.7, these components appear to include hash functionality and memory to store tags/targets/context. Nowhere is it explained that these components execute instructions, or even receive instructions (they receive a PC value, not an instruction per se), as claimed. They appear to have no execution circuitry to do so. Therefore, the examiner is not clear on what structure applicant is trying to encompass with the claimed processing units. Consequently, BRI is taken and 112(a)/(b) rejections appear below.
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.
The examiner notes that 112(f) has not been invoked, in claim 1, for “at an electronic device…providing, when…a…directory…has a respective existing entry, a target identifier of [a] respective existing entry” because, from FIG.7, a directory 701/702 is the part of the device that does the providing of the target 705, and a directory necessarily requires hardware storage/memory (to store and output/provide the data of the directory). As such, the device is deemed to be modified by sufficient structure (storage/memory) to carry out the providing, and prong (C) of the three-prong test is not satisfied.
At least one claim is identified as including non-limiting contingent limitations. “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).
Regarding claim 1, when at least one of a respective directory at each of the first processing unit and the second processing unit has a respective existing entry corresponding to the instruction, the method only requires the receiving and providing steps (and not the generating step). Alternatively, when the respective directories at each of the first processing unit and the second processing unit do not have the respective existing entry corresponding to the instruction, the method only requires the receiving and generating steps (and not the providing step). Further, when the generating step is required by the method, only the generating in one of the respective directory at the first processing unit or the respective directory at the second processing unit is required based on the instruction indicating either CIS or CS, respectively.
Regarding claim 2, the method only requires that either the first or second processing unit performing the determining depending on the indicator value. For instance, for a single indirect branch instruction, if the indicator is CIS, then the method never requires determining at the second processing unit (again, note that “CIS” in line 3 should read --CS--).
Regarding claims 3-5, applicant is merely further defining an entry that may not exist in claim 1. For instance, in claim 3, if the providing step is not performed by the method of claim 1 (because a directory does not include a respective existing entry), then the respective existing entry of claim 3 does not exist. Thus, under one interpretation, each of claims 3-5 includes no further limitation due to the contingent providing step of claim 1.
Regarding claim 6, the limitations therein are not required when the respective existing entry is in a directory and the generating step of claim 1 is not performed.
Regarding claim 8, when the providing step of claim 1 is not performed by the method, claim 8 includes no further limitation. However, if the providing step of claim 1 is performed, claim 8 still includes no further limitation when only one of the directories includes the respective existing entry.
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-9 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 claims 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 pre-AIA the inventor(s), at the time the application was filed, had possession of the claimed invention.
Regarding claims 1, 6, and 9, as described above in the “Claim Interpretation” section, the disclosure does not provide adequate structure for the electronic device, fill mechanism, and first and second processing units, to perform the claimed generating, completing, and executing functions, respectively. The specification does not demonstrate that applicant has made an invention that achieves the claimed functions 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. It is recommended that applicant claim (in claim 1) an electronic circuit, processor, or some other non-generic structural component instead of the generic electronic device so as to not invoke 112(f). Applicant can also claim (in claim 6) a fill circuit instead of a fill mechanism. The examiner does not have a recommendation for claim 9 at this time.
Claims 2-8 are rejected due to their dependence on a claim lacking adequate written description.
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-9 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.
Referring to claims 1, 6, and 9, the electronic device, fill mechanism, and first and second processing units, in combination with at least some of their respective functions, invoke 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph. However, as described above in the “Claim Interpretation” section, the written description fails to disclose the corresponding structure, material, or acts for performing at least some of the functions and to clearly link the structure, material, or acts to the functions. Therefore, the claims are indefinite and is rejected under 35 U.S.C. 112(b) or pre-AIA 35 U.S.C. 112, second paragraph.
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.
Claims 2-8 are rejected due to their dependence on an indefinite claim.
Claim Rejections - 35 USC § 102
The following is a quotation of the appropriate paragraphs of 35 U.S.C. 102 that form the basis for the rejections under this section made in this Office action:
A person shall be entitled to a patent unless –
(a)(1) the claimed invention was patented, described in a printed publication, or in public use, on sale, or otherwise available to the public before the effective filing date of the claimed invention.
Claims 1 and 6-8 are rejected under 35 U.S.C. 102(a)(1) as being anticipated by Chen et al. (US 6,721,877 B1).
Referring to claim 1, Chen has taught a method comprising, at an electronic device (FIG.8, processor 10) including a first processing unit (FIG.6, at least 94) and a second processing unit (FIG.6, at least 92) each coupled to tangible, non-transitory processor-readable memory (FIG.8 shows the processor 10 connected to DRAM (non-transitory memory) 204 (column 23, lines 5-10). FIG.1 shows processor 10 in more detail, including branch prediction unit 18, which is shown in detail in FIG.6. Thus, the processing units (at least 92 and 94) of the branch prediction unit of the processor are coupled to the memory):
receiving, from a computer program, an instruction representing an indirect branch of the computer program (from column 23, lines 5-10, the processor 10 receives instructions from a computer program, including an indirect branch instruction (e.g. see the abstract)), the instruction having an indicator identifying one of context-sensitive (CS) and context-insensitive (CIS) (see FIG.6, and note the S-bit in 94. From column 19, lines 50-66, this bit is associated with an indirect branch instruction and indicates whether the branch instruction is context-sensitive (i.e., predicted by directory 92, which receives an index from 90 based on the branch PC (from 18D) and historical context 98) or context-insensitive (i.e., predicted by directory 94, which only receives an index based on the branch PC and not additional context 98));
providing, when at least one of a respective directory at each of the first processing unit and the second processing unit has a respective existing entry corresponding to the instruction, a target identifier of at least one respective existing entry, the target identifier identifying a target for the indirect branch (from FIG.6, note that when either or both of directories 92 and 94 have an entry that corresponds to the indirect branch instruction, a predicted target address is provided to selector 96);
(this limitation is not required by the method claim due to contingency (see “Claim Interpretation” section above). Thus, Chen need not teach the generating to anticipate this claim).
Referring to claim 6, the limitations therein are not required by the method due to contingency (see “Claim Interpretation” section above). Thus, Chen need not teach the limitations of claim 6 to anticipate the claim. Therefore, claim 6 is rejected for the same reasons as claim 1.
Referring to claim 7, Chen has taught the method of claim 1 wherein the indicator of the instruction is a label of one of CS and CIS (from FIG.6, the S-bit is a 1-bit label of CS/CIS status. For instance, S=0 might be a label that indicates the indirect branch is context-insensitive, while S=1 might be a label that indicates that the indirect branch is context-sensitive (or vice-versa)).
Referring to claim 8, Chen has taught the method of claim 1 wherein providing, when at least one of the respective directories at each of the first processing unit and the second processing unit has the respective existing entry corresponding to the instruction, the target identifier of at least one respective existing entry includes: providing, when each of the respective directories at each of the first processing unit and the second processing unit has the respective existing entry corresponding to the instruction, the target identifier of one respective existing entry in accordance with an arbitration scheme (from FIG.6, each directory 92 and 94 may include a target identifier for the same branch. Both of these target identifiers are sent to mux 96, which is controlled by the S bit to select and provide one of the two target identifiers. Thus, the S-bit implements a form of arbitration (when 0, it selects one target, and when 1, it selects the other target). Alternatively, even if Chen did not teach the providing in the last four lines of claim 8, such providing is not required to be taught by Chen due to contingency (see the “Claim Interpretation” section above). As a result, claim 8 is additionally rejected for the same reasons as claim 1 when the condition of claim 8 is not met)).
Claim Rejections - 35 USC § 103
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
Claims 2 and 4-5 are rejected under 35 U.S.C. 103 as being unpatentable over Chen.
Referring to claim 2, Chen has taught the method of claim 1 but has not taught, at the electronic device: determining, (see claim objection above), whether the respective directory has the respective existing entry corresponding to the instruction. Chen has taught, from column 20, lines 36-44, that the second directory 92 is tagless (meaning there is no tag comparator, as required by 112(f) interpretation). However, this is merely an example embodiment where a larger directory is implemented so as to eliminate tag comparison hardware (column 14, line 54, to column 15, line 22). This implies that if a smaller directory is used, tag comparison hardware could be implemented. Tag comparison is useful when multiple branches could map to the same entry in a smaller directory so that the system can determine if the entry is holding a prediction for the current branch or holding a prediction for another branch that mapped to the same entry. As a result, in order to reduce the size of the directory as well as use smaller address buses between index generator 90 and directory 92 (which in combination could reduce hardware size/footprint), and ensure that a prediction in an accessed entry is a prediction for the current branch and not some other branch, it would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to modify Chen to shrink directory 92 and implement tag comparison for, at the electronic device: determining, at the second processing unit when the instruction indicates CS (i.e., when the S bit is set such that directory 92 will provide the prediction), whether the respective directory has the respective existing entry corresponding to the instruction. Again, note that the struck-through limitation is not required by the claim due to contingency.
Referring to claim 4, Chen has taught the method of claim 1 but has not taught wherein the respective existing entry of the respective directory at the second processing unit is a tag. However, note that it would have been obvious to modify Chen’s directory 92 to include a tag for similar reasoning provided in the rejection of claim 2 (e.g. to reduce directory size and ensure that the entry being addressed does correspond to the current indirect branch instruction). Furthermore, with respect to the tag including a hash of a program counter and context information, see FIG.6 and note that index generator 90 receives, as inputs, the branch program counter from 18D and context information 98, then applies some function to these inputs, and then outputs a result of the function. In Chen, as modified, the function output would be used to index into directory 92 and perform tag comparison to verify the entry is for the current branch. This function is deemed a hash function that somehow combines the program counter and the context information to arrive at an output value for accessing an entry).
Referring to claim 5, Chen, as modified, has taught the method of claim 4 wherein the context information includes at least one of a branch address (FIG.6, 98, which are previous target addresses), a branch taken and not-taken history, and a function call stack.
Claim 3 is rejected under 35 U.S.C. 103 as being unpatentable over Chen in view of Stark (US 2004/0250054 A1).
Referring to claim 3, Chen has taught the method of claim 1 but has not taught wherein the respective existing entry of the respective directory at the first processing unit is a tag including a hash of a program counter. However, first note that it would have been obvious to modify Chen’s directory 94 to include a tag (to reduce directory size and ensure that the entry being addressed does correspond to the current indirect branch instruction) for similar reasoning set forth above in the rejection of claim 2. Chen, even as modified, has still not taught the claimed hash. Instead, Chen sends the least significant bits of the branch PC directly to directory 94 (see FIG.6 and column 20, lines 36-40). Stark, on the other hand, uses a hash function on the program counter to determine the index to a predictor (see paragraph [0065] and FIG.6, 606). A hash function is useful for more even distribution of entries throughout the directory. For instance, in Chen, there may be many indirect branch instructions that share the same least significant bits. Thus, in a direct-mapped cache (which is an example implementation in Chen (column 20, lines 40-42)), only one prediction could be stored for all of these branches at any given time. With a hash function, the program counter bits could be sent to a hash function to generate unique bits to allow multiple branch instructions that share the same least significant bits in their PC to hash to multiple different locations in the directory, thereby allowing the directory to track more than one prediction for these branches. This would reduce collisions and improve prediction accuracy. Note that some bits of the hash result would be used to access an entry while others would be used to compare the contents of the entry to make sure the entry is for the current branch. 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 Chen such that the respective existing entry of the respective directory at the first processing unit is a tag including a hash of a program counter.
---------------------------------------------------------------------------------------------------------------------
Claim Rejections - 35 USC § 102
The following is a quotation of the appropriate paragraphs of 35 U.S.C. 102 that form the basis for the rejections under this section made in this Office action:
A person shall be entitled to a patent unless –
(a)(1) the claimed invention was patented, described in a printed publication, or in public use, on sale, or otherwise available to the public before the effective filing date of the claimed invention.
Claims 9 and 1-8 are rejected under 35 U.S.C. 102(a)(1) as being anticipated by Farooq et al., “Compiler Support for Value-Based Indirect Branch Prediction”.
Referring to claim 9, Farooq has taught an electronic device (Table 2 on p.193 refers to a processor) comprising a first processing unit (FIG.2 on p.188, at least BTB) and a second processing unit (FIG.2, at least HIB) each coupled to non-transitory processor-readable memory (Table 2 refers to a memory, which would be addressed by PC addresses in the fetch stage of FIG.2 to obtain stored program instructions (FIG.3)), the memory having stored thereon instructions to be executed by the first processing unit and the second processing unit (the code of FIG.3(d) on p.189 is executed in part due to processing by the BTB and HIB) to implement a method comprising:
receiving, from a computer program, an instruction representing an indirect branch of the computer program (FIG.4), the instruction having an indicator identifying one of context-sensitive (CS) and context-insensitive (CIS) (FIG.4 on p.190, bit 13, which is a 1-bit indicator that specifies VBBI or no VBBI. From section 2 and FIG.2, VBBI is used when a compiler detects that the target of an indirect branch instruction is correlated with some prior instruction. VBBI is used by storing the result of the prior instruction in the HIB so that the result can be used to determine a predicted target for the indirect branch instruction. As such, when bit 13 = 1, this indicates CS because the branch is sensitive to context provided by a prior instruction. When bit 13 = 0, VBBI is not used, which indicates CIS because the branch is insensitive to HIB data generated by a prior instruction);
providing, when at least one of a respective directory at each of the first processing unit and the second processing unit has a respective existing entry corresponding to the instruction, a target identifier of at least one respective existing entry, the target identifier identifying a target for the indirect branch of the computer program (from section 2 and FIG.2, when the HIB contains a hint entry for the indirect branch, the hint value (target identifier) is selected by the mux at the bottom of FIG.2, and used in combination with the branch’s PC value to identify a target in the BTB); and
generating, in the respective directory at the first processing unit when the instruction indicates CIS and in the respective directory at the second processing unit when the instruction indicates CS, a respective instant entry corresponding to the instruction when the respective directories at each of the first processing unit and the second processing unit do not have the respective existing entry corresponding to the instruction (from section 2, an entry is created when a hint instruction is executed. Prior to this, the directory (HIB) at the second processing unit would not have this entry. And, a hint instruction is only executed when VBBI is being used (i.e., an indirect branch instruction to use the hint indicates CS), as determined by the compiler prior to runtime. In other words, it is because a branch indicates CS that a hint instruction will generate an HIB entry. When the branch indicates CIS, an entry is only created in the BTB).
Claim 1 is directed to the method performed by the device of claim 9. As such, claim 1 is rejected for at least a subset of reasoning set forth in the rejection of claim 9 (again, note that not all claim 1 limitations are required by the method (see the “Claim Interpretation” section above)).
Referring to claim 2, Farooq has taught the method of claim 1 further comprising, at the electronic device: determining, (see claim objection above), whether the respective directory has the respective existing entry corresponding to the instruction (see FIG.2, and note that the PC is compared to the jmp_pc to determine whether the HIB includes an entry for the current indirect branch instruction). Note that the struck-through language is not required by the method or Farooq.
Referring to claims 3-5, the limitations therein are not required by the method due to contingency (see “Claim Interpretation” section above). Thus, because Farooq teaches a method including only the receiving and generating of claim 1, Farooq need not teach any of the limitations related to the providing of claim 1, which include the limitations of claims 3-5, in order to anticipate claims 3-5. Therefore, claims 3-5 are rejected for the same reasons that the method of receiving and generating of claim 1 are rejected.
Referring to claim 6, the limitations therein are not required by the method due to contingency (see “Claim Interpretation” section above). Thus, because Farooq teaches a method including only the receiving and providing of claim 1, Farooq need not teach any of the limitations related to the generating of claim 1, which include the limitations of claim 6, in order to anticipate claim 6. Therefore, claim 6 is rejected for the same reasons that the method of receiving and providing of claim 1 are rejected.
Referring to claim 7, Farooq has taught the method of claim 1 wherein the indicator of the instruction is a label of one of CS and CIS (again, from FIG.4, a ‘1’ in bit 13 is a CS label and a ‘0’ in bit 13 is a CIS label).
Referring to claim 8, the limitations therein are not required by the method due to contingency (see “Claim Interpretation” section above). Thus, because Farooq teaches a method including only the receiving and generating of claim 1, Farooq need not teach any of the limitations related to the providing of claim 1, which include the limitations of claim 8, in order to anticipate claim 8. Therefore, claim 8 is are rejected for the same reasons that the method of receiving and generating of claim 1 are rejected. Alternatively, since Farooq teaches a method including only the receiving and providing of claim 1, and because the providing in the last four lines of claim 8 are contingent (see the “Claim Interpretation” section above), Farooq has taught the method of claim 8 for similar reasoning that Farooq teaches the method of claim 1, because claim 8 includes no further limitation when the condition of claim 8 is not met)).
Conclusion
The following prior art made of record and not relied upon is considered pertinent to applicant's disclosure:
Sun (US 2022/0197661 A1) has taught context-based memory indirect branch target prediction where a prediction is selected between a context-based prediction and another prediction, where the former is given priority (e.g. see paragraph 39).
Kountanis (US 2021/0240476 A1) has taught a TAGE-type indirect branch predictor (FIG.3) with multiple directories that are indexed by varying amounts of history, including no history.
Bouzguarrou (US 11,941,403 B2) has taught tracking correlation between an indirect branch and one or more other instructions and based the target prediction of the indirect branch based on the correlated instruction(s) instead of a longer history.
Sadasivam (US 2018/0314525 A1) has taught an ITTAGE predictor and pattern history table.
Kothari (US 2013/0311760 A1) has taught a multi-level indirect predictor using a confidence counter and filter scheme.
Kalamatianos has taught “Predicting Indirect Branches via Data Compression”, including having a compiler/linker set a bit in an indirect branch instruction that indicates ST (single target) or MT (multiple target) (see section 5).
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