Information processing apparatus, replacing method, and computer-readable recording medium on which a replacing program is recorded

Abstract

The present invention relates to an information processing apparatus predicting a branch destination of a branch instruction using a branch history register to realize effective replacement by enabling an unnecessary entry to be selected as an entry, which is an object of replacement, without using new resources in a full-associative memory device. The invention includes a selector for selecting one entry from all entries of a past branch history memory section if all entries of the past branch history memory section are in use when a branch history about a new branch instruction is registered into the past branch history memory section and a replacing section for registering the branch history about the new branch instruction into one entry selected by said selector, wherein the selector has a first selecting function of selecting one entry based on the branch history held by the past branch history memory section.

1 . A replacing method for a full-associative memory device, the replacing method being used for entries of said memory device in case that all of said entries are in use when a new entry is registered into said memory device, said method comprising: 
 selecting one entry from all entries of said memory device on the basis of information originally provided in entries of said memory device; and    registering said new entry into said selected one entry.    
   
   
       2 . The replacing method according to  claim 1 , wherein: 
 said selecting further comprises selecting said one entry on the basis of a branch history held by a past branch history memory section,    said selecting further comprises selecting, as said one entry, an entry registered earliest of all entries of said past branch history memory section,    wherein, an entry selected on the basis of the branch history held by the past branch history memory section is employed on a higher priority basis than the selected entry registered earliest of all entries of said past branch history memory section.    
   
   
       3 . The replacing method according to  claim 1 , wherein: 
 said selecting further comprises selecting said one entry on the basis of a branch history held by a past branch history memory section,    said selecting further comprises selecting, as said one entry, an entry used earliest for prediction by a branch direction predictor of all entries of said past branch history memory section,    wherein, an entry selected on the basis of the branch history held by the past branch history memory section is employed on a higher priority basis than the selected entry used earliest for prediction by the branch direction predictor of all entries of said past branch history memory section.    
   
   
       4 . The replacing method according to  claim 1 , wherein: 
 said selecting further comprises selecting said one entry on the basis of a branch history held by a past branch history memory section, and    said branch history held by said past branch history memory section includes only branches taken.    
   
   
       5 . The replacing method according to  claim 2 , wherein said branch history held by said past branch history memory section includes only branches taken.  
   
   
       6 . The replacing method according to  claim 3 , wherein said branch history held by said past branch history memory section includes only branches taken.  
   
   
       7 . The replacing method according to  claim 4 , wherein the number of branches taken included in said branch history held by said past branch history memory section is equal to or greater than a predetermined number.  
   
   
       8 . The replacing method according to  claim 5 , wherein the number of branches taken included in said branch history held by said past branch history memory section is equal to or greater than a predetermined number.  
   
   
       9 . The replacing method according to  claim 6 , the number of branches taken included in said branch history held by said past branch history memory section is equal to or greater than a predetermined number