Mechanism for detecting and handling a starvation of a thread in a multithreading processor environment

• US 20040216103A1
• Filed: 04/24/2003
• Published: 10/28/2004
• Est. Priority Date: 04/24/2003
• Status: Abandoned Application

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Kalla, Ronald Nick, Burky, William Elton
• Application Number:
  US10/422,656
• Publication Number:
  US 20040216103A1
• Time in Patent Office: Days
• US Class Current: 718/100
• CPC Class Codes: G06F 9/3836 Instruction issuing, e.g. dynamic instruction scheduling or out of order instruction execution
• CPC Class Codes: G06F 9/384 Register renaming
• CPC Class Codes: G06F 9/3851 from multiple instruction streams, e.g. multistreaming
• CPC Class Codes: G06F 9/3858 Result writeback, i.e. updating the architectural state or memory
• CPC Class Codes: G06F 9/38585 with result invalidation, e.g. nullification
• CPC Class Codes: G06F 9/3861 Recovery, e.g. branch miss-prediction, exception handling error detection or correction G06F11/00

Abstract

A method and multithread processor for detecting and handling the starvation of a thread. A counter associated with a first thread may be set with a pre-selected value. The counter may be updated in response to receiving a notification. The notification may indicate which, if any, group of instructions has been completed for the first and second threads. The counter may be updated in response to receiving the notification by decrementing a current value stored in the counter if the group of instructions is completed for the second thread and not for the first thread. If the value of the counter reaches a predetermined value, then a thread starvation condition may be detected for the first thread. That is, if the value of the counter reaches the predetermined value, then the first thread may be starved.

Claims

1. A method for detecting and handling the starvation of a thread in a multithreading processor comprising the steps of:

setting a counter associated with a first thread with a pre-selected value;

receiving a first notification, wherein said first notification indicates which, if any, group of instructions has been completed for said first and a second thread;

updating said counter in response to receiving said first notification, wherein said counter is updated in response to receiving said first notification by changing a current value stored in said counter if said group of instructions is completed for said second thread and not for said first thread; and

detecting a starvation of said first thread in response to a value in said counter.

2. The method as recited in claim 1, wherein said current value in said counter is changed by decrementing said current value by a value of one if said group of instructions is completed for said second thread and not for said first thread.

3. The method as recited in claim 2, wherein said starvation of said first thread is detected if said value of said counter is a predetermined value, wherein said predetermined value is zero.

4. The method as recited in claim 1 further comprising the step of:

reloading said counter with a previous value stored in said counter if said first notification indicates that a group of instructions has not been completed for either of said first thread and said second thread.

5. The method as recited in claim 1 further comprising the step of:

loading said counter with said pre-selected value if said first notification indicates a group of instructions is completed for said first thread.

6. The method as recited in claim 1 further comprising the step of:

receiving a second notification if said value of said counter is not zero.

7. The method as recited in claim 1 further comprising the step of:

flushing instructions of said second thread in a dispatch unit.

8. The method as recited in claim 7 further comprising the step of:

determining if said value of said counter remains at zero after receiving a second notification indicating which, if any, group of instructions has been completed for said first thread and said second thread.

9. The method as recited in claim 8 further comprising the step of:

flushing instructions of said second thread subsequent to a next to complete instruction of said second thread if said value of said counter remained at zero after receiving said second notification.

10. The method as recited in claim 9 further comprising the step of:

determining if said value of said counter remains at zero after receiving a third notification indicating which, if any, group of instructions has been completed for said first thread and said second thread.

11. The method as recited in claim 10 further comprising the step of:

flushing said next to complete instruction of said second thread if said value of said counter remained at zero after receiving said third notification.

12. A multithreading processor, comprising:

a dispatch unit;

a queue coupled to said dispatch unit, wherein said dispatch unit is configured to dispatch decoded instructions for a first thread and a second thread to said queue; and

a completion unit coupled to said queue, wherein said completion unit is configured to receive status information on said dispatched decoded instructions to said queue, wherein said completion unit comprises;

a group completion table configured to track when a group of instructions for said first thread and said second thread is completed,

wherein said dispatch unit comprises;

a register coupled to said completion unit configured to store a pre-selected value;

a counter associated with said first thread coupled to said register;

logic for setting said counter with said pre-selected value;

logic for receiving a first notification from said group completion table, wherein said first notification indicates which, if any, group of instructions has been completed for said first and said second thread;

logic for updating said counter in response to receiving said first notification by changing a current value stored in said counter if said group of instructions is completed for said second thread and not for said first thread; and

logic for detecting a starvation of said first thread in response to a value in said counter.

13. The multithreading processor as recited in claim 12, wherein said current value in said counter is changed by decrementing said current value by a value of one if said group of instructions is completed for said second thread and not for said first thread.

14. The multithreading processor as recited in claim 13, wherein said starvation of said first thread is detected if said value of said counter is a predetermined value, wherein said predetermined value is zero.

15. The multithreading processor as recited in claim 12, wherein said dispatch unit further comprises:

logic for reloading said counter with a previous value stored in said counter if said first notification indicates that a group of instructions has not been completed for either of said first thread and said second thread.

16. The multithreading processor as recited in claim 12, wherein said dispatch unit further comprises:

logic for loading said counter with said pre-selected value if said first notification indicates a group of instructions is completed for said first thread.

17. The multithreading processor as recited in claim 12, wherein said dispatch unit further comprises:

logic for receiving a second notification if said value of said counter is not zero.

18. The multithreading processor as recited in claim 12, wherein said dispatch unit further comprises:

logic for flushing instructions of said second thread in said dispatch unit.

19. The multithreading processor as recited in claim 18, wherein said dispatch unit further comprises:

logic for determining if said value of said counter remains at zero after receiving a second notification indicating which, if any, group of instructions has been completed for said first thread and said second thread.

20. The multithreading processor as recited in claim 19, wherein said dispatch unit further comprises:

logic for flushing instructions of said second thread subsequent to a next to complete instruction of said second thread if said value of said counter remained at zero after receiving said second notification.

21. The multithreading processor as recited in claim 20, wherein said dispatch unit further comprises:

logic for determining if said value of said counter remains at zero after receiving a third notification indicating which, if any, group of instructions has been completed for said first thread and said second thread.

22. The multithreading processor as recited in claim 21, wherein said dispatch unit further comprises:

logic for flushing said next to complete instruction of said second thread if said value of said counter remained at zero after receiving said third notification.