Package mars.tools

Class BHTSimulator

java.lang.Object
java.awt.Component
java.awt.Container
java.awt.Window
java.awt.Frame
javax.swing.JFrame
mars.tools.AbstractMarsTool
mars.tools.BHTSimulator
All Implemented Interfaces:
ImageObserver, MenuContainer, Serializable, EventListener, Accessible, RootPaneContainer, WindowConstants, Memory.Listener, MarsTool
public class BHTSimulator extends AbstractMarsTool
A MARS tool for simulating branch prediction with a Branch History Table (BHT)

The simulation is based on observing the access to the instruction memory area (text segment). If a branch instruction is encountered, a prediction based on a BHT is performed. The outcome of the branch is compared with the prediction and the prediction is updated accordingly. Statistics about the correct and incorrect number of predictions can be obtained for each BHT entry. The number of entries in the BHT and the history that is considered for each prediction can be configured interactively. A change of the configuration however causes a re-initialization of the BHT.

The tool can be used to show how branch prediction works in case of loops and how effective such simple methods are. In case of nested loops the difference of BHT with 1 or 2 Bit history can be explored and visualized.

Author:
Ingo Kofler (ingo.kofler@itec.uni-klu.ac.at)
See Also:

  • Field Details

    • DEFAULT_ENTRY_COUNT

      public static final int DEFAULT_ENTRY_COUNT
      Constant for the default size of the BHT.
      See Also:

    • DEFAULT_HISTORY_SIZE

      public static final int DEFAULT_HISTORY_SIZE
      Constant for the default history size.
      See Also:

    • DEFAULT_INITIAL_VALUE

      public static final boolean DEFAULT_INITIAL_VALUE
      Constant for the default inital value.
      See Also:

    • NAME

      public static final String NAME
      The name of the tool.
      See Also:

    • VERSION

      public static final String VERSION
      The version of the tool.
      See Also:

  • Constructor Details

    • BHTSimulator

      public BHTSimulator()
      Construct an instance of this tool. This will be used by the ToolManager.

  • Method Details

    • startObserving

      protected void startObserving()
      Adds BHTSimulator as observer of the text segment.
      Overrides:
      startObserving in class AbstractMarsTool
      See Also:

    • stopObserving

      protected void stopObserving()
      Description copied from class: AbstractMarsTool
      Unregister this tool as a listener of memory and/or registers, if applicable. This method is called when the tool is closed by the user. Does nothing by default.
      Overrides:
      stopObserving in class AbstractMarsTool
      See Also:

    • buildMainDisplayArea

      protected JComponent buildMainDisplayArea()
      Creates a GUI and initialize the GUI with the default values.
      Specified by:
      buildMainDisplayArea in class AbstractMarsTool

    • getName

      public String getName()
      Returns the name of the tool.
      Specified by:
      getName in interface MarsTool
      Specified by:
      getName in class AbstractMarsTool
      Returns:
      The tool's name as a string.

    • reset

      protected void reset()
      Perform a reset of the simulator. This causes the BHT to be reseted and the log messages to be cleared.
      Overrides:
      reset in class AbstractMarsTool

    • handlePreBranchInst

      protected void handlePreBranchInst(int address, BasicStatement statement)
      Handles the execution branch instruction. This method is called each time a branch instruction is executed. Based on the address of the instruction the corresponding index into the BHT is calculated. The prediction is obtained from the BHT at the calculated index and is visualized appropriately.
      Parameters:
      statement - The branch statement that is executed.

    • handleExecuteBranchInstruction

      protected void handleExecuteBranchInstruction(int branchInstructionAddress, boolean branchTaken)
      Handles the execution of the branch instruction. The correctness of the prediction is visualized in both the table and the log message area. The BHT is updated based on the information if the branch instruction was taken or not.
      Parameters:
      branchInstructionAddress - The address of the branch instruction.
      branchTaken - The information if the branch is taken or not (determined in a step before).

    • isBranchInstruction

      protected static boolean isBranchInstruction(BasicStatement statement)
      Determines if the instruction is a branch instruction or not.
      Parameters:
      statement - the statement to investigate
      Returns:
      true, if statement is a branch instruction, otherwise false

    • willBranch

      protected static boolean willBranch(BasicStatement statement)
      Checks if the branch instruction delivered as parameter will branch or not.
      Parameters:
      statement - The branch instruction to be investigated.
      Returns:
      true if the branch will be taken, otherwise false.

    • extractBranchAddress

      protected static int extractBranchAddress(int address, BasicStatement statement)
      Extracts the target address of the branch.

      In MIPS the target address is encoded as 16-bit value. The target address is encoded relative to the address of the instruction after the branch instruction

      Parameters:
      statement - The branch instruction.
      Returns:
      The address of the instruction that is executed if the branch is taken.

    • memoryRead

      public void memoryRead(int address, int length, int value, int wordAddress, int wordValue)
      Callback for text segment access by the MIPS simulator.

      The method is called each time the text segment is accessed to fetch the next instruction. If the next instruction to execute was a branch instruction, the branch prediction is performed and visualized. In case the last instruction was a branch instruction, the outcome of the branch prediction is analyzed and visualized.

      Parameters:
      address - The address which was read from.
      length - The number of bytes read. Will always be 1 (single byte), Memory.BYTES_PER_HALFWORD, or Memory.BYTES_PER_WORD.
      value - The value which was read.
      wordAddress - The address of the word affected by the operation.
      wordValue - The full value of the word.