Interrupt driven dynamic adjustment of branch predictions

• US 5,838,962 A
• Filed: 04/09/1997
• Issued: 11/17/1998
• Est. Priority Date: 04/09/1997
• Status: Expired due to Term

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Larson, Douglas V.
• Primary Examiner(s): Ellis, Richard L.
• Application Number:
  US08/840,080
• Time in Patent Office: 587 Days
• Field of Search: 395/584, 395/585, 395/586, 395/587, 395/704, 395/709, 395/183.11, 395/183.14
• US Class Current: 712/239
• CPC Class Codes: G06F 11/3466 Performance evaluation by tracing or monitoring
• CPC Class Codes: G06F 9/3844 using dynamic branch prediction, e.g. using branch history tables

Abstract

Branch predictions are adjusted by interrupting a central processing unit and observing a pending branch instruction. An interrupt is generated using a counter, timer, or software-based interrupt. The interrupt causes a prediction adjustment routine to execute, which in turn determines whether a pending branch instruction will branch. The actual branch behavior of the branch instruction is compared to the predicted branch behavior of the branch instruction, and the prediction is adjusted accordingly based on the accuracy of the prediction and previous branch behavior. After the prediction has been adjusted (if necessary), execution returns to the program that contains the branch instruction that was evaluated.

Claims

1. A method of adjusting a branch prediction associated with a branch instruction contained in a segment of program code that is being executed by a central processing unit, the method comprising:

interrupting execution of the program code when execution of the branch instruction by the central processing unit is pending;

executing a prediction adjustment routine that updates the branch prediction; and

resuming execution of the program code.

2. The method of claim 1 wherein interrupting execution of the program code when execution of the branch instruction by the central processing unit is pending comprises:

initializing a timer to a time interval;

waiting for the time interval to expire; and

interrupting execution of the program code when the time interval has expired.

3. The method of claim 2 and further comprising:

waiting for the branch instruction after the time interval has expired.

4. The method of claim 2 wherein initializing a timer to a time interval comprises:

initializing a timer to a random time interval.

5. The method of claim 1 wherein interrupting execution of the program code when execution of the branch instruction by the central processing unit is pending comprises:

initializing an instruction counter to an instruction count;

counting instructions as they are executed; and

interrupting execution of the program code when a number of instruction that have been executed equals the instruction count.

6. The method of claim 5 and further comprising:

waiting for the branch instruction after the instruction count has been reached.

7. The method of claim 5 initializing an instruction counter to an instruction count comprises:

initializing an instruction counter to a random instruction count.

8. The method of claim 1 wherein interrupting execution of the program code when execution of the branch instruction by the central processing unit is pending comprises:

executing a break instruction that interrupts execution of the program code; and

replacing the break instruction with the branch instruction.

9. The method of claim 1 wherein interrupting execution of the program code when execution of the branch instruction by the central processing unit is pending comprises:

setting a flag that causes the branch instruction to generate an interrupt; and

interrupting execution of the program code after when the first break instruction after setting the flag is encountered.

10. The method of claim 1 wherein executing a prediction adjustment routine that updates the branch prediction:

evaluating a branch condition of the branch instruction to determine whether the branch instruction will branch;

evaluating a branch prediction associated with the branch instruction;

determining whether the branch prediction is correct or incorrect; and

toggling the branch prediction if the branch prediction is incorrect.

11. The method of claim 1 wherein executing a prediction adjustment routine that updates the branch prediction comprises:

evaluating a branch condition of the branch instruction to determine whether the branch instruction will branch;

evaluating a branch prediction associated with the branch instruction;

determining whether the branch prediction is correct or incorrect;

saving whether the branch prediction is correct or incorrect as branch history;

updating the branch prediction based on branch history and determining whether the branch prediction is correct or incorrect.

12. The method of claim 11 wherein updating the branch prediction based on branch history and determining whether the branch prediction is correct or incorrect comprises:

toggling the branch prediction if the prediction is incorrect when evaluated twice in a row.

13. The method of claim 1 wherein executing a prediction adjustment routine that updates the branch prediction includes:

examining a pending instruction to determine whether the pending instruction is the branch instruction; and

resuming execution of the program code if the pending instruction is not the branch instruction.

14. The method of claim 1 wherein executing a prediction adjustment routine that updates the branch prediction includes:

examining a pending instruction to determine whether the pending instruction is the branch instruction; and

emulating execution of instructions from the program code if the pending instruction is not the branch instruction, until the branch instruction is reached.

15. A computer system comprising:

a memory system for storing computer instructions, wherein a portion of the computer instructions comprise a branch prediction adjustment routine that when executed evaluates a pending branch instruction and updates a branch prediction associated with the pending branch instruction based on whether the branch prediction is correct; and

a central processing unit for executing the computer instructions, the central processing unit including;

an interrupt unit for launching the branch prediction adjustment routine in response to an interrupt.

16. The computer system of claim 15 wherein the interrupt unit includes a timer that measures a time interval and generates the interrupt when the time interval has expired.

17. The computer system of claim 15 wherein the interrupt unit includes an instruction counter that can be initialized to an instruction count and generates the interrupt after a number instructions that have been executed equals the instruction count.

18. The computer system of claim 15 wherein the interrupt unit generates the interrupt after encountering a break instruction.

19. The computer system of claim 15 and further comprising:

a status flag that causes the interrupt unit to generate the interrupt when the branch instruction is pending.

20. The computer system of claim 15 wherein the branch prediction adjustment routine evaluates a pending branch instruction and updates a branch prediction associated with the pending branch instruction based on whether the branch prediction is correct and based on branch history.

21. The computer system of claim 20 wherein the branch prediction adjustment routine toggles the branch prediction if the branch prediction is incorrect when evaluated twice in a row.

22. A program storage medium having computer readable program code thereon for adjusting a branch prediction associated with a branch instruction contained in a segment of executable program code that is being executed by a central processing unit, the program storage medium comprising:

a first segment of the computer readable program code for causing interruption of execution of the executable program code when execution of the branch instruction by the central processing unit is pending;

a second segment of the computer readable code for adjusting the branch prediction associated with the branch instruction;

a third segment of the computer readable program code for executing the second segment of the computer readable code in response to an interrupt caused by the first segment of the computer readable code; and

a fourth segment of the computer readable program code that resumes execution of the executable program code.

23. A program storage medium readable by a computer, tangibly embodying program instructions executable by the computer to implement a method that adjusts a branch prediction associated with a branch instruction contained in a segment of program code that is being executed by a central processing unit, the method comprising:

interrupting execution of the program code when execution of the branch instruction by the central processing unit is pending;

executing a prediction adjustment routine that updates the branch prediction; and

resuming execution of the program code.