Information processing apparatus, method, and computer-readable recording medium for replacing an entry in a memory device

A replacing method for an information processing apparatus which includes a branch history register holding, in order to predict a branch destination of a branch instruction, a correspondence table providing the correspondence between an address of said branch instruction and an address of the predicted branch destination of said branch instruction, a past branch history memory section holding past branch directions of said branch instruction as a branch history, a branch direction predictor for predicting a branch direction of said branch instruction on the basis of said branch history held by said past branch history memory section, and a branch history register updating section for updating said correspondence table held by said branch history register on the basis of the branch direction predicted by said branch direction predictor, said replacing method, used for entries of said past branch history memory section in case that all of said entries are in use when a branch history about a new branch instruction is registered into said past branch history memory section, said replacing method comprising:

• selecting one entry from all entries of said past branch history memory section if a plurality of the branch histories use all entries of said past branch history memory section when said branch history about said new branch instruction is being registered into said past branch history memory section;
• and
• replacing the branch history registered in said selected one entry with said new branch history about said new branch instruction,
• said selecting comprising selecting as said one entry, if past branch directions exist in the past branch history memory section, an entry in which said branch history held by said past branch history memory section includes only branches taken and in which the number of branches taken included in said branch history held by said past branch history memory section is equal to or more than a predetermined number.

A computer-readable recording medium storing a program for an information processing apparatus comprising a branch history register holding, in order to predict a branch destination of a branch instruction, a correspondence table providing the correspondence between an address of said branch instruction and an address of the predicted branch destination of said branch instruction;

• a past branch history memory section holding past branch directions of said branch instruction as a branch history;
• a branch direction predictor predicting a branch direction of said branch instruction on the basis of said branch history held by said past branch history memory section;
• and a branch history register updating section updating said correspondence table held by said branch history register on the basis of the branch direction predicted by said branch direction predictor, the replacing program allowing a computer to realize a replacing function used for entries of said past branch history memory section in case that all of said entries are in use when a branch history about a new branch instruction is registered into said past branch history memory section, and allowing said computer to:
• function as a selector for selecting one entry from all entries of said past branch history memory section if a plurality of the branch histories use all entries of said past branch history memory section when the branch history about the new branch instruction is being registered into said past branch history memory section, and as a replacing section replacing the branch history registered in said one selected entry with the branch history about said new branch instruction;
• and
• function such that said selector selects, as said one entry, if past branch directions exist in the past branch history memory section, an entry in which said branch history held by said past branch history memory section includes only branches taken and in which the number of branches taken included in said branch history held by said past branch history memory section is equal to or more than a predetermined number.