FAST INDEX TREE FOR ACCELERATED BRANCH PREDICTION

• US 20130332714A1
• Filed: 03/05/2013
• Published: 12/12/2013
• Est. Priority Date: 06/12/2012
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Bonanno, James J., Prasky, Brian R., Saporito, Anthony
• Granted Patent: US 9,250,909 B2
• Time in Patent Office: Days
• US Class Current: 712/239
• CPC Class Codes: G06F 9/38 Concurrent instruction execution, e.g. pipeline or look ahead
• CPC Class Codes: G06F 9/3806 using address prediction, e.g. return stack, branch history buffer
• CPC Class Codes: G06F 9/3844 using dynamic branch prediction, e.g. using branch history tables

Abstract

Embodiments relate to using a fast index tree for accelerated branch prediction. A computer-implemented method includes determining, by a computer, that searching of a branch target buffer is to be performed under FIT control. A current search address is saved. The branch target buffer is searched at the saved current search address for a branch prediction. A FIT next-search address is determined based on reading branch taken and branch not taken paths for a next search level of predicted branches from a FIT structure. The searching is re-indexed based on the FIT next-search address. Based on locating the branch prediction, the searching is continued under FIT control with the current search address set based on the FIT next-search address. Based on failing to locate the branch prediction, the searching is re-indexed with the saved current search address, and the searching is performed without FIT control.

Claims

1. A computer-implemented method for accelerated branch prediction using a fast index tree (FIT), the method comprising:

determining, by a computer, that searching of a branch target buffer is to be performed under FIT control;

saving a current search address for searching of the branch target buffer;

searching the branch target buffer at the saved current search address for a branch prediction;

determining, by the computer, a FIT next-search address based on reading branch taken and branch not taken paths for a next search level of predicted branches from a FIT structure;

re-indexing the searching of the branch target buffer based on the FIT next-search address;

determining, by the computer, whether the searching at the saved current search address located the branch prediction;

based on the searching at the saved current search address locating the branch prediction, continuing the searching of the branch target buffer under FIT control with the current search address set based on the FIT next-search address; and

based on the searching at the saved current search address failing to locate the branch prediction, re-indexing the searching of the branch target buffer with the saved current search address and performing the searching of the branch target buffer without FIT control.

2. The computer-implemented method of claim 1, further comprising:

shutting off auxiliary structures comprising one or more of;

a multiple target table and a pattern history table, based on determining that searching of the branch target buffer is to be performed under FIT control.

3. The computer-implemented method of claim 1, wherein the FIT structure further comprises:

FIT content addressable memory to translate between a branch target buffer location and a FIT location, branch target buffer pointers to redirect searching of the branch target buffer for the branch taken and branch not taken paths when searching of the branch target buffer is under FIT control, and FIT pointers to redirect searching of the FIT structure for the branch taken and branch not taken paths.

4. The computer-implemented method of claim 3, further comprising:

based on determining that the searching of the branch target buffer is to be performed without FIT control, determining whether a branch is found that belongs in the FIT structure;

starting a FIT search based on determining that the FIT search is not active and the branch is found that belongs in the FIT structure;

based on determining that the branch is found that belongs in the FIT structure and the branch is not identified in the FIT content addressable memory, installing the branch in the FIT structure;

based on determining that the branch is identified in the FIT content addressable memory and a previous branch leading to the branch belongs in the FIT structure, updating the FIT structure to link the previous branch and the branch;

determining whether the searching of the branch target buffer is synchronized with the FIT search;

re-indexing the searching of the branch target buffer based on whether the branch was taken or not taken; and

based on determining that the searching of the branch target buffer is synchronized with the FIT search, performing the searching of the branch target buffer under FIT control.

5. The computer-implemented method of claim 4, wherein the FIT search further comprises:

searching the FIT structure for a current search level;

determining whether one or more pointers in a FIT entry for the current level are valid;

stopping the FIT search based on determining that no pointers in the FIT entry for the current level are valid;

determining whether a prediction from the branch target buffer has been received within a predetermined number of search levels; and

based on determining that the prediction from the branch target buffer has been received within the predetermined number of search levels, incrementing the current search level and re-indexing the FIT structure based on the incremented current search level.

6. The computer-implemented method of claim 3, further comprising:

based on determining that an entry has been written in the branch target buffer, accessing the FIT content addressable memory to determine whether the entry is in the FIT structure;

based on determining that the entry is in the FIT structure, determining whether the entry is a valid match based on a FIT CAM valid field corresponding to the entry in the FIT content addressable memory;

based on determining that the entry is valid, invalidating the entry in the FIT content addressable memory and all matching FIT pointers associated with the entry;

based on determining that a branch has completed with a valid FIT pointer along a predicted path, saving a next-FIT pointer; and

based on determining that a next completed branch is a surprise branch that belongs in the branch target buffer, invalidating all valid FIT pointers matching the saved next-FIT pointer.

7. The computer-implemented method of claim 3, further comprising:

based on writing a new entry in the FIT content addressable memory, selecting an entry to remove from the FIT structure; and

invalidating any valid pointers in the FIT structure with a matching pointer value of the entry to remove from the FIT structure.