Method for dynamic scheduling in a distributed environment

Abstract

A method and system is provided for assigning programs in a workflow to one or more nodes for execution. Prior to the assignment, a priority of execution of each program is calculated in relation to its dependency upon data received and transmitted data. Based upon the calculated priority and the state of each of the nodes, the programs in the workflow are dynamically assigned to one or more nodes for execution. In addition to the node assignment based upon priority, preemptive execution of the programs in the workflow is determined so that the programs in the workflow may not preemptively be executed at a selected node in response to the determination.

1 . A method for assigning resources to a plurality of processing nodes comprising: 
 deciding priority of execution dependency of a program;    dynamically assigning said program to a node based upon said priority and in accordance with a state of each node in a multinode system;    determining preemptive execution of said program; and    executing said program at a designated node non-preemptively in response to a positive determination.    
   
   
       2 . The method of  claim 1 , wherein said priority is based upon a criteria selected from a group consisting of: topological sorting method, and a shortest path length from a start program.  
   
   
       3 . The method of  claim 1 , wherein the step of deciding priority of execution dependency of a program includes normalizing said priority.  
   
   
       4 . The method of  claim 1 , wherein the step of deciding priority of execution dependency of a program includes assigning said program to a logical node based upon an estimated computation and transmission cost.  
   
   
       5 . The method of  claim 4 , further comprising storing said logical node assignment in a workflow database of a global scheduler based upon said estimated costs.  
   
   
       6 . The method of  claim 1 , wherein the step of dynamically assigning said program to a node includes assigning said program to a physical node at time of execution.  
   
   
       7 . The method of  claim 1 , wherein the step of dynamically assigning said program to a node includes assigning said program to a logical node based upon estimated computation and transmission costs.  
   
   
       8 . A system comprising: 
 a plurality of operating nodes;    a scheduling manager adapted to decide priority of execution dependency of a program;    a global scheduler adapted to dynamically assign said program to a node based upon said priority and a state of each node in said system; and    a program manager adapted to determine applicability of preemptive execution of said program, and to non-preemptively execute said program at a designated node in response to a positive determination.    
   
   
       9 . The system of  claim 8 , wherein said priority is based upon a criteria selected from a group consisting of: topological sorting method, and a shortest path length from a start program.  
   
   
       10 . The system of  claim 8 , wherein said scheduling manager is adapted to normalize said priority.  
   
   
       11 . The system of  claim 8 , wherein said scheduling manager is adapted to assign said program to a logical node based upon estimated computation and transmission costs.  
   
   
       12 . The system of  claim 11 , further comprising a workflow database adapted to store said logical node assignment based upon said estimated costs.  
   
   
       13 . The system of  claim 8 , wherein said global scheduler is adapted to assign said program to a physical node at time of execution.  
   
   
       14 . An article comprising: 
 a computer-readable signal-bearing medium;    a plurality of operating nodes in said medium;    means in said medium for deciding priority of execution dependency of a program;    means in said medium for dynamically assigning said program to one of said nodes based upon said priority and a state of each node in said system; and    means in said medium for determining applicability of preemptive execution of said program, and to non-preemptively execute said program at a designated node in response to a positive determination.    
   
   
       15 . The article of  claim 14 , wherein said medium is selected from a group consisting of: a recordable data storage medium, and a modulated carrier signal.  
   
   
       16 . The article of  claim 14 , wherein said means for deciding priority of execution dependency includes criteria selected from a group consisting of: topological sorting method, and a shortest path length from a start program.  
   
   
       17 . The article of  claim 14 , wherein said means for dynamically assigning said program to a node based upon said priority and a state of each node in said system normalizes priority of execution.  
   
   
       18 . The article of  claim 14 , wherein said means for deciding priority of execution dependency of a program includes assigning said program to a node based upon said priority and a state of each node in said system assigns said program to a logical node based upon estimated computation and transmission costs.  
   
   
       19 . The article  claim 18 , further comprising means in the medium for storing said logical node assignment based upon said estimated costs.  
   
   
       20 . The article of  claim 14 , wherein said means for dynamically assigning said program to one of said node based upon said priority and state of each node includes assigning said program to a physical node at time of execution.