Browse Prior Art Database

Method and algorithm for implementing a dynamic flush generator for a branch predictor based on a bogus branch density measure

IP.com Disclosure Number: IPCOM000009378D
Publication Date: 2002-Aug-20
Document File: 2 page(s) / 83K

Publishing Venue

The IP.com Prior Art Database

Abstract

Disclosed is a method and algorithm for implementing a dynamic flush generator for a branch predictor based on a bogus branch density measure. Benefits include improved performance and improved functionality.

This text was extracted from a Microsoft Word document.
This is the abbreviated version, containing approximately 50% of the total text.

Method and algorithm for implementing a dynamic flush generator for a branch predictor based on a bogus branch density measure

Disclosed is a method and algorithm for implementing a dynamic flush generator for a branch predictor based on a bogus branch density measure. Benefits include improved performance and improved functionality.

Background

              Any branch predictor, during its operation, can produce bogus branch predictions. These predictions are branch predictions that are intended for use in a certain part of the code but are used by another part of the code. These bogus branch predictions imply a performance penalty because they may require removal from the branch predictor and a prediction correction. In some cases, the number of bogus branches could become so great the entire branch predictor may be flushed to avoid the performance penalty.

              Conventionally, two possible policies are available:

·        Do not flush the branch predictor and pay the performance penalty of moving to a new code area.

·        Flush on every task switch if task switches are too frequent, which would have some performance impact.

              A bogus branch prediction occurs for several reasons:

·        Task switching in which the linear address used by the branch target buffer (BTB) is mapped to a different code area. The BTB uses prediction from the old code portion for predicting in the new code area.

·        Aliasing. If the code mapping is not changed (due to area saving), BTBs may not use the complete address to identify entries. Sometimes TAG bits are discarded and result in aliasing. For example, if the most significant bytes (MSBs) of the BTB address are discarded, and two parts of code differ only by the discarded bits, when the program executes one of the parts, the BTB may make predictions that correspond to the other part.

·        Mapping. In general, any addressing manipulation that maps more than one code area to the same bits used by a certain BTB implementat...