Methods and apparatus for analytical processing of provenance data for HPC workflow optimization

Patent metadata

Field	Value
Publication number	US-10013656-B1
Application number	US-201414580732-A
Country	US
Kind code	B1
Filing date	Dec 23, 2014
Priority date	Dec 23, 2014
Publication date	Jul 3, 2018
Grant date	Jul 3, 2018

Abstract

Methods and apparatus are provided for analytical processing of provenance data for High Performance Computing workflow optimization. Prediction models for a workflow composed of a plurality of activities are created by (i) generating a plurality of prediction functions from input features and output features of the workflow, wherein each of the prediction functions predicts at least one output feature of at least one of activities of the workflow based on the input features of at least one activity; and (ii) combining the plurality of prediction functions to generate the prediction models, wherein each of the prediction models predicts a final output feature of the workflow based on an input of the workflow for a given execution plan of the workflow. A plurality of the prediction models can be evaluated to select, among the possible execution plans, an instantiation of the workflow for a given input that optimizes a given user goal.

First claim

What is claimed is:

1. A method for generating one or more prediction models for a workflow composed of a plurality of activities, comprising:
extracting one or more input features from input data from a plurality of previous executions of said plurality of activities and extracting one or more output features from output data from said plurality of previous executions of said plurality of activities, wherein said plurality of activities execute in one or more computing devices;
automatically learning, using at least one processing device, a plurality of prediction functions from one or more input features and one or more output features of said workflow, wherein each of said prediction functions predicts at least one of said output features of at least one of said plurality of activities of said workflow based on one or more of said input features of said at least one activity of said workflow;
selecting, using said at least one processing device, one of said plurality of prediction functions for each of said plurality of activities in said workflow based on a particular goal and a succession of said plurality of activities according to a definition of said workflow to generate a selected subset of prediction functions;
combining, using said at least one processing device, said selected subset of said plurality of prediction functions to generate said one or more prediction models based on the succession of said plurality of activities according to the definition of said workflow, wherein each of said one or more prediction models predicts a final output feature of said workflow based on one or more of said input features extracted from one or more initial inputs of said workflow; and
selecting an instantiation of said workflow for a given input and said particular goal by evaluating a plurality of said one or more prediction models.

2. The method of claim 1 , wherein said one or more input features and said one or more output features are extracted from one or more of input data, output data, execution data and provenance data of said workflow.

3. The method of claim 2 , wherein said one or more input features and said one or more output features comprise features from within one or more files referenced by said provenance data.

4. The method of claim 1 , wherein one or more of said input features and said output features are extracted using one or more file format cartridges.

5. The method of claim 1 , wherein said plurality of activities of said workflow are specified by a user, and wherein said user further specifies one or more data dependencies between said plurality of activities and an association of one or more input features of at least one activity with one or more output features of at least one prior activity.

6. The method of claim 1 , wherein each of said one or more prediction models predicts a final output feature of said workflow for a given execution plan of said workflow.

7. The method of claim 1 , wherein said one or more output features of a given activity are propagated through said workflow as one or more input features of one or more activities following said given activity of said workflow.

8. The method of claim 1 , wherein said instantiation of said workflow is selected by evaluating a prediction model representing said particular goal.

9. The method of claim 1 , wherein said instantiation of said workflow is selected for said given input and said particular goal subject to one or more additional constraints.

10. The method of claim 1 , wherein at least one parameter of one or more of a program and of one or more execution engines related to said workflow is unspecified, and wherein a value for said at least one unspecified parameter is selected to instantiate the workflow for said given input and said particular goal.

11. The method of claim 1 , further comprising the step of repeating said steps of automatically learning a plurality of prediction functions and combining said plurality of prediction functions to regenerate said one or more prediction models based on new provenance data.

12. A computer program product comprising a non-transitory machine-readable storage medium having encoded therein executable code of one or more software programs, wherein the one or more software programs when executed perform the following steps:
extracting one or more input features from input data from a plurality of previous executions of said plurality of activities and extracting one or more output features from output data from said plurality of previous executions of said plurality of activities, wherein said plurality of activities execute in one or more computing devices;
automatically learning, using at least one processing device, a plurality of prediction functions from one or more input features and one or more output features of said workflow, wherein each of said prediction functions predicts at least one of said output features of at least one of said plurality of activities of said workflow based on one or more of said input features of said at least one activity of said workflow;
selecting, using said at least one processing device, one of said plurality of prediction functions for each of said plurality of activities in said workflow based on a particular goal and a succession of said plurality of activities according to a definition of said workflow to generate a selected subset of prediction functions;
combining, using said at least one processing device, said selected subset of said plurality of prediction functions to generate said one or more prediction models based on the succession of said plurality of activities according to the definition of said workflow, wherein each of said one or more prediction models predicts a final output feature of said workflow based on one or more of said input features extracted from one or more initial inputs of said workflow; and
selecting an instantiation of said workflow for a given input and said particular goal by evaluating a plurality of said one or more prediction models.

13. A system for generating one or more prediction models for a workflow comprised of a plurality of activities, comprising:
a memory; and
at least one hardware device, coupled to the memory, operative to implement the following steps:
extracting one or more input features from input data from a plurality of previous executions of said plurality of activities and extracting one or more output features from output data from said plurality of previous executions of said plurality of activities, wherein said plurality of activities execute in one or more computing devices;
automatically learning, using at least one processing device, a plurality of prediction functions from one or more input features and one or more output features of said workflow, wherein each of said prediction functions predicts at least one of said output features of at least one of said plurality of activities of said workflow based on one or more of said input features of said at least one activity of said workflow;
selecting, using said at least one processing device, one of said plurality of prediction functions for each of said plurality of activities in said workflow based on a particular goal and a succession of said plurality of activities according to a definition of said workflow to generate a selected subset of prediction functions;
combining, using said at least one processing device, said selected subset of said plurality of prediction functions to generate said one or more prediction models based on the succession of said plurality of activities according to the definition of said workflow, wherein each of said one or more predi

Assignees

• Emc Ip Holding Co Llc

Inventors

• Ciarlini Angelo E M
• Dias Jonas F
• Salas Percy E Rivera

Classifications

• G06N5/01

  Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound · CPC title

• G06F9/453

  Help systems · CPC title

• G06N20/00 Primary

  Machine learning · CPC title

• G06F9/5038

  considering the execution order of a plurality of tasks, e.g. taking priority or time dependency constraints into consideration (scheduling strategies G06F9/4881 and subgroups) · CPC title

• G06N5/04 Primary

  Inference or reasoning models · CPC title