DETAILED ACTION
Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Claims 1, 3-11, and 13-20 are pending in this office action and presented for examination. Claims 1, 7, 9, 11, and 18 are newly amended, and claims 2 and 12 are newly cancelled by the amendment received September 4, 2026.
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.
Claim(s) 1, 4-11, and 14-20 is/are rejected under 35 U.S.C. 102(a)(1) as being anticipated by Godard et al. (Godard) (US 20160132331 A1).
Consider claim 1, Godard discloses a method comprising: determining that a processor is to execute at least a portion of a first set of instructions ([0046], lines 1-7, the computer processor of the present application executes sequences of instructions organized as blocks of instructions (or “instruction blocks”). The instruction blocks can be extended basic blocks or “EBBs.” Each given EBB is a sequence of instructions with a single entry point (the head of the EBB) and possibly one or several control transfer operations forming exit points as shown in FIG. 1; [0050], lines 18-23, the predictor for each given Exit Table entry can include an address field. For both branch-type and call-type predictor entries, the address field of the given Exit Table predictor entry represents the entry address of the target EBB (the EBB that is the target of the branch operation or the call operation); [0050], lines 32-35, the address field of the given Exit Table entry can be used to derive the key to look up and access the Exit Table entry corresponding to the target EBB fragment; [0065], lines 1-3, the key used to look up the initial EBB fragment of an EBB can correspond to the entry address of the EBB as described herein; [0078], lines 10-15, when an EBB fragment is executed, it will require instructions from some number of cache lines before it exits (or is predicted to exit) and will not require subsequent cache lines containing instructions beyond this exit point (even if the EBB exits well before the predicted exit point); [0079], lines 6-18, more specifically, the address field of a given predictor is used to derive the memory address for the starting cache line of a corresponding EBB fragment. The Prefetcher uses the memory address for the starting cache line of the corresponding EBB fragment to fetch such starting cache line into cache (if not already in cache). The Prefetcher can then apply offsets to the base memory address of the starting cache line such that the Prefetcher fetches the additional cache lines of the corresponding EBB fragment into cache (if not already in cache), where the number of additional cache lines and corresponding offsets are dictated by the line count value of the given predictor; [0084], lines 1-17, there are several possible ways to convey the “exit is here” information. For example, the predictor entry can possibly contain a count of the number of instructions to decode between entry and exit of the EBB fragment. Or the predictor can possibly contain the address or offset of the exiting instruction. Or on a statically scheduled machine the predictor can possibly contain a count of the number of cycles spent in the EBB fragment. This might appear to be the same as the number of instructions executed in the EBB. The limitation with all of these indicators is that they are large, and space in the Exit Table is at a premium. However, the indicator can be compressed by noting that necessarily the exit will be from some instruction that ends in the last predicted line. Consequently, the exit can be takes as an instruction count from the point at which the final cache line of the respective EBB fragment enters decode, rather than from the start of the respective EBB fragment); determining an address associated with a sequentially first instruction of the first set of instructions ([0050], lines 18-23, the predictor for each given Exit Table entry can include an address field. For both branch-type and call-type predictor entries, the address field of the given Exit Table predictor entry represents the entry address of the target EBB (the EBB that is the target of the branch operation or the call operation)); determining a branch prediction index based on the address ([0050], lines 32-35, the address field of the given Exit Table entry can be used to derive the key to look up and access the Exit Table entry corresponding to the target EBB fragment; [0051], lines 1-5, the Prediction Logic of the computer processor is configured to access the Exit Table (and possibly an Exit Cache associated therewith) to generate and store a chain of predictors that refer to consecutive EBB fragments of the program to be executed by the computer processor; [0056], lines 1-4, in generating the chain of the predictors, the address field of a predictor as part of an entry read-out from the Exit Table can be used to generate a key to look up and access the next predictor in the chain) and fields of a branch history, wherein each field represents a distance between a sequentially first instruction of a respective previously executed set of instructions ([0062], lines 3-7, one or more predictions corresponding to a given EBB can be stored as entries in the Exit Table. Each such prediction includes an address field, which can be used to obtain the entry address of the predicted next EBB in the program code) and a respective previously-taken branch instruction of the respective previously executed set of instructions ([0050], lines 35-38, the predictor for each given Exit Table entry can also include information that represents the extent of the instructions of the corresponding EBB fragment that are predicted to be executed; [0056], lines 4-9, the predictor information that represents the extent of the sequential instructions of a given EBB fragment for the chain of predictors can be used to control the prefetching, fetching, instruction buffer read-out, and instruction-shifting operations for the instructions of the given EBB fragment; [0057], lines 1-19, in one embodiment, the predictor information that represents the extent of the instructions of the EBB fragment that are predicted to be executed as stored in the memory system includes a cache line count field and an instruction count field as shown in FIG. 4. The cache line count field indicates the number of cache lines of the memory system that store the sequence of sequential instructions of the EBB fragment. The instruction count field indicates the number of instructions of the EBB fragment that are found in the last cache line of the EBB fragment. The cache line count field of a given predictor can be used in conjunction with the address of the EBB fragment to control the prefetching and fetching operations of cache lines that include the instructions of the EBB fragment. The instruction count field of the predictor can be used to control the read-out of the sequence of instructions of the EBB fragment from the Instruction Buffer to the decode stage as well as the instruction shifting that isolates instructions of the EBB fragment for further decode processing; [0078], lines 10-15, when an EBB fragment is executed, it will require instructions from some number of cache lines before it exits (or is predicted to exit) and will not require subsequent cache lines containing instructions beyond this exit point (even if the EBB exits well before the predicted exit point); [0079], lines 6-18, more specifically, the address field of a given predictor is used to derive the memory address for the starting cache line of a corresponding EBB fragment. The Prefetcher uses the memory address for the starting cache line of the corresponding EBB fragment to fetch such starting cache line into cache (if not already in cache). The Prefetcher can then apply offsets to the base memory address of the starting cache line such that the Prefetcher fetches the additional cache lines of the corresponding EBB fragment into cache (if not already in cache), where the number of additional cache lines and corresponding offsets are dictated by the line count value of the given predictor; [0084], lines 1-17, there are several possible ways to convey the “exit is here” information. For example, the predictor entry can possibly contain a count of the number of instructions to decode between entry and exit of the EBB fragment. Or the predictor can possibly contain the address or offset of the exiting instruction. Or on a statically scheduled machine the predictor can possibly contain a count of the number of cycles spent in the EBB fragment. This might appear to be the same as the number of instructions executed in the EBB. The limitation with all of these indicators is that they are large, and space in the Exit Table is at a premium. However, the indicator can be compressed by noting that necessarily the exit will be from some instruction that ends in the last predicted line. Consequently, the exit can be takes as an instruction count from the point at which the final cache line of the respective EBB fragment enters decode, rather than from the start of the respective EBB fragment); querying a table ([0050], line 2, Exit Table) based on the branch prediction ([0050], lines 1-3, the computer processor also includes Prediction Logic that employs an Exit Table whose entries store predictors) index ([0050], lines 4-6, each given Exit Table entry is associated with a key by which the given Exit Table entry may be accessed (looked up)) to determine a predicted exit point of the first set of instructions ([0050], lines 6-8, the predictor corresponding to a given EBB fragment can include information that represents a predicted execution path that exits the given EBB fragment; [0050], lines 35-38, the predictor for each given Exit Table entry can also include information that represents the extent of the instructions of the corresponding EBB fragment that are predicted to be executed; [0056], lines 4-9, the predictor information that represents the extent of the sequential instructions of a given EBB fragment for the chain of predictors can be used to control the prefetching, fetching, instruction buffer read-out, and instruction-shifting operations for the instructions of the given EBB fragment; [0057], lines 1-19, in one embodiment, the predictor information that represents the extent of the instructions of the EBB fragment that are predicted to be executed as stored in the memory system includes a cache line count field and an instruction count field as shown in FIG. 4. The cache line count field indicates the number of cache lines of the memory system that store the sequence of sequential instructions of the EBB fragment. The instruction count field indicates the number of instructions of the EBB fragment that are found in the last cache line of the EBB fragment. The cache line count field of a given predictor can be used in conjunction with the address of the EBB fragment to control the prefetching and fetching operations of cache lines that include the instructions of the EBB fragment. The instruction count field of the predictor can be used to control the read-out of the sequence of instructions of the EBB fragment from the Instruction Buffer to the decode stage as well as the instruction shifting that isolates instructions of the EBB fragment for further decode processing; [0078], lines 10-15, when an EBB fragment is executed, it will require instructions from some number of cache lines before it exits (or is predicted to exit) and will not require subsequent cache lines containing instructions beyond this exit point (even if the EBB exits well before the predicted exit point); [0079], lines 6-18, more specifically, the address field of a given predictor is used to derive the memory address for the starting cache line of a corresponding EBB fragment. The Prefetcher uses the memory address for the starting cache line of the corresponding EBB fragment to fetch such starting cache line into cache (if not already in cache). The Prefetcher can then apply offsets to the base memory address of the starting cache line such that the Prefetcher fetches the additional cache lines of the corresponding EBB fragment into cache (if not already in cache), where the number of additional cache lines and corresponding offsets are dictated by the line count value of the given predictor; [0084], lines 1-17, there are several possible ways to convey the “exit is here” information. For example, the predictor entry can possibly contain a count of the number of instructions to decode between entry and exit of the EBB fragment. Or the predictor can possibly contain the address or offset of the exiting instruction. Or on a statically scheduled machine the predictor can possibly contain a count of the number of cycles spent in the EBB fragment. This might appear to be the same as the number of instructions executed in the EBB. The limitation with all of these indicators is that they are large, and space in the Exit Table is at a premium. However, the indicator can be compressed by noting that necessarily the exit will be from some instruction that ends in the last predicted line. Consequently, the exit can be takes as an instruction count from the point at which the final cache line of the respective EBB fragment enters decode, rather than from the start of the respective EBB fragment); and fetching, by the processor, a subset of the first set of instructions based on the predicted exit point ([0050], lines 6-8, the predictor corresponding to a given EBB fragment can include information that represents a predicted execution path that exits the given EBB fragment; [0050], lines 35-38, the predictor for each given Exit Table entry can also include information that represents the extent of the instructions of the corresponding EBB fragment that are predicted to be executed; [0056], lines 4-9, the predictor information that represents the extent of the sequential instructions of a given EBB fragment for the chain of predictors can be used to control the prefetching, fetching, instruction buffer read-out, and instruction-shifting operations for the instructions of the given EBB fragment; [0057], lines 1-19, in one embodiment, the predictor information that represents the extent of the instructions of the EBB fragment that are predicted to be executed as stored in the memory system includes a cache line count field and an instruction count field as shown in FIG. 4. The cache line count field indicates the number of cache lines of the memory system that store the sequence of sequential instructions of the EBB fragment. The instruction count field indicates the number of instructions of the EBB fragment that are found in the last cache line of the EBB fragment. The cache line count field of a given predictor can be used in conjunction with the address of the EBB fragment to control the prefetching and fetching operations of cache lines that include the instructions of the EBB fragment. The instruction count field of the predictor can be used to control the read-out of the sequence of instructions of the EBB fragment from the Instruction Buffer to the decode stage as well as the instruction shifting that isolates instructions of the EBB fragment for further decode processing; [0078], lines 10-15, when an EBB fragment is executed, it will require instructions from some number of cache lines before it exits (or is predicted to exit) and will not require subsequent cache lines containing instructions beyond this exit point (even if the EBB exits well before the predicted exit point); [0079], lines 6-18, more specifically, the address field of a given predictor is used to derive the memory address for the starting cache line of a corresponding EBB fragment. The Prefetcher uses the memory address for the starting cache line of the corresponding EBB fragment to fetch such starting cache line into cache (if not already in cache). The Prefetcher can then apply offsets to the base memory address of the starting cache line such that the Prefetcher fetches the additional cache lines of the corresponding EBB fragment into cache (if not already in cache), where the number of additional cache lines and corresponding offsets are dictated by the line count value of the given predictor; [0084], lines 1-17, there are several possible ways to convey the “exit is here” information. For example, the predictor entry can possibly contain a count of the number of instructions to decode between entry and exit of the EBB fragment. Or the predictor can possibly contain the address or offset of the exiting instruction. Or on a statically scheduled machine the predictor can possibly contain a count of the number of cycles spent in the EBB fragment. This might appear to be the same as the number of instructions executed in the EBB. The limitation with all of these indicators is that they are large, and space in the Exit Table is at a premium. However, the indicator can be compressed by noting that necessarily the exit will be from some instruction that ends in the last predicted line. Consequently, the exit can be takes as an instruction count from the point at which the final cache line of the respective EBB fragment enters decode, rather than from the start of the respective EBB fragment).
Consider claim 4, Godard discloses the method of claim 1 (see above), wherein the querying of the table includes receiving a count of fetch packets associated with the predicted exit point and an offset of the predicted exit point within a fetch packet ([0050], lines 35-38, the predictor for each given Exit Table entry can also include information that represents the extent of the instructions of the corresponding EBB fragment that are predicted to be executed; [0056], lines 4-9, the predictor information that represents the extent of the sequential instructions of a given EBB fragment for the chain of predictors can be used to control the prefetching, fetching, instruction buffer read-out, and instruction-shifting operations for the instructions of the given EBB fragment; [0057], lines 1-19, in one embodiment, the predictor information that represents the extent of the instructions of the EBB fragment that are predicted to be executed as stored in the memory system includes a cache line count field and an instruction count field as shown in FIG. 4. The cache line count field indicates the number of cache lines of the memory system that store the sequence of sequential instructions of the EBB fragment. The instruction count field indicates the number of instructions of the EBB fragment that are found in the last cache line of the EBB fragment. The cache line count field of a given predictor can be used in conjunction with the address of the EBB fragment to control the prefetching and fetching operations of cache lines that include the instructions of the EBB fragment. The instruction count field of the predictor can be used to control the read-out of the sequence of instructions of the EBB fragment from the Instruction Buffer to the decode stage as well as the instruction shifting that isolates instructions of the EBB fragment for further decode processing; [0078], lines 10-15, when an EBB fragment is executed, it will require instructions from some number of cache lines before it exits (or is predicted to exit) and will not require subsequent cache lines containing instructions beyond this exit point (even if the EBB exits well before the predicted exit point); [0079], lines 6-18, more specifically, the address field of a given predictor is used to derive the memory address for the starting cache line of a corresponding EBB fragment. The Prefetcher uses the memory address for the starting cache line of the corresponding EBB fragment to fetch such starting cache line into cache (if not already in cache). The Prefetcher can then apply offsets to the base memory address of the starting cache line such that the Prefetcher fetches the additional cache lines of the corresponding EBB fragment into cache (if not already in cache), where the number of additional cache lines and corresponding offsets are dictated by the line count value of the given predictor; [0084], lines 1-17, there are several possible ways to convey the “exit is here” information. For example, the predictor entry can possibly contain a count of the number of instructions to decode between entry and exit of the EBB fragment. Or the predictor can possibly contain the address or offset of the exiting instruction. Or on a statically scheduled machine the predictor can possibly contain a count of the number of cycles spent in the EBB fragment. This might appear to be the same as the number of instructions executed in the EBB. The limitation with all of these indicators is that they are large, and space in the Exit Table is at a premium. However, the indicator can be compressed by noting that necessarily the exit will be from some instruction that ends in the last predicted line. Consequently, the exit can be takes as an instruction count from the point at which the final cache line of the respective EBB fragment enters decode, rather than from the start of the respective EBB fragment; [0050], lines 23-28, in this case, the address field of the Exit Table entry can be a logical offset of the entry address of the target EBB relative to a base address stored in a special purpose register of the computer processor or by an offset from the entry address of the exiting EBB corresponding to the predictor).
Consider claim 5, Godard discloses the method of claim 1 (see above), wherein the querying of the table includes receiving an indication of a likelihood that a branch at the predicted exit point will be taken ([0095], lines 1-9, each predictor entry of the Exit Table can include information about the quality of the prediction defined by the predictor entry, such as an estimate of how likely the prediction is to be correct. An EBB that exits only by a single unconditional branch will have a prediction that is 100% accurate, while one that can and does exit from any of several conditional branches may have a prediction that is relatively unlikely to be correct, even if the prediction is the most likely of the alternatives).
Consider claim 6, Godard disclose the method of claim 5 (see above) further comprising updating the indication of likelihood based on whether the branch was taken ([0095], lines 9-16, moreover, program transfer behavior frequently changes during execution. For example, during one phase of execution, an EBB fragment may usually exit via a branch operation A, but in a later phase of execution, the same EBB fragment may usually exit via another branch operation B. Such variability makes it desirable for the prediction for the EBB fragment to change over time, so as to track the most likely exit based on the recent behavior; [0096], lines 1-25, thus, program execution of the EBB fragments can be used to update the quality information of the corresponding predictor entries as stored in the Exit Table and then modify the predictions defined by the predictor entries themselves when warranted by the quality information. Specifically, when a prediction defined by an Exit Table entry is successful, i.e., execution of the EBB fragment corresponding to the Exit Table entry did in fact exit at the predicted point and to the predicted target, the key for such EBB fragment can be used to access the Exit Table entry and raise the quality information of the predictor entry as appropriate. When a prediction defined by an Exit Table entry is not successful (a mispredict), i.e., execution of the EBB fragment corresponding to the Exit Table entry did not in fact exit at the predicted point and to the predicted target, the key for such EBB fragment can be used to access the Exit Table entry and lower the quality information of the predictor entry as appropriate. In the case of a mispredict, the execution behavior carries information that defines the prediction that would have been correct for that key. If the quality information for the Exit Table entry drops below a replacement threshold, the prediction defined by the Exit Table entry can be replaced by the corrected prediction carried by the execution behavior. This same replacement operation is performed in the event that the Exit Table does not have any entry corresponding to the key; [0098], lines 1-29, in one embodiment, the quality information of the prediction defined by the predictor entry can be represented by a one-bit or two-bit saturating counter that is part of each predictor entry. The counter can be updated based on the execution behavior of the corresponding EBB fragment. If the prediction defined by a predictor for a given EBB fragment is found to have been correct during execution of the given EBB fragment, i.e. the EBB fragment did in fact exit where it was expected to, the counter can be incremented (unless saturated at the maximum count value). However, if the prediction defined by a predictor for a given EBB fragment is found to have been incorrect during execution of the given EBB fragment, i.e. the EBB fragment did not in fact exit where it was expected to, the counter can be decremented. If the counter saturates down (i.e., its count was already at the minimum count value), then the predictor of the entry can be updated to predict what would have been the correct prediction and (in most variations) the counter is incremented again. The effect of the counter is that the predictor entry remains in the Exit Table if it is usually correct, but if is incorrect for more than a few consecutive predictions then it will be replaced. In one example, the quality information of the predictor can be defined by a single bit, indicating strong confidence and weak confidence in the prediction. This allows the predictor entry for a corresponding EBB fragment to miss (predict wrong) twice in a row before being replaced by an updated prediction. In other examples, the quality information of the predictor can be defined by multiple bits so as to provide finer divisions of confidence).
Consider claim 7, Godard discloses the method of claim 1 (see above), wherein: the subset of the first set of instructions is a first subset; the first set of instructions includes a second subset between the first subset and a second set of instructions; and the method further comprises determining, based on the predicted exit point, whether to fetch a subset of the second set of instructions after the first subset of the first set of instructions without fetching the second subset of the first set of instructions therebetween ([0046], lines 1-7, the computer processor of the present application executes sequences of instructions organized as blocks of instructions (or “instruction blocks”). The instruction blocks can be extended basic blocks or “EBBs.” Each given EBB is a sequence of instructions with a single entry point (the head of the EBB) and possibly one or several control transfer operations forming exit points as shown in FIG. 1; [0050], lines 18-23, the predictor for each given Exit Table entry can include an address field. For both branch-type and call-type predictor entries, the address field of the given Exit Table predictor entry represents the entry address of the target EBB (the EBB that is the target of the branch operation or the call operation); [0050], lines 32-35, the address field of the given Exit Table entry can be used to derive the key to look up and access the Exit Table entry corresponding to the target EBB fragment; [0065], lines 1-3, the key used to look up the initial EBB fragment of an EBB can correspond to the entry address of the EBB as described herein; [0078], lines 10-15, when an EBB fragment is executed, it will require instructions from some number of cache lines before it exits (or is predicted to exit) and will not require subsequent cache lines containing instructions beyond this exit point (even if the EBB exits well before the predicted exit point); [0079], lines 6-18, more specifically, the address field of a given predictor is used to derive the memory address for the starting cache line of a corresponding EBB fragment. The Prefetcher uses the memory address for the starting cache line of the corresponding EBB fragment to fetch such starting cache line into cache (if not already in cache). The Prefetcher can then apply offsets to the base memory address of the starting cache line such that the Prefetcher fetches the additional cache lines of the corresponding EBB fragment into cache (if not already in cache), where the number of additional cache lines and corresponding offsets are dictated by the line count value of the given predictor; [0084], lines 1-17, there are several possible ways to convey the “exit is here” information. For example, the predictor entry can possibly contain a count of the number of instructions to decode between entry and exit of the EBB fragment. Or the predictor can possibly contain the address or offset of the exiting instruction. Or on a statically scheduled machine the predictor can possibly contain a count of the number of cycles spent in the EBB fragment. This might appear to be the same as the number of instructions executed in the EBB. The limitation with all of these indicators is that they are large, and space in the Exit Table is at a premium. However, the indicator can be compressed by noting that necessarily the exit will be from some instruction that ends in the last predicted line. Consequently, the exit can be takes as an instruction count from the point at which the final cache line of the respective EBB fragment enters decode, rather than from the start of the respective EBB fragment; [0079], lines 18-22, note that the prefetch operations are carried out over an exact number of cache lines that are part of the EBB fragment. This is an exact prefetch as the exact number of needed cache lines will be loaded into cache if not already in cache; [0080], lines 11-13, the exact prefetch operations can avoid wasting cache space on cache lines that are loaded speculatively and not used as a result of the blind prefetch strategy).
Consider claim 8, Godard discloses the method of claim 7 (see above) further comprising, based on the predicted exit point, beginning execution of the second set of instructions prior to determining whether a branch associated with the predicted exit point will be taken ([0054], line 5, follow-on execution; [0204], lines 1-7, in the event of a taken mispredict, the Decode Control Logic 155 has no corresponding predictor entry to work from and the chain of predictions that had been feeding it are useless. In this case, the Mispredict Recovery Logic 159 can be configured to discard the internal state of the Decode Stage 107 and unwind any instructions that have been issued down the wrong path; [0004], lines 1-5, modern computer processors (also known as central processing units or CPUs) employ branch prediction and a pipelined instruction fetch process so as to be able to feed a new decoded instruction (or several, depending on the architecture) into issue every cycle).
Consider claim 9, Godard discloses the method of claim 1 (see above), wherein: the branch prediction index is a first branch prediction index; the branch history is a first branch history; and the method further comprises: executing a branch instruction of the first set of instructions; and based on the branch instruction: determining a second branch prediction index based on the address associated with the sequentially first instruction of the first set of instructions and a second branch history; and storing fetch information associated with the branch instruction in the table using the second branch prediction index ([0232], lines 6-9, the search key of the Exit Table can be modified to contain history information about the flow of control that led up to the keyed EBB or EBB fragment, and selects from among the stored predictor entries; [0051], lines 1-5, the Prediction Logic of the computer processor is configured to access the Exit Table (and possibly an Exit Cache associated therewith) to generate and store a chain of predictors that refer to consecutive EBB fragments of the program to be executed by the computer processor; [0056], lines 1-4, in generating the chain of the predictors, the address field of a predictor as part of an entry read-out from the Exit Table can be used to generate a key to look up and access the next predictor in the chain; [0095], lines 9-16, moreover, program transfer behavior frequently changes during execution. For example, during one phase of execution, an EBB fragment may usually exit via a branch operation A, but in a later phase of execution, the same EBB fragment may usually exit via another branch operation B. Such variability makes it desirable for the prediction for the EBB fragment to change over time, so as to track the most likely exit based on the recent behavior; [0096], lines 1-25, thus, program execution of the EBB fragments can be used to update the quality information of the corresponding predictor entries as stored in the Exit Table and then modify the predictions defined by the predictor entries themselves when warranted by the quality information. Specifically, when a prediction defined by an Exit Table entry is successful, i.e., execution of the EBB fragment corresponding to the Exit Table entry did in fact exit at the predicted point and to the predicted target, the key for such EBB fragment can be used to access the Exit Table entry and raise the quality information of the predictor entry as appropriate. When a prediction defined by an Exit Table entry is not successful (a mispredict), i.e., execution of the EBB fragment corresponding to the Exit Table entry did not in fact exit at the predicted point and to the predicted target, the key for such EBB fragment can be used to access the Exit Table entry and lower the quality information of the predictor entry as appropriate. In the case of a mispredict, the execution behavior carries information that defines the prediction that would have been correct for that key. If the quality information for the Exit Table entry drops below a replacement threshold, the prediction defined by the Exit Table entry can be replaced by the corrected prediction carried by the execution behavior. This same replacement operation is performed in the event that the Exit Table does not have any entry corresponding to the key; [0098], lines 1-29, in one embodiment, the quality information of the prediction defined by the predictor entry can be represented by a one-bit or two-bit saturating counter that is part of each predictor entry. The counter can be updated based on the execution behavior of the corresponding EBB fragment. If the prediction defined by a predictor for a given EBB fragment is found to have been correct during execution of the given EBB fragment, i.e. the EBB fragment did in fact exit where it was expected to, the counter can be incremented (unless saturated at the maximum count value). However, if the prediction defined by a predictor for a given EBB fragment is found to have been incorrect during execution of the given EBB fragment, i.e. the EBB fragment did not in fact exit where it was expected to, the counter can be decremented. If the counter saturates down (i.e., its count was already at the minimum count value), then the predictor of the entry can be updated to predict what would have been the correct prediction and (in most variations) the counter is incremented again. The effect of the counter is that the predictor entry remains in the Exit Table if it is usually correct, but if is incorrect for more than a few consecutive predictions then it will be replaced. In one example, the quality information of the predictor can be defined by a single bit, indicating strong confidence and weak confidence in the prediction. This allows the predictor entry for a corresponding EBB fragment to miss (predict wrong) twice in a row before being replaced by an updated prediction. In other examples, the quality information of the predictor can be defined by multiple bits so as to provide finer divisions of confidence).
Consider claim 10, Godard discloses the method of claim 9 (see above), wherein the fetch information includes a count of fetch packets associated with the branch instruction and an offset of the branch instruction within a fetch packet ([0050], lines 35-38, the predictor for each given Exit Table entry can also include information that represents the extent of the instructions of the corresponding EBB fragment that are predicted to be executed; [0056], lines 4-9, the predictor information that represents the extent of the sequential instructions of a given EBB fragment for the chain of predictors can be used to control the prefetching, fetching, instruction buffer read-out, and instruction-shifting operations for the instructions of the given EBB fragment; [0057], lines 1-19, in one embodiment, the predictor information that represents the extent of the instructions of the EBB fragment that are predicted to be executed as stored in the memory system includes a cache line count field and an instruction count field as shown in FIG. 4. The cache line count field indicates the number of cache lines of the memory system that store the sequence of sequential instructions of the EBB fragment. The instruction count field indicates the number of instructions of the EBB fragment that are found in the last cache line of the EBB fragment. The cache line count field of a given predictor can be used in conjunction with the address of the EBB fragment to control the prefetching and fetching operations of cache lines that include the instructions of the EBB fragment. The instruction count field of the predictor can be used to control the read-out of the sequence of instructions of the EBB fragment from the Instruction Buffer to the decode stage as well as the instruction shifting that isolates instructions of the EBB fragment for further decode processing; [0078], lines 10-15, when an EBB fragment is executed, it will require instructions from some number of cache lines before it exits (or is predicted to exit) and will not require subsequent cache lines containing instructions beyond this exit point (even if the EBB exits well before the predicted exit point); [0079], lines 6-18, more specifically, the address field of a given predictor is used to derive the memory address for the starting cache line of a corresponding EBB fragment. The Prefetcher uses the memory address for the starting cache line of the corresponding EBB fragment to fetch such starting cache line into cache (if not already in cache). The Prefetcher can then apply offsets to the base memory address of the starting cache line such that the Prefetcher fetches the additional cache lines of the corresponding EBB fragment into cache (if not already in cache), where the number of additional cache lines and corresponding offsets are dictated by the line count value of the given predictor; [0084], lines 1-17, there are several possible ways to convey the “exit is here” information. For example, the predictor entry can possibly contain a count of the number of instructions to decode between entry and exit of the EBB fragment. Or the predictor can possibly contain the address or offset of the exiting instruction. Or on a statically scheduled machine the predictor can possibly contain a count of the number of cycles spent in the EBB fragment. This might appear to be the same as the number of instructions executed in the EBB. The limitation with all of these indicators is that they are large, and space in the Exit Table is at a premium. However, the indicator can be compressed by noting that necessarily the exit will be from some instruction that ends in the last predicted line. Consequently, the exit can be takes as an instruction count from the point at which the final cache line of the respective EBB fragment enters decode, rather than from the start of the respective EBB fragment; [0050], lines 23-28, in this case, the address field of the Exit Table entry can be a logical offset of the entry address of the target EBB relative to a base address stored in a special purpose register of the computer processor or by an offset from the entry address of the exiting EBB corresponding to the predictor).
Consider claim 11, Godard discloses a circuit device comprising: a processor configured to execute at least a portion of a first set of instructions ([0046], lines 1-7, the computer processor of the present application executes sequences of instructions organized as blocks of instructions (or “instruction blocks”). The instruction blocks can be extended basic blocks or “EBBs.” Each given EBB is a sequence of instructions with a single entry point (the head of the EBB) and possibly one or several control transfer operations forming exit points as shown in FIG. 1; [0050], lines 18-23, the predictor for each given Exit Table entry can include an address field. For both branch-type and call-type predictor entries, the address field of the given Exit Table predictor entry represents the entry address of the target EBB (the EBB that is the target of the branch operation or the call operation); [0050], lines 32-35, the address field of the given Exit Table entry can be used to derive the key to look up and access the Exit Table entry corresponding to the target EBB fragment; [0065], lines 1-3, the key used to look up the initial EBB fragment of an EBB can correspond to the entry address of the EBB as described herein; [0078], lines 10-15, when an EBB fragment is executed, it will require instructions from some number of cache lines before it exits (or is predicted to exit) and will not require subsequent cache lines containing instructions beyond this exit point (even if the EBB exits well before the predicted exit point); [0079], lines 6-18, more specifically, the address field of a given predictor is used to derive the memory address for the starting cache line of a corresponding EBB fragment. The Prefetcher uses the memory address for the starting cache line of the corresponding EBB fragment to fetch such starting cache line into cache (if not already in cache). The Prefetcher can then apply offsets to the base memory address of the starting cache line such that the Prefetcher fetches the additional cache lines of the corresponding EBB fragment into cache (if not already in cache), where the number of additional cache lines and corresponding offsets are dictated by the line count value of the given predictor; [0084], lines 1-17, there are several possible ways to convey the “exit is here” information. For example, the predictor entry can possibly contain a count of the number of instructions to decode between entry and exit of the EBB fragment. Or the predictor can possibly contain the address or offset of the exiting instruction. Or on a statically scheduled machine the predictor can possibly contain a count of the number of cycles spent in the EBB fragment. This might appear to be the same as the number of instructions executed in the EBB. The limitation with all of these indicators is that they are large, and space in the Exit Table is at a premium. However, the indicator can be compressed by noting that necessarily the exit will be from some instruction that ends in the last predicted line. Consequently, the exit can be takes as an instruction count from the point at which the final cache line of the respective EBB fragment enters decode, rather than from the start of the respective EBB fragment), wherein the processor includes: fetch circuitry (FIG. 6, instruction fetch unit (fetcher)); and branch prediction circuitry (FIG. 6, prediction logic 111) that includes a table memory configured to store a table (FIG. 6, exit table 113), wherein the branch prediction circuitry is configured to: determine an address associated with the first set of instructions ([0050], lines 18-23, the predictor for each given Exit Table entry can include an address field. For both branch-type and call-type predictor entries, the address field of the given Exit Table predictor entry represents the entry address of the target EBB (the EBB that is the target of the branch operation or the call operation)); determine a branch prediction index based on the address ([0050], lines 32-35, the address field of the given Exit Table entry can be used to derive the key to look up and access the Exit Table entry corresponding to the target EBB fragment; [0051], lines 1-5, the Prediction Logic of the computer processor is configured to access the Exit Table (and possibly an Exit Cache associated therewith) to generate and store a chain of predictors that refer to consecutive EBB fragments of the program to be executed by the computer processor; [0056], lines 1-4, in generating the chain of the predictors, the address field of a predictor as part of an entry read-out from the Exit Table can be used to generate a key to look up and access the next predictor in the chain) and fields of a branch history, wherein each field represents a distance between a sequentially first instruction of a respective previously executed set of instructions ([0062], lines 3-7, one or more predictions corresponding to a given EBB can be stored as entries in the Exit Table. Each such prediction includes an address field, which can be used to obtain the entry address of the predicted next EBB in the program code) and a respective previously-taken branch instruction of the respective previously executed set of instructions ([0050], lines 35-38, the predictor for each given Exit Table entry can also include information that represents the extent of the instructions of the corresponding EBB fragment that are predicted to be executed; [0056], lines 4-9, the predictor information that represents the extent of the sequential instructions of a given EBB fragment for the chain of predictors can be used to control the prefetching, fetching, instruction buffer read-out, and instruction-shifting operations for the instructions of the given EBB fragment; [0057], lines 1-19, in one embodiment, the predictor information that represents the extent of the instructions of the EBB fragment that are predicted to be executed as stored in the memory system includes a cache line count field and an instruction count field as shown in FIG. 4. The cache line count field indicates the number of cache lines of the memory system that store the sequence of sequential instructions of the EBB fragment. The instruction count field indicates the number of instructions of the EBB fragment that are found in the last cache line of the EBB fragment. The cache line count field of a given predictor can be used in conjunction with the address of the EBB fragment to control the prefetching and fetching operations of cache lines that include the instructions of the EBB fragment. The instruction count field of the predictor can be used to control the read-out of the sequence of instructions of the EBB fragment from the Instruction Buffer to the decode stage as well as the instruction shifting that isolates instructions of the EBB fragment for further decode processing; [0078], lines 10-15, when an EBB fragment is executed, it will require instructions from some number of cache lines before it exits (or is predicted to exit) and will not require subsequent cache lines containing instructions beyond this exit point (even if the EBB exits well before the predicted exit point); [0079], lines 6-18, more specifically, the address field of a given predictor is used to derive the memory address for the starting cache line of a corresponding EBB fragment. The Prefetcher uses the memory address for the starting cache line of the corresponding EBB fragment to fetch such starting cache line into cache (if not already in cache). The Prefetcher can then apply offsets to the base memory address of the starting cache line such that the Prefetcher fetches the additional cache lines of the corresponding EBB fragment into cache (if not already in cache), where the number of additional cache lines and corresponding offsets are dictated by the line count value of the given predictor; [0084], lines 1-17, there are several possible ways to convey the “exit is here” information. For example, the predictor entry can possibly contain a count of the number of instructions to decode between entry and exit of the EBB fragment. Or the predictor can possibly contain the address or offset of the exiting instruction. Or on a statically scheduled machine the predictor can possibly contain a count of the number of cycles spent in the EBB fragment. This might appear to be the same as the number of instructions executed in the EBB. The limitation with all of these indicators is that they are large, and space in the Exit Table is at a premium. However, the indicator can be compressed by noting that necessarily the exit will be from some instruction that ends in the last predicted line. Consequently, the exit can be takes as an instruction count from the point at which the final cache line of the respective EBB fragment enters decode, rather than from the start of the respective EBB fragment); determine a predicted exit point of the first set of instructions ([0050], lines 6-8, the predictor corresponding to a given EBB fragment can include information that represents a predicted execution path that exits the given EBB fragment; [0050], lines 35-38, the predictor for each given Exit Table entry can also include information that represents the extent of the instructions of the corresponding EBB fragment that are predicted to be executed; [0056], lines 4-9, the predictor information that represents the extent of the sequential instructions of a given EBB fragment for the chain of predictors can be used to control the prefetching, fetching, instruction buffer read-out, and instruction-shifting operations for the instructions of the given EBB fragment; [0057], lines 1-19, in one embodiment, the predictor information that represents the extent of the instructions of the EBB fragment that are predicted to be executed as stored in the memory system includes a cache line count field and an instruction count field as shown in FIG. 4. The cache line count field indicates the number of cache lines of the memory system that store the sequence of sequential instructions of the EBB fragment. The instruction count field indicates the number of instructions of the EBB fragment that are found in the last cache line of the EBB fragment. The cache line count field of a given predictor can be used in conjunction with the address of the EBB fragment to control the prefetching and fetching operations of cache lines that include the instructions of the EBB fragment. The instruction count field of the predictor can be used to control the read-out of the sequence of instructions of the EBB fragment from the Instruction Buffer to the decode stage as well as the instruction shifting that isolates instructions of the EBB fragment for further decode processing; [0078], lines 10-15, when an EBB fragment is executed, it will require instructions from some number of cache lines before it exits (or is predicted to exit) and will not require subsequent cache lines containing instructions beyond this exit point (even if the EBB exits well before the predicted exit point); [0079], lines 6-18, more specifically, the address field of a given predictor is used to derive the memory address for the starting cache line of a corresponding EBB fragment. The Prefetcher uses the memory address for the starting cache line of the corresponding EBB fragment to fetch such starting cache line into cache (if not already in cache). The Prefetcher can then apply offsets to the base memory address of the starting cache line such that the Prefetcher fetches the additional cache lines of the corresponding EBB fragment into cache (if not already in cache), where the number of additional cache lines and corresponding offsets are dictated by the line count value of the given predictor; [0084], lines 1-17, there are several possible ways to convey the “exit is here” information. For example, the predictor entry can possibly contain a count of the number of instructions to decode between entry and exit of the EBB fragment. Or the predictor can possibly contain the address or offset of the exiting instruction. Or on a statically scheduled machine the predictor can possibly contain a count of the number of cycles spent in the EBB fragment. This might appear to be the same as the number of instructions executed in the EBB. The limitation with all of these indicators is that they are large, and space in the Exit Table is at a premium. However, the indicator can be compressed by noting that necessarily the exit will be from some instruction that ends in the last predicted line. Consequently, the exit can be takes as an instruction count from the point at which the final cache line of the respective EBB fragment enters decode, rather than from the start of the respective EBB fragment) based on querying the table ([0050], line 2, Exit Table) using the branch prediction ([0050], lines 1-3, the computer processor also includes Prediction Logic that employs an Exit Table whose entries store predictors) index ([0050], lines 4-6, each given Exit Table entry is associated with a key by which the given Exit Table entry may be accessed (looked up)); and cause the fetch circuitry to fetch a subset of the first set of instructions from a memory, wherein the subset is based on the predicted exit point ([0050], lines 6-8, the predictor corresponding to a given EBB fragment can include information that represents a predicted execution path that exits the given EBB fragment; [0050], lines 35-38, the predictor for each given Exit Table entry can also include information that represents the extent of the instructions of the corresponding EBB fragment that are predicted to be executed; [0056], lines 4-9, the predictor information that represents the extent of the sequential instructions of a given EBB fragment for the chain of predictors can be used to control the prefetching, fetching, instruction buffer read-out, and instruction-shifting operations for the instructions of the given EBB fragment; [0057], lines 1-19, in one embodiment, the predictor information that represents the extent of the instructions of the EBB fragment that are predicted to be executed as stored in the memory system includes a cache line count field and an instruction count field as shown in FIG. 4. The cache line count field indicates the number of cache lines of the memory system that store the sequence of sequential instructions of the EBB fragment. The instruction count field indicates the number of instructions of the EBB fragment that are found in the last cache line of the EBB fragment. The cache line count field of a given predictor can be used in conjunction with the address of the EBB fragment to control the prefetching and fetching operations of cache lines that include the instructions of the EBB fragment. The instruction count field of the predictor can be used to control the read-out of the sequence of instructions of the EBB fragment from the Instruction Buffer to the decode stage as well as the instruction shifting that isolates instructions of the EBB fragment for further decode processing; [0078], lines 10-15, when an EBB fragment is executed, it will require instructions from some number of cache lines before it exits (or is predicted to exit) and will not require subsequent cache lines containing instructions beyond this exit point (even if the EBB exits well before the predicted exit point); [0079], lines 6-18, more specifically, the address field of a given predictor is used to derive the memory address for the starting cache line of a corresponding EBB fragment. The Prefetcher uses the memory address for the starting cache line of the corresponding EBB fragment to fetch such starting cache line into cache (if not already in cache). The Prefetcher can then apply offsets to the base memory address of the starting cache line such that the Prefetcher fetches the additional cache lines of the corresponding EBB fragment into cache (if not already in cache), where the number of additional cache lines and corresponding offsets are dictated by the line count value of the given predictor; [0084], lines 1-17, there are several possible ways to convey the “exit is here” information. For example, the predictor entry can possibly contain a count of the number of instructions to decode between entry and exit of the EBB fragment. Or the predictor can possibly contain the address or offset of the exiting instruction. Or on a statically scheduled machine the predictor can possibly contain a count of the number of cycles spent in the EBB fragment. This might appear to be the same as the number of instructions executed in the EBB. The limitation with all of these indicators is that they are large, and space in the Exit Table is at a premium. However, the indicator can be compressed by noting that necessarily the exit will be from some instruction that ends in the last predicted line. Consequently, the exit can be takes as an instruction count from the point at which the final cache line of the respective EBB fragment enters decode, rather than from the start of the respective EBB fragment).
Consider claim 14, Godard discloses the circuit device of claim 11 (see above), wherein the branch prediction circuitry is configured to receive, from the table, a count of fetch packets associated with the predicted exit point and an offset of the predicted exit point within a fetch packet ([0050], lines 35-38, the predictor for each given Exit Table entry can also include information that represents the extent of the instructions of the corresponding EBB fragment that are predicted to be executed; [0056], lines 4-9, the predictor information that represents the extent of the sequential instructions of a given EBB fragment for the chain of predictors can be used to control the prefetching, fetching, instruction buffer read-out, and instruction-shifting operations for the instructions of the given EBB fragment; [0057], lines 1-19, in one embodiment, the predictor information that represents the extent of the instructions of the EBB fragment that are predicted to be executed as stored in the memory system includes a cache line count field and an instruction count field as shown in FIG. 4. The cache line count field indicates the number of cache lines of the memory system that store the sequence of sequential instructions of the EBB fragment. The instruction count field indicates the number of instructions of the EBB fragment that are found in the last cache line of the EBB fragment. The cache line count field of a given predictor can be used in conjunction with the address of the EBB fragment to control the prefetching and fetching operations of cache lines that include the instructions of the EBB fragment. The instruction count field of the predictor can be used to control the read-out of the sequence of instructions of the EBB fragment from the Instruction Buffer to the decode stage as well as the instruction shifting that isolates instructions of the EBB fragment for further decode processing; [0078], lines 10-15, when an EBB fragment is executed, it will require instructions from some number of cache lines before it exits (or is predicted to exit) and will not require subsequent cache lines containing instructions beyond this exit point (even if the EBB exits well before the predicted exit point); [0079], lines 6-18, more specifically, the address field of a given predictor is used to derive the memory address for the starting cache line of a corresponding EBB fragment. The Prefetcher uses the memory address for the starting cache line of the corresponding EBB fragment to fetch such starting cache line into cache (if not already in cache). The Prefetcher can then apply offsets to the base memory address of the starting cache line such that the Prefetcher fetches the additional cache lines of the corresponding EBB fragment into cache (if not already in cache), where the number of additional cache lines and corresponding offsets are dictated by the line count value of the given predictor; [0084], lines 1-17, there are several possible ways to convey the “exit is here” information. For example, the predictor entry can possibly contain a count of the number of instructions to decode between entry and exit of the EBB fragment. Or the predictor can possibly contain the address or offset of the exiting instruction. Or on a statically scheduled machine the predictor can possibly contain a count of the number of cycles spent in the EBB fragment. This might appear to be the same as the number of instructions executed in the EBB. The limitation with all of these indicators is that they are large, and space in the Exit Table is at a premium. However, the indicator can be compressed by noting that necessarily the exit will be from some instruction that ends in the last predicted line. Consequently, the exit can be takes as an instruction count from the point at which the final cache line of the respective EBB fragment enters decode, rather than from the start of the respective EBB fragment; [0050], lines 23-28, in this case, the address field of the Exit Table entry can be a logical offset of the entry address of the target EBB relative to a base address stored in a special purpose register of the computer processor or by an offset from the entry address of the exiting EBB corresponding to the predictor).
Consider claim 15, Godard discloses the circuit device of claim 11 (see above), wherein the branch prediction circuitry is configured to receive, from the table, an indication of a likelihood that a branch at the predicted exit point will be taken ([0095], lines 1-9, each predictor entry of the Exit Table can include information about the quality of the prediction defined by the predictor entry, such as an estimate of how likely the prediction is to be correct. An EBB that exits only by a single unconditional branch will have a prediction that is 100% accurate, while one that can and does exit from any of several conditional branches may have a prediction that is relatively unlikely to be correct, even if the prediction is the most likely of the alternatives).
Consider claim 16, Godard disclose the circuit device of claim 15 (see above), wherein the processor is configured to update the indication of likelihood based on whether the branch was taken ([0095], lines 9-16, moreover, program transfer behavior frequently changes during execution. For example, during one phase of execution, an EBB fragment may usually exit via a branch operation A, but in a later phase of execution, the same EBB fragment may usually exit via another branch operation B. Such variability makes it desirable for the prediction for the EBB fragment to change over time, so as to track the most likely exit based on the recent behavior; [0096], lines 1-25, thus, program execution of the EBB fragments can be used to update the quality information of the corresponding predictor entries as stored in the Exit Table and then modify the predictions defined by the predictor entries themselves when warranted by the quality information. Specifically, when a prediction defined by an Exit Table entry is successful, i.e., execution of the EBB fragment corresponding to the Exit Table entry did in fact exit at the predicted point and to the predicted target, the key for such EBB fragment can be used to access the Exit Table entry and raise the quality information of the predictor entry as appropriate. When a prediction defined by an Exit Table entry is not successful (a mispredict), i.e., execution of the EBB fragment corresponding to the Exit Table entry did not in fact exit at the predicted point and to the predicted target, the key for such EBB fragment can be used to access the Exit Table entry and lower the quality information of the predictor entry as appropriate. In the case of a mispredict, the execution behavior carries information that defines the prediction that would have been correct for that key. If the quality information for the Exit Table entry drops below a replacement threshold, the prediction defined by the Exit Table entry can be replaced by the corrected prediction carried by the execution behavior. This same replacement operation is performed in the event that the Exit Table does not have any entry corresponding to the key; [0098], lines 1-29, in one embodiment, the quality information of the prediction defined by the predictor entry can be represented by a one-bit or two-bit saturating counter that is part of each predictor entry. The counter can be updated based on the execution behavior of the corresponding EBB fragment. If the prediction defined by a predictor for a given EBB fragment is found to have been correct during execution of the given EBB fragment, i.e. the EBB fragment did in fact exit where it was expected to, the counter can be incremented (unless saturated at the maximum count value). However, if the prediction defined by a predictor for a given EBB fragment is found to have been incorrect during execution of the given EBB fragment, i.e. the EBB fragment did not in fact exit where it was expected to, the counter can be decremented. If the counter saturates down (i.e., its count was already at the minimum count value), then the predictor of the entry can be updated to predict what would have been the correct prediction and (in most variations) the counter is incremented again. The effect of the counter is that the predictor entry remains in the Exit Table if it is usually correct, but if is incorrect for more than a few consecutive predictions then it will be replaced. In one example, the quality information of the predictor can be defined by a single bit, indicating strong confidence and weak confidence in the prediction. This allows the predictor entry for a corresponding EBB fragment to miss (predict wrong) twice in a row before being replaced by an updated prediction. In other examples, the quality information of the predictor can be defined by multiple bits so as to provide finer divisions of confidence).
Consider claim 17, Godard discloses the circuit device of claim 11 (see above), wherein: the subset of the first set of instructions is a first subset; the first set of instructions includes a second subset between the first subset and a second set of instructions; and the branch prediction circuitry is configured to determine, based on the predicted exit point, whether to cause the fetch circuitry to fetch a subset of the second set of instructions from the memory after the first subset of the first set of instructions without fetching the second subset of the first set of instructions therebetween ([0046], lines 1-7, the computer processor of the present application executes sequences of instructions organized as blocks of instructions (or “instruction blocks”). The instruction blocks can be extended basic blocks or “EBBs.” Each given EBB is a sequence of instructions with a single entry point (the head of the EBB) and possibly one or several control transfer operations forming exit points as shown in FIG. 1; [0050], lines 18-23, the predictor for each given Exit Table entry can include an address field. For both branch-type and call-type predictor entries, the address field of the given Exit Table predictor entry represents the entry address of the target EBB (the EBB that is the target of the branch operation or the call operation); [0050], lines 32-35, the address field of the given Exit Table entry can be used to derive the key to look up and access the Exit Table entry corresponding to the target EBB fragment; [0065], lines 1-3, the key used to look up the initial EBB fragment of an EBB can correspond to the entry address of the EBB as described herein; [0078], lines 10-15, when an EBB fragment is executed, it will require instructions from some number of cache lines before it exits (or is predicted to exit) and will not require subsequent cache lines containing instructions beyond this exit point (even if the EBB exits well before the predicted exit point); [0079], lines 6-18, more specifically, the address field of a given predictor is used to derive the memory address for the starting cache line of a corresponding EBB fragment. The Prefetcher uses the memory address for the starting cache line of the corresponding EBB fragment to fetch such starting cache line into cache (if not already in cache). The Prefetcher can then apply offsets to the base memory address of the starting cache line such that the Prefetcher fetches the additional cache lines of the corresponding EBB fragment into cache (if not already in cache), where the number of additional cache lines and corresponding offsets are dictated by the line count value of the given predictor; [0084], lines 1-17, there are several possible ways to convey the “exit is here” information. For example, the predictor entry can possibly contain a count of the number of instructions to decode between entry and exit of the EBB fragment. Or the predictor can possibly contain the address or offset of the exiting instruction. Or on a statically scheduled machine the predictor can possibly contain a count of the number of cycles spent in the EBB fragment. This might appear to be the same as the number of instructions executed in the EBB. The limitation with all of these indicators is that they are large, and space in the Exit Table is at a premium. However, the indicator can be compressed by noting that necessarily the exit will be from some instruction that ends in the last predicted line. Consequently, the exit can be takes as an instruction count from the point at which the final cache line of the respective EBB fragment enters decode, rather than from the start of the respective EBB fragment; [0079], lines 18-22, note that the prefetch operations are carried out over an exact number of cache lines that are part of the EBB fragment. This is an exact prefetch as the exact number of needed cache lines will be loaded into cache if not already in cache; [0080], lines 11-13, the exact prefetch operations can avoid wasting cache space on cache lines that are loaded speculatively and not used as a result of the blind prefetch strategy).
Consider claim 18, Godard discloses the circuit device of claim 17 (see above), wherein the processor is configured to begin execution of the second set of instructions prior to determining whether a branch associated with the predicted exit point will be taken ([0054], line 5, follow-on execution; [0204], lines 1-7, in the event of a taken mispredict, the Decode Control Logic 155 has no corresponding predictor entry to work from and the chain of predictions that had been feeding it are useless. In this case, the Mispredict Recovery Logic 159 can be configured to discard the internal state of the Decode Stage 107 and unwind any instructions that have been issued down the wrong path; [0004], lines 1-5, modern computer processors (also known as central processing units or CPUs) employ branch prediction and a pipelined instruction fetch process so as to be able to feed a new decoded instruction (or several, depending on the architecture) into issue every cycle).
Consider claim 19, Godard discloses the control device of claim 11 (see above), wherein: the branch prediction index is a first branch prediction index; the branch history is a first branch history; and the processor is configured to: execute a branch instruction of the first set of instructions; and based on the branch instruction: determine a second branch prediction index based on the address associated with the first set of instructions and a second branch history; and store fetch information associated with the branch instruction in the table using the second branch prediction index ([0232], lines 6-9, the search key of the Exit Table can be modified to contain history information about the flow of control that led up to the keyed EBB or EBB fragment, and selects from among the stored predictor entries; [0051], lines 1-5, the Prediction Logic of the computer processor is configured to access the Exit Table (and possibly an Exit Cache associated therewith) to generate and store a chain of predictors that refer to consecutive EBB fragments of the program to be executed by the computer processor; [0056], lines 1-4, in generating the chain of the predictors, the address field of a predictor as part of an entry read-out from the Exit Table can be used to generate a key to look up and access the next predictor in the chain; [0095], lines 9-16, moreover, program transfer behavior frequently changes during execution. For example, during one phase of execution, an EBB fragment may usually exit via a branch operation A, but in a later phase of execution, the same EBB fragment may usually exit via another branch operation B. Such variability makes it desirable for the prediction for the EBB fragment to change over time, so as to track the most likely exit based on the recent behavior; [0096], lines 1-25, thus, program execution of the EBB fragments can be used to update the quality information of the corresponding predictor entries as stored in the Exit Table and then modify the predictions defined by the predictor entries themselves when warranted by the quality information. Specifically, when a prediction defined by an Exit Table entry is successful, i.e., execution of the EBB fragment corresponding to the Exit Table entry did in fact exit at the predicted point and to the predicted target, the key for such EBB fragment can be used to access the Exit Table entry and raise the quality information of the predictor entry as appropriate. When a prediction defined by an Exit Table entry is not successful (a mispredict), i.e., execution of the EBB fragment corresponding to the Exit Table entry did not in fact exit at the predicted point and to the predicted target, the key for such EBB fragment can be used to access the Exit Table entry and lower the quality information of the predictor entry as appropriate. In the case of a mispredict, the execution behavior carries information that defines the prediction that would have been correct for that key. If the quality information for the Exit Table entry drops below a replacement threshold, the prediction defined by the Exit Table entry can be replaced by the corrected prediction carried by the execution behavior. This same replacement operation is performed in the event that the Exit Table does not have any entry corresponding to the key; [0098], lines 1-29, in one embodiment, the quality information of the prediction defined by the predictor entry can be represented by a one-bit or two-bit saturating counter that is part of each predictor entry. The counter can be updated based on the execution behavior of the corresponding EBB fragment. If the prediction defined by a predictor for a given EBB fragment is found to have been correct during execution of the given EBB fragment, i.e. the EBB fragment did in fact exit where it was expected to, the counter can be incremented (unless saturated at the maximum count value). However, if the prediction defined by a predictor for a given EBB fragment is found to have been incorrect during execution of the given EBB fragment, i.e. the EBB fragment did not in fact exit where it was expected to, the counter can be decremented. If the counter saturates down (i.e., its count was already at the minimum count value), then the predictor of the entry can be updated to predict what would have been the correct prediction and (in most variations) the counter is incremented again. The effect of the counter is that the predictor entry remains in the Exit Table if it is usually correct, but if is incorrect for more than a few consecutive predictions then it will be replaced. In one example, the quality information of the predictor can be defined by a single bit, indicating strong confidence and weak confidence in the prediction. This allows the predictor entry for a corresponding EBB fragment to miss (predict wrong) twice in a row before being replaced by an updated prediction. In other examples, the quality information of the predictor can be defined by multiple bits so as to provide finer divisions of confidence).
Consider claim 20, Godard discloses the circuit device of claim 19 (see above), wherein the fetch information includes a count of fetch packets associated with the branch instruction and an offset of the branch instruction within a fetch packet ([0050], lines 35-38, the predictor for each given Exit Table entry can also include information that represents the extent of the instructions of the corresponding EBB fragment that are predicted to be executed; [0056], lines 4-9, the predictor information that represents the extent of the sequential instructions of a given EBB fragment for the chain of predictors can be used to control the prefetching, fetching, instruction buffer read-out, and instruction-shifting operations for the instructions of the given EBB fragment; [0057], lines 1-19, in one embodiment, the predictor information that represents the extent of the instructions of the EBB fragment that are predicted to be executed as stored in the memory system includes a cache line count field and an instruction count field as shown in FIG. 4. The cache line count field indicates the number of cache lines of the memory system that store the sequence of sequential instructions of the EBB fragment. The instruction count field indicates the number of instructions of the EBB fragment that are found in the last cache line of the EBB fragment. The cache line count field of a given predictor can be used in conjunction with the address of the EBB fragment to control the prefetching and fetching operations of cache lines that include the instructions of the EBB fragment. The instruction count field of the predictor can be used to control the read-out of the sequence of instructions of the EBB fragment from the Instruction Buffer to the decode stage as well as the instruction shifting that isolates instructions of the EBB fragment for further decode processing; [0078], lines 10-15, when an EBB fragment is executed, it will require instructions from some number of cache lines before it exits (or is predicted to exit) and will not require subsequent cache lines containing instructions beyond this exit point (even if the EBB exits well before the predicted exit point); [0079], lines 6-18, more specifically, the address field of a given predictor is used to derive the memory address for the starting cache line of a corresponding EBB fragment. The Prefetcher uses the memory address for the starting cache line of the corresponding EBB fragment to fetch such starting cache line into cache (if not already in cache). The Prefetcher can then apply offsets to the base memory address of the starting cache line such that the Prefetcher fetches the additional cache lines of the corresponding EBB fragment into cache (if not already in cache), where the number of additional cache lines and corresponding offsets are dictated by the line count value of the given predictor; [0084], lines 1-17, there are several possible ways to convey the “exit is here” information. For example, the predictor entry can possibly contain a count of the number of instructions to decode between entry and exit of the EBB fragment. Or the predictor can possibly contain the address or offset of the exiting instruction. Or on a statically scheduled machine the predictor can possibly contain a count of the number of cycles spent in the EBB fragment. This might appear to be the same as the number of instructions executed in the EBB. The limitation with all of these indicators is that they are large, and space in the Exit Table is at a premium. However, the indicator can be compressed by noting that necessarily the exit will be from some instruction that ends in the last predicted line. Consequently, the exit can be takes as an instruction count from the point at which the final cache line of the respective EBB fragment enters decode, rather than from the start of the respective EBB fragment; [0050], lines 23-28, in this case, the address field of the Exit Table entry can be a logical offset of the entry address of the target EBB relative to a base address stored in a special purpose register of the computer processor or by an offset from the entry address of the exiting EBB corresponding to the predictor).
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.
Claim(s) 3 and 13 is/are rejected under 35 U.S.C. 103 as being unpatentable over Godard as applied to claims 1 and 11 above, and further in view of Ranganathan (Control Flow Speculation for Distributed Architectures).
Consider claim 3, Godard discloses the method of claim 1 (see above), wherein the branch prediction index is based on the address and the branch history ([0232], lines 6-9, the search key of the Exit Table can be modified to contain history information about the flow of control that led up to the keyed EBB or EBB fragment, and selects from among the stored predictor entries; [0051], lines 1-5, the Prediction Logic of the computer processor is configured to access the Exit Table (and possibly an Exit Cache associated therewith) to generate and store a chain of predictors that refer to consecutive EBB fragments of the program to be executed by the computer processor; [0056], lines 1-4, in generating the chain of the predictors, the address field of a predictor as part of an entry read-out from the Exit Table can be used to generate a key to look up and access the next predictor in the chain).
However, Godard does not disclose that the branch prediction index is based on an exclusive-OR (XOR) function of the address and the branch history.
On the other hand, Ranganathan discloses a branch prediction index is based on an exclusive-OR (XOR) function of an address and a branch history (page 17, Figure 2.1).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to combine the teaching of Ranganathan with the invention of Godard to increase efficiency relative to determining an index based on an address and a branch history that does not entail a hash function. Alternatively, this modification merely entails combining prior art elements (the prior art elements of Godard as cited above, and Ranganathan’s explicit teaching of using an XOR function) according to known methods (Examiner submits that the use of an XOR function to perform a hash is well-known; Examiner also notes that Ranganathan’s invention is likewise directed to exit history-based prediction) to yield predictable results (the overall limitation of the branch prediction index being based on an exclusive-OR (XOR) function of the address and the branch history), which is an example of a rationale that may support a conclusion of obviousness as per MPEP 2143.
Consider claim 13, Godard discloses the circuit device of claim 11 (see above), wherein the branch prediction index is based on the address and the branch history ([0232], lines 6-9, the search key of the Exit Table can be modified to contain history information about the flow of control that led up to the keyed EBB or EBB fragment, and selects from among the stored predictor entries; [0051], lines 1-5, the Prediction Logic of the computer processor is configured to access the Exit Table (and possibly an Exit Cache associated therewith) to generate and store a chain of predictors that refer to consecutive EBB fragments of the program to be executed by the computer processor; [0056], lines 1-4, in generating the chain of the predictors, the address field of a predictor as part of an entry read-out from the Exit Table can be used to generate a key to look up and access the next predictor in the chain).
However, Godard does not disclose that the branch prediction index is based on an exclusive-OR (XOR) function of the address and the branch history.
On the other hand, Ranganathan discloses a branch prediction index is based on an exclusive-OR (XOR) function of an address and a branch history (page 17, Figure 2.1).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to combine the teaching of Ranganathan with the invention of Godard to increase efficiency relative to determining an index based on an address and a branch history that does not entail a hash function. Alternatively, this modification merely entails combining prior art elements (the prior art elements of Godard as cited above, and Ranganathan’s explicit teaching of using an XOR function) according to known methods (Examiner submits that the use of an XOR function to perform a hash is well-known; Examiner also notes that Ranganathan’s invention is likewise directed to exit history-based prediction) to yield predictable results (the overall limitation of the branch prediction index being based on an exclusive-OR (XOR) function of the address and the branch history), which is an example of a rationale that may support a conclusion of obviousness as per MPEP 2143.
Response to Arguments
Applicant on page 8 argues: “Applicant has amended the specification in accordance with the Examiner's suggestions. In view of this amendment, Applicant respectfully requests that the Examiner withdraw the objection to the specification.”
In view of the aforementioned amendments, the associated previously presented objections to the specification are withdrawn.
Applicant on page 8 argues: “Without commenting on the merits of the double patenting rejection based on the '646 and '917 patents, Applicant may be amenable to filing a terminal disclaimer, if necessary, when the present claims are indicated as allowable. It is respectfully noted that claim amendments made during the course of prosecution may obviate the double patenting rejection, and the Applicant respectfully requests that the double patenting rejection be held in abeyance until the claims are indicated as otherwise allowable.”
In view of the instant amendments to the independent claims, the previously presented double patenting rejections are withdrawn.
Applicant on page 9 argues: ‘Regarding claim 1, Applicant has amended the phrase "the first set of instruction" in lines 3-4 to "the first set of instructions," which has antecedent basis to "a first set of instructions" in line 2. This addresses the antecedent basis issue for claim 1 and its dependent claims 2-10.’
In view of the aforementioned amendment, the associated previously presented indefinite rejection is withdrawn.
Applicant on page 9 argues: ‘Regarding claims 7 and 18, Applicant has amended the phrase "the predicated exit point" to "the predicted exit point." This addresses antecedent basis issue for claims 7 and 18.’
In view of the aforementioned amendments, the associated previously presented indefinite rejections are withdrawn.
Applicant on page 9 argues: ‘Regarding claim 9, Applicant has amended the phrase "determining a second branch prediction index based on the address of the sequentially first instruction of the first set of instructions and a second branch history" to "determining a second branch prediction index based on the address associated with the sequentially first instruction of the first set of instructions and a second branch history." This updated language has antecedent basis to claim 1.’
In view of the aforementioned amendment, the associated previously presented indefinite rejection is withdrawn.
Applicant on page 10: ‘Claim 11 is amended in a similar manner. Thus, the amended claims 1 and 11, which incorporate features previously recited by claims 2 and 12, respectively, recite that the branch prediction index is determined based on both the entry address and fields of a branch history, wherein the fields indicate a distance (referred to hereinafter as "distance fields") between a sequentially first instruction of a respective previously executed set of instructions and a respective previously-taken branch instruction of the respective previously executed set of instructions.’
However, Examiner notes that the aforementioned claims do not recite that the branch prediction index is determined based on “both” the entry address and fields of a branch history. As such, the aforementioned claims can be broadly interpreted to necessitate determining a) a branch prediction index based on the address, and b) fields of a branch history.
Applicant on page 10 argues: ‘With respect to Godard, the Exit Table index is described as being determined based on the entry address of the EBB alone. For instance, Godard explicitly states "the key used to look up the initial EBB fragment of an EBB can correspond to the entry address of the EBB." Godard, [0065]. Godard's cache-line count and instruction count fields, disclosed in [0057] and which the Examiner maps to the claimed distance fields, play no role in generating that index. They are retrieved as outputs after the Exit Table index lookup is complete. In other words, they are what the query returns, not what drives the query.’
Examiner first generally notes that Godard teaches an embodiment wherein the Exit Table index is not just based on the entry address of the EBB but also on a further factor ([0232], lines 6-9, the search key of the Exit Table can be modified to contain history information about the flow of control that led up to the keyed EBB or EBB fragment, and selects from among the stored predictor entries; [0051], lines 1-5, the Prediction Logic of the computer processor is configured to access the Exit Table (and possibly an Exit Cache associated therewith) to generate and store a chain of predictors that refer to consecutive EBB fragments of the program to be executed by the computer processor; [0056], lines 1-4, in generating the chain of the predictors, the address field of a predictor as part of an entry read-out from the Exit Table can be used to generate a key to look up and access the next predictor in the chain).
Nevertheless, with respect to the claimed language, Examiner notes that while it may be the case that “Godard's cache-line count and instruction count fields, disclosed in [0057] and which the Examiner maps to the claimed distance fields, play no role in generating that index. They are retrieved as outputs after the Exit Table index lookup is complete. In other words, they are what the query returns, not what drives the query”, the aforementioned claims do not necessitate that the distance fields play a role in generating the index. As noted above, the aforementioned claims do not recite that the branch prediction index is determined based on “both” the entry address and fields of a branch history. As such, the aforementioned claims can be broadly interpreted to necessitate determining a) a branch prediction index based on the address, and b) fields of a branch history.
Applicant on page 10 argues: “It is further noted that the Examiner's mapping on this point is internally inconsistent. The Examiner maps Godard's Exit Table index to the claimed branch prediction index, meaning the inputs to Godard's Exit Table index are the relevant inputs for comparison/lookup. Yet the Examiner simultaneously maps the claimed distance fields to Godard's cache-line count and instruction count, which are fields that are retrieved as outputs of that same Exit Table lookup, not inputs to it. A value cannot be both an output of a table lookup and an input that generates it.”
However, as noted above, the aforementioned claims do not necessitate that the distance fields are an input that generates the table lookup.
Applicant on page 11 argues: ‘By contrast, claims 1 and 11 recite the opposite. That is, the distance fields and the entry address are inputs used to determine the branch prediction index. The "distance fields" of Godard (e.g., alleged as the cache-line count and instruction count fields) are not inputs used to determine a branch prediction index (e.g., the alleged Exit Table index). Furthermore, even if Godard's fields could be characterized as inputs (which they cannot), they would still not qualify as the claimed distance fields as Godard expressly states that its instruction count is measured "from the point at which the final cache line of the respective EBB fragment enters decode, rather than from the start of the respective EBB fragment." Godard, [0084]. The amended claims 1 and 11 recite that the distance is measured from the sequentially first instruction of the previously-executed set. Thus, Godard's own disclosure confirms its distance fields, which are an output rather than an input, measure from a different reference point entirely.’
However, as noted above, the aforementioned claims do not necessitate that both the distance fields and the entry address are inputs used to determine the branch prediction index. Examiner further generally notes that Godard discloses multiple [overall] fields (an overall field per entry), each overall field including a cache-line count field and an instruction count field; therefore, each overall field (which includes not only the argued instruction count field but also the recited cache-line count field) “represents” the recited distance. Examiner also notes that the claims do not recite “measure” language.
Applicant on page “In summary, Godard does not teach or suggest determining a branch prediction index based on an address and fields of a branch history, wherein each field represents a distance between a sequentially first instruction of a respective previously executed set of instructions and a respective previously-taken branch instruction of the respective previously executed set of instructions. Accordingly, Applicant respectfully requests withdrawal of the Section 102 rejection of independent claims 1 and 11, and of claims 4-10 and 14-20 depending therefrom.”
However, as noted above, the aforementioned claims do not recite that the branch prediction index is determined based on “both” the entry address and fields of a branch history. As such, the aforementioned claims can be broadly interpreted to necessitate determining a) a branch prediction index based on the address, and b) fields of a branch history.
Applicant on page 11 argues: “Claims 3 and 13 depend from claims 1 and 11, respectively. Ranganathan does not obviate the deficiencies of Godard as applied to claims 1 and 11. Hence, claims 3 and 13 are allowable at least by virtue of their dependency from claims 1 and 11. Applicant respectfully requests withdrawal of the Section 103 rejection of claims 3 and 13.”
Examiner’s response to arguments above with respect to claims 1 and 11 are likewise applicable to the arguments directed to claims 3 and 13 above.
Conclusion
THIS ACTION IS MADE FINAL. 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 KEITH E VICARY whose telephone number is (571)270-1314. The examiner can normally be reached Monday to Friday, 9:00 AM to 5:00 PM.
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, 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.
/KEITH E VICARY/Primary Examiner, Art Unit 2183
Prosecution Insights