Sub-task processor distribution scheduling

Abstract

A method for processing of processor executable tasks and a processor readable medium having embodied therein processor executable instructions for implementing the method are disclosed. A system for distributing processing work amongst a plurality of distributed processors is also disclosed. A task generated with a local node is divided into one or more sub-tasks. An optimum number of nodes x on which to process the sub-tasks is determined If x is greater than one a determination is made to either (1) execute the task at the local node with the processor unit, (2), distribute the task among two or more local node processors, (3) distribute the task to one or more of the distributed nodes accessible to the local node over a LAN, or (4) distribute the task to one or more of the distributed nodes that are accessible to the local node over a WAN.

1 . A method for processing of processor executable tasks, comprising:
 generating a task with a local node, wherein the local node includes one or more processor units operably coupled to one or more distributed nodes;   dividing the task into one or more sub-tasks;   determining an optimum number of nodes x on which to process the one or more sub-tasks, wherein x is based at least partly on parameters relating to processing the sub-tasks at nodes accessible by the local node; and   if x is greater than one, based on the value of x, making a determination as to whether to (1) execute the task at the local node with the processor unit, (2), distribute the task among two or more local node processors, (3) distribute the task to one or more of the distributed nodes accessible to the local node over a LAN, or (4) distribute the task to one or more of the distributed nodes that are accessible to the local node over a WAN; and   implementing (1), (2), (3), or (4) with the local node according to the determination.   
   
   
       2 . The method of  claim 1 , further comprising distributing the sub-tasks to x nodes for processing. 
   
   
       3 . The method of  claim 2 , further comprising retrieving output data for the sub-tasks from the x nodes. 
   
   
       4 . The method of  claim 1 , further comprising collecting the parameters relating to processing the sub-tasks. 
   
   
       5 . The method of  claim 4 , further comprising storing the parameters in a data storage medium that is accessible by the local node. 
   
   
       6 . The method of  claim 4 , wherein the parameters include one or more of a number of available nodes, data transfer rates between the local node and one or more distributed nodes, round trip times between the local node and one or more distributed nodes, a number processor cycles for each sub-task, an amount of memory space required for each sub-task, an amount of storage space required for each sub-tasks, and a network bandwidth available for transmitting data related to the sub-tasks. 
   
   
       7 . The method of  claim 1  wherein determining the optimum number of nodes x is based on a minimum effective execution time (EET) for the task. 
   
   
       8 . The method of  claim 7  wherein the EET is calculated by a formula of the type: 
     
       
         
           
             
               EET 
               ≈ 
               
                 
                   
                     f 
                      
                     
                       ( 
                       
                         x 
                         , 
                         TS 
                         , 
                         CS 
                       
                       ) 
                     
                   
                   
                     BW 
                     o 
                   
                 
                 + 
                 
                   ET 
                   x 
                 
                 + 
                 
                   RS 
                   
                     BW 
                     i 
                   
                 
                 + 
                 RTT 
               
             
             , 
           
         
       
       where ET represents an execution time of all sub-tasks on one node, 
       TS represents a total size of data which is divided among the sub-tasks, 
       CS represents a constant sized data needed by each sub-task, 
       RS represents a total size of output data produced by the tasks 
       BW o , BW i  respectively represent outgoing and incoming bandwidths for all nodes, and 
       RTT represents a round-trip message time from the local node to a distributed node. 
     
   
   
       9 . The method of  claim 1  wherein x is based on an execution time of all tasks on one node (ET) and a round-trip message time (RTT) from the local node to a distributed node. 
   
   
       10 . The method of  claim 9  wherein the determination of x is based on a ratio of ET to RTT. 
   
   
       11 . The method of  claim 1  wherein determining the optimum number of nodes x includes a consideration of additional metrics. 
   
   
       12 . The method of  claim 11  wherein the consideration of the additional metrics include determining a cost of processing the sub-tasks. 
   
   
       13 . The method of  claim 12  wherein determining the cost of processing the sub-tasks includes determining a cost per node. 
   
   
       14 . The method of  claim 13  wherein determining the cost per node includes determining an amount of bandwidth or execution time used on each distributed node. 
   
   
       15 . The method of  claim 13  wherein determining the cost per node is based on one or more of the number of nodes x, a desired quality of service, an amount of constant sized data, a cost of transmission and a cost of usage. 
   
   
       16 . The method of  claim 13  wherein determining a cost of processing the sub-tasks includes obtaining a cost from a look-up table of costs from providers. 
   
   
       17 . The method of  claim 13  wherein determining a cost of processing the sub-tasks includes the use of a liquid capital market in which providers bid for customers. 
   
   
       18 . The method of  claim 11  wherein the additional metrics include one or more user defined policies. 
   
   
       19 . The method of  claim 1  wherein each sub-tasks is characterized by a sub-task type, wherein the sub-task type distinguishes one type of sub-task from another and/or provides information for determining the optimum number of nodes x. 
   
   
       20 . The method of  claim 1 , further comprising determining the contents of caches associated with one or more distributed nodes. 
   
   
       21 . The method of  claim 20 , further comprising preferentially distributing sub-tasks to nodes having code and/or data needed for processing the sub-task. 
   
   
       22 . A system for distributing processing work amongst a plurality of distributed nodes, the system comprising:
 a local node connected to the plurality of distributed nodes, wherein the local node includes one or more processor units;   processor executable instructions embodied in a processor readable storage medium for execution by the one or more processor units, the instructions including:
 one or more instructions for generating a task with the local node; 
 one or more instructions for dividing the task into one or more sub-tasks; 
 one or more instructions for determining an optimum number of nodes x on which to process the one or more sub-tasks, wherein x is based at least partly on parameters relating to processing the sub-tasks at nodes accessible by the local node; and 
 one or more instructions for determining, if x is greater than 1, based on the value of x, making a determination as to whether to (1) execute the task at the local node with the processor unit, (2), distribute the task among two or more local node processors, (3) distribute the task to one or more of the distributed nodes that are accessible to the local node over a LAN, or (4) distribute the task to one or more of the distributed nodes that are accessible to the local node over a WAN; and 
 one or more instructions for implementing (1), (2), (3), or (4) with the local node according to the determination. 
   
   
   
       23 . The system of  claim 22 , further comprising a memory coupled to the local node. 
   
   
       24 . The system of  claim 23 , further comprising information relating to the parameters stored in the memory. 
   
   
       25 . The system of  claim 22  wherein the parameters include one or more of a number of available nodes, data transfer rates between the local node and one or more other nodes, round trip times between the local node and one or more other nodes, a number processor cycles for each sub-task, an amount of memory space required for each sub-task, an amount of storage space required for each sub-tasks, and a network bandwidth available for transmitting data related to the sub-tasks. 
   
   
       26 . The system of  claim 22 , wherein the processor executable instructions further include an instruction for collecting the parameters from the distributed nodes. 
   
   
       27 . The system of  claim 26 , further comprising a memory coupled to the local node, the processor executable instructions including one or more instructions for storing the parameters in the memory. 
   
   
       28 . The system of  claim 27 , wherein the processor executable instructions include one or more instructions for updating the parameters in the memory. 
   
   
       29 . The system of  claim 22 , wherein the processor executable instructions include one or more instructions for determining x based on a minimum effective execution time (EET). 
   
   
       30 . The system of  claim 29  wherein the EET is calculated by a formula of the type: 
     
       
         
           
             
               EET 
               ≈ 
               
                 
                   
                     f 
                      
                     
                       ( 
                       
                         x 
                         , 
                         TS 
                         , 
                         CS 
                       
                       ) 
                     
                   
                   
                     BW 
                     o 
                   
                 
                 + 
                 
                   ET 
                   x 
                 
                 + 
                 
                   RS 
                   
                     BW 
                     i 
                   
                 
                 + 
                 RTT 
               
             
             , 
           
         
       
       where ET represents an execution time of all tasks on one node, 
       TS represents a total size of data which is divided among the sub-tasks, 
       CS represents a constant sized data needed by each sub-task, 
       RS represents a total size of output data produced by the tasks 
       BW o , BW i , respectively represent outgoing and incoming bandwidths for all processor nodes, and 
       RTT represents a round-trip message time from the local node to a node accessible by the local node. 
     
   
   
       31 . The system of  claim 22  wherein x is based on an execution time of all tasks on one node (ET) and a round-trip message time (RTT) from the local node to a node accessible by the local node. 
   
   
       32 . The system of  claim 31  wherein the determination of x is based on a ratio of ET to RTT. 
   
   
       33 . The system of  claim 22  wherein x is based on one or more additional metrics. 
   
   
       34 . The system of  claim 33  wherein the additional metrics include a cost of processing the sub-tasks and/or one or more user-defined policies. 
   
   
       35 . The system of  claim 22  wherein each sub-tasks is characterized by a sub-task type, wherein the sub-task type distinguishes one type of sub-task from another and/or provides information for determining the optimum number of nodes x. 
   
   
       36 . A processor readable storage medium having embodied therein processor executable instructions for implementing a method for processing of processor executable tasks, the instructions including:
 one or more instructions for generating a task with a local node, wherein the local node includes one or more processor units;   one or more instructions for dividing the task into one or more sub-tasks;   one or more instructions for determining an optimum number of nodes x on which to process the one or more sub-tasks, wherein x is based at least partly on parameters relating to processing the sub-tasks at nodes accessible by the local node; and   one or more instructions for determining, if x is greater than 1, based on the value of x, whether to (1) execute the task at the local node with the processor unit, (2), distribute the task among two or more local node processors, (3) distribute the task to one or more of the distributed nodes that are accessible to the local node over a LAN, or (4) distribute the task to one or more of the distributed nodes that are accessible to the local node over a WAN; and   one or more instructions for implementing (1), (2), (3), or (4) with the local node according to the determination.