Quick index tree for accelerated branching forecast

摘要

Advanced branching prediction system using a fast index tree (FIT) with the system having:a branching buffer;a FIT structure, comprising a table or tables, which index the positions of entries in the branching target buffer, with one or more tables having a majority of entries;of which each represents a node in a binary tree and specifies a first next predicted branching in the branching target buffer along a missed branching path and a second predicted branching in the branching target buffer along a selected branching path,where each node of the binary tree represents a branching in a program code;anda processing circuit which is configured to perform a process comprising:Determine that the branching buffer shall be searched under FIT control;Save a current search address to search the branch target buffer;Search the branch target buffer at the saved current search address for a branch forecast;Determine a next FIT search address based on reading branching paths taken and not taken from the FIT structure for a next search stage of predicted branching;re-indexing the branching buffer search based on the next FIT search address;Determine whether the branch forecast has been found by searching the saved current search address;Based on the fact that the branch forecast was found by searching the saved current search address, continue searching the branch target buffer under FIT control, setting the current search address based on the next FIT search address;andbased on the fact that the branching forecast was not found by searching the saved current search address, re-indexing the browsing of the branching target buffer with the saved current search address and performing the browsing of the branching target buffer without FIT control.