Browse Prior Art Database

Method for a variable-width indirect branch predictor array

IP.com Disclosure Number: IPCOM000128939D
Publication Date: 2005-Sep-21
Document File: 5 page(s) / 65K

Publishing Venue

The IP.com Prior Art Database

Abstract

Disclosed is a method for a variable-width indirect branch predictor array. Benefits include improved functionality and improved performance.

This text was extracted from a Microsoft Word document.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 44% of the total text.

Method for a variable-width indirect branch predictor array

Disclosed is a method for a variable-width indirect branch predictor array. Benefits include improved functionality and improved performance.

Background

              Indirect branch instructions (IBs) branch to a target address stored in a register. As a result, the register must be accessed and the instruction pointer (or program counter) must be updated to this address before subsequent instructions can be fetched. On systems with deeply-pipelined superscalar processors, waiting for the real target to redirect instruction fetch is costly in terms of processing overhead. Approximately a hundred opportunities to issue instructions can be wasted while waiting to issue the branch instruction and read the real target to fetch the next instruction.

              Many hardware solutions have been proposed to predict IB targets and improve processor performance. These solutions are based on predictor arrays that record past IB targets and use the past as a predictor of the future. Predictions are made for every IB by reading from the array. It is trained for mispredictions by writing into the array (see Figure 1).

              Many conventional hardware solutions exist to predict IB targets and improve processor performance. These solutions are based on predictor arrays that record past IB targets and use the past as a predictor of the future. A single prediction requires the storage of a full virtual address, such as 64 bits. Several thousand entries are typically required to reach the point of diminishing returns. This extensive history is impractical to implement with microarchitectures, and most commercial IB predictors implement a few hundred entries.

              IB targets are typically close to the IB in the virtual memory space. This characteristic is highly dependent on the compiler technology or run-time environment. Additionally, the IB can exist to call a dynamically linked function, call a virtual function, or to branch to a case in a switch statement. Many IBs require prediction of a small range of the low-order bits of the target. The high-order bits are the same as those of the IBs’ addresses. As a result, predicting a small number of bits might be sufficient. However, a significant number of easily-predicted branches can exist that require the prediction of all bits.

General description

              The disclosed method is a variable-width indirect branch predictor array. The method provides a full-width prediction of 60 bits but can be implemented for 20-bit and 40-bit predictions. Other divisions are possible with subtle implications to the implementation. The algorithm chosen to index into the predictor array is insignificant. However, because a line can contain multiple predictions in its fields, the index must contain a component to identify the line and a component to identify a specific field.

Advantages

              The disclosed method provides advantages, including:
•         ...