Method for maintaining a branch prediction history table

• US 10,423,418 B2
• Filed: 11/30/2015
• Issued: 09/24/2019
• Est. Priority Date: 11/30/2015
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Gellerich, Wolfgang, Held, Peter M., Schwidefsky, Martin, Shum, Chung-Lung K.
• Primary Examiner(s): Li, Aimee
• Assistant Examiner(s): Doman, Shawn
• Application Number:
  US14/953,633
• Publication Number:
  US 20170153895A1
• Time in Patent Office: 1,394 Days
• Field of Search: 712240, 712228, 718108
• CPC Class Codes: G06F 9/3004 to perform operations on memory
• CPC Class Codes: G06F 9/3806 using address prediction, e.g. return stack, branch history buffer
• CPC Class Codes: G06F 9/3851 from multiple instruction streams, e.g. multistreaming
• CPC Class Codes: G06F 9/461 Saving or restoring of program or task context
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues

Abstract

A method for managing tasks in a computer system comprising a processor and a memory, the method includes performing a first task by the processor, the first task comprising task-relating branch instructions and task-independent branch instructions and executing the branch prediction method, the execution resulting in task-relating branch prediction data in the branch prediction history table. In response to determining that the first task is to be interrupted or terminated, the method includes storing the task-relating branch prediction data of the first task in the task structure of the first task. In response to determining that a second task is to be continued, the method includes reading task-relating branch prediction data of the second task from the task structure of the second task, storing the task-relating branch prediction data of the second task in the branch prediction history table, and ensuring that task-independent branch prediction data is maintained.

Claims

1. A computer system having a processor and a memory, the processor being configured for executing tasks, the tasks comprising task-relating branch instructions and task-independent branch instructions, and being configured for executing a branch prediction method for predicting the behavior of the task-relating branch instructions and the task-independent branch instructions and determining branch prediction data for the task-relating branch instructions and the task-independent branch instructions,

the processor comprising a control register for controlling the tasks to be executed and a branch prediction history table for storing branch prediction data determined with the branch prediction method,

the memory comprising a memory area for storing a task structure of each of the tasks, the task structure being configured for storing branch prediction data,

the processor is configured to:

identify the task-independent branch instructions by identifying the task-independent branch instructions as being tagged with a processor state indicating user or privileged mode or by identifying an address range of the task-independent branch instructions as the address range of standard libraries, wherein the task-independent branch instructions produce task-independent branch prediction data;

perform a first task by the processor, the first task comprising task-relating branch instructions and the task-independent branch instructions,

execute the branch prediction method, resulting in branch prediction data, including task-independent branch prediction data produced by the task independent branch instructions in the branch prediction history table,

in response to determining that the first task is to be interrupted or terminated, store task-relating branch prediction data of the first task in the task structure of the first task,

in response to determining that a second task is to be continued or started, read task-relating branch prediction data of the second task from the task structure of the second task, store the task-relating branch prediction data of the second task in the branch prediction history table, and ensure that the task-independent branch prediction data produced by the task independent branch instruction is maintained in the branch prediction history table; and

provide a first marking to the task-relating branch prediction data of the second task in the branch prediction history table, the first marking indicating that the task-independent branch prediction data produced by the task independent branch instructions is exempt from replacement in the branch prediction history table while the second task is executing.

2. The computer system of claim 1, wherein in response to determining that the second task is to be continued or started the processor is further configured to read task-relating data of the second task from the task structure of the second task by the processor, the task-relating data comprising information indicating whether the task structure of the second task comprises task-relating branch prediction data, wherein only in case that the task-relating data comprises information that the task structure of the second task comprises task-relating branch prediction data performing the reading of the task-relating branch prediction data of the second task.

3. The computer system of claim 1, wherein in response to determining that the first task is to be interrupted or terminated the processor is further configured to store task-relating data of the first task in the task structure of the first task, the task-relating data of the first task comprising information that the task structure of the first task comprises task-relating branch prediction data.

4. The computer system of claim 1, wherein the processor is further configured to identified task-relating branch prediction data in the branch prediction history table and replace the identified task-relating branch prediction data of the branch prediction history with the task-relating branch prediction data of the second task, the identifying being performed using the first marking.

5. The computer system of claim 1, wherein the processor is further configured determine whether sufficient bandwidth is available for storing the task-relating branch prediction data of the first task in the task structure of the first task and storing the task-relating branch prediction data of the first task in the task structure of the first task in case sufficient bandwidth is available and storing a notice in the task structure of the first task that no task-relating branch prediction data are stored of the first task in case no sufficient bandwidth is available.

6. The computer system of claim 5, wherein in case that no sufficient bandwidth for storing the task-relating branch prediction data of the first task is available the processor is further configured to determine task-relating branch prediction data belonging to conditional branch instructions or unconditional branch instructions and determine whether sufficient bandwidth is available for storing the task-relating branch prediction data of the conditional branch instructions or the unconditional branch instructions and store only the task-relating branch prediction data of the conditional branch instructions or of the unconditional branch instructions in case sufficient bandwidth is available for storing task-relating branch prediction data of the conditional branch instructions or the unconditional branch instructions.

7. The computer system of claim 5, wherein before reading the task-relating branch prediction data of the second task the processor is further configured to determine whether the task structure of the second task comprises a notice that no task-relating branch prediction data are stored in the task structure of the second task and only reading the task-relating branch prediction data of the second task in case that no notice is available.

8. The computer system of claim 1, wherein the processor is further configured to determine whether sufficient bandwidth is available for reading the task-relating branch prediction data of the second task from the task structure of the second task, the reading of the task-relating branch prediction data of the second task being only performed in case sufficient bandwidth is available, the reading of the task-relating branch prediction data of the second task being terminated in case no sufficient bandwidth is available.