Patent ID: 7930339
Filing Date: 2011-04-19
Classification: A63F,G06F

Abstract:
1. A task allocation method for allocating a plurality of tasks, which include those tasks that are dependent on each other, to respective nodes in communication with one another in a distributed processing system, each node provided with at least one processor, the method comprising: determining antecedent dependency between the plurality of tasks; obtaining respective time constraints imposed on the plurality of tasks; computing an absolute earliest start time at which one or more of the plurality of tasks can be started and an absolute latest start time allowed in order to complete the one or more tasks within the respective time constraints imposed on the plurality of tasks; computing respective task movable ranges for the one or more tasks based on a subtraction of the absolute earliest start times from respective absolute latest start times for the one or more tasks; selecting initially a group of tasks having smaller task movable ranges from the one or more tasks, for allocation to the respective nodes within the distributed processing system; selecting at least one task from the group of tasks for allocation to at least one destination node based on the determined dependency when all tasks within the group of tasks have same task movable range wherein the at least one task has a longer data communication time with a precedent or a descendant task; allocating the at least one task to the destination node among the nodes of the distributed processing system, giving priority to those tasks having smaller task movable ranges wherein, if a plurality of target tasks have a same data communication time to communicate with the descendant task, allocating the target task to the destination node on a priority basis based on the absolute earliest start time of a most important descendant task descendant from the target task, the most important descendant task being a task with the smallest absolute earliest start time.