Method for maintaining a branch prediction history table

• US 10,430,194 B2
• Filed: 03/10/2016
• Issued: 10/01/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:
  US15/065,911
• Publication Number:
  US 20170153893A1
• Time in Patent Office: 1,300 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 method for managing tasks in a computer system comprising a processor and a memory containing program instructions, the processor being configured for executing tasks, the program instructions 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 method comprising:

identifying 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;

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

executing the branch prediction method, resulting in branch prediction data, including the 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, storing 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, reading task-relating branch prediction data of the second task from the task structure of the second task and storing the task-relating branch prediction data of the second task in the branch prediction history table, and ensuring that the task-independent branch prediction data produced by the task independent branch instructions is maintained in the branch prediction history table; and

providing 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 method of claim 1, in response to determining that the second task is to be continued or started, reading 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 method of claim 1, in response to determining that the first task is to be interrupted or terminated, storing task-relating data of the first task in the task structure of the first task, the task-relating data comprising information that the task structure of the first task comprises task-relating branch prediction data.

4. The method of claim 1, the storing of the task-relating branch prediction data of the second task comprising identifying task-relating branch prediction data in the branch prediction history table and replacing the identified task-relating branch prediction data of the branch prediction history with all or part of the task-relating branch prediction data of the second task, the identifying being performed using the first marking.

5. The method of claim 1, further comprising determining 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 method of claim 5, in case that no sufficient bandwidth for storing the task-relating branch prediction data of the first task is available, determining task-relating branch prediction data belonging to conditional branch instructions and/or unconditional branch instructions and determining whether sufficient bandwidth is available for storing the task-relating branch prediction data of the conditional branch instructions or the unconditional branch instructions and storing 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 method of claim 5, before reading the task-relating branch prediction data of the second task, determining 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 method of claim 1, the method further comprising determining 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 available, the reading of the task-relating branch prediction data of the second task being terminated in case no sufficient bandwidth is available.