Task Processing Scheduling Method and Device for Applying the Method

• US 20080263555A1
• Filed: 07/28/2005
• Published: 10/23/2008
• Est. Priority Date: 07/30/2004
• Status: Active Grant

• Current Assignee: Commissariat a L'Energie Atomique (AES Corporation)
• Original Assignee: Commissariat a L'Energie Atomique (AES Corporation)
• Inventors: Collette, Thierry, Blanc, Frederic, Ventroux, Nicolas, Chevobbe, Stephane
• Granted Patent: US 8,522,243 B2
• Time in Patent Office: Days
• US Class Current: 718/103
• CPC Class Codes: G06F 2209/5021 Priority
• CPC Class Codes: G06F 2209/506 Constraint
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• 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

Abstract

The invention relates to a method for scheduling the processing of tasks and to the associated device, the processing of a task comprising a step for configuring resources required for executing the task and a step for executing the task on the thereby configured resources, the method comprising a selection (1) of at least one level of independent tasks to be processed in accordance with an order of precedence and a step for sorting (2) out the tasks of the level of tasks to be processed in order to define, an order of priority in the processing of the tasks, depending on the number of resources required for processing the tasks on the one hand and on a time characteristic of the tasks on the other hand.

Claims

1. A scheduling method for processing tasks, the execution of which is conditioned by an order of precedence, the processing of a task comprising a step for configuring resources required for executing the task and a step for executing the task on the thereby configured resources, characterized in that it comprises:

a selection (1) of at least one level of independent tasks to be processed, in accordance with the order of precedence,

a step for sorting (2) out the tasks at the level of the tasks to be processed in order to define an order of priority in the processing of the tasks, depending on the number of resources required for processing each of the tasks on the one hand and on a quantity characteristic of the tasks on the other hand,

an evaluation (3) of the number of available resources for processing the tasks at the task level, and

an assignment (4) of the tasks at the task level to the available resources according to the order of priority.

2. The scheduling method for processing tasks according to claim 1, characterized in that the sorting (2) step comprises a first sorting according to the number of resources required for executing the tasks on the one hand, so that the tasks are processed according to a decreasing order of the number of resources required for their processing and, a second sorting according to the characteristic quantity of the tasks on the other hand, so that the tasks are processed according to an increasing or decreasing order of their characteristic quantity.

3. The scheduling method for processing tasks according to claim 2, characterized in that the first sorting precedes the second sorting, the second sorting being applied as soon as the number of resources required for processing several tasks is identical for said several tasks.

4. The scheduling method for processing tasks according to claim 2, characterized in that the second sorting precedes the first sorting, the first sorting being applied as soon as the characteristic quantity of the tasks relative to several tasks is identical for said several tasks.

5. The scheduling method for processing tasks according to claim 1, characterized in that the quantity characteristic of the tasks is the processing time of the tasks, or the configuration time of the resources required for executing the tasks, or the execution time of the tasks, or a time which is left to a task for executing depending on an execution time constraint associated with the tasks, or the processing, configuration or execution time of one or several tasks of upper rank in the order of precedence of the tasks, or a latest end date for configuring the tasks or executing the tasks, or an earliest or latest start date for configuring or executing one or several tasks of upper rank in the order or precedence of the tasks, or a time depending on a periodicity relative to one or several tasks, or a time depending on the whole or part of the characteristic quantities listed above.

6. The scheduling method for processing tasks according to claim 1, characterized in that the quantity characteristic of the tasks is a passband width useful for executing the tasks, or an arrival rate of data processed by the tasks, or a number of useful resources for storing or communicating data processed by the tasks, or a cost for communicating with other tasks or with resources shared among the tasks, or a power consumption generated by the processing of the tasks, or a piece of information which measures the complexity of the operations associated with the execution of the tasks, or a piece of information which measures the regularity of an algorithm associated with the execution of the tasks, or a piece of information which measures the parallelism of task execution, or a piece of information which measures a priority independent of the tasks and imposed by a user in the case of multi-user use, or a function of the whole or part of characteristic quantities listed above.

7. The scheduling method for processing tasks according to claim 1, characterized in that the quantity characteristic of the tasks is a piece of information relating to the position of the tasks in an application graph.

8. The scheduling method for processing tasks according to claim 7, characterized in that the piece of information relating to the position of the tasks in an application graph is the time which is left to the tasks for executing before the end of a time constraint imposed on the processing time of the application graph, or the largest number of tasks which remain to be processed before the end of the application graph, or the largest number of tasks of upper rank in the order of precedence of the tasks, or the sum of the execution times of the tasks of upper rank in the order of precedence of the tasks, or a function of the whole or part of the quantities listed above.

9. The scheduling method for processing tasks according to claim 1, characterized in that the level of independent tasks is defined by validating constraints of precedence of the tasks at the task level.

10. The scheduling method for processing tasks according to claim 1, characterized in that the assignment of the available resources depending on the order of priority is dynamically repeated until all the tasks of the task level are processed.

11. The scheduling method for processing tasks according to claim 1, characterized in that the processing of a task level of rank G begins as soon as all the tasks of the task level of rank G-1 which precedes the task level of rank G, have been configured.

12. The scheduling method for processing tasks according to claim 1, characterized in that it comprises a step for rejecting the processing of one or more tasks of the task level to be processed in order to allow degraded operation.

13. A method for processing tasks, the condition of which is conditioned by an order of precedence, the processing of a task comprising a step for configuring resources required for executing the task and a step for executing the task on thereby configured resources, characterized in that it comprises a scheduling of the processing of the tasks according to the method of any of claim 1 and in that the configuration of the resources and the execution of the tasks are activated by a configuration token and by an execution token, respectively.

14. A scheduling device for processing tasks, the execution of which is conditioned by an order of precedence, the processing of a task comprising a step for configuring resources required for executing the task and a step for executing the task on the thereby configured resources, characterized in that it comprises:

a component (CR) which contains a set of tasks to be processed,

a selection block (BS) for selecting at least one level of independent tasks to be processed among the set of tasks contained in the component (CR), according to the order of precedent,

means (BM1, BM2 , TP) for sorting out the tasks of the selected task level according to an order of priority so that the tasks are processed, depending on the number of resources required for processing each of the tasks on the one hand and on a quantity characteristic of the tasks on the other hand, and

means (BG) for assigning resources available to the processing of tasks depending on the order of priority.

15. The scheduling device for processing tasks according to claim 14, characterized in that the means (BM1, BM2 , TP) for sorting the tasks of a selected task level comprise:

a first memory block (BM1) containing information (R0, R1, . . . , RN) representative of the number of resources required for processing each task,

a second memory block (BM2) containing pieces of information (D0, D1, . . . , DN) representative of quantities characteristic of the tasks,

first comparison means (MC1) for comparing with each other the representative pieces of information of the quantities characteristic of the tasks of the task level,

second comparison means (MC2) for comparing the number of available resources with the number of resources required for processing the tasks of the task level, and

means (TP) for establishing the order of priority depending on the comparison results delivered by the first and second comparison means.

16. The device according to claim 15, characterized in that the means (TP) for establishing the order of priority depending on the comparison results comprise a set of shift registers containing binary data.

17. The device according to any claim 14, characterized in that the quantity characteristic of the tasks is the processing time of the tasks, or the configuration time of the resources required for executing the tasks, or the execution time of the tasks, or a time which is left to a task for executing depending on an execution time constraint associated with the task, of the processing, configuration or execution time of one or several tasks of upper rank in the order of precedence of the tasks, or a latest end date for configuring the tasks or executing the tasks, or an earliest or latest start date for configuring or executing one or several tasks of upper rank in the order of precedence of the tasks, or a time depending on a periodicity relative to one or more tasks, or a time depending on the whole or part of the characteristic quantities listed above.

18. The device according to claim 14, characterized in that the quantity characteristic of the tasks is a passband width useful for executing the tasks, or an arrival rate of data processed by the tasks, or a number of useful resources for storing or communicating data processed by the tasks, or a cost for communicating with other tasks or resources shared among the tasks, or a power consumption generated by the processing of the tasks, or a piece of information which measures the complexity of the operations associated with the execution of the tasks, or a piece of information which measures the regularity of algorithm associated with the execution of the tasks, or a piece of information which measures the parallelism of execution of the tasks, or a piece of information which measures a priority independent of the tasks and imposed by a user in the case of multi-user use, or a function of the whole or part of the characteristic quantities listed above.

19. The device according to claim 14, characterized in that the quantity characteristic of the tasks is a piece of information relating to the position of the tasks in an application graph.

20. The device according to claim 19, characterized in that the piece of information relating to the position of the tasks in an application graph is the time which is left to the tasks for executing before the end of a time constraint imposed on the processing time of the application graph, or the largest number of tasks which remain to be processed before the end of the application graph, or the largest number of tasks of upper rank in the order of precedence of the tasks, or the sum of the execution times of the tasks of upper rank in the order of precedence of the tasks, or a function of the whole or part of the quantities listed above.

21. The scheduling device for processing tasks according to claim 14, characterized in that the component (CR) which contains the set of tasks to be processed is a reconfigurable component suitable for control which comprises N+1 cells (Ci) representing N+1 states of a graph for applying the tasks to be executed, each cell containing a task to be executed, and a reconfigurable interconnection network for connecting the different states of the graph to each other.

22. A device for processing tasks, characterized in that it comprises a scheduling device for processing tasks according to claim 21, a configuration token and an execution token traveling through the interconnection network for activating the configuration of the tasks and the execution of the tasks, respectively.

23. The device according to claim 14, characterized in that the selection block (BS) comprises means for rejecting the processing of one or several tasks of the task level to be processed in order to allow degraded operation.