Method and apparatus for task scheduling on heterogeneous multi-core reconfigurable computing platform

• US 10,452,605 B2
• Filed: 06/13/2017
• Issued: 10/22/2019
• Est. Priority Date: 03/27/2015
• Status: Active Grant

• Current Assignee: University of Science and Technology of China (Chinese Academy of Sciences), Huawei Technologies Co., Ltd. (Huawei Investment & Holding Co., Ltd.)
• Original Assignee: Huawei Technologies Co., Ltd. (Huawei Investment & Holding Co., Ltd.)
• Inventors: Wang, Chao, Li, Xi, Zhou, Xuehai, Zhang, Junneng, Chen, Peng, Guo, Qi
• Primary Examiner(s): Truong, Camquy
• Application Number:
  US15/621,768
• Publication Number:
  US 20170277654A1
• Time in Patent Office: 861 Days
• CPC Class Codes: G06F 15/177 Initialisation or configuration control processor initialisation G06F9/4405
• CPC Class Codes: G06F 9/48 Program initiating; Program switching, e.g. by interrupt
• CPC Class Codes: G06F 9/4843 by program, e.g. task dispatcher, supervisor, operating system
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: G06F 9/50 Allocation of resources, e.g. of the central processing unit [CPU]
• CPC Class Codes: G06F 9/505 considering the load
• CPC Class Codes: G06F 9/5066 Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs mappping at compile time, see G06F8/451
• CPC Class Codes: G06F 9/5083 Techniques for rebalancing the load in a distributed system

Abstract

A method for task scheduling on a heterogeneous multi-core reconfigurable computing platform is disclosed, the method includes: determining an execution manner of a target task according to popularity of the to-be-executed target task and usage of a reconfigurable resource of the heterogeneous multi-core reconfigurable computing platform, where the execution manner includes a hardware manner or a software manner, for the target task, there is no corresponding target intellectual property IP core for executing the target task on the heterogeneous multi-core reconfigurable computing platform, the popularity of the target task is used to indicate central processing unit CPU usage of the target task, and the usage of the reconfigurable resource is used to indicate a usage status of the reconfigurable resource; and executing the target task according to the determined execution manner.

Claims

1. A method for task scheduling on a heterogeneous multi-core reconfigurable computing platform, the method comprising:

determining an execution manner of a target task, comprising a hardware manner or a software manner, according to popularity of the target task which is to-be-executed and usage of a reconfigurable resource of the heterogeneous multi-core reconfigurable computing platform, including;

(a) determining whether weighted popularity of the target task is greater than or equal to a product of the usage of the reconfigurable resource and a reconfiguration coefficient when the weighted popularity of the target task is greater than or equal to the product, determining the execution manner is the hardware manner;

or

(b) when the weighted popularity of the target task is less than the product, determining the execution manner is the software manner;

wherein there is no corresponding target intellectual property (IP) core for executing the target task on the heterogeneous multi-core reconfigurable computing platform, the popularity of the target task indicates central processing unit (CPU) usage of the target task, and the usage of the reconfigurable resource indicates a usage status of the reconfigurable resource; and

executing the target task according to the determined execution manner.

2. The method according to claim 1, wherein the determining the execution manner of the target task comprises:

determining weighted popularity C_w of the target task according to the popularity of the target task, where C_w=C·

S, C is the popularity of the target task, C=N₁·

T₁/T_L, T_L is a time length between a current time point and a time point at which reconfiguration is performed on the reconfigurable resource last time, N₁ is a quantity of times for which the target task is executed within T_L in the software manner, T₁ is a time length required for a single execution of the target task in the software manner, S is a hardware speedup ratio of the target task, and the hardware speedup ratio S is used to indicate a ratio between a corresponding execution speed at which the target task is executed in the hardware manner and a corresponding execution speed at which the target task is executed in the software manner;

determining the usage E_ave of the reconfigurable resource of the heterogeneous multi-core reconfigurable computing platform according to the following formulas;

3. The method according to claim 2, wherein the determining the execution manner of the target task according to the weighted popularity C_w of the target task and the usage E_ave of the reconfigurable resource comprises:

when it is determined that the weighted popularity C_w of the target task is greater than or equal to a product of E_ave and k, determining that the execution manner of the target task is the hardware manner, wherein k is a reconfiguration coefficient of the heterogeneous multi-core reconfigurable computing platform, and is used to indicate a reconfiguration overhead of the heterogeneous multi-core reconfigurable computing platform;

or

when it is determined that the weighted popularity C_w of the target task is less than a product of E_ave and k, determining that the execution manner of the target task is the software manner.

4. The method according to claim 1, wherein the method further comprises:

determining a to-be-executed task; and

when an IP core for executing the to-be-executed task is not deployed on the heterogeneous multi-core reconfigurable computing platform, determining the to-be-executed task as the to-be-executed target task.

5. The method according to claim 4, wherein the method further comprises:

when an IP core for executing the to-be-executed task is deployed on the heterogeneous multi-core reconfigurable computing platform, determining that an execution manner of the to-be-executed task is hardware execution.

6. The method according to claim 1, wherein the heterogeneous multi-core reconfigurable computing platform comprises multiple reconfigurable resource packages, and when determining that the execution manner of the target task is the hardware manner, the executing the target task according to the determined execution manner comprises:

reconfiguring at least one reconfigurable resource package in the multiple reconfigurable resource packages to be a target IP core for executing the target task; and

executing the target task by using the target IP core.

7. The method according to claim 6, wherein the reconfiguring the at least one reconfigurable resource package comprises:

reconfiguring a target reconfigurable resource package in the multiple reconfigurable resource packages to be the target IP core, wherein the target reconfigurable resource package is a reconfigurable resource package with a longest idle time in the multiple reconfigurable resource packages.

8. An apparatus for task scheduling on a heterogeneous multi-core reconfigurable computing platform, wherein the apparatus comprises:

a processor, and

a memory which stores processor-executable instructions, which when executed causes the processor to implement the following operations;

determining an execution manner of a target task, comprising a hardware manner or a software manner, according to popularity of the target task which is to-be-executed and usage of a reconfigurable resource of the heterogeneous multi-core reconfigurable computing platform, including;

(a) determining whether weighted popularity of the target task is greater than or equal to a product of the usage of the reconfigurable resource and a reconfiguration coefficient;

(b) when the weighted popularity of the target task is greater than or equal to the product, determining the execution manner is the hardware manner;

or when the weighted popularity of the target task is less than the product, determining the execution manner is the software manner;

wherein for the target task, there is no corresponding target intellectual property (IP) core for executing the target task on the heterogeneous multi-core reconfigurable computing platform, the popularity of the target task indicates central processing unit (CPU) usage of the target task, and the usage of the reconfigurable resource indicates a usage status of the reconfigurable resource; and

executing the target task according to the execution manner .

9. The apparatus according to claim 8, wherein in terms of determining the execution manner of the target task, the operations comprise:

determining weighted popularity C_w of the target task according to the popularity of the target task, where C_w=C·

S, C is the popularity of the target task, C=N₁·

T₁/T_L, T_L is a time length between a current time point and a time point at which reconfiguration is performed on the reconfigurable resource last time, N₁ is a quantity of times for which the target task is executed within T_L in the software manner, T₁ is a time length required for a single execution of the target task in the software manner, S is a hardware speedup ratio of the target task, and the hardware speedup ratio S is used to indicate a ratio between a corresponding execution speed at which the target task is executed in the hardware manner and a corresponding execution speed at which the target task is executed in the software manner;

determining the usage E_ave of the reconfigurable resource of the heterogeneous multi-core reconfigurable computing platform according to the following formulas;

10. The apparatus according to claim 9, wherein in terms of determining the execution manner of the target task, the operations comprise:

when it is determined that the weighted popularity C_w of the target task is greater than or equal to a product of E_ave and k, determining that the execution manner of the target task is the hardware manner, wherein k is a reconfiguration coefficient of the heterogeneous multi-core reconfigurable computing platform, and is used to indicate a reconfiguration overhead of the heterogeneous multi-core reconfigurable computing platform;

or

when it is determined that the weighted popularity C_w of the target task is less than a product of E_ave and k, determining that the execution manner of the target task is the software manner.

11. The apparatus according to claim 8, wherein the operations further comprise:

determining a to-be-executed task; and

when an IP core for executing the to-be-executed task is not deployed on the heterogeneous multi-core reconfigurable computing platform, determining the to-be-executed task as the to-be-executed target task.

12. The apparatus according to claim 11, wherein the operations further comprise:

when an IP core for executing the to-be-executed task is deployed on the heterogeneous multi-core reconfigurable computing platform, determining that an execution manner of the to-be-executed task is hardware execution.

13. The apparatus according to claim 8, wherein the heterogeneous multi-core reconfigurable computing platform comprises multiple reconfigurable resource packages, and in terms of executing the target task according to the determined execution manner, the operations comprise:

when it is determined that the execution manner of the target task is the hardware manner, reconfiguring at least one reconfigurable resource package in the multiple reconfigurable resource packages to be a target IP core for executing the target task; and

executing the target task by using the target IP core.

14. The apparatus according to claim 13, wherein in terms of reconfiguring the at least one reconfigurable resource package, the operations further comprise:

reconfiguring a target reconfigurable resource package in the multiple reconfigurable resource packages to be the target IP core, wherein the target reconfigurable resource package is a reconfigurable resource package with a longest idle time in the multiple reconfigurable resource packages.

15. An apparatus for task scheduling on a heterogeneous multi-core reconfigurable computing platform, wherein the apparatus comprises:

a processor, configured to execute an instruction stored in a storage;

the storage, configured to store the instruction and data, and provide the instruction and the data for the processor; and

a communications bus, configured to implement connection communication between the processor and the storage;

wherein

the processor is configured to;

determine an execution manner of a target task, comprising a hardware manner or a software manner, according to popularity of the target task which is to-be-executed and usage of a reconfigurable resource of the heterogeneous multi-core reconfigurable computing platform, including;

(a) determining whether weighted popularity of the target task is greater than or equal to a product of the usage of the reconfigurable resource and a reconfiguration coefficient when the weighted popularity of the target task is greater than or equal to the product, determining the execution manner is the hardware manner;

or

(b) when the weighted popularity of the target task is less than the product, determining the execution manner is the software manner;

wherein for the target task, there is no corresponding target intellectual property core for executing the target task on the heterogeneous multi-core reconfigurable computing platform, the popularity of the target task indicates central processing unit (CPU) usage of the target task, and the usage of the reconfigurable resource indicates a usage status of the reconfigurable resource; and

execute the target task according to the determined execution manner.

16. The apparatus according to claim 15, wherein the processor is configured to:

determine weighted popularity C_w of the target task according to the popularity of the target task, where C_w=C·

S, C is the popularity of the target task, C=N₁·

T₁/T_L, T_L is a time length between a current time point and a time point at which reconfiguration is performed on the reconfigurable resource last time, N₁ is a quantity of times for which the target task is executed within T_L in the software manner, T₁ is a time length required for a single execution of the target task in the software manner, S is a hardware speedup ratio of the target task, and the hardware speedup ratio S is used to indicate a ratio between a corresponding execution speed at which the target task is executed in the hardware manner and a corresponding execution speed at which the target task is executed in the software manner;

determine the usage E_ave of the reconfigurable resource of the heterogeneous multi-core reconfigurable computing platform according to the following formulas;

17. The apparatus according to claim 16, wherein the processor is configured to:

when it is determined that the weighted popularity C_w of the target task is greater than or equal to a product of E_ave and k, determine that the execution manner of the target task is the hardware manner, wherein k is a reconfiguration coefficient of the heterogeneous multi-core reconfigurable computing platform, and is used to indicate a reconfiguration overhead of the heterogeneous multi-core reconfigurable computing platform;

or

when it is determined that the weighted popularity C_w of the target task is less than a product of E_ave and k, determine that the execution manner of the target task is the software manner.

18. The apparatus according to claim 15, wherein the processor is configured to:

determine a to-be-executed task; and

when an IP core for executing the to-be-executed task is not deployed on the heterogeneous multi-core reconfigurable computing platform, determine the to-be-executed task as the to-be-executed target task.

19. The apparatus according to claim 15, wherein the processor is configured to:

reconfigure at least one reconfigurable resource package in the multiple reconfigurable resource packages to be a target IP core for executing the target task; and

execute the target task by using the target IP core.

20. The apparatus according to claim 19, wherein the processor is configured to:

reconfigure a target reconfigurable resource package in the multiple reconfigurable resource packages to be the target IP core, wherein the target reconfigurable resource package is a reconfigurable resource package with a longest idle time in the multiple reconfigurable resource packages.

21. The apparatus according to claim 18, wherein the processor is configured to:

when an IP core for executing the to-be-executed task is deployed on the heterogeneous multi-core reconfigurable computing platform, determine that an execution manner of the to-be-executed task is hardware execution.