# US 8,751,776 B2 · Method for predicting branch target address based on previous prediction > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 8,751,776 B2 - Document ID: US8751776B2 - Status: Granted - Kind: B2 - Application number: 13/914,002 - Filed: 2013-06-10 - Published: 2013-10-17 - Granted: 2014-06-10 - Earliest claimed: 2011-01-07 - Assignees: Fujitsu Limited - Applicants: Fujitsu Limited - Inventors: Megumi Ukai - Web page: https://patentgrep.com/patent/US8751776B2 ## CPC - G06F 9/3844: {using dynamic branch prediction, e.g. using branch history tables} - G06F 9/322: {for non-sequential address} - G06F 9/323: {for indirect branch instructions} - G06F 9/3806: {using address prediction, e.g. return stack, branch history buffer} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract A branch target address table is provided for each branch instruction having a plurality of branch targets. Each branch target address table stores a history of a plurality of branch target addresses determined in the past by executing a corresponding branch instruction. A branch target prediction unit predicts a predicted branch target address with respect to a branch instruction with reference to the history of branch target addresses stored in the branch target address table corresponding to the branch instruction. The predicted branch target address obtained as a result of the prediction is stored, for example, in a predicted branch target address storage unit in association with the branch instruction, and is referenced by an instruction fetch control unit at the time of prefetching a branch target instruction. ## Claims ### Claim 1 An arithmetic processing apparatus comprising: a plurality of branch target address tables provided for respective branch instructions each having a plurality of branch targets and configured to store a history of a plurality of branch target addresses determined in a past by executing the respective branch instructions; and a branch target prediction unit configured to predict a predicted branch target address with respect to a branch instruction with reference to the history of the branch target addresses stored in a branch target address table corresponding to the branch instruction; wherein: in a first period before a branch target prediction based on a predicted branch target address predicted by the branch target prediction unit with respect to a branch instruction that completed execution is correct for first time, the branch target prediction unit sequentially registers, each time the branch instruction completes execution, a branch target address determined based on the completed branch instruction in an entry in order from a topmost entry of a branch target address table corresponding to the completed branch instruction, and outputs a branch target address registered in the topmost entry of the branch target address table corresponding to the completed branch instruction, as the predicted branch target address, and in a second period after the branch target prediction based on the predicted branch target address predicted by the branch target prediction unit with respect to the branch instruction that completed execution is correct for the first time, the branch target prediction unit sequentially selects, each time the branch instruction completes execution, an entry having a branch target address registered therein, in order from a topmost one of entries of the branch target address table corresponding to the completed branch instruction, and outputs a branch target address registered in the selected entry, as the predicted branch target address. ### Claim 2 (depends on 1) The arithmetic processing apparatus according to claim 1, further comprising: a predicted branch target address storage unit configured to store predicted branch target addresses for the respective branch instructions; and an address registration unit configured to register the predicted branch target address predicted by the branch target prediction unit in association with an address of the branch instruction corresponding to the predicted branch target address in the predicted branch target address storage unit. ### Claim 3 (depends on 2) The arithmetic processing apparatus according to claim 2, further comprising an instruction fetch control unit configured to obtain, when a branch instruction is fetched from a memory, a predicted branch target address stored in association with the branch instruction to be fetched, from the predicted branch target address storage unit as an address of an instruction to be fetched next. ### Claim 4 (depends on 2) The arithmetic processing apparatus according to claim 2, wherein, when a branch instruction completes execution, a predicted branch target address with respect to the completed branch instruction is predicted by the branch target prediction unit, and is registered in the predicted branch target address storage unit. ### Claim 5 (depends on 1) The arithmetic processing apparatus according to claim 1, wherein, when a branch instruction completes execution, the branch target prediction unit predicts a predicted branch target address with respect to the completed branch instruction. ### Claim 6 (depends on 1) The arithmetic processing apparatus according to claim 1, wherein the branch target prediction unit outputs, as the predicted branch target address, a branch target address registered in each of the branch target address tables, in order of registration. ### Claim 7 (depends on 1) The arithmetic processing apparatus according to claim 1, wherein, when a branch instruction completes execution, the branch target prediction unit searches a branch target address table corresponding to the completed branch instruction for an entry where a same address as a branch target determined based on the completed branch instruction is registered, registers, upon detecting no entry where the same address is registered, the branch target address determined based on the completed branch instruction in a first free entry out of free entries of the branch target address table corresponding to the completed branch instruction, and outputs the branch target address stored in the topmost entry of the branch target address table, as the predicted branch target address, and outputs, upon detecting the entry where the same address is registered, a branch target address stored in an entry next to the detected entry, as the predicted branch target address. ### Claim 8 (depends on 1) The arithmetic processing apparatus according to claim 1, wherein, when a branch instruction completes execution, the branch target prediction unit selects, upon determining that a branch target prediction based on a predicted branch target address predicted by the branch target prediction unit with respect to the completed branch instruction is correct, an entry next to an entry selected when the branch instruction completed execution last time, from a branch target address table corresponding to the completed branch instruction, and outputs a branch target address stored in the current selected entry, as the predicted branch target address, and outputs, upon determining that the branch target prediction based on the predicted branch target address predicted by the branch target prediction unit with respect to the completed branch instruction is a misprediction, a branch target address stored in a topmost entry of the branch target address table corresponding to the completed branch instruction, as the predicted branch target address. ### Claim 9 (depends on 1) The arithmetic processing apparatus according to claim 1, wherein: the branch target prediction unit sequentially registers a branch target address determined based on a branch instruction that has completed execution, in an entry in order from a topmost entry of a branch target address table corresponding to the completed branch instruction until the branch target address table has no free entries; and when a branch instruction completes execution, the branch target prediction unit selects, upon determining that a branch target prediction based on a predicted branch target address predicted by the branch target prediction unit with respect to the completed branch instruction is a misprediction, a topmost entry of a branch target address table corresponding to the completed branch instruction, and outputs a branch target address registered in the current selected entry, as the predicted branch target address, and selects, upon determining that the branch target prediction based on the predicted branch target address predicted by the branch target prediction unit with respect to the completed branch instruction is correct, an entry next to an entry selected last time from the branch target address table corresponding to the completed branch instruction, and outputs a branch target address registered in the current selected entry, as the predicted branch target address. ### Claim 10 (depends on 1) The arithmetic processing apparatus according to claim 1, wherein, when the branch instruction completes execution in the second period and a branch target prediction based on a predicted branch target address predicted by the branch target prediction unit with respect to the completed branch instruction is a misprediction, the branch target prediction unit outputs the branch target address registered in the topmost entry of the branch target address table corresponding to the completed branch instruction, as the predicted branch target address. ### Claim 11 (depends on 1) The arithmetic processing apparatus according to claim 1, further comprising: a plurality of pointers provided for the respective branch instructions and configured to point to an entry of the branch target address tables corresponding to the respective branch instructions, wherein: when the branch instruction completes execution in the first period, the branch target prediction unit sets a pointer corresponding to the completed branch instruction so as to point to the topmost entry of the branch target address table corresponding to the completed branch instruction, and outputs a branch target address registered in an entry pointed by the pointer, as the predicted branch target address; and when the branch instruction completes execution in the second period, the branch target prediction unit sets, upon determining that the branch target prediction based on the predicted branch target address predicted by the branch target prediction unit with respect to the completed branch instruction is correct, the pointer corresponding to the completed branch instruction so as to point to a next entry in the branch target address table corresponding to the completed branch instruction, and outputs a branch target address registered in the entry pointed by the pointer, as the predicted branch target address, and sets, upon determining that the branch target prediction based on the predicted branch target address predicted by the branch target prediction unit with respect to the completed branch instruction is a misprediction, the pointer corresponding to the completed branch instruction so as to point to the topmost entry of the branch target address table corresponding to the completed branch instruction, and outputs the branch target address registered in the entry pointed by the pointer, as the predicted branch target address. ### Claim 12 (depends on 1) The arithmetic processing apparatus according to claim 1, further comprising a plurality of pointers provided for the respective branch instructions and configured to point to an entry of the branch target address tables corresponding to the respective branch instructions, wherein: when the branch instruction completes execution in the first period, the branch target prediction unit registers a branch target address in an entry pointed by a pointer in the branch target address table corresponding to the completed branch instruction, and sets the pointer corresponding to the completed branch instruction so as to point to a next entry in the branch target address table corresponding to the completed branch instruction; and when a branch instruction completes execution in the second period, the branch target prediction unit sets, upon determining that the branch target prediction based on the predicted branch target address predicted by the branch target prediction unit with respect to the completed branch instruction is correct, the pointer corresponding to the completed branch instruction so as to point to a next entry in the branch target address table corresponding to the completed branch instruction, and outputs the branch target address registered in the entry pointed by the pointer, as the predicted branch target address, and sets, upon determining that the branch target prediction based on the predicted branch target address predicted by the branch target prediction unit with respect to the completed branch instruction is a misprediction, the pointer corresponding to the completed branch instruction so as to point to the topmost entry in the branch target address table corresponding to the completed branch instruction, and outputs the branch target address registered in the entry pointed by the pointer, as the predicted branch target address. ### Claim 13 (depends on 12) The arithmetic processing apparatus according to claim 12, wherein: when the branch instruction completes execution in the second period and the branch target prediction based on the predicted branch target address predicted by the branch target prediction unit with respect to the completed branch instruction is correct, the branch target prediction unit updates the pointer corresponding to the completed branch instruction so as to point to a next entry in the branch target address table corresponding to the completed branch instruction, outputs, when a branch target address is registered in the entry pointed by the updated pointer, the branch target address registered in the entry pointed by the pointer, as the predicted branch target address, and sets, when no branch target address is registered in the entry pointed by the updated pointer, the pointer corresponding to the completed branch instruction so as to point to the topmost entry of the branch target address table corresponding to the completed branch instruction, and outputs the branch target address registered in the entry pointed by the pointer, as the predicted branch target address. ### Claim 14 A branch prediction method comprising: referring, by an arithmetic processing apparatus, to a plurality of branch target address tables provided for respective branch instructions each having a plurality of branch targets and configured to store a history of a plurality of branch target addresses determined in a past by executing the respective branch instructions; predicting, by the arithmetic processing apparatus, a predicted branch target address with respect to a branch instruction with reference to the history of the branch target addresses stored in a branch target address table corresponding to the branch instruction; in a first period before a branch target prediction based on a predicted branch target address predicted with respect to a branch instruction that completed execution is correct for first time, and each time the branch instruction completes execution, sequentially registering a branch target address determined based on the completed branch instruction in an entry in order from a topmost entry of a branch target address table corresponding to the completed branch instruction, and outputs a branch target address registered in the topmost entry of the branch target address table corresponding to the completed branch instruction, as the predicted branch target address; and in a second period after the branch target prediction based on the predicted branch target address predicted with respect to the branch instruction that completed execution is correct for the first time, and each time the branch instruction completes execution, sequentially selecting an entry having a branch target address registered therein, in order from a topmost one of entries of the branch target address table corresponding to the completed branch instruction, and outputs a branch target address registered in the selected entry, as the predicted branch target address.