Browse Prior Art Database

Method for indirect branch prediction using a memory hierarchy

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

Publishing Venue

The IP.com Prior Art Database

Abstract

Disclosed is a method for indirect branch prediction using a memory hierarchy. Benefits include improved functionality, improved performance, and improved power 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 41% of the total text.

Method for indirect branch prediction using a memory hierarchy

Disclosed is a method for indirect branch prediction using a memory hierarchy. Benefits include improved functionality, improved performance, and improved power performance.

Background

              Conventionally, indirect branch instructions (IBs) direct execution to a target address stored in a register. It must be accessed and the instruction pointer program counter must be updated before subsequent instructions can be fetched. In systems with deeply pipelined superscalar processors, waiting for the real target to redirect the instruction fetch can be very costly in terms of processing overhead. The time to issue approximately a hundred instructions can be wasted while waiting to issue the branch instruction and read the real target.

              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. Large capacities are required to reach the point of diminishing returns. Microprocessor workloads are trending toward larger application footprints, multithreading, and servicing of independent transactions. These trends lead to more distant reuse of IBs, which requires even larger IB-predictor arrays to achieve acceptable prediction accuracy. This requirement occurs along with trends favoring lower-power and smaller cores. As a result, processors mispredict 50% or more of their indirect branches. To increase the problem further, software trends, such as object orientation and dynamic linking, provide incentive to use IBs.

General description

              The disclosed method is IB prediction using the existing memory hierarchy as a predictor array. The method reduces the hardware cost of IB prediction, increases the predictor capacity, and improves prediction accuracy.

              The key elements of the disclosed method include:

•             Utilization of existing caching mechanisms and storage for indirect branch prediction

•             Two prediction priority levels

•             Hashing of past IB predictor targets for the index of the predictor array

•             Use of physical or virtual memory

•             Prediction made by IB for the next IB

Advantages

              The disclosed method provides advantages, including:
•             Improved functionality due to providing indirect branch prediction using a memory hierarchy

•             Improved performance due to increasing the predictor capacity

•             Improved performance due to incorporation of multiple prediction methods
•             Improved performance due to temporal locality of the cache hierarchy

•             Improved power performance due to eliminating predictor hardware

•             Reduced hardware complexity due to eliminating predictor hardware

Detailed description

              The disclosed method uses the same caching concepts that prioritize the lo...