Classifications

• • G—PHYSICS
  • G06—COMPUTING OR CALCULATING; COUNTING
  • G06F—ELECTRIC DIGITAL DATA PROCESSING
  • G06F9/00—Arrangements for program control, e.g. control units
  • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
  • G06F9/44—Arrangements for executing specific programs
  • G06F9/448—Execution paradigms, e.g. implementations of programming paradigms
  • G06F9/4498—Finite state machines

Definitions

• the present system comprises a runtime environment for parallel computing and other high performance applications.
• Primary functions of the present system include storing, controlling, and running small run-time state- machine-associated programs called kernels.
• the system uses four interface methods: kernel management, algorithm management, kernel execution, and algorithm execution.
• Algorithms, kernels used in the algorithms, inputs to and outputs from the algorithms, and the number of computing nodes to be used in executing each step of each of the algorithms are initially defined.
• the algorithms and the kernels are added to respective libraries.
• a request for execution of one of the algorithms is received, and input datasets for the algorithm are transferred to the system.
• the requested algorithm is then executed to generate output data sets.
• Figure 2 is an exemplary illustration of a requester-system interaction
• Figure 3 is a flowchart showing an exemplary set of steps performed by the present system in executing an algorithm
• Figure 4 is an exemplary illustration of an HPC state machine.
• Figure 1 is an exemplary diagram showing high-level
• system 100 includes a processor 101 which, in operation, executes a kernel management module 110, an algorithm management module 105, a kernel execution module 130, and an Docket No.: 514405 algorithm execution module 125.
• System 100 further includes libraries 1 15 / 120 which respectively store algorithms 1 17 and kernels 122.
• System 100 is coupled to a host management system 145, which provides management of system functions, and issues system requests.
• Algorithm execution module 125 initiates execution of kernels invoked by algorithms that are executed.
• Algorithm execution system 135 may comprise any computing system with multiple computing nodes 140 which can execute kernels stored in system 100.
• Management system 145 can be any external client computer system which requests services from the present system 00. These services, which are described in detail below, include requesting that kernels or algorithms be added/changed/deleted from a respective library within the current system.
• the external client system can request that a
• kernel/algorithm be executed. It should be noted that the description of kernel and algorithm management and execution is merely exemplary, and the claimed system is not limited to the specific file names, formats and instructions
• a kernel is an executable computer program or program segment that contains data transformation/data code, and no program execution control code.
• Execution control code is any code that can change which code is to be executed next.
• kernels 122 are stored in a kernel library file 121 in kernel library 120.
• System 100 in an exemplary embodiment, provides kernel management to add, change or delete a kernel in a kernel library file 121 by adding, updating, or deleting the .DLL
• kernel management module 1 (Dynamic Linked Library) or .SO (Shared Object) library or other library file that contains the kernel of interest.
• references to "the system” in this section refer, in general, to system 100, and in applicable embodiments, refer more specifically to kernel management module 1 10.
• All kernel management messages sent from host system 145 to system 100 contain library and kernel information.
• the kernel information fields are Library Title and KerneMTitle.
• the system Upon completion of a management task, the system creates and sends a Return Status message containing completion Docket No.: 514405 status.
• the Status field contains a zero if the task was completed successfully or a non-zero if the task could not be completed.
• Kernels 122 are grouped with other kernels from the same originating organization and category in a kernel library file 121 which is created when the first kernel is added, and deleted when the last kernel is deleted.
• the name of the library file (Library_Title) is the concatenation of the organization and category names with a '_' character between them.
• the library is of file type .DLL, .SO, or other library file type, depending on the operating system which is used as a platform by the system.
• the Library_Title is the name of the library file that contains the kernel
• Kernel_Title is the name of the kernel to add.
• the Kernel_Add_Request message is defined below:
• the system determines if the library named Library_Title exists. Library existence is checked Docket No.: 514405 by comparing Library_Title to all library titles in the
• Kernel_Titles 162 stored in the Library_Kernel_Table 161.
• Non-existence of the kernel in the library causes the system to attempt to add the kernel to the kernel library file 121. Unsuccessful addition of the kernel to the library causes the system to generate and send the
• Library_Kernel_Table causes the system to remove the library and generate and send the Return_Status message containing a 22 (Kernel Add/Update Error) in its Status field to the requester.
• Library_Kernel_Table causes the system to attempt to reload the
• Kernel_Change_Request message When the system receives a Kernel_Change_Request message from management system 145, the system attempts to change an existing kernel Docket No.: 514405 in its library of kernels.
• the Library_Title is the name of the library file that contains the kernel, and Kernel_Title is the name of the kernel to add.
• Kernel_Change_Request message is defined below:
• the system determines if the Library_Title exists by comparing Library_Title to all Library_Titles in the Library_Kernel_Table_List. If the library does exist, the system determines if the kernel exists within the library by comparing the
• Kernel_Title to all Kernel_Titles stored in the Library Kernel table.
• Kernel_Title does not exist in the Library_Kernel_Table for the library, the system generates and sends the
• the system replaces the old kernel information with the information from the new kernel definition by replacing the contents of the Library_Title library file.
• Unsuccessful replacement of the library causes the system to generate and send the Return_Status message containing a 22 (Kernel Add/Update Error - library not replaced) in its Status field to the requester.
• Unsuccessful reload of the Library_Kernel_Table_Address for all kernels in the library causes the system to restore the prior contents of the library, remove the added kernel from the Library_Kernel_Table, and restore the address list of the Library_Kernel_Table. It then generates and sends the Return_Status message Docket No.: 514405 containing a 23 (Kernel Not Added/Changed Error - kernel not found in library) in its Status field to the requester.
• the system receives the Kernel_Delete_Request message from management system 145 and attempts to delete an existing kernel in its library of kernels.
• Kernel_Delete_Request is defined below:
• the system determines if the Library_Title exists by comparing Library_Title to all Library_Titles in the Library_Kernel_Table_List. If the library does exist, the system determines if the kernel exists within the library by comparing the
• Kernel_Title to all Kernel_Titles stored in the Library Kernel table.
• the system replaces the old kernel information with the information from the new kernel definition by replacing the contents of the Library_Title library file. Unsuccessful replacement of the library causes the system to generate and send the
• Successful library replacement causes the system to verify that the deleted kernel is not in the library. If the deleted kernel exists in the library, then the system restores the prior contents of the library, restore the deleted Kernel to the Library_Kernel_Table, and restore the address list of the
• Library_Kernel_Table causes the system to generate and send the
• Algorithm management allows the present system 100 to add, change, or delete an algorithm.
• An algorithm is a state machine that comprises states (kernel invocations) and state transitions (the conditions needed to go from one state to another). References to "the system” in this section refer in general to system 100, and in applicable embodiments, to algorithm management module 105.
• Each algorithm 1 17 is kept in an algorithm definition file 1 16 in algorithm library 115 with a name (Algorithm_Title) that is the concatenation of the organization name, the category name, algorithm name, and user name with a '_' character between each of the names.
• the '@' character in the user name is replaced with the string "_MPT_”.
• the Algorithm_Title is further concatenated with the string "_OWN”, “_POST”, or "_PUBLISH” depending upon where the kernel has been posted or published.
• the algorithm may exist in the OWN, Docket No.: 514405
• the file type of the file is ".MPT".
• Algorithm_Table 150 The Algorithm_Title is the name of the file that contains the algorithm to add.
• the Algorithm_Add_Request is defined below:
• the system Upon receipt of the Algorithm_Add_Request message, the system checks to see if the algorithm exists by comparing Algorithm_Title to all Algorithm_Titles 151 in the Algorithm_Table 150. Existence of the algorithm in the Algorithm table causes the system to generate and send the Return_Status message containing a 29 (Algorithm Already Exists Error) in its Status field to the requester.
• a 29 Algorithm Already Exists Error
• Non-existence of the algorithm in the Algorithm table causes the system to save the algorithm data to an algorithm definition file 116.
• Unsuccessful saving of the algorithm data to the algorithm definition file 1 16 in algorithm library 115 causes the system to generate and send the Return_Status message containing a 29 (Algorithm Already Exists Error) in its Status field to the requester.
• Algorithm_Change_Request When the system receives an Algorithm_Change_Request message, the system attempts to change the algorithm in the system algorithm title list 151 in the Algorithm_Table 150.
• the Algorithm_Title is the name of the file that contains the algorithm to change.
• the Algorithm_Change_Request message is defined below:
• the system Upon receipt of the Algorithm_Change_Request message, the system checks the existence of the algorithm by comparing Algorithm_Title to all Algorithm_Titles in the Algorithm_Table. Non-existence of the algorithm in the Algorithm_Table causes the system to generate and send the Return_Status message containing a 31 (Algorithm Does Not Exist Error) in its Status field to the requester.
• a 31 Algorithm Does Not Exist Error
• Unsuccessful change of the algorithm file contents causes the system to generate and send the Return_Status message containing a 32 (Algorithm Unsuccessfully Changed Error) in its Status field to the requester.
• Successful change of the algorithm file contents causes the system to generate and send the Return_Status message containing a zero in its Status field to the requester.
• Algorithm_Delete_Request When the system receives an Algorithm_Delete_Request message and the system attempts to delete the algorithm from the system Algorithm List.
• the Algorithm_Title is the name of the file that contains the algorithm to delete.
• the Algorithm_Delete_Request message is defined below:
• the system Upon receipt of the Algorithm_Change_Request message, the system checks for algorithm existence by comparing Algorithm_Title to all Algorithm_Titles in the Algorithm_Table. Non-existence of the algorithm causes the system to generate and send the Return_Status message containing a 31 (Algorithm Does Not Exist Error) in its Status field to the requester.
• FIG 2 is an exemplary illustration of requester 145 - system 100 interaction.
• Executing an algorithm means that the system accesses an algorithm 117 (contained in a respective algorithm definition file 1 16) in response to an 'execute' request, at step 201 , and executes the contained state machine until completion. The execution begins with the first state and continues through each required transition to new states until the completion state is executed or an error is encountered. Docket No.: 514405
• the system verifies that the algorithm exists in its Algorithm table.
• the system verifies all execution parameters. If either of these checks fails, the user is notified and the request rejected. This should be done before the investment is made to transfer all input data sets to the system.
• the input datasets need to be sent to the system in a reliable manner.
• the system requests each dataset from the requester.
• the datasets are transferred to dataset buffer 103 one at a time to ensure that unambiguous transfer is accomplished.
• the system requests each specified dataset from the execution requester (typically host management system 145) and completes receiving the dataset before moving to the next dataset. This procedure of inputting datasets is collectively shown by the series of steps indicated by brace 205.
• the system starts the execution of the algorithm.
• the algorithm execution continues until the final state of the algorithm is reached, an error is encountered, or the user cancels the execution.
• the system notifies the requester of the completion status of the execution.
• the requester may request the sending of the output datasets to the requester. This transfer is done in essentially the inverse of the way in which the input datasets are sent to the system.
• the requester sends a request for each dataset and the system responds with the dataset or a reason why it is unavailable, as indicated by the series of steps referenced by brace 210.
• a dataset may be unavailable when a requester cancels or when an error occurs during execution.
• the requester Once the requester has requested all desired datasets, at step 212 the requester notifies the system that it is finished and that the system can de-allocate all resources that were in use during algorithm execution, including all datasets and computing resources. Once the system has responded to this request, at step 214, the execution process is complete. Docket No.: 514405
• Algorithm_Execute_Request message is used for this task and is defined below:
• the system checks for Algorithm existence by comparing Algorithm_Title to all Algorithm_Titles in the Algorithm_Table. Non-existence of the algorithm causes the system to generate and send the Return_Status message containing a 31 (Algorithm Does Not Exist Error) in its Status field to the requester.
• the Dataset_Response message appears as follows:
• the requester If the dataset name is not recognized by the requester, the requester generates and sends the Dataset_Response message to the system with the Status field set to 56 (Dataset Name Not Recognized).
• the system If any error code is returned by the requester, the system generates and sends an Algorithm_Execution_Response message containing a 59 (Dataset Receive Failed) in its Status field and to the requester along with the status returned by the requester in the Error_Status_Supplemental field and the dataset name in the Error_Entity_Name field.
• 59 Dataset Receive Failed
• the system If the system cannot store the received dataset contents, the system generates and sends the Algorithm_Execution_Response message containing a 60 (Dataset Store Failed) in its Status field, the dataset name in the Error_Entity_Name field, and any system error code in the
• algorithm execution module 125 proceeds initiate the execution of the Algorithm on nodes 140 of algorithm execution system 135. Once execution completes for any reason, the system generates and sends the
• the supplemental error fields may contain additional information that may aid in determining the cause of the error. Additionally, the output dataset fields may also contain useful information.
• the requester may retrieve the output datasets from the system using the same protocol as the present system uses to retrieve the input datasets from the requester: Docket No.: 514405
• the requester generates and sends a Dataset_Request with the dataset_name set to the name of the dataset to be retrieved. If the dataset is not available (a dataset can be stored in dataset buffer 103 after execution and/or deleted after transmission to the user), the system generates and sends the Dataset_Response message with the status field set to 57 (Dataset Not
• the system If the dataset is available, the system generates and sends the Dataset_Response message with the status field set to 0 to the requester.
• the Dataset_Response is followed by the contents of the dataset.
• the requester may request any other dataset, particularly if the execution ended in failure. In this case, the system may respond with a 0 status and the dataset contents or may respond with the status field set to 57 (Dataset Not Available) to the requester.
• This message causes the system to terminate the execution job and release all resources, such as memory and datasets, associated with the job. Once all resources are released, the system generates and sends a
• Status_return message with the status set to 0 to the requester. If this message is received while the job is still running, the system generates and sends a Status_return message with the status set to 66 (Execute Still Running) to the requester. Other error status values are returned as appropriate.
• a kernel is always one state whereas an algorithm is always more than one state.
• An HPC (high performance computing) state machine effectively constitutes a set of 'states', each of which is a single kernel that contains compiled software and state-transitions (or state-vectors) which are the conditions under which control is transferred from one state to another.
• Executing a kernel means that the system executes a simple one-state algorithm that calls the kernel. Because of this, all messaging for dataset retrieval at job start and end as well as for job cancel and resource release appears and proceeds like the execution of an algorithm as indicated above. An exception to this is the Kernel_Execute_Request and
• Kernel_Execute_Response which is used in place of the
• Kernel_Execute_Request The format of the Kernel_Execute_Request is as follows:
• Kernel_Execute_Response The format of the Kernel_Execute_Response is as follows:
• An algorithm is defined herein to be a directly executable Finite State Machine containing a series of steps that are taken to complete a
• An algorithm definition is a parsable, unambiguous text description composed of more than one states.
• the algorithm definition is Docket No.: 514405 converted by algorithm management module 105 into a table or list containing index numbers, kernels, transition conditions and the index of a to-be- transitioned-to kernel. All characters in the definition are printable ASCII characters. While the state definitions of the algorithm are normally defined to be case insensitive, kernel identifiers (the identifiers of the kernels to be executed) are normally case sensitive. Line feeds, carriage returns and blank characters are ignored. State entries are separated by a semicolon and are comprised of four sub-sections - node count, input datasets, output datasets, and transitions. Although human readability is not required (the algorithm definition may be generated by management system 145 ), it can be accommodated within this format.
• StateNumber is an index for this state, giving the rest of the algorithm an index by which to refer to this state.
• the values of StateNumber should start at 1 and increment by one. It is never 0, as a next state of 0 indicates that execution has completed.
• the Kernelldentifer is the identifier of the kernel to run during this state. It is comprised of the Library_Title and the Kernel_Title of a kernel concatenated with a ':' character between them. It should correspond to the name of a dynamic library which contains the code for the kernel and the function name of the kernel.
• the Node Count subsection defines the number of nodes that are used to execute the kernel. It has the following format:
• the Min value denotes the minimum number of nodes that are used to run the kernel. This is usually 1. It may also be 0, which also means 1.
• the Opt value denotes the optimal number of nodes that are used to run the kernel. A value of 0 should be specified if there is no restriction or Docket No.: 514405 recommendation on the number of nodes to be used. A value of In may be specified if a division of the number of nodes specified by the user at run time is to be used. Likewise, a value of * n may be used for a multiple of the number of nodes specified by the user at run time.
• the Max value denotes the maximum number of nodes that are used to run the kernel. This is usually 0, which denotes to use the number of nodes specified by the user at run time. If a division or multiple of the number of nodes specified by the user at run time is desired, the same syntax may be used here as for the Opt value.
• the Input Datasets subsection defines the names of the input datasets that are used to execute the kernel. These names correspond to either a dataset that is an input to the algorithm or a dataset that is produced by the execution of a kernel in another state. The names are positionally dependent on the implementation of the kernel being executed and are separated by commas.
• the Output Datasets subsection defines the names of the output datasets that is produced when the kernel is executed. The names are
• the Transitions subsection defines the next state to be transitioned to after the execution of this kernel.
• the transitions are in a form of a pair of conditions and next_state indices separated by commas.
• the pairs are scanned from left to right and the processing stops when the first true condition is encountered.
• the state transitions to the corresponding next _state for that condition and all other condition/next_state pairs are ignored.
• next_state is used for the next state to be executed for the algorithm. If Docket No.: 514405 no condition is found to be true, the execution of the algorithm is declared to be complete.
• the dataset_name must correspond to either a dataset that is an input to the algorithm or a dataset that is produced by the execution of a kernel in another state. Multiple elements are accessed via the use of an index that is used as an offset into the database to find a particular element.
• the dataset_element_type is one of the following shown in Table
• next state is always the index of another state in the algorithm.
• a next state of 0 (zero) always indicates that the execution of the algorithm is complete.
• the above code is step 12 in the algorithm.
• the Kernelldentifier is:
• the kernel comes from the library (Library_Title) Shop_Tools (where the organization name is Shop and the category name is Tools).
• the Kernel_Title is ConvolveWithFilter_bob_MPT_Shop.com_POST , where the KernelName is ConvolveWithFilter which is owned by user bob@Shop.com.
• the kernel specified is the one in the posted state.
• the node count specifier says that at least one (1 ) node must be used; otherwise, there is no restriction on the number of compute nodes to use.
• the Input Dataset list has three members (datasets):
• the Output Dataset list has two members (datasets):
• the Transition has the following meaning:
• FIG. 3 is a flowchart summarizing an exemplary set of steps performed by the present system in executing an algorithm.
• a definition is provided for the Docket No.: 514405 kernels to be used, the names of the input datasets to be used, the names of output datasets to be generated, the next step to execute, and the number of nodes to be used to execute each kernel (or step), as described above.
• Kernels 122 to be executed are added to kernel library 120 at step 310, and algorithms 117 to be executed are added to algorithm library 1 15, at step 320.
• existence of the requested algorithm is verified, and the algorithm's execution parameters are verified, at respective steps 325 and 330.
• the algorithm is then transferred from algorithm library 1 15 to algorithm execution system 35 at step 333.
• step 335 the input datasets for the algorithm are transferred to algorithm execution system 135 one at a time, and at step 340, each state transition in the algorithm is evaluated and conditionally executed in order until the final state of the algorithm is reached. Prior to execution, each kernel invoked by the algorithm is transferred from kernel library 120 to the algorithm execution system 135. Finally, at step 345, algorithm completion status and all output data sets are returned to the requester.
• Table 6 is an example of an HPC algorithm definition / HPC State Machine:
• FIG. 4 is an exemplary illustration of an HPC state machine 401 in a system context. There are several differences between an HPC
• the state number (state #) is an index that identifies the row in the algorithm definition that holds the state. A zero state index indicates the last-state condition.
• the state is actually the library and kernel name that is to be executed, as indicated by arrow 403 in Figure 4.
• the Cluster Node is an index that identifies the row in the algorithm definition that holds the state. A zero state index indicates the last-state condition.
• the state is actually the library and kernel name that is to be executed, as indicated by arrow 403 in Figure 4.
• Allocation entry in the HPC state machine provides a way to dynamically specify the minimum, maximum, and optimal node count usable by the executed kernel.
• the ability to specify a node count means that, unlike a standard state machine, an HPC state machine is suited for parallel processing.
• Selection of the actual node count used is a function of the designated condition.
• the input and output variable lists consist of the memory address of the variable, the variable type and the number of dimensions associated with the variable. All variables used by a "Condition” must be either variables found in the input/output variable lists, constants, or a computed index value within a loop. This allows a state transition vector to access the required variables without needing to compile special codes into the source code of the kernel.
• a standard high performance computer system does not use a finite state machine (FSM) - it runs computer programs that have Message Passing Interface (MPI) functions embedded in that code. Adding MPI functions to standard software means changing that software and possibly injecting new bugs into it. Using the present method, parallel states can be injected into an FSM without recompiling or changing the original code.
• FSM finite state machine
• MPI Message Passing Interface
• a state transition In a standard state machine a state transition consists of a condition and a vector linking together two states.
• a condition can link together a state with multiple states (called a state list).
• Each state in the state list is executed on a separate node, as indicated by arrows 405 and 406 in Figure 4.
• Each node can have a single or multiple processors, and/or single or multiple cores, which means that multiple parallel threads on multiple machines can be spawned from a single transition.
• To collapse back down to a single node the special transition called "Collapse" is used. This transitions both 'collapses' down to a single node and transitions to a new state.
• a loop allows a transition to efficiently call itself, initialize and calculate an index value, and then transition to one or more new states.

Landscapes

• Engineering & Computer Science (AREA)
• Software Systems (AREA)
• Theoretical Computer Science (AREA)
• Physics & Mathematics (AREA)
• General Engineering & Computer Science (AREA)
• General Physics & Mathematics (AREA)
• Multi Processors (AREA)
• Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
• Stored Programmes (AREA)

Applications Claiming Priority (2)

Publications (2)

Family

ID=45605663

Family Applications (1)

Country Status (3)

Families Citing this family (7)

Family Cites Families (9)

• 2011
  • 2011-08-17 EP EP11818745.9A patent/EP2606424A4/de not_active Withdrawn
  • 2011-08-17 JP JP2013524967A patent/JP2013534347A/ja active Pending
  • 2011-08-17 WO PCT/US2011/048134 patent/WO2012024435A2/en not_active Ceased

Also Published As

Similar Documents

Legal Events