Scheduling in a Multicore Architecture

• US 20140317378A1
• Filed: 05/01/2014
• Published: 10/23/2014
• Est. Priority Date: 09/30/2005
• Status: Active Grant

• Current Assignee: Synopsys Incorporated
• Original Assignee: Fujitsu Semiconductor Limited (Fujitsu Limited), Synopsys Incorporated
• Inventors: Lippett, Mark David
• Granted Patent: US 9,164,953 B2
• Time in Patent Office: Days
• US Class Current: 712/15
• CPC Class Codes: G06F 1/3203 Power management, i.e. event-based initiation of a power-saving mode
• CPC Class Codes: G06F 15/80 comprising an array of processing units with common control, e.g. single instruction multiple data processors G06F15/82 takes precedence ; for correlation function computation G06F17/15
• CPC Class Codes: G06F 2209/483 Multiproc
• CPC Class Codes: G06F 2209/5011 Pool
• CPC Class Codes: G06F 9/466 Transaction processing
• CPC Class Codes: G06F 9/4893 taking into account power or heat criteria power management in computers in general G06F1/3203; thermal management in computers in general G06F1/206
• CPC Class Codes: G06F 9/5027 the resource being a machine, e.g. CPUs, Servers, Terminals
• CPC Class Codes: G06F 9/5038 considering the execution order of a plurality of tasks, e.g. taking priority or time dependency constraints into consideration scheduling strategies G06F9/4881 and subgroups
• CPC Class Codes: Y02D 10/00 Energy efficient computing, e.g. low power processors, power management or thermal management

Abstract

This invention relates to scheduling threads in a multicore processor. Executable transactions may be scheduled using at least one distribution queue, which lists executable transactions in order of eligibility for execution, and multilevel scheduler which comprises a plurality of linked individual executable transaction schedulers. Each of these includes a scheduling algorithm for determining the most eligible executable transaction for execution. The most eligible executable transaction is outputted from the multilevel scheduler to the at least one distribution queue.

Claims

1. A method of scheduling executable transactions in a multicore processor comprising a plurality of processor elements, wherein at least one processor element comprises reconfigurable logic, the method comprising:

providing a configuration queue of executable transactions for a first configuration of the reconfigurable logic comprising one of a field programmable gate array (FPGA) or a memory, the executable transactions allocated to and ready for execution by the reconfigurable logic;

outputting the executable transactions of the configuration queue to the reconfigurable processor element for execution when the reconfigurable logic is configured according to the first configuration; and

reconfiguring the reconfigurable logic according to a second configuration when a pre-determined threshold is reached.

2. The method of claim 1, further comprising:

providing at least one distribution queue comprising executable transactions in order of eligibility for execution;

providing a plurality of executable transaction schedulers, each executable transaction scheduler comprising a scheduling algorithm for determining the most eligible executable transaction for execution from a number of candidate executable transactions;

linking the executable transaction schedulers together into a multilevel scheduler; and

outputting a most eligible executable transaction from the multilevel scheduler to the at least one distribution queue.

3. The method of claim 2, wherein reconfiguring the reconfigurable logic comprises:

stopping the output of the contents of the configuration queue associated with the first configuration;

reconfiguring the reconfigurable logic according to the second configuration;

providing a second configuration queue of executable transactions for the second configuration allocated to and ready for execution by the reconfigurable logic; and

outputting the executable transactions of the second configuration queue to the reconfigurable processor element for execution.

4. The method of claim 1, wherein the pre-determined threshold is a maximum time allowed before a particular executable transaction must be executed.

5. The method of claim 1, wherein the second configuration is selected based on a length of a configuration queue associated with the second configuration.

6. The method of claim 5, wherein the second configuration is selected in response to being associated with the longest configuration queue.

7. A non-transitory computer-readable storage medium comprising computer-executable instructions for scheduling executable transactions in a multicore processor comprising a plurality of processor elements, wherein at least one processor element comprises reconfigurable logic, the instructions, when executed, configured to:

provide a configuration queue of executable transactions for a first configuration of the reconfigurable logic comprising one of a field programmable gate array (FPGA) or a memory, the executable transactions allocated to and ready for execution by the reconfigurable logic;

output the executable transactions of the configuration queue to the reconfigurable processor element for execution when the reconfigurable logic is configured according to the first configuration; and

reconfigure the reconfigurable logic according to a second configuration when a pre-determined threshold is reached.

8. The non-transitory computer-readable storage medium of claim 7, further comprising instructions configured to:

provide at least one distribution queue comprising executable transactions in order of eligibility for execution;

provide a plurality of executable transaction schedulers, each executable transaction scheduler comprising a scheduling algorithm for determining the most eligible executable transaction for execution from a number of candidate executable transactions;

link the executable transaction schedulers together into a multilevel scheduler; and

output a most eligible executable transaction from the multilevel scheduler to the at least one distribution queue.

9. The non-transitory computer-readable storage medium of claim 8, wherein reconfiguring the reconfigurable logic comprises:

stopping the output of the contents of the configuration queue associated with the first configuration;

reconfiguring the reconfigurable logic according to the second configuration;

providing a second configuration queue of executable transactions for the second configuration allocated to and ready for execution by the reconfigurable logic; and

outputting the executable transactions of the second configuration queue to the reconfigurable processor element for execution.

10. The non-transitory computer-readable storage medium of claim 7, wherein the pre-determined threshold is a maximum time allowed before a particular executable transaction must be executed.

11. The non-transitory computer-readable storage medium of claim 8, wherein the second configuration is selected based on a length of a configuration queue associated with the second configuration.

12. The non-transitory computer-readable storage medium of claim 11, wherein the second configuration is selected in response to being associated with the longest configuration queue.

13. A multicore processor system comprising:

a multicore processor comprising a plurality of processor elements, where at least one processor element comprises reconfigurable logic comprising one of a field programmable gate array (FPGA) or a memory;

a configuration queue of executable transactions for a first configuration of the reconfigurable logic, the executable transactions allocated to and ready for execution by the reconfigurable logic, the configuration queue configured to output the executable transactions of the configuration queue to the reconfigurable processor element for execution when the reconfigurable logic is configured according to the first configuration; and

a controller configured to reconfigure the reconfigurable logic according to a second configuration when a pre-determined threshold is reached.

14. The multicore processor system of claim 13, further comprising:

a distribution queue comprising executable transactions in order of eligibility for execution; and

a plurality of executable transaction schedulers, each executable transaction scheduler comprising a scheduling algorithm for determining the most eligible executable transaction for execution from a number of candidate executable transactions, wherein the executable transaction schedules are linked together into a multilevel scheduler, the multilevel scheduler configured to output a most eligible executable transaction to the distribution queue.

16. The multicore processor system of claim 14, wherein the controller is configured to:

stop the output of the contents of the configuration queue associated with the first configuration;

reconfigure the reconfigurable logic according to the second configuration;

provide a second configuration queue of executable transactions for the second configuration allocated to and ready for execution by the reconfigurable logic; and

output the executable transactions of the second configuration queue to the reconfigurable processor element for execution.

17. The multicore processor system of claim 13, wherein the pre-determined threshold is a maximum time allowed before a particular executable transaction must be executed.

18. The multicore processor system of claim 13, wherein the second configuration is selected based on a length of a configuration queue associated with the second configuration.