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

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.

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;
• 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.