METHOD AND APPARATUS FOR REGULATING PROCESSING CORE LOAD IMBALANCE

• US 20160378565A1
• Filed: 06/26/2015
• Published: 12/29/2016
• Est. Priority Date: 06/26/2015
• Status: Active Grant

• Current Assignee: Advanced Micro Devices, Inc.
• Original Assignee: Advanced Micro Devices SDN Berhad (Advanced Micro Devices, Inc.)
• Inventors: Yilmazer, Ayse, Che, Shuai, Beckmann, Bradford, Orr, Marc S.
• Granted Patent: US 9,678,806 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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/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; 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.

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 threashold 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 threashold 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 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 performed atomically and within a device scope of the first processing core and the second processing core; and

stealing the one or more queue elements from the second donation queue associated with the workgroups executing on the second processing core is performed atomically and within the device scope.

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

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

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

8. An electronic device comprising:

a hybrid donation and stealing queueing control module 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; 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.

9. The electronic device of claim 8, wherein the hybrid donation and stealing queueing control module 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.

10. The electronic device of claim 8, wherein the hybrid donation and stealing queueing control module 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.

11. The electronic device of claim 8 wherein the hybrid donation and stealing queueing control module is operative 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 atomically and within a device scope of the first processing core and the second processing core; and

steal the one or more queue elements from the second donation queue associated with the workgroups executing on the second processing core atomically and within the device scope.

12. The electronic device of claim 8, wherein the hybrid donation and stealing queueing control module is operative 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.

13. The electronic device of claim 8 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.

14. The electronic device of claim 8, wherein the hybrid donation and stealing queueing control module 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.

15. The electronic device of claim 8, wherein the hybrid donation and stealing queueing control 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.

16. The electronic device of claim 8, wherein the hybrid donation and stealing queueing control module 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.

17. 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; 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.

18. The non-transitory computer readable medium of claim 17, 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 a the first donation queue is below the first threshold and a queue level of the second donation queue is below a second threshold.

19. The non-transitory computer readable medium of claim 17, 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.

20. The non-transitory computer readable medium of claim 17, wherein the one or more processors:

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 atomically and within a device scope of the first processing core and the second processing core; and

steal the one or more queue elements from the second donation queue associated with the workgroups executing on the second processing core atomically and within the device scope.