Method and apparatus for dynamic resource allocation of processing units on a resource allocation plane having a time axis and a processing unit axis

Patent metadata

Field	Value
Publication number	US-9311157-B2
Application number	US-201113246323-A
Country	US
Kind code	B2
Filing date	Sep 27, 2011
Priority date	Sep 27, 2010
Publication date	Apr 12, 2016
Grant date	Apr 12, 2016

Abstract

A method and apparatus for dynamic resource allocation in a system having at least one processing unit are disclosed. The method of dynamic resource allocation includes receiving information on a task to which resources are allocated and partitioning the task into one or more task parallel units; converting the task into a task block having a polygonal shape according to expected execution times of the task parallel units and dependency between the task parallel units; allocating resources to the task block by placing the task block on a resource allocation plane having a horizontal axis of time and a vertical axis of processing units; and executing the task according to the resource allocation information. Hence, CPU resources and GPU resources in the system can be used in parallel at the same time, increasing overall system efficiency.

First claim

What is claimed is:

1. A method of dynamic resource allocation for a system having a plurality of processing units as resources, the method comprising the steps of:
receiving information on a task to which the resources are to be allocated;
partitioning the task into a plurality of parallel task units;
converting the plurality of parallel task units into at least one task block;
setting the task block having a shape that is formed based on estimated execution times of the plurality of parallel task units and whether dependency exists between the plurality of parallel task units in the task block;
allocating the resources to the task block by placing the task block on a resource allocation plane having a horizontal time axis and a vertical processing unit axis,
wherein allocating the resources to the task block comprises:
performing horizontal movement of the task block on the resource allocation plane by moving the task block to a position having a smallest time value along a topmost of the plurality of processing units on the vertical processing unit axis while not conflicting with any existing task blocks on the resource allocation plane;
performing vertical movement by moving the task block down the vertical processing unit axis to coordinates that do not conflict with any existing task blocks on the resource allocation plane; and
determining whether the horizontal movement and the vertical movement have been performed for all of the plurality of processing units of the system; and

executing the plurality of parallel task units included in the task block according to the allocated resources.

2. The method of claim 1 , wherein allocating the resources to the task block further comprises:
when the horizontal movement and the vertical movement have not been performed for all of the plurality of processing units, repeating performance of the horizontal movement and the vertical movement until the horizontal movement and the vertical movement have been performed for all of the plurality of processing units; and
when the horizontal movement and the vertical movement have been performed for all processing units, placing the task block at a position on the resource allocation plane having the smallest time value.

3. The method of claim 2 , further comprising, when a new task is received after executing the task, allocating the resources to the new task on the resource allocation plane by repeating the horizontal movement and the vertical movement for the new task.

4. The method of claim 2 , further comprising, when processing of a task block to which the resources are already allocated ends earlier than its estimated execution time, allocating the resources to a new task on the resource allocation plane and repeating the horizontal movement and the vertical movement for all remaining task blocks on the resource allocation plane.

5. The method of claim 1 , wherein the plurality of processing units comprises one of a core of a Central Processing Unit (CPU) and a processing element of a Graphics Processing Unit (GPU).

6. The method of claim 1 , wherein the shape of the task block comprises a first polygon with a right angle for all angles, if no dependency is present between the plurality of parallel task units, and
wherein the shape of the task block comprises a second polygon with a non-right angle for at least one angle, if dependency is present between the plurality of parallel task units.

7. The method of claim 6 , wherein a slope of the second polygon is determined based on an amount of dependency between the plurality of parallel task units.

8. An apparatus for dynamic resource allocation in a system having a plurality of processing units as resources, the apparatus comprising:
a dynamic resource allocation block that receives information on a task to which the resources are to be allocated, partitions the task into a plurality of parallel task units, converts the plurality of parallel task units into at least one task block, set the task block having a shape that is formed based on estimated execution times of the plurality of parallel task units and whether dependency exists between the plurality of parallel task units in the task block, and allocates the resources to the task block by placing the task block on a resource allocation plane having a horizontal time axis and a vertical processing unit axis,
wherein the dynamic resource allocation block allocates the resources to the task block by:
performing horizontal movement of the task block on the resource allocation plane by moving the task block to a position having a smallest time value along a topmost of the plurality of processing units on the vertical processing unit axis while not conflicting with any existing task blocks on the resource allocation plane,
performing vertical movement by moving the task block down the vertical processing unit axis to coordinates that do not conflict with any existing task blocks on the resource allocation plane, and
determining whether the horizontal movement and the vertical movement have been performed for all of the plurality of processing units of the system; and

at least one hardware processing unit that executes the plurality of task units included in the task block according to the allocated resources.

9. The apparatus of claim 8 , wherein the dynamic resource allocation block repeats the horizontal movement and the vertical movement when the horizontal movement and the vertical movement have not been performed for all of the plurality of processing units, and places the task block at a position on the resource allocation plane having the smallest time value when the horizontal movement and the vertical movement have been performed for all of the plurality of processing units.

10. The apparatus of claim 9 , wherein the dynamic resource allocation block allocates the resources to a new task on the resource allocation plane by repeating the horizontal movement and the vertical movement for the new task, when the new task is received after executing the task.

11. The apparatus of claim 9 , wherein the dynamic resource allocation block allocates the resources to a new task on the resource allocation plane and repeats the horizontal movement and the vertical movement for all remaining task blocks on the resource allocation plane, when processing of a task block to which the resources are already allocated ends earlier than its estimated execution time after executing the task.

12. The apparatus of claim 8 , wherein the at least one hardware processing unit comprises one of a core of a Central Processing Unit (CPU) and a processing element of a Graphics Processing Unit (GPU).

13. The apparatus of claim 8 , wherein the shape of the task block comprises a first polygon with a right angle for all angles, if no dependency is present between the plurality of parallel task units, and
wherein the shape of the task block comprises a second polygon with a non-right angle for at least one angle, if dependency is present between the plurality of parallel task units.

14. The apparatus of claim 13 , wherein a slope of the second polygon is determined based on an amount of dependency between the plurality of parallel task units.

15. An article of manufacture for dynamic resource allocation for a system having a plurality of processing units as resources, comprising a non-transitory machine readable medium containing one or more programs which when executed implement the steps of:
receiving information on a task to which the resources are to be allocated;
partitioning the task into a plurality of parallel task units;
c

Assignees

• Kim Kyoung Hoon
• Yeo In Choon
• Lee Seung Wook
• Kim Joong Baik
• Lee Il Ho
• Song Jeong Ig
• Samsung Electronics Co Ltd

Inventors

• Kim Kyoung Hoon
• Yeo In Choon
• Lee Seung Wook
• Kim Joong Baik
• Lee Il Ho
• Song Jeong Ig

Classifications

• G06F9/5066 Primary

  Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs (mappping at compile time, see G06F8/451) · CPC title

• G06F2209/5017

  Task decomposition · CPC title