Branch prediction accuracy in a processor that supports speculative execution

Abstract

One embodiment of the present invention provides a system which improves branch prediction accuracy in a processor that supports speculative-execution. During normal-execution mode, the system issues instructions in program order. Upon encountering a launch condition which causes a processor to enter a speculative-execution mode, the system performs a checkpoint and begins executing instructions in a speculative-execution mode. Upon encountering a branch instruction during speculative-execution mode, the system selects the subsequent instruction to be executed based on a current state of a branch predictor and does not update the current state of the branch predictor, thereby preventing the branch predictor from being incorrectly updated twice when re-executing the branch instruction after returning to normal-execution mode.

Description

BACKGROUND [0001] 1. Field of the Invention [0002] The present invention relates to techniques for improving the performance of computer systems. More specifically, the present invention relates to a method and apparatus for improving branch prediction accuracy in a processor that supports speculative execution. [0003] 2. Related Art [0004] Advances in semiconductor fabrication technology have given rise to dramatic increases in microprocessor clock speeds. This increase in microprocessor clock speeds has not been matched by a corresponding increase in memory access speeds. Hence, the disparity between microprocessor clock speeds and memory access speeds continues to grow, and is beginning to create significant performance problems. Execution profiles for fast microprocessor systems show that a large fraction of execution time is spent not within the microprocessor core, but within memory structures outside of the microprocessor core. This means that the microprocessor systems spend...

AI Technical Summary

Benefits of technology

[0015] One embodiment of the present invention provides a system which improves branch prediction accuracy in a processor that supports speculative-execution. During normal-execution mode, the system issues instructions in program order. Upon encountering a launch condition which causes a processor to enter a speculative-execution mode, the system performs a checkpoint and begins executing instructions in a speculative-execution mode. Upon encountering a branch instruction during speculative-execution mode, the system selects the subsequent instruction to be executed based on a current state of a branch predictor and updates the branch prediction only from weakly-not-taken to weakly-taken or from weakly-taken to weakly-not-taken during speculative-execution mode. Note that updating the branch predictor in this fashion prevents the branch predictor from being incorrectly updated twice when re-executing the branch instruction after returning to normal-execution mode.

[0023] One embodiment of the present invention provides a system which improves branch prediction accuracy in a processor that supports speculative-execution. During normal-execution mode, the system issues instructions in program order. Upon encountering a launch condition which causes a processor to enter a speculative-execution mode, the system performs a checkpoint and begins executing instructions in a speculative-execution mode. Upon encountering a branch instruction during speculative-execution mode, the system selects the subsequent instruction to be executed based on a current state of a branch predictor and leaves the branch predictor in the current state. Note that leaving the branch predictor in the current state prevents the branch predictor from being incorrectly updated twice when re-executing the branch instruction after returning to normal-execution mode.

Problems solved by technology

Hence, the disparity between microprocessor clock speeds and memory access speeds continues to grow, and is beginning to create significant performance problems.

This means that the microprocessor systems spend a large fraction of time waiting for memory references to complete instead of performing computational operations.

When a memory reference, such as a load operation, generates a cache miss, the subsequent access to level-two (L2) cache (or memory) can require dozens or hundreds of clock cycles to complete, during which time the processor is typically idle, performing no useful work.

Unfortunately, existing out-of-order designs have a hardware complexity that grows quadratically with the size of the issue queue.

Practically speaking, this constraint limits the number of entries in the issue queue to one or two hundred, which is not sufficient to hide memory latencies as processors continue to get faster.

Moreover, constraints on the number of physical registers that can be used for register renaming purposes during out-of-order execution also limit the effective size of the issue queue.

Unfortunately certain operations, such as branch instructions, can be adversely affected by speculative-execution.

During speculative-execution, a problem can arise when the processor updates the branch prediction mechanism once during speculative-execution and then incorrectly updates the branch prediction a second time upon resuming normal-execution.

This duplication of updates to the branch prediction can cause the processor to subsequently mispredict the branch, thereby causing considerable performance degradation.

Images