Infinite processor thread balancing

Patent metadata

Field	Value
Publication number	US-10558464-B2
Application number	US-201715428441-A
Country	US
Kind code	B2
Filing date	Feb 9, 2017
Priority date	Feb 9, 2017
Publication date	Feb 11, 2020
Grant date	Feb 11, 2020

Abstract

Embodiments include load-balancing a plurality of simultaneous threads of a processor. An example method includes computing a minimum group count for a thread from the plurality of threads. The minimum group count indicates a minimum number of groups of instructions to be assigned to the thread. The method further includes computing a maximum allowed group count for the thread. The maximum allowed group count indicates a maximum number of groups of instructions to be assigned to the thread. The method further includes issuing one or more groups of instructions for execution by the thread based on the minimum group count and the maximum allowed group count for the thread.

First claim

What is claimed is:

1. A computer implemented method for load-balancing a plurality of simultaneous threads of a processor, the method comprising:
computing a completion rate for a thread from the plurality of simultaneous threads, the completion rate indicative of a number of groups of instructions completed by the thread over a predetermined number of instruction cycles;
computing a minimum group count for the thread, the minimum group count indicative of a minimum number of groups of instructions to be assigned to the thread;
computing a maximum allowed group count for the thread, the maximum allowed group count indicative of a maximum number of groups of instructions to be assigned to the thread; and
issuing one or more groups of instructions for execution by the thread based on the minimum group count and the maximum allowed group count for the thread.

2. The computer implemented method of claim 1 , wherein computing the completion rate for the thread comprises monitoring completion of a number of groups using an adjustable window.

3. The computer implemented method of claim 1 , wherein computing the maximum allowed group count for the thread comprises:
determining that the thread is being starved by the maximum allowed group count of said thread itself, and in response incrementing the maximum allowed group count of the thread.

4. The computer implemented method of claim 3 , wherein the thread is determined to be starving itself based on the thread not being in an issue queue of the processor, the number of groups of instructions assigned to the thread matching the maximum allowed group count of the thread, and the thread not being blocked for dispatch.

5. The computer implemented method of claim 1 , wherein the thread is a first thread, and wherein computing the maximum allowed group count for the thread comprises:
determining that the first thread is starving a second thread, and in response decrementing the maximum allowed group count of the first thread.

6. The computer implemented method of claim 5 , wherein the first thread is determined to be starving the second thread based on:
the second thread not being in an issue queue of the processor,
the first thread being ahead of the second thread in dispatch order, and
the first thread and the second thread not being blocked for dispatch.

7. The computer implemented method of claim 6 , wherein the first thread is determined to be starving the second thread further based on the second thread being dispatched at least once since last flush of an instruction pipeline by the processor.

8. The computer implemented method of claim 1 , wherein computing the maximum allowed group count for the thread comprises:
determining that the thread missed an execution cycle, and in response incrementing the maximum allowed group count of the thread.

9. The computer implemented method of claim 8 , wherein the thread is determined to have missed an execution cycle based on:
the thread not starving another thread,
none of the other threads being dispatched, and
the number of groups of instructions assigned to the thread being lesser than the maximum allowed group count for the thread.

10. A processing system for load-balancing a plurality of simultaneous threads of a processor, the system comprising:
an instruction decode unit; and
an instruction fetch unit in communication with the instruction decode unit, the instruction fetch unit configured to:
compute a minimum group count for a thread from the plurality of simultaneous threads, the minimum group count indicative of a minimum number of groups of instructions to be assigned to the thread, the minimum group count based on a group completion rate of the thread;
compute a maximum allowed group count for the thread, the maximum allowed group count indicative of a maximum number of groups of instructions to be assigned to the thread; and
issue one or more groups of instructions for execution by the thread based on the minimum group count and the maximum allowed group count for the thread.

11. The system of claim 10 , wherein computing the maximum allowed group count for the thread comprises:
determining that the thread is being starved by the maximum allowed group count of said thread itself, and in response incrementing the maximum allowed group count of the thread.

12. The system of claim 10 , wherein the thread is a first thread, and wherein computing the maximum allowed group count for the thread comprises:
determining that the first thread is starving a second thread, and in response decrementing the maximum allowed group count of the first thread.

13. The system of claim 10 , wherein computing the maximum allowed group count for the thread comprises:
determining that the thread missed an execution cycle, and in response incrementing the maximum allowed group count of the thread.

14. A computer program product for load-balancing a plurality of simultaneous threads of a processor, the computer program product comprising a computer readable storage medium, the computer readable storage medium comprising computer executable instructions, wherein the computer readable storage medium comprises instructions to:
compute a minimum group count for a thread from the plurality of simultaneous threads, the minimum group count indicative of a minimum number of groups of instructions to be assigned to the thread, the minimum group count is based on a group completion rate of the thread;
compute a maximum allowed group count for the thread, the maximum allowed group count indicative of a maximum number of groups of instructions to be assigned to the thread; and
issue one or more groups of instructions for execution by the thread based on the minimum group count and the maximum allowed group count for the thread.

15. The computer program product of claim 14 , wherein computing the maximum allowed group count for the thread comprises:
determining that the thread is being starved by the maximum allowed group count of said thread itself, and in response incrementing the maximum allowed group count of the thread.

16. The computer program product of claim 14 , wherein the thread is a first thread, and wherein computing the maximum allowed group count for the thread comprises:
determining that the first thread is starving a second thread, and in response decrementing the maximum allowed group count of the first thread.

17. The computer program product of claim 14 , wherein computing the maximum allowed group count for the thread comprises:
determining that the thread missed an execution cycle, and in response incrementing the maximum allowed group count of the thread.

Assignees

• IBM

Inventors

• Alexander Gregory W
• Duffy Stephen
• Hutton David S
• Jacobi Christian
• Saporito Anthony
• Song Somin

Classifications

• G06F9/3863

  using multiple copies of the architectural state, e.g. shadow registers · CPC title

• G06F9/5083

  Techniques for rebalancing the load in a distributed system · CPC title

• G06F9/3851 Primary

  from multiple instruction streams, e.g. multistreaming · CPC title

• G06F9/3854

  Instruction completion, e.g. retiring, committing or graduating · CPC title

• G06F9/3858

  Result writeback, i.e. updating the architectural state or memory · CPC title