Method and apparatus for distributing processing core workloads among processing cores

• US 9,678,806 B2
• Filed: 06/26/2015
• Issued: 06/13/2017
• Est. Priority Date: 06/26/2015
• Status: Active Grant

• Current Assignee: Advanced Micro Devices, Inc.
• Original Assignee: Advanced Micro Devices, Inc.
• Inventors: Beckmann, Bradford, Che, Shuai, Orr, Marc S., Yilmazer, Ayse
• Primary Examiner(s): GHAFFARI, ABU Z
• Application Number:
  US14/751,311
• Publication Number:
  US 20160378565A1
• Time in Patent Office: 718 Days
• Field of Search: None
• CPC Class Codes: G06F 9/30047 Prefetch instructions; cache control instructions
• CPC Class Codes: G06F 9/3887 controlled by a single instruction for multiple data lanes [SIMD]
• CPC Class Codes: G06F 9/3888 controlled by a single instruction for multiple threads [SIMT] in parallel
• CPC Class Codes: G06F 9/505 considering the load
• CPC Class Codes: G06F 9/5083 Techniques for rebalancing the load in a distributed system

Abstract

Briefly, methods and apparatus to rebalance workloads among processing cores utilizing a hybrid work donation and work stealing technique are disclosed that improve workload imbalances within processing devices such as, for example, GPUs. In one example, the methods and apparatus allow for workload distribution between a first processing core and a second processing core by providing queue elements from one or more workgroup queues associated with workgroups executing on the first processing core to a first donation queue that may also be associated with the workgroups executing on the first processing core. The method and apparatus also determine if a queue level of the first donation queue is beyond a threshold, and if so, steal one or more queue elements from a second donation queue associated with workgroups executing on the second processing core.

Claims

1. A method for workload distribution between a first processing core and a second processing core comprising:

providing queue elements from one or more workgroup queues associated with workgroups executing on the first processing core to a first donation queue associated with the workgroups executing on the first processing core atomically and within a device scope of the first processing core and the second processing core; and

when a queue level of the first donation queue is below a first threshold, stealing one or more queue elements from a second donation queue associated with workgroups executing on the second processing core to the first donation queue atomically and within the device scope of the first processing core and the second processing core.

2. The method of claim 1, wherein stealing the one or more queue elements from the second donation queue associated with the workgroups executing on the second processing core is performed when the queue level of the first donation queue is below the first threshold and a queue level of the second donation queue is below a second threshold.

3. The method of claim 1, wherein stealing the one or more queue elements from the second donation queue associated with the workgroups executing on the second processing core is performed when the queue level of the first donation queue is below the first threshold and a queue level of the one or more workgroup queues associated with workgroups executing on the first processing core is below a third threshold.

4. The method of claim 1 wherein providing queue elements from the one or more workgroup queues associated with the workgroups executing on the first processing core to the first donation queue associated with the workgroups executing on the first processing core is performed when the one or more workgroup queues associated with the workgroups executing on the first processing core are beyond a fourth threshold.

5. The method of claim 1 comprising:

determining queue levels of the one or more workgroup queues associated with the workgroups executing on the first processing core, wherein providing the queue elements from the one or more workgroup queues associated with the workgroups executing on the first processing core to the first donation queue associated with the workgroups executing on the first processing core is based on the determined queue levels of the one or more workgroup queues associated with the workgroups executing on the first processing core;

determining queue levels of one or more workgroup queues associated with the workgroups executing on the second processing core; and

providing the queue elements from the one or more workgroup queues associated with the workgroups executing on the second processing core to the second donation queue associated with the workgroups executing on the second processing core based on the determined queue levels of the one or more workgroup queues associated with the workgroups executing on the second processing core.

6. The method of claim 1 comprising:

determining the queue level of the first donation queue; and

determining a queue level of the second donation queue, wherein stealing the one or more queue elements from the second donation queue associated with the workgroups executing on the second processing core is based on the determined queue level of the first donation queue and the determined queue level of the second donation queue.

7. An electronic device comprising:

a processor that is operative to;

provide queue elements from one or more workgroup queues associated with workgroups executing on a first processing core to a first donation queue associated with the workgroups executing on the first processing core atomically and within a device scope of the first processing core and the second processing core; and

when a queue level of the first donation queue is below a first threshold, steal one or more queue elements from a second donation queue associated with workgroups executing on the second processing core to the first donation queue atomically and within the device scope of the first processing core and the second processing core.

8. The electronic device of claim 7, wherein the processor is operative to steal the one or more queue elements from the second donation queue associated with the workgroups executing on the second processing core when the queue level of the first donation queue is below the first threshold and a queue level of the second donation queue is below a second threshold.

9. The electronic device of claim 7, wherein the processor is operative to steal the one or more queue elements from the second donation queue associated with the workgroups executing on the second processing core when the queue level of the first donation queue is below the first threshold and a queue level of the one or more workgroup queues associated with workgroups executing on the first processing core is below a third threshold.

10. The electronic device of claim 7, wherein processor to provide the queue elements from the one or more workgroup queues associated with the workgroups executing on the first processing core to the first donation queue associated with the workgroups executing on the first processing core when the one or more workgroup queues associated with the workgroups executing on the first processing core are beyond a fourth threshold.

11. The electronic device of claim 7 comprising:

a first memory device operatively coupled to the first processing core, wherein the first memory device stores the one or more workgroup queues associated with the workgroups executing on the first processing core;

a second memory device operatively coupled to the second processing core, wherein the second memory device stores one or more workgroup queues associated with workgroups executing on the second processing core;

a third memory device operatively coupled to the first and second processing cores, wherein the third memory device stores the first donation queue and the second donation queue.

12. The electronic device of claim 7, wherein the processor comprises work donation control logic operative to:

determine queue levels of the one or more workgroup queues associated with the workgroups executing on the first processing core, wherein providing the queue elements from the one or more workgroup queues associated with workgroups executing on the first processing core to the first donation queue is based on the determined queue levels of the one or more workgroup queues associated with the workgroups executing on the first processing core;

determine queue levels of one or more workgroup queues associated with the workgroups executing on the second processing core; and

provide the queue elements from the one or more workgroup queues associated with the workgroups executing on the second processing core to the second donation queue associated with the workgroups executing on the second processing core based on the determined queue levels of the one or more workgroup queues associated with the workgroups executing on the second processing core.

13. The electronic device of claim 7, wherein the processor module comprises:

a workgroup queue element dequeuer operative to dequeue queue elements from the one or more workgroup queues associated with workgroups executing on the first processing core;

a workgroup queue element queuer operative to queue elements to the one or more workgroup queues associated with workgroups executing on the first processing core;

a donation queue element queuer operative to queue elements to the first donation queue and to the second donation queue; and

a donation queue element dequeuer operative to dequeue queue elements from the first donation queue and the second donation queue.

14. The electronic device of claim 7, wherein the processor comprises work stealing control logic operative to:

determine the queue level of the first donation queue; and

determine the queue level of the second donation queue, wherein stealing the one or more queue elements from the second donation queue associated with the workgroups executing on the second processing core is based on the determined queue level of the first donation queue and the determined queue level of the second donation queue.

15. A non-transitory computer readable medium comprising executable instructions that when executed by one or more processors causes the one or more processors to:

provide queue elements from one or more workgroup queues associated with workgroups executing on a first processing core to a first donation queue associated with the workgroups executing on the first processing core atomically and within a device scope of the first processing core and the second processing core; and

when a queue level of the first donation queue is below a first threshold, steal one or more queue elements from a second donation queue associated with workgroups executing on the second processing core to the first donation queue atomically and within the device scope of the first processing core and the second processing core.

16. The non-transitory computer readable medium of claim 15, wherein the one or more processors steal the one or more queue elements from the second donation queue associated with the workgroups executing on the second processing core when the queue level of the first donation queue is below the first threshold and a queue level of the second donation queue is below a second threshold.

17. The non-transitory computer readable medium of claim 15, wherein the one or more processors steal the one or more queue elements from the second donation queue associated with the workgroups executing on the second processing core when the queue level of the first donation queue is below the first threshold and a queue level of the one or more workgroup queues associated with workgroups executing on the first processing core is below a third threshold.