Abstract:
A method, apparatus, and system for executing an application on a plurality of processing nodes within a heterogeneous computing environment associates a set of context-dependent procedures with each task to be performed and schedules a particular context-dependent procedure based on resource availability and needs. In certain embodiments, one are more tasks are organized into sequentially executed units of execution referred to as frames. The context-dependent procedures selected to perform each task within a frame may be selected to minimize the variance in resource utilization (such as processing time) within each frame. In one embodiment, a resource sufficiency test may be conducted for a selected procedure and the selected procedure may be scheduled for execution if the resource sufficiency test is affirmative.

Description:
RELATED APPLICATIONS  
       [0001]     The present application claims the benefit of U.S. Provisional Application No. 60/519,123, filed on Nov. 12, 2003. 
     
    
     FIELD OF THE INVENTION  
       [0002]     The present invention relates generally to data processing methods and systems. Specifically, the invention relates to methods and systems for simultaneously executing an application on multiple computers.  
       BACKGROUND  
       [0003]     Parallel processing remains an elusive goal in data processing systems. Although, many computational tasks are parallelizable, the complexity and inflexibility associated with parallel programming and execution techniques has restricted parallel execution to a few well-behaved problems such as weather forecasting and finite-element analysis. The complicated messaging and coordination mechanisms commonly used in parallel processing applications typically require that an application be rewritten for each execution environment. What is needed are methods and systems that enable parallel execution in a variety of execution environments.  
       SUMMARY OF THE INVENTION  
       [0004]     The present invention has been developed in response to the present state of the art, and in particular, in response to the problems and needs in the art that have not yet been fully solved by currently available parallel execution systems. Accordingly, the present invention has been developed to provide an improved method and system for executing applications in a heterogeneous computing environment that overcome many or all of the shortcomings in the art.  
         [0005]     In one aspect of the present invention, a method for executing an application on a plurality of processing nodes includes associating a set of context-dependent procedures with a task, each procedure in the set of context-dependent procedures capable of executing the task in at least one computing context, invoking a resource sufficiency test for a selected procedure of the plurality of procedures associated with a task, and scheduling the selected procedure for execution if the resource sufficiency test is affirmative.  
         [0006]     The context-dependent procedures selected for execution may be selected to balance resource utilization within a unit of execution known as a frame. In one embodiment, a resource consumption metric associated with each procedure indicates the estimated level of resource utilization required to execute the particular task. The resource consumption metric may be updated after actual execution of the procedure. For example, the resource consumption metric may be increased in response to slow execution, or decreased in response to fast execution.  
         [0007]     In certain embodiments, invoking a resource sufficiency test includes inspecting a resource pool and removing resources from the resource pool if sufficient resources are available to enable execution. If sufficient resources are not available, the method may select another procedure from the set of context-dependent procedures to execute the desired task. In one embodiment, the initially selected procedure for each task is a procedure with the highest resource consumption metric and various combinations of procedures are tested until a combination is found that is capable of performing the required tasks with the available resources.  
         [0008]     In some embodiments, tasks are assigned to various frames and the frames are used as loosely coupled units of execution within the computing environment. The tasks associated with a frame may be sequentially or concurrently executed subject to dependency constraints. In one embodiment, macroinstructions such as loop instructions, branch instructions, or end instructions may be associated with a frame in order to provide high-level flow control. In certain embodiments, a trigger may be associated with a frame that requires the occurrence of a specific event or condition before the tasks within the frame may be executed.  
         [0009]     The present invention provides a flexible framework for developing and executing applications within heterogeneous computing environments. Resource utilization is initially estimated and balanced and subsequently refined based on actual usage. Utilization of a wide variety of resources may be factored into the procedure selection process such as processing nodes, communications bandwidth, volatile storage, and non-volatile storage.  
         [0010]     In another aspect of the present invention an apparatus for performing the above-mentioned method includes an execution module comprising a plurality of context-dependent procedures capable of performing a task and a scheduler configured to execute a selected procedure of the plurality of context-dependent procedures. The scheduling module may also be configured to conduct a resource sufficiency test as a qualification for execution and schedule the selected procedure for execution if the resource sufficiency test is affirmative. In certain embodiments, the scheduler is configured to operate on frames that may have a trigger and/or macroinstruction associated therewith in order to provide high-level flow control within the deployed computing environment.  
         [0011]     The various elements and aspects of the present invention facilitate parallel execution of applications on a plurality of computational nodes within a heterogeneous computing environment. Applications may be re-deployed within a different environment with little or no development. These and other features and advantages of the present invention will become more fully apparent from the following description and appended claims, or may be learned by the practice of the invention as set forth hereinafter.  
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0012]     In order that the advantages of the invention will be readily understood, a more particular description of the invention briefly described above will be rendered by reference to specific embodiments that are illustrated in the appended drawings. Understanding that these drawings depict only typical embodiments of the invention and are not therefore to be considered to be limiting of its scope, the invention will be described and explained with additional specificity and detail through the use of the accompanying drawings, in which:  
         [0013]      FIG. 1  is a schematic block diagram depicting one example of computing environment wherein the present invention may be deployed;  
         [0014]      FIG. 2  is a block diagram depicting one embodiment of a parallel execution apparatus of the present invention; and  
         [0015]      FIG. 3  is a flow chart diagram depicting one embodiment of a parallel execution method of the present invention.  
     
    
     DETAILED DESCRIPTION OF THE INVENTION  
       [0016]     It will be readily understood that the components of the present invention, as generally described and illustrated in the Figures herein, may be arranged and designed in a wide variety of different configurations. Thus, the following more detailed description of the embodiments of the apparatus, method, and system of the present invention, as represented in  FIGS. 1 through 3 , is not intended to limit the scope of the invention, as claimed, but is merely representative of selected embodiments of the invention.  
         [0017]     Many of the functional units described in this specification have been labeled as modules, in order to more particularly emphasize their implementation independence. For example, a module may be implemented as a hardware circuit comprising custom VLSI circuits or gate arrays, off-the-shelf semiconductors such as logic chips, transistors, or other discrete components. A module may also be implemented in programmable hardware devices such as field programmable gate arrays, programmable array logic, programmable logic devices or the like.  
         [0018]     Modules may also be implemented in software for execution by various types of processors. An identified module of executable code may, for instance, comprise one or more physical or logical blocks of computer instructions which may, for instance, be organized as an object, procedure, or function. Nevertheless, the executables of an identified module need not be physically located together, but may comprise disparate instructions stored in different locations which, when joined logically together, comprise the module and achieve the stated purpose for the module.  
         [0019]     Indeed, a module of executable code could be a single instruction, or many instructions, and may even be distributed over several different code segments, among different programs, and across several memory devices. Similarly, operational data may be identified and illustrated herein within modules, and may be embodied in any suitable form and organized within any suitable type of data structure. The operational data may be collected as a single data set, or may be distributed over different locations including over different storage devices, and may exist, at least partially, merely as electronic signals on a system or network.  
         [0020]     Reference throughout this specification to “one embodiment” or “an embodiment” means that a particular feature, structure, or characteristic described in connection with the embodiment is included in at least one embodiment of the present invention. Thus, appearances of the phrases “in one embodiment” or “in an embodiment” in various places throughout this specification are not necessarily all referring to the same embodiment and the described features, structures, or characteristics may be combined in any suitable manner in one or more embodiments.  
         [0021]      FIG. 1  is a schematic block diagram depicting one example of a computing environment  100  wherein the present invention may be deployed. The depicted computing environment  100  includes a first computing environment  100   a  and a second computing environment  100   b  containing various computing systems and devices such as workstations  110  and servers  120  interconnect by local area networks  130 . A wide-area network  140 , such as the internet, interconnects the computing environments  100   a  and  10   b.    
         [0022]     The computing environment  100  may be a heterogenous computing environment that includes computing devices and systems of widely varying storage capacity, processing performance, and communications bandwidth. Many of the computing devices and systems (i.e. computing nodes) may sit idle for considerable periods of time. The present invention provides means and methods to harness the resources of computing networks and environments such as the computing environment  100 .  
         [0023]      FIG. 2  is a block diagram depicting one embodiment of a parallel execution node  200  of the present invention. As depicted, the parallel execution node  200  includes a scheduler  210 , one or more execution modules  230 , one or more execution contexts  250 , and a resource pool  270 . The depicted parallel execution node  200  enables coordinated parallel execution in a robust manner and may be deployed on a variety of processing devices and systems such as those depicted in  FIG. 1  in order to facilitate parallel execution of data processing tasks.  
         [0024]     The depicted scheduler  210  enables execution of one or more course-grained functions or tasks  215  as a unit of execution known as a frame  220 . The frames  220  are sequentially executed and may be loosely synchronized across a computing domain such as a grid. The tasks  215  within a frame may be sequentially or concurrently executed subject to any dependencies within the frame. Actual execution of the frame  220  may be deferred until (i.e. dependent on) occurrence of an event or condition referred to as a trigger  225 .  
         [0025]     The execution modules  230  contain application code in the form of invokable procedures  235  grouped into tasks  215 . Each procedure  235  grouped within a particular task  215  may be capable of completing the task  215  within a particular execution context  250 . The procedures  235  within an execution module  230  may also include procedures for partitioning and assembling datasets to enable parallel execution of specific tasks on multiple execution nodes  200 . The execution modules  230  may also include a module descriptor (not shown). In one embodiment, the module descriptor describes the procedures and associated datasets within the module including parameters and dependencies.  
         [0026]     In the depicted embodiment, each procedure  235  is associated with a computing context  240  that references a list of resources  245  needed to execute that particular procedure. In another embodiment, a resource allocation function (not shown) associated with the procedure  235  is invoked that determines whether sufficient resources are available in the resource pool  270  to execute the procedure. In certain embodiments, a usage meter or resource consumption metric  255  indicates the expected usage of resources for a procedure  235  and may be used to balance the usage of resources  245  by the various tasks within a frame. The resource consumption metric  255  may be updated after actual execution of the procedure. For example, the resource consumption metric  255  may be increased in response to slow execution, or decreased in response to fast execution.  
         [0027]     The present invention uses the frames as units of execution within a computing environment such as a heterogeneous network of servers and workstations. In certain embodiments, branching and flow control macroinstructions  275  may be associated with the frames  220  in order to enable high level programmability. Providing the macroinstructions  275  simplifies development of procedures in that many conditional situations may be ignored by the context-dependent procedures. Providing the macroinstructions  275  also enables code re-use in that many applications may be created by using macroinstructions to invoke previously developed tasks and procedures.  
         [0028]     The present invention provides a flexible framework for developing and executing applications within heterogeneous computing environments. Resource utilization is initially estimated and balanced and subsequently refined based on actual usage. Utilization of a wide variety of resources may be factored into the procedure selection process such as processing nodes, communications bandwidth, volatile storage, and non-volatile storage.  
         [0029]      FIG. 3  is a flow chart diagram depicting one embodiment of a parallel execution method  300  of the present invention. The depicted parallel execution method  300  includes developing  310  one or more context-dependent procedures, associating  320  one or more context-dependent procedures with each task, associating  330  one or more tasks with each frame, selecting  340  a context-dependent procedure and associated resources for each task in a frame, scheduling  350  a frame for execution, waiting  360  for a frame trigger, executing  370  a context-dependent procedure for each task in a frame, testing  380  for a last frame, and advancing  390  to a next frame. The depicted parallel execution method  300  enables balanced processing in heterogeneous computing environments. One of skill in the art will appreciate that the described processing steps may be accomplished in a manner appropriate for the platform on which it is deployed and need not be executed in the depicted order.  
         [0030]     Developing  310  one or more context-dependent procedures may include developing several different procedures each of which are capable of completing a task in a different computing context or environment. For example, one procedure may enable completion of a task on a single node, while another procedure may partition a task and enable completion on multiple nodes.  
         [0031]     Associating  320  one or more context-dependent procedures with each task provides the scheduler  210 , or the like, with one or more execution options for a particular task. Subsequently, associating  330  one or more tasks with each frame provides the scheduler  210  with convenient units of execution. In one embodiment, the tasks to be associated together and executed within a frame are selected by a programmer or system administrator based on their knowledge of system performance. In another embodiment, an optimizer groups tasks into frames.  
         [0032]     Selecting  340  a context-dependent procedure for each task in a frame may include assessing whether sufficient resourses are available to execute the context-dependent procedure. In certain embodiments, a usage meter or resource consumption metric indicates the expected usage of resources for a context-dependent procedure. In one embodiment, selecting  340  includes finding a combination of context-dependent procedures that provides the least variance in (expected) resource consumption including processing time. In another embodiment, a computing context identifier is specified by the application and the selected procedure is a procedure that is registered to execute the identified computing context.  
         [0033]     In certain embodiments, selecting  340  a context-dependent procedure includes inspecting a resource pool and removing resources from the resource pool if sufficient resources are available to enable execution. If sufficient resources are not available, the another procedure from the set of context-dependent procedures may be selected to execute the desired task. In one embodiment, the initially selected procedure for each task is a procedure with the highest resource consumption metric and various combinations of procedures are tested until a combination is found that is capable of performing the required tasks with the available resources.  
         [0034]     Scheduling  350  a frame for execution may include placing the frame in a pending execution queue (not shown). Waiting  360  for a frame trigger may include waiting for a specific event or condition. Subsequently, executing  370  may include invoking a context-dependent procedure for each task in a frame or placing a handle to each context-dependent procedure in an execution queue (not shown) or the like.  
         [0035]     Testing  380  for a last frame tests whether additional frames need to be processed. In one embodiment, testing  380  for a last frame includes ascertaining whether the current frame includes a macroinstruction such as a loop instruction, a branch instruction, or an end instruction. If the last frame has been processed the method ends  395 , otherwise, the method continues by advancing  390  to a selected frame such as a frame indicated by a macroinstruction.  
         [0036]     The present invention provides means and methods to schedule and execute applications (in parallel) on a plurality of computational nodes within a heterogeneous computing environment. The present invention eases the development and deployment of parallel execution applications. Applications may be redeployed within a different environment with little or no development.  
         [0037]     The present invention may be embodied in other specific forms without departing from its spirit or essential characteristics. The described embodiments are to be considered in all respects only as illustrative and not restrictive. The scope of the invention is, therefore, indicated by the appended claims rather than by the foregoing description. All changes which come within the meaning and range of equivalency of the claims are to be embraced within their scope.