Infinite processor thread balancing

Patent metadata

Field	Value
Publication number	US-10884754-B2
Application number	US-201916674237-A
Country	US
Kind code	B2
Filing date	Nov 5, 2019
Priority date	Feb 9, 2017
Publication date	Jan 5, 2021
Grant date	Jan 5, 2021

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 maximum allowed group count for a thread from the plurality of simultaneous threads, the maximum allowed group count indicative of a maximum number of groups of instructions to be assigned to the thread;
determining that the thread is starved by the maximum allowed group count for the thread;
in response to the thread being starved, incrementing the maximum allowed group count of the thread; and
issuing one or more groups of instructions for execution by the thread based on a minimum group count and the maximum allowed group count for the thread.

2. The computer implemented method of claim 1 , further comprising:
computing a completion rate for the thread, the completion rate indicative of a number of groups of instructions completed by the thread over a predetermined number of instruction cycles; and
determining a minimum group count for the thread based on the completion rate, the minimum group count indicative of a minimum number of groups of instructions to be assigned to the thread.

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

4. The computer implemented method of claim 1 , wherein the thread is determined to be starved 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 maximum allowed group count for a thread from the plurality of simultaneous threads, the maximum allowed group count indicative of a maximum number of groups of instructions to be assigned to the thread;
determine that the thread is starved by the maximum allowed group count for the thread;
in response to the thread being starved, increment the maximum allowed group count of the thread; and
issue one or more groups of instructions for execution by the thread based on a minimum group count and the maximum allowed group count for the thread.

11. The system of claim 10 , wherein the instruction fetch unit is further configured to compute a minimum group count for the thread based on a group completion rate of the thread, the minimum group count indicative of a minimum number of groups of instructions to be assigned to the thread.

12. The system of claim 11 , wherein computing the completion rate for the thread comprises monitoring completion of a number of groups using an adjustable window.

13. The system of claim 10 , wherein the thread is determined to be starved 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.

14. 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.

15. 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.

16. 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 maximum allowed group count for a thread from the plurality of simultaneous threads, the maximum allowed group count indicative of a maximum number of groups of instructions to be assigned to the thread;
determine that the thread is starved by the maximum allowed group count for the thread;
in response to the thread being starved, increment the maximum allowed group count of the thread; and
issue one or more groups of instructions for execution by the thread based on a minimum group count and the maximum allowed group count for the thread.

17. The computer program product of claim 16 , wherein the thread is determined to be starved 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.

18. The computer program product of claim 16 , 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.

19. The computer program product of claim 18 , 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.

20. The computer program product of claim 19 , 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.

Assignees

• IBM

Inventors

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

Classifications

• G06F9/3854

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

• G06F9/3851 Primary

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

• G06F9/5083

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

• G06F9/3863

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

• G06F9/3857

  Physics · mapped topic