APPARATUS AND METHOD FOR HARDWARE-BASED TASK SCHEDULING

• US 20150301854A1
• Filed: 04/21/2015
• Published: 10/22/2015
• Est. Priority Date: 04/21/2014
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Park, Jongchul, Koo, Jinkyu, Han, Sangbok, Kim, Myungsun
• Granted Patent: US 9,880,875 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 2209/483 Multiproc
• CPC Class Codes: G06F 2209/486 Scheduler internals
• CPC Class Codes: G06F 2209/509 Offload
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: Y02B 70/10 Technologies improving the efficiency by using switched-mode power supplies [SMPS], i.e. efficient power electronics conversion e.g. power factor correction or reduction of losses in power supplies or efficient standby modes
• CPC Class Codes: Y02D 10/00 Energy efficient computing, e.g. low power processors, power management or thermal management

Abstract

Provided are a method and apparatus for task scheduling based on hardware. The method for task scheduling in a scheduler accelerator based on hardware includes: managing task related information based on tasks in a system; updating the task related information in response to a request from a CPU; selecting a candidate task to be run next after a currently running task for each CPU on the basis of the updated task related information; and providing the selected candidate task to each CPU. The scheduler accelerator supports the method for task scheduling based on hardware.

Claims

1. A method for task scheduling in a scheduler accelerator based on hardware, the method comprising:

managing task related information based on tasks in a system;

updating the task related information in response to a request from a CPU;

selecting a candidate task to be run next after a currently running task for each CPU on the basis of the updated task related information; and

providing the selected candidate task to each CPU.

2. The method of claim 1, wherein the task related information comprises at least one of task/group pool information regarding all tasks in the system and groups of tasks, group information used to manage tasks ready to run, information on runtimes of individual tasks, or task status information regarding a currently running task and candidate task for each CPU.

3. The method of claim 2, wherein the group information is represented by bitmaps whose bits indicate ready-to-run states of all tasks and groups in the system.

4. The method of claim 1, wherein selecting a candidate task to be run next comprises:

finding ready-to-run tasks from the group information through bitmap operation; and

selecting a task with the shortest runtime from among the ready-to-run tasks as the candidate task.

5. The method of claim 4, wherein selecting a candidate task to be run next comprises:

checking whether the task selected as having the shortest runtime is a group;

determining, when the selected task is not a group, the selected task as the candidate task for each CPU; and

selecting, when the selected task is a group, a task with the shortest runtime from among tasks in the group as the candidate task.

6. The method of claim 2, wherein updating the task related information comprises updating, when the request from the CPU is a task creation request, the task/group pool information on the basis of a task ID contained in the task creation request.

7. The method of claim 2, wherein updating the task related information comprises:

updating, when the request from the CPU is a task enqueue request, bit information of the group information on the basis of a task ID contained in the task enqueue request;

checking whether the parent group of the task ID is the root group; and

updating, when the parent group is not the root group, bit information of the group information for the parent group, and checking whether the parent group is the root group.

8. The method of claim 2, wherein updating the task related information comprises:

updating, when the request from the CPU is a task dequeue request, bit information of the group information on the basis of a task ID contained in the task dequeue request;

checking whether no task in the parent group of the task ID is ready to run;

terminating, when at least one task in the parent group is ready to run, update of the group information; and

continuing, when no task in the parent group is ready to run, updating and checking until the parent group becomes the root group.

9. The method of claim 2, further comprising:

clearing, when the candidate task is selected by a CPU, the candidate task field of the task status information; and

selecting a new candidate task to update the candidate task field of the task status information.

10. The method of claim 4, wherein selecting a candidate task to be run next comprises:

checking whether the selected task has an affinity for a particular CPU; and

controlling, when the selected task has CPU affinity, a process of finding a task with the shortest runtime from among tasks having an affinity for the CPU, finding a task with the shortest runtime from among tasks without CPU-affinity, and selecting the one with a shorter runtime of the found tasks with CPU-affinity and without CPU-affinity as the candidate task.

11. A scheduler accelerator based on hardware for task scheduling, comprising:

an interface module configured to interwork with one or more CPUs; and

a task manager module configured to control a process for managing task related information based on tasks in a system, updating the task related information in response to a request from a CPU, selecting a candidate task to be run next after a currently running task for each CPU on the basis of the updated task related information, and providing the selected candidate task to each CPU.

12. The scheduler accelerator of claim 11, wherein the task related information comprises at least one of:

task/group pool information regarding all tasks in the system and groups of tasks, group information used to manage tasks ready to run, information on runtimes of individual tasks, or task status information regarding a currently running task and candidate task for each CPU.

13. The scheduler accelerator of claim 12, wherein the group information is represented by bitmaps including bits configured to indicate ready-to-run states of all tasks and groups in the system.

14. The scheduler accelerator of claim 11, wherein the task manager module is configured to control a process for finding ready-to-run tasks from the group information through bitmap operation, and selecting a task with the shortest runtime from among the ready-to-run tasks as the candidate task.

15. The scheduler accelerator of claim 14, wherein the task manager module is configured to control a process for checking whether the task selected as having the shortest runtime is a group, determining, when the selected task is not a group, the selected task as the candidate task for each CPU, and selecting, when the selected task is a group, a task with the shortest runtime from among tasks in the group as the candidate task.

16. The scheduler accelerator of claim 12, wherein, when the request from the CPU is a task creation request, the task manager module controls an operation to update the task/group pool information on the basis of a task ID contained in the task creation request.

17. The scheduler accelerator of claim 12, wherein, when the request from the CPU is a task enqueue request, the task manager module controls a process for updating bit information of the group information on the basis of a task ID contained in the task enqueue request, checking whether the parent group of the task ID is the root group, and updating, when the parent group is not the root group, bit information of the group information for the parent group and checking whether the parent group is the root group.

18. The scheduler accelerator of claim 12, wherein, when the request from the CPU is a task dequeue request, the task manager module controls a process for updating bit information of the group information on the basis of a task ID contained in the task dequeue request, checking whether no task in the parent group of the task ID is ready to run, terminating, when at least one task in the parent group is ready to run, update of the group information, and continuing, when no task in the parent group is ready to run, updating and checking until the parent group becomes the root group.

19. The scheduler accelerator of claim 12, wherein, when the candidate task is selected by a CPU, the task manager module controls a process for clearing the candidate task field of the task status information, and selecting a new candidate task to update the candidate task field of the task status information.

20. The scheduler accelerator of claim 14, wherein the task manager module is configured to check whether the selected task has an affinity for a particular CPU, and control, when the selected task has CPU affinity, a process for finding a task with the shortest runtime from among tasks having an affinity for the CPU, finding a task with the shortest runtime from among tasks without CPU-affinity, and selecting the one with a shorter runtime of the found tasks with CPU-affinity and without CPU-affinity as the candidate task.