Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Method for Maintaining Branch History Table Accuracy with Reduced Table Size

IP.com Disclosure Number: IPCOM000123156D
Original Publication Date: 1998-Jun-01
Included in the Prior Art Database: 2005-Apr-04
Document File: 3 page(s) / 115K

Publishing Venue

IBM

Related People

Jeremiah, TL: AUTHOR [+3]

Abstract

The organization of a Branch History Table is optimized by partitioning it into regions separately accessible by the operating system, user program, and shared libraries. Simulation studies have shown branch prediction accuracy can be maintained while reducing the total table size.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Method for Maintaining Branch History Table Accuracy with Reduced
Table Size

   The organization of a Branch History Table is optimized
by partitioning it into regions separately accessible by the
operating system, user program, and shared libraries.  Simulation
studies have shown branch prediction accuracy can be maintained
while reducing the total table size.

   Branch prediction is frequently used in microprocessors
to allow speculative execution of instructions which logically
follow a branch without the necessity of fetching instructions down
both the taken and not-taken branch paths.  A frequently used method
of branch prediction employs various types of history tables, which
predict future branch outcomes based on previous branch history.  It
is common to access such tables based on an address related to the
branch instruction or by a pattern bit vector generated from recently
executed branches, or some combination of the above.  The accuracy of
such history-based mechanisms can degrade in the presence of task
switching and other system activity.

   The operating system executes instructions in what is often
called supervisor state, and the user program functions in problem
state.  Usually, the state can be easily determined from a register
within the microprocessor.  It is common to switch from problem
state to supervisor state after executing a few tens of thousands of
instructions.  After building up history on the user program
execution, the switch to supervisor state causes the history to be
polluted with branch history from executing operating system code.
The same process also happens when switching back to problem state.

   Disclosed is a method to improve branch prediction
accuracy by the inclusion of additional machine state information
beyond address and pattern for the purpose of accessing branch
history tables (BHTs).  In particular, simulation studies with
workload traces have shown equivalent branch prediction accuracy for
a large uniform BHT and a smaller BHT partitioned into separate
regions for the operating system, user code, and common libraries.

   By including additional state information as an input to
the BHT, the table is effectively segregated, allowing history from
the supervisor state, at least, to be preserved across task switches,
thereby imp...