Patent ID: 8892852

Claim:
A branch prediction device having a pipeline structure for performing branch prediction based on a global branch history on a computer processor having a pipeline structure, the branch prediction device comprising: a branch prediction information accumulation processing section; and a pipeline access control section, wherein the branch prediction information accumulation processing section includes a pattern history table for storing branch prediction information and branch establish availability information indicating availability of establishment of immediately preceding branching (establishing or not establishing) as branch prediction groups; and wherein the pipeline access control section includes: an index information control section; a first section control section; and a second selection control section, wherein: the index information control section includes an extended-folded-index-register unit and calculates in advance, regarding a value of index information for selecting the branch prediction information or the branch prediction group of the branch prediction information accumulation processing section, in one period of branch prediction generation pipeline for performing the pipeline processing regarding branch prediction generation, a value of the index information in another period to be executed after the one period, supplies index information required for processing in each period of the branch prediction generation pipeline, and causes an output of a shift register configuring the extended-folded-index-register unit to be an input of a row selection by the first selection control section; the extended-folded-index-register unit includes: a shift register that temporarily stores branch history information for past commands and hash values of the branch command addresses; and a logic circuit that includes a function of inputting a hash value of a rewound destination, a function of inputting an object branch command address, a function of inputting an output of a branch prediction logic immediately before, and a function of inputting an output of the shift register, wherein the logic circuit compresses a total bit of the branch history information and an execution path history information using a hash logic to thereby produce index information of the compressed bit; the first selection control section uses the output of the shift register as the input of the row selection directly, and performs the first selection control processing by row selection according to the value of the index information corresponding to the one period calculated by the index information control section; and the second selection control section performs the second selection control processing by column selection in the other period different from the one period in which the first selection control processing is performed to the branch prediction of the same branch command, according to the value of the index information corresponding to the other period calculated by the index information control section.