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-21 are pending in this office action and presented for examination.
Examiner appreciates the two-column flow chart format of FIG. 5 and 6, as the addition of the right column significantly facilitates understanding of the invention.
Specification
The disclosure is objected to because of the following informalities. Appropriate correction is required.
In paragraph [0019], line 7, “48-bits” should be “48 bits”. (Also see the immediately following objection.)
Paragraph [0019], lines 4-7, discloses “Given a 32-Byte fetch group comprising 16 2-Byte branching instructions (and thereby 16 potential exit points) and a branch predictor circuit that requires a count of up to 16 for branch predictions, the resulting predictor entry must be 48-bits.” However, it is unclear as to whether “48-bits” should instead be “64 bits”.
In paragraph [0020], “database” should be “a database”.
Paragraph [0020] discloses “For example, if there were 16 instructions in a fetch group, the offset could be a 3-bit entry that could encode a value capable of identifying each instruction in the fetch group.” However, it is unclear as to how 3 bits can identify 16 instructions.
In paragraph [0024], line 18, “48-bits” should be “48 bits”.
Paragraph [0026], lines 4-5, discloses “However, the prediction entry associated with each fetch group may instead be an 18-bit data structure with a 6-bit counter and a 3-bit offset.” However, FIG. 2 appears to show a 9-bit data structure.
In paragraph [0026], line 12, it is unclear as to whether “00011” should instead be 6 bits rather than 5 bits, in view of the context of the paragraph.
In paragraph [0032], line 5, “lead” may have been intended to be “led”.
In paragraph [0035], line 4, “prefect” should be “prefetch”.
In paragraph [0035], line 6, the comma following “211” should be deleted for grammatical clarity.
Paragraph [0036], lines 2-3, discloses “For example, the offset may be an n-bit data value that is used to represent n2 different instructions in a fetch group”. However, this statement does not appear to be accurate. For example, a 3-bit data value does not appear to be able to be used to represent 9 different instructions.
In paragraph [0036], line 5, “16 instruction” should be “16-instruction”.
In paragraph [0040], last line, “9-bits” should be “9 bits”.
Drawings
The drawings are objected to because:
The drawing sheet numbering must be clear and larger than the numbers used as reference characters to avoid confusion.
Regarding FIG. 1, FIG. 2, FIG. 3, FIG. 4, FIG. 5, and FIG. 6, numbers, letters, and reference characters must measure at least .32 cm. (1/8 inch) in height.
In FIG. 1, “Inst_7_Cound” should be “Inst_7_Count”.
In FIG. 3, top half, “Inst_7_Cound” should be “Inst_7_Count”.
In FIG. 3, bottom half, “Inst_7_Cound” should be “Inst_7_Count”.
MPEP 608.02, section V, states that “[l]ead lines are required for each reference character except for those which indicate the surface or cross section on which they are placed. Such a reference character must be underlined to make it clear that a lead line has not been left out by mistake." However, Figure 4 contains reference characters (400, 401) that are neither underlined nor associated with lead lines.
Corrected drawing sheets in compliance with 37 CFR 1.121(d) are required in reply to the Office action to avoid abandonment of the application. Any amended replacement drawing sheet should include all of the figures appearing on the immediate prior version of the sheet, even if only one figure is being amended. The figure or figure number of an amended drawing should not be labeled as “amended.” If a drawing figure is to be canceled, the appropriate figure must be removed from the replacement sheet, and where necessary, the remaining figures must be renumbered and appropriate changes made to the brief description of the several views of the drawings for consistency. Additional replacement sheets may be necessary to show the renumbering of the remaining figures. Each drawing sheet submitted after the filing date of an application must be labeled in the top margin as either “Replacement Sheet” or “New Sheet” pursuant to 37 CFR 1.121(d). If the changes are not accepted by the examiner, the applicant will be notified and informed of any required corrective action in the next Office action. The objection to the drawings will not be held in abeyance.
Claim Rejections - 35 USC § 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-6, 9, 11-16, and 19 is/are rejected under 35 U.S.C. 102(a)(1) as being anticipated by Hoogerbrugge (US 20010020265 A1).
Consider claim 1, Hoogerbrugge discloses a method, in which each step is conducted by a branch prediction circuit ([0018], line 8, branch prediction unit) and an instruction fetch circuit ([0006], line 9, a bundle must be fetched; [0020], line 3, multiplexer 164) operating in combination in a computer processor ([0018], line 2, processor 10) that is executing a program ([0021], line 2, program of instructions), comprising: fetching a group of instructions ([0006], line 9, a bundle must be fetched; [0021], lines 3-4, number of commands; [0021], line 2, VLIW), in a fetch group ([0006], line 9, a bundle must be fetched; [0021], lines 3-4, number of commands; [0021], line 2, VLIW), from an instruction memory ([0018], line 5, instruction memory); associating a counter ([0012], lines 11-16, a saturating count of a number of executions of the branch command in which the branch is taken at that position. The state represents such a count only for the expected command, that is, only when there is a state transition to a different expected command a count for another command will start to become represented; [0013], lines 1-12, for example, the state for an instruction may represent that taking a branch as a result of a command at a certain position is expected. The state also represents a count of either 1 or 2 executions of that command where a branch is taken. If the branch is not taken when the instruction is executed and the state represents a count of 2, a transition will be made to a state where the command is still the expected command, but the count will go from 2 to 1. If the branch is not taken and the count is 1, a transition will be made to a state that represents that another branch command, if any, is the expectedly taken branch with a count of 1 for that other command; [0041], lines 5-6, one bit to represent whether there is a strong or a weak preference; [0041], line 9, more bits for the strength of the prediction; [0039], lines 1-12, if the branch history memory 160 stores information identifying a state that represents a strong preference for an outcome of the source instruction and that outcome occurs as a result of execution, the state remains unaffected. If a different outcome occurs and the state has a strong preference, a transition is made to the state with a weak preference for the same outcome as the original state with a strong preference. If the state represents a weak preference for an outcome of the source instruction and that outcome occurs as a result of execution, a transition occurs to the state with a strong preference for the same outcome as the original state with a weak preference; [0040], lines 6-7, information similar to the saturating count is represented only for the preferred outcome; alternatively, [0018], line 2, program counter) and an offset ([0041], lines 6-7, two bits to represent for which of the four possible outcomes there is a preference; [0038], lines 1-4, the diagram shows states for prediction of a "no-branch" outcome and for a taken outcome of a branch command from a first, second or third position in the source instruction respectively) with the fetch group ([0035], lines 4-6, branch history memory is an associative memory (e.g. fully associative, set associative or direct mapped), that can be accessed using the address of the source instruction; [0006], line 9, a bundle must be fetched; [0021], lines 3-4, number of commands; [0021], line 2, VLIW); predicting, using the counter and the offset, that a branching instruction in the fetch group will be used to branch the program ([0025], lines 4-12, the branch history information represents statistical information about the frequency with which the one or more branch commands from the instruction have led to a change in the program counter 12 before. Selection unit 161 uses this information to generate a decision whether a taken branch should be predicted and which of the branch commands in the instruction is the taken branch whose target address will affect the program counter 12); and prefetching at least one instruction indicated by the branching instruction ([0024], lines 1-6, the branch prediction unit 16 caters for this problem by predicting which instructions should be executed after an instruction that contains one or more branch commands, before the processor 10 has actually been able to instruct the program counter 12 about the result of the branch commands).
Consider claim 2, Hoogerbrugge discloses the method of claim 1 (see above), wherein: the offset comprises sufficient bits to represent each instruction in the fetch group ([0041], lines 6-7, two bits to represent for which of the four possible outcomes there is a preference; [0038], lines 1-4, the diagram shows states for prediction of a "no-branch" outcome and for a taken outcome of a branch command from a first, second or third position in the source instruction respectively); and the branching instruction is associated with a value of the offset ([0041], lines 6-7, two bits to represent for which of the four possible outcomes there is a preference; [0038], lines 1-4, the diagram shows states for prediction of a "no-branch" outcome and for a taken outcome of a branch command from a first, second or third position in the source instruction respectively).
Consider claim 3, Hoogerbrugge discloses the method of claim 1 (see above), further comprising: receiving an indication that the program was branched by the branching instruction; and incrementing the counter in response to the indication ([0012], lines 11-13, a saturating count of a number of executions of the branch command in which the branch is taken at that position; [0039], lines 8-12, if the state represents a weak preference for an outcome of the source instruction and that outcome occurs as a result of execution, a transition occurs to the state with a strong preference for the same outcome as the original state with a weak preference).
Consider claim 4, Hoogerbrugge discloses the method of claim 1 (see above), further comprising: receiving an indication that the program was branched by a different branching instruction in the fetch group; and lowering the counter in response to the indication ([0013], lines 5-8, if the branch is not taken when the instruction is executed and the state represents a count of 2, a transition will be made to a state where the command is still the expected command, but the count will go from 2 to 1; [0039], lines 5-8, if a different outcome occurs and the state has a strong preference, a transition is made to the state with a weak preference for the same outcome as the original state with a strong preference).
Consider claim 5, Hoogerbrugge discloses the method of claim 1 (see above), further comprising: receiving an indication that the program was branched by a different branching instruction in the fetch group ([0013], lines 5-8, if the branch is not taken when the instruction is executed and the state represents a count of 2, a transition will be made to a state where the command is still the expected command, but the count will go from 2 to 1; [0039], lines 5-8, if a different outcome occurs and the state has a strong preference, a transition is made to the state with a weak preference for the same outcome as the original state with a strong preference); modifying a hysteresis counter in response to the indication ([0013], lines 5-8, if the branch is not taken when the instruction is executed and the state represents a count of 2, a transition will be made to a state where the command is still the expected command, but the count will go from 2 to 1; [0039], lines 5-8, if a different outcome occurs and the state has a strong preference, a transition is made to the state with a weak preference for the same outcome as the original state with a strong preference); and comparing the hysteresis counter with a threshold ([0013], lines 8-12, if the branch is not taken and the count is 1, a transition will be made to a state that represents that another branch command, if any, is the expectedly taken branch with a count of 1 for that other command).
Consider claim 6, Hoogerbrugge discloses the method of claim 1 (see above), wherein: the fetch group has a number of instructions that is at least 4 ([0002], lines 1-3, VLIW processors have instructions that are made up of at least two commands for simultaneous execution by the processor); the counter and the offset form a branch predictor entry for the fetch group ([0035], lines 1-3, branch history memory 160 stores information about a state that represents statistical information about previous executions of the source instruction; [0035], lines 4-6, branch history memory is an associative memory (e.g. fully associative, set associative or direct mapped), that can be accessed using the address of the source instruction; [0006], line 9, a bundle must be fetched; [0021], lines 3-4, number of commands; [0021], line 2, VLIW); the offset is less than or equal to a number of bits required to represent the number of instructions ([0041], lines 6-7, two bits to represent for which of the four possible outcomes there is a preference; [0038], lines 1-4, the diagram shows states for prediction of a "no-branch" outcome and for a taken outcome of a branch command from a first, second or third position in the source instruction respectively; [0002], lines 1-3, VLIW processors have instructions that are made up of at least two commands for simultaneous execution by the processor); and the branch predictor entry is less than or equal to 9 bits ([0041], lines 3-11, in the example of FIG. 3, 3-bit labels may be used. One way of assigning these labels is to use one bit to represent whether there is a strong or a weak preference and two bits to represent for which of the four possible outcomes there is a preference. Of course, with other state diagrams other assignments may be used, using more bits for the strength of the preference and an appropriate number of bits to distinguish the preferred outcome; [0002], lines 1-3, VLIW processors have instructions that are made up of at least two commands for simultaneous execution by the processor).
Consider claim 9, Hoogerbrugge discloses the method of claim 1 (see above), wherein: the fetch group has a number of instructions that is at least 16 ([0002], lines 1-3, VLIW processors have instructions that are made up of at least two commands for simultaneous execution by the processor); the counter and the offset form a branch predictor entry for the fetch group ([0035], lines 1-3, branch history memory 160 stores information about a state that represents statistical information about previous executions of the source instruction; [0035], lines 4-6, branch history memory is an associative memory (e.g. fully associative, set associative or direct mapped), that can be accessed using the address of the source instruction; [0006], line 9, a bundle must be fetched; [0021], lines 3-4, number of commands; [0021], line 2, VLIW); the offset is less than or equal to a number of bits needed to represent the number of instructions ([0041], lines 6-7, two bits to represent for which of the four possible outcomes there is a preference; [0038], lines 1-4, the diagram shows states for prediction of a "no-branch" outcome and for a taken outcome of a branch command from a first, second or third position in the source instruction respectively; [0002], lines 1-3, VLIW processors have instructions that are made up of at least two commands for simultaneous execution by the processor); and the branch predictor entry is less than or equal to 9 bits ([0041], lines 3-11, in the example of FIG. 3, 3-bit labels may be used. One way of assigning these labels is to use one bit to represent whether there is a strong or a weak preference and two bits to represent for which of the four possible outcomes there is a preference. Of course, with other state diagrams other assignments may be used, using more bits for the strength of the preference and an appropriate number of bits to distinguish the preferred outcome; [0002], lines 1-3, VLIW processors have instructions that are made up of at least two commands for simultaneous execution by the processor).
Consider claim 11, Hoogerbrugge discloses the method of claim 1 (see above), further comprising: associating a second counter ([0012], lines 11-16, a saturating count of a number of executions of the branch command in which the branch is taken at that position. The state represents such a count only for the expected command, that is, only when there is a state transition to a different expected command a count for another command will start to become represented; [0013], lines 1-12, for example, the state for an instruction may represent that taking a branch as a result of a command at a certain position is expected. The state also represents a count of either 1 or 2 executions of that command where a branch is taken. If the branch is not taken when the instruction is executed and the state represents a count of 2, a transition will be made to a state where the command is still the expected command, but the count will go from 2 to 1. If the branch is not taken and the count is 1, a transition will be made to a state that represents that another branch command, if any, is the expectedly taken branch with a count of 1 for that other command; [0041], lines 5-6, one bit to represent whether there is a strong or a weak preference; [0041], line 9, more bits for the strength of the prediction; [0039], lines 1-12, if the branch history memory 160 stores information identifying a state that represents a strong preference for an outcome of the source instruction and that outcome occurs as a result of execution, the state remains unaffected. If a different outcome occurs and the state has a strong preference, a transition is made to the state with a weak preference for the same outcome as the original state with a strong preference. If the state represents a weak preference for an outcome of the source instruction and that outcome occurs as a result of execution, a transition occurs to the state with a strong preference for the same outcome as the original state with a weak preference; [0040], lines 6-7, information similar to the saturating count is represented only for the preferred outcome) and a second offset with a different branching instruction ([0041], lines 6-7, two bits to represent for which of the four possible outcomes there is a preference; [0038], lines 1-4, the diagram shows states for prediction of a "no-branch" outcome and for a taken outcome of a branch command from a first, second or third position in the source instruction respectively) in the fetch group ([0035], lines 4-6, branch history memory is an associative memory (e.g. fully associative, set associative or direct mapped), that can be accessed using the address of the source instruction; [0006], line 9, a bundle must be fetched; [0021], lines 3-4, number of commands; [0021], line 2, VLIW); receiving an indication that the program was branched by the different branching instruction in the fetch group; and incrementing the second counter in response to the indication ([0012], lines 11-13, a saturating count of a number of executions of the branch command in which the branch is taken at that position; [0039], lines 8-12, if the state represents a weak preference for an outcome of the source instruction and that outcome occurs as a result of execution, a transition occurs to the state with a strong preference for the same outcome as the original state with a weak preference).
Consider claim 12, Hoogerbrugge discloses a processor ([0018], line 2, processor 10) comprising: a branch prediction circuit ([0018], line 8, branch prediction unit); an instruction fetch circuit ([0006], line 9, a bundle must be fetched; [0020], line 3, multiplexer 164), wherein the instruction fetch circuit fetches a group of instructions ([0006], line 9, a bundle must be fetched; [0021], lines 3-4, number of commands; [0021], line 2, VLIW), in a fetch group ([0006], line 9, a bundle must be fetched; [0021], lines 3-4, number of commands; [0021], line 2, VLIW), from an instruction memory ([0018], line 5, instruction memory), from an instruction memory ([0018], line 5, instruction memory); and a counter ([0012], lines 11-16, a saturating count of a number of executions of the branch command in which the branch is taken at that position. The state represents such a count only for the expected command, that is, only when there is a state transition to a different expected command a count for another command will start to become represented; [0013], lines 1-12, for example, the state for an instruction may represent that taking a branch as a result of a command at a certain position is expected. The state also represents a count of either 1 or 2 executions of that command where a branch is taken. If the branch is not taken when the instruction is executed and the state represents a count of 2, a transition will be made to a state where the command is still the expected command, but the count will go from 2 to 1. If the branch is not taken and the count is 1, a transition will be made to a state that represents that another branch command, if any, is the expectedly taken branch with a count of 1 for that other command; [0041], lines 5-6, one bit to represent whether there is a strong or a weak preference; [0041], line 9, more bits for the strength of the prediction; [0039], lines 1-12, if the branch history memory 160 stores information identifying a state that represents a strong preference for an outcome of the source instruction and that outcome occurs as a result of execution, the state remains unaffected. If a different outcome occurs and the state has a strong preference, a transition is made to the state with a weak preference for the same outcome as the original state with a strong preference. If the state represents a weak preference for an outcome of the source instruction and that outcome occurs as a result of execution, a transition occurs to the state with a strong preference for the same outcome as the original state with a weak preference; [0040], lines 6-7, information similar to the saturating count is represented only for the preferred outcome; alternatively, [0018], line 2, program counter) and an offset ([0041], lines 6-7, two bits to represent for which of the four possible outcomes there is a preference; [0038], lines 1-4, the diagram shows states for prediction of a "no-branch" outcome and for a taken outcome of a branch command from a first, second or third position in the source instruction respectively) associated with the fetch group ([0035], lines 4-6, branch history memory is an associative memory (e.g. fully associative, set associative or direct mapped), that can be accessed using the address of the source instruction; [0006], line 9, a bundle must be fetched; [0021], lines 3-4, number of commands; [0021], line 2, VLIW), wherein the counter and the offset are used to predict that a branching instruction in the fetch group will be used to branch a program ([0025], lines 4-12, the branch history information represents statistical information about the frequency with which the one or more branch commands from the instruction have led to a change in the program counter 12 before. Selection unit 161 uses this information to generate a decision whether a taken branch should be predicted and which of the branch commands in the instruction is the taken branch whose target address will affect the program counter 12), and at least one instruction indicated by the branching instruction is prefetched ([0024], lines 1-6, the branch prediction unit 16 caters for this problem by predicting which instructions should be executed after an instruction that contains one or more branch commands, before the processor 10 has actually been able to instruct the program counter 12 about the result of the branch commands).
Consider claim 13, Hoogerbrugge discloses the processor of claim 12 (see above), wherein: the offset comprises sufficient bits to represent each instruction in the fetch group ([0041], lines 6-7, two bits to represent for which of the four possible outcomes there is a preference; [0038], lines 1-4, the diagram shows states for prediction of a "no-branch" outcome and for a taken outcome of a branch command from a first, second or third position in the source instruction respectively); and the branching instruction is associated with a value of the offset ([0041], lines 6-7, two bits to represent for which of the four possible outcomes there is a preference; [0038], lines 1-4, the diagram shows states for prediction of a "no-branch" outcome and for a taken outcome of a branch command from a first, second or third position in the source instruction respectively).
Consider claim 14, Hoogerbrugge discloses the processor of claim 12 (see above), wherein: the counter is incremented in response to an indication that the program was branched by the branching instruction ([0012], lines 11-13, a saturating count of a number of executions of the branch command in which the branch is taken at that position; [0039], lines 8-12, if the state represents a weak preference for an outcome of the source instruction and that outcome occurs as a result of execution, a transition occurs to the state with a strong preference for the same outcome as the original state with a weak preference).
Consider claim 15, Hoogerbrugge discloses the processor of claim 12 (see above), wherein: the processor receives an indication that the program was branched by a different branching instruction in the fetch group; the counter is lowered in response to the indication ([0013], lines 5-8, if the branch is not taken when the instruction is executed and the state represents a count of 2, a transition will be made to a state where the command is still the expected command, but the count will go from 2 to 1; [0039], lines 5-8, if a different outcome occurs and the state has a strong preference, a transition is made to the state with a weak preference for the same outcome as the original state with a strong preference); and the offset is set to a second value associated with the different branching instruction ([0013], lines 8-12, if the branch is not taken and the count is 1, a transition will be made to a state that represents that another branch command, if any, is the expectedly taken branch with a count of 1 for that other command).
Consider claim 16, Hoogerbrugge discloses the processor of claim 12 (see above), wherein: the fetch group has a number of instructions that is at least 16 ([0002], lines 1-3, VLIW processors have instructions that are made up of at least two commands for simultaneous execution by the processor); the counter and the offset form a branch predictor entry for the fetch group ([0035], lines 1-3, branch history memory 160 stores information about a state that represents statistical information about previous executions of the source instruction; [0035], lines 4-6, branch history memory is an associative memory (e.g. fully associative, set associative or direct mapped), that can be accessed using the address of the source instruction; [0006], line 9, a bundle must be fetched; [0021], lines 3-4, number of commands; [0021], line 2, VLIW); the offset is less than or equal to a number of bits required to represent the number of instructions ([0041], lines 6-7, two bits to represent for which of the four possible outcomes there is a preference; [0038], lines 1-4, the diagram shows states for prediction of a "no-branch" outcome and for a taken outcome of a branch command from a first, second or third position in the source instruction respectively; [0002], lines 1-3, VLIW processors have instructions that are made up of at least two commands for simultaneous execution by the processor); and the branch predictor entry is less than or equal to 9 bits ([0041], lines 3-11, in the example of FIG. 3, 3-bit labels may be used. One way of assigning these labels is to use one bit to represent whether there is a strong or a weak preference and two bits to represent for which of the four possible outcomes there is a preference. Of course, with other state diagrams other assignments may be used, using more bits for the strength of the preference and an appropriate number of bits to distinguish the preferred outcome; [0002], lines 1-3, VLIW processors have instructions that are made up of at least two commands for simultaneous execution by the processor).
Consider claim 19, Hoogerbrugge discloses the processor of claim 12 (see above), wherein: the fetch group has a number of instructions that is at least 16 ([0002], lines 1-3, VLIW processors have instructions that are made up of at least two commands for simultaneous execution by the processor); the counter and the offset form a branch predictor entry for the fetch group ([0035], lines 1-3, branch history memory 160 stores information about a state that represents statistical information about previous executions of the source instruction; [0035], lines 4-6, branch history memory is an associative memory (e.g. fully associative, set associative or direct mapped), that can be accessed using the address of the source instruction; [0006], line 9, a bundle must be fetched; [0021], lines 3-4, number of commands; [0021], line 2, VLIW); the offset is less than or equal to a number of bits needed to represent the number of instructions ([0041], lines 6-7, two bits to represent for which of the four possible outcomes there is a preference; [0038], lines 1-4, the diagram shows states for prediction of a "no-branch" outcome and for a taken outcome of a branch command from a first, second or third position in the source instruction respectively; [0002], lines 1-3, VLIW processors have instructions that are made up of at least two commands for simultaneous execution by the processor); and the branch predictor entry is less than or equal to 9 bits ([0041], lines 3-11, in the example of FIG. 3, 3-bit labels may be used. One way of assigning these labels is to use one bit to represent whether there is a strong or a weak preference and two bits to represent for which of the four possible outcomes there is a preference. Of course, with other state diagrams other assignments may be used, using more bits for the strength of the preference and an appropriate number of bits to distinguish the preferred outcome; [0002], lines 1-3, VLIW processors have instructions that are made up of at least two commands for simultaneous execution by the processor).
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) 7, 10, 17, and 20-21 is/are rejected under 35 U.S.C. 103 as being unpatentable over Hoogerbrugge (in the case of claims 7, 10, and 17, as applied to claims 1 and 12 above), and further in view of Navada (US 20170322810 A1)
Consider claim 7, Hoogerbrugge discloses the method of claim 1 (see above), wherein: the counter and the offset form a branch predictor entry for the fetch group in a table of the branch prediction circuit ([0035], lines 1-3, branch history memory 160 stores information about a state that represents statistical information about previous executions of the source instruction; [0035], lines 4-6, branch history memory is an associative memory (e.g. fully associative, set associative or direct mapped), that can be accessed using the address of the source instruction; [0006], line 9, a bundle must be fetched; [0021], lines 3-4, number of commands; [0021], line 2, VLIW).
However, Hoogerbrugge does not disclose that the branch predictor entry is in a tagged geometric history length table of the branch prediction circuit.
On the other hand, Navada discloses a branch predictor entry is in a tagged geometric history length table of a branch prediction circuit ([0005], lines 4-7, TAGE predictors are gaining popularity for their ability to make predictions of increased accuracy by taking into account contexts and history associated with branch instructions).
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 Navada with the invention of Hoogerbrugge in order to increase prediction accuracy.
Consider claim 10, Hoogerbrugge discloses the method of claim 1 (see above), wherein: the counter and the offset form a branch predictor entry for the fetch group in a table of the branch prediction circuit ([0035], lines 1-3, branch history memory 160 stores information about a state that represents statistical information about previous executions of the source instruction; [0035], lines 4-6, branch history memory is an associative memory (e.g. fully associative, set associative or direct mapped), that can be accessed using the address of the source instruction; [0006], line 9, a bundle must be fetched; [0021], lines 3-4, number of commands; [0021], line 2, VLIW); the table includes a set of branch predictor entries; and each branch predictor entry in the set of branch predictor entries is associated with a different fetch group of the program ([0035], lines 4-6, branch history memory is an associative memory (e.g. fully associative, set associative or direct mapped), that can be accessed using the address of the source instruction).
However, Hoogerbrugge does not disclose that the branch predictor entry is in a tagged geometric history length table of the branch prediction circuit.
On the other hand, Navada discloses a branch predictor entry is in a tagged geometric history length table of a branch prediction circuit ([0005], lines 4-7, TAGE predictors are gaining popularity for their ability to make predictions of increased accuracy by taking into account contexts and history associated with branch instructions).
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 Navada with the invention of Hoogerbrugge in order to increase prediction accuracy.
Consider claim 17, Hoogerbrugge discloses the processor of claim 12 (see above), wherein: the counter and the offset form a branch predictor entry for the fetch group in a table of the branch prediction circuit ([0035], lines 1-3, branch history memory 160 stores information about a state that represents statistical information about previous executions of the source instruction; [0035], lines 4-6, branch history memory is an associative memory (e.g. fully associative, set associative or direct mapped), that can be accessed using the address of the source instruction; [0006], line 9, a bundle must be fetched; [0021], lines 3-4, number of commands; [0021], line 2, VLIW).
However, Hoogerbrugge does not disclose that the branch predictor entry is in a tagged geometric history length table of the branch prediction circuit.
On the other hand, Navada discloses a branch predictor entry is in a tagged geometric history length table of a branch prediction circuit ([0005], lines 4-7, TAGE predictors are gaining popularity for their ability to make predictions of increased accuracy by taking into account contexts and history associated with branch instructions).
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 Navada with the invention of Hoogerbrugge in order to increase prediction accuracy.
Consider claim 20, Hoogerbrugge discloses a method in which each step is conducted by a branch prediction circuit ([0018], line 8, branch prediction unit) and an instruction fetch circuit ([0006], line 9, a bundle must be fetched; [0020], line 3, multiplexer 164) operating in combination in a computer processor ([0018], line 2, processor 10) that is executing a program ([0021], line 2, program of instructions), comprising: fetching a group of instructions ([0006], line 9, a bundle must be fetched; [0021], lines 3-4, number of commands; [0021], line 2, VLIW), in a fetch group ([0006], line 9, a bundle must be fetched; [0021], lines 3-4, number of commands; [0021], line 2, VLIW), from an instruction memory ([0018], line 5, instruction memory); associating a counter ([0012], lines 11-16, a saturating count of a number of executions of the branch command in which the branch is taken at that position. The state represents such a count only for the expected command, that is, only when there is a state transition to a different expected command a count for another command will start to become represented; [0013], lines 1-12, for example, the state for an instruction may represent that taking a branch as a result of a command at a certain position is expected. The state also represents a count of either 1 or 2 executions of that command where a branch is taken. If the branch is not taken when the instruction is executed and the state represents a count of 2, a transition will be made to a state where the command is still the expected command, but the count will go from 2 to 1. If the branch is not taken and the count is 1, a transition will be made to a state that represents that another branch command, if any, is the expectedly taken branch with a count of 1 for that other command; [0041], lines 5-6, one bit to represent whether there is a strong or a weak preference; [0041], line 9, more bits for the strength of the prediction; [0039], lines 1-12, if the branch history memory 160 stores information identifying a state that represents a strong preference for an outcome of the source instruction and that outcome occurs as a result of execution, the state remains unaffected. If a different outcome occurs and the state has a strong preference, a transition is made to the state with a weak preference for the same outcome as the original state with a strong preference. If the state represents a weak preference for an outcome of the source instruction and that outcome occurs as a result of execution, a transition occurs to the state with a strong preference for the same outcome as the original state with a weak preference; [0040], lines 6-7, information similar to the saturating count is represented only for the preferred outcome; alternatively, [0018], line 2, program counter) and an offset ([0041], lines 6-7, two bits to represent for which of the four possible outcomes there is a preference; [0038], lines 1-4, the diagram shows states for prediction of a "no-branch" outcome and for a taken outcome of a branch command from a first, second or third position in the source instruction respectively) with the fetch group ([0035], lines 4-6, branch history memory is an associative memory (e.g. fully associative, set associative or direct mapped), that can be accessed using the address of the source instruction; [0006], line 9, a bundle must be fetched; [0021], lines 3-4, number of commands; [0021], line 2, VLIW); predicting, using the counter and the offset, that a branching instruction in the fetch group will be used to branch the program ([0025], lines 4-12, the branch history information represents statistical information about the frequency with which the one or more branch commands from the instruction have led to a change in the program counter 12 before. Selection unit 161 uses this information to generate a decision whether a taken branch should be predicted and which of the branch commands in the instruction is the taken branch whose target address will affect the program counter 12); and prefetching at least one instruction indicated by the branching instruction ([0024], lines 1-6, the branch prediction unit 16 caters for this problem by predicting which instructions should be executed after an instruction that contains one or more branch commands, before the processor 10 has actually been able to instruct the program counter 12 about the result of the branch commands).
However, Hoogerbrugge does not explicitly disclose a non-transitory computer-readable medium storing instructions, which when executed by a processor cause the processor to conduct the aforementioned method.
On the other hand, Navada discloses a non-transitory computer-readable medium storing instructions, which when executed by a processor cause the processor to conduct a method ([0015], lines 1-4, yet another exemplary aspect is directed to a non-transitory computer readable storage medium comprising code, which, when executed by a processor, causes the processor to perform operations).
It would have been obvious to one of ordinary skill in the art before the effective filing date of claimed invention to combine the teaching of Navada with the invention of Hoogerbrugge in order to increase flexibility relative to a fully hardware approach. Alternatively, this modification merely entails combining prior art elements (the prior art elements of Hoogerbrugge as cited above, and Navada’s explicit teaching of a non-transitory computer-readable medium embodiment) according to known methods (Examiner submits that the general use of a non-transitory computer-readable medium to implement a method was well-known to one of ordinary skill in the art before the effective filing date of the claimed invention) to yield predictable results (the invention of Hoogerbrugge, implemented via a non-transitory computer-readable medium), which is an example of a rationale that may support a conclusion of obviousness as per MPEP 2143.
Consider claim 21, the overall combination entails discloses the non-transitory computer-readable medium of claim 20 (see above), wherein: the offset comprises sufficient bits to represent each instruction in the fetch group (Hoogerbrugge, [0041], lines 6-7, two bits to represent for which of the four possible outcomes there is a preference; [0038], lines 1-4, the diagram shows states for prediction of a "no-branch" outcome and for a taken outcome of a branch command from a first, second or third position in the source instruction respectively); and the branching instruction is associated with a value of the offset ([0041], lines 6-7, two bits to represent for which of the four possible outcomes there is a preference; [0038], lines 1-4, the diagram shows states for prediction of a "no-branch" outcome and for a taken outcome of a branch command from a first, second or third position in the source instruction respectively).
Claim(s) 8 and 18 is/are rejected under 35 U.S.C. 103 as being unpatentable over Hoogerbrugge as applied to claims 1 and 12 above, and further in view of Navada (US 20170322810 A1) and Kumar et al. (Kumar) (US 20220302917 A1)
Consider claim 8, Hoogerbrugge discloses the method of claim 1 (see above), wherein: the counter and the offset form a branch predictor entry for the fetch group in a table of the branch prediction circuit ([0035], lines 1-3, branch history memory 160 stores information about a state that represents statistical information about previous executions of the source instruction; [0035], lines 4-6, branch history memory is an associative memory (e.g. fully associative, set associative or direct mapped), that can be accessed using the address of the source instruction; [0006], line 9, a bundle must be fetched; [0021], lines 3-4, number of commands; [0021], line 2, VLIW); and the branch predictor entry does not have any other counters ([0040], lines 6-7, information similar to the saturating count is represented only for the preferred outcome).
However, Hoogerbrugge does not disclose that the branch predictor entry is in a tagged geometric history length table of the branch prediction circuit. Hoogerbrugge also does not disclose the computer processor is a RISC-V processor with C-extension support.
On the other hand, Navada discloses a branch predictor entry is in a tagged geometric history length table of a branch prediction circuit ([0005], lines 4-7, TAGE predictors are gaining popularity for their ability to make predictions of increased accuracy by taking into account contexts and history associated with branch instructions).
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 Navada with the invention of Hoogerbrugge in order to increase prediction accuracy.
However, the combination thus far does not entail that the computer processor is a RISC-V processor with C-extension support.
On the other hand, Kumar discloses a computer processor that is a RISC-V processor ([0043], line 4, RISC-V) with C-extension support ([0099], line 3, RISC-V c-extension).
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 Kumar with the combination of Hoogerbrugge and Navada in order to increase efficiency (Hoogerbrugge, [0007], line 1) for RISC-V processors with C-extension support in particular, and in order to avoid restrictions or licensing issues (Kumar, [0043], lines 5-6).
Consider claim 18, Hoogerbrugge discloses the processor of claim 12 (see above), wherein: the counter and the offset form a branch predictor entry for the fetch group in a table of the branch prediction circuit ([0035], lines 1-3, branch history memory 160 stores information about a state that represents statistical information about previous executions of the source instruction; [0035], lines 4-6, branch history memory is an associative memory (e.g. fully associative, set associative or direct mapped), that can be accessed using the address of the source instruction; [0006], line 9, a bundle must be fetched; [0021], lines 3-4, number of commands; [0021], line 2, VLIW); and the branch predictor entry does not have any other counters ([0040], lines 6-7, information similar to the saturating count is represented only for the preferred outcome).
However, Hoogerbrugge does not disclose that the branch predictor entry is in a tagged geometric history length table of the branch prediction circuit. Hoogerbrugge also does not disclose the processor is a RISC-V processor with C-extension support.
On the other hand, Navada discloses a branch predictor entry is in a tagged geometric history length table of a branch prediction circuit ([0005], lines 4-7, TAGE predictors are gaining popularity for their ability to make predictions of increased accuracy by taking into account contexts and history associated with branch instructions).
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 Navada with the invention of Hoogerbrugge in order to increase prediction accuracy.
However, the combination thus far does not entail that the processor is a RISC-V processor with C-extension support.
On the other hand, Kumar discloses a processor that is a RISC-V processor ([0043], line 4, RISC-V) with C-extension support ([0099], line 3, RISC-V c-extension).
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 Kumar with the combination of Hoogerbrugge and Navada in order to increase efficiency (Hoogerbrugge, [0007], line 1) for RISC-V processors with C-extension support in particular, and in order to avoid restrictions or licensing issues (Kumar, [0043], lines 5-6).
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure.
Chirca et al. (US 20200210191 A1) discloses “a prediction is made as to which branch instruction from one or more branch instructions in a sequence of instruction code will cause the program flow to branch (or jump) to a new location, (in other words, predict which of the branches will actually result in a taken branch) so that the instruction fetch logic begins to fetch from the predicted program memory location” (see paragraph [0017]); “a fetch-packet can contain as many as 16 instruction words in 16 corresponding ‘word slots’. In some examples, an instruction word is 32-bits wide. A branch instruction may be located in any of the 16 instruction word slots” (see paragraph [0040]); and a count, offset, and hysteresis bits in an exit history table (See FIG. 4A), which is relevant to the claimed branch prediction, fetch group, counter, and offset.
Talcott et al. (US 5964869) discloses “Branch predictor 202 receives the current fetch bundle address and uses the address to predict the outcome of conditional control-flow instructions. Branch predictor 202 may output a single branch prediction for a fetch bundle or may output a plurality of branch predictions for a fetch bundle. For example, branch predictor 202 may output eight branch predictions per fetch bundle. If a fetch bundle includes eight instructions, one branch prediction applies to each instruction within a fetch bundle. Branch predictor 202 may implement any conventional branch prediction algorithm. For example, branch predictor 202 may store one bit identifying whether the last iteration of the branch was taken or not taken and predict the same outcome. Alternatively, a two-bit saturating counter may be used for each branch prediction. A saturating counter is a counter that does not rollover. When the maximum count reached, the counter maintains the maximum count until the counter is decremented. Similarly, when the minimum count is reached, the counter maintains the minimum count until the counter is incremented. Each time a branch is taken, the saturating counter is incremented and each time the branch is not taken the saturating counter is decremented. The most significant bit of the counter identifies whether to predict the next iteration of the branch as taken or not taken. The saturating counter adds hysteresis to the prediction such that multiple not taken branches must occur prior to predicting a branch not taken when the saturating counter is in a strongly taken state” (see col. 9, line 60, to col. 10, line 20), which is relevant to the claimed branch prediction, fetch group, and counter.
Patel et al. (US 6115810) discloses “Two branch target are produced because each instruction fetch operation actually retrieves a group of eight consecutive instructions (a fetch group), and the base address for fetch group is used to predict the address of the next fetch group. Since each fetch group has more than one instruction, it is possible for a fetch group to contain multiple branch instructions. Hence, the system illustrated in FIG. 5 stores two predicted branch targets for each fetch group. BTA0 is associated with four instructions in the lower half of the fetch group and BTA1 is associated with four instructions in the upper half of the fetch group” (col. 6, lines 28-38), which is relevant to the claimed branch prediction and fetch group.
Talcott et al. (US 6289441 B1) discloses “In a preferred embodiment, each of the BPT counters corresponds to two instructions within the current fetch bundle. This typically corresponds to the SPARC instruction set architecture or an instruction sets with delay branches. The assumption here is that no two consecutive fetch instructions will be branches, hence, only four counters are needed. Although it is possible that two consecutive fetch instructions may both be branches, this occurrence is rare. Hence, the assumption is sufficiently accurate. Of course, greater accuracy may be achieved if BPT 155 provides eight counters, each corresponding to an instruction in the fetch bundle; however, this likely means increased hardware cost, which may not be warranted for many of the applications” (see col. 4, lines 7-19), which is relevant to the claimed branch prediction, counters and fetch group.
Talcott (US 6738897 B1) discloses “Each BPT entry … contains the same amount of n-bit counters … per BPT entry as the amount of local histories in the LBHT entry. In FIG. 5, for example, since there are four local histories (194, 196, 198, 200) in the LBHT entry (144), each BPT entry contains four n-bit counters. Thus, in effect, if four branches must be predicted simultaneously, then one BPT entry contains four, n-bit counters, and one LBHT entry contains four branch histories. This allows the processor to make predictions with regard to branch instructions within an entire bundle of instructions by considering the local branch histories of multiple instructions” (see col. 6, lines 28-40) and discloses “In order to make that determination, the branch prediction scheme, i.e., the branch predictor, first selects the appropriate LBHT entry based on the offset from the start of the fetch bundle (step 110). This selection mechanism is employed so that for a particular instruction bundle, the nth instruction location in the bundle is associated with the nth local history in a LBHT entry. For example, assuming that there is an 8-instruction fetch bundle and 8 local histories in a particular LBHT entry, the first instruction associates with the first local history in the LBHT entry. Those skilled in the art will appreciate that other embodiments may use a different amount of local histories per LBHT entry” (see col. 5, lines 34-45), which is relevant to the claimed branch prediction, offset, counter, and fetch group.
Talcott (US 6948055 B1) discloses “An index based upon the fetch bundle address has typically been used to select several prediction counters from which multiple branch predictions are made dependent upon the location of the branches in the fetch bundle. These counters may be simple two-bit counters with saturation. Typically, the counter is incremented when the branch instruction is taken and it is decremented when the instruction is not taken. For example, the branch instruction could be taken if the counter is in state 2 or 3, and not taken if the counter is in state 0 or 1. The saturation attribute inhibits the counter from recycling. For example, if the counter is in state 3 and a branch instruction is taken, the counter will stay in state 3 and not increment back to state 0. This mechanism attempts to predict branch instructions by gathering and representing the aggregate behavior of previous branch instructions. Improvements made to this mechanism include using branch history so that the processor recognizes repetitive patterns in previous branch instructions to predict later branch instructions” (see col. 3, lines 10-28), which is relevant to the claimed branch prediction, counter, and fetch group.
Godard et al. (US 20160132331 A1) discloses “note that the Exit Table can be configured such that entries of the Exit Table do not store predictions for never-taken conditional branch-type control transfer operations. In this case, control falls through to a later exit, which can be associated with a prediction stored as an entry in the Exit Table” (see [0059]); “As described herein, EBBs are linear segments of program code with a single entry point (entry address) and one or more possible exit points. 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” (see paragraph [0062]); “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” (see paragraph [0084]); and “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” (see paragraph [0098]), which is relevant to the claimed branch prediction, offset, counter, and fetch group.
Al Sheikh (US 20190004805 A1) discloses “In conventional implementations, branch prediction tables for superscalar processors may be overdesigned, in the sense that they may be provided with the capacity to deliver predictions for even the unlikely cases in which all instructions in a fetch group are branch instructions. Put another way, each entry of a conventional branch prediction table may have branch prediction mechanisms for each possible instruction position in a fetch group such that the maximum number of predictions which may be provided by each entry may be equal to the maximum number of instructions which may be present in a fetch group. For instance, there may be multiple branch prediction mechanisms such as state machines which may be available for potentially predicting multiple branch instructions, if present, in a fetch group” (see paragraph [0006]), and “a multi-tagged branch prediction table is disclosed, wherein each entry of the multi-tagged branch prediction table is tagged with two or more tags. The two or more tags may correspond to two or more fetch groups of instructions, fetched for example to be executed by a superscalar processor (wherein the superscalar processor may be configured to fetch two or more instructions in parallel in each one of the two or more fetch groups). Each entry of the multi-tagged branch prediction table may hold two or more branch prediction mechanisms, such as 2-bit branch prediction counters or 3-bit branch prediction counters as known in the art (and also briefly explained in the following sections). Since two or more fetch groups can utilize a single entry of the multi-tagged branch prediction table, the utilization of the multiple branch prediction mechanisms in each entry is improved” (see paragraph [0025]), which is relevant to the claimed branch prediction, counter, and fetch group.
Pistol et al. (US 10445102 B1) discloses “value for hysteresis indicates whether the entire entry for the fetch group address (or a portion, thereof) should remain stored in the first predictor, rather than be replaced” (see col. 2, lines 35-39), and “During misprediction, in an embodiment, the corresponding strength value is reduced (weakened). As described above, in one embodiment, the strength value is a saturating count. In one embodiment, correct predictions increase the count, whereas, mispredictions decrease the count” (see col. 7, lines 57-61), which is relevant to the claimed branch prediction, count, and fetch group.
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