Browse Prior Art Database

Method for a unified-array two-level indirect branch predictor

IP.com Disclosure Number: IPCOM000128940D
Publication Date: 2005-Sep-21
Document File: 4 page(s) / 15K

Publishing Venue

The IP.com Prior Art Database

Abstract

Disclosed is a method for a unified-array two-level indirect branch predictor. Benefits include improved functionality, improved performance, and improved cost effectiveness.

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 53% of the total text.

Method for a unified-array two-level indirect branch predictor

Disclosed is a method for a unified-array two-level indirect branch predictor. Benefits include improved functionality, improved performance, and improved cost effectiveness.

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).

              A branch target buffer (BTB) indexes a prediction for an IB target based on the address of the IB. A path-based predictor indexes a prediction based on a brief history of IB targets (and possibly IB instruction addresses). Other techniques are similar and differ only in the information and algorithm used to index into the predictor array. A cascaded predictor utilizes multiple predictor arrays and multiple indexing schemes. If the more complex algorithm fails to make a prediction (based on a tag miss), the simpler prediction is used.

              Conventionally, cascaded prediction works well because some IBs are predicted well by a simple BTB. Others require more sophistication, such as path-based prediction. However, different workloads have a different mix of simple and difficult IBs.

Description

              The disclosed method is a unified-array two-level IB predictor. The method requires hardware similar to a two-level cascaded predictor but performs better across workloads. The unified array stores a different mix of simple and difficult predictions based on the workload. For discussion, assume the simple predictions are BTB predictions, and the difficult predictions are path-based. Additionally, schemes with more than two levels of prediction use a unified array, but the description is limited to two levels (see Figure 2).

              The disclosed method includes index logic that determines a BTB and a path-based index. The most...