METHOD, SYSTEM, AND COMPUTER PROGRAM PRODUCT FOR OPTIMIZING RUNTIME BRANCH SELECTION IN A FLOW PROCESS

• US 20100115251A1
• Filed: 11/04/2008
• Published: 05/06/2010
• Est. Priority Date: 11/04/2008
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Hulse, Brian, Jackson, Callum P., Watkinson, Amanda J., Phippen, Robert W., Parkinson, Ian W., Kalus, Christopher
• Granted Patent: US 8,984,259 B2
• Time in Patent Office: Days
• US Class Current: 712/234
• CPC Class Codes: G06F 2209/508 Monitor
• CPC Class Codes: G06F 9/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

Abstract

A method, system, and computer program product for optimizing runtime branch selection in a flow process are provided. The method includes gathering performance metrics of flow branch behavior for executed flows in a runtime system over time and using aggregated performance metrics for the behavior to determine an optimal ordering of branches for a currently running flow. The optimal ordering is determined by identifying one or more branch points in the flow, generating ordering permutations for at least a portion of the branches in the branch point for the flow to identify any permutations that have not been executed, gathering metrics for permutation(s) of the branch point in the flow, comparing the metrics to performance metrics of executed flows having substantially similar flow branch behavior, and identifying optimal branch ordering for the permutation(s) based upon the comparison. The method also includes executing the flow according to the optimal branch ordering.

Claims

1. A method for optimizing runtime branch selection in a flow process, comprising:

gathering and storing performance metrics of flow branch behavior for executed flows in a runtime system over a period of time;

using aggregated performance metrics for the flow branch behavior to determine an optimal ordering of branches for a currently running flow, comprising;

identifying at least one branch point in the currently running flow, the branch point having two or more branches;

generating ordering permutations for at least a portion of the branches in the branch point for the currently running flow to identify any permutations that have not been executed;

gathering metrics for at least one permutation of the branch point in the currently running flow;

comparing the metrics to performance metrics of executed flows having substantially similar flow branch behavior; and

identifying optimal branch ordering for the permutation based upon the comparison; and

executing the flow according to the optimal branch ordering.

2. The method of claim 1, wherein the optimal branch ordering is determined by identifying a permutation from the stored performance metrics that, based upon past executions, is determined to execute faster than other permutations from the stored performance metrics or is determined to use fewer resources to complete than other permutations from the stored performance metrics.

3. The method of claim 2, wherein gathering the metrics includes gathering load values that reflect time spent completing a flow branch;

wherein an average load value is calculated by averaging load values for multiple activated flow branches.

4. The method of claim 2, wherein gathering the metrics includes identifying common branches taken in a flow.

5. The method of claim 1, further comprising:

updating the stored performance metrics with statistical data reflecting execution of the flow using the optimal branch ordering.

6. The method of claim 1, wherein the permutation indicates a path of the branch point and reflects a particular sequence of tasks in the flow.

7. A method for optimizing runtime branch selection in a statically-configured flow process, comprising:

identifying flow branch behavior for flows in a runtime system, the flow branch behavior including locations in a flow where clones are taken; and

reducing the number of clones otherwise created at runtime by selecting any branches that, upon execution, would require cloning of data associated with another branch, and executing the selected branches before executing the other branch.

8. The method of claim 7, wherein identifying flow branch behavior in a runtime system further includes:

identifying asynchronous and synchronous service calls in a flow;

determining a runtime of the asynchronous and synchronous service calls using a corresponding timeout value; and

ordering execution of the asynchronous and synchronous service calls, using the time out value, such that short-lived synchronous calls are executed while waiting for long-lived asynchronous service calls in the flow.

9. A system for optimizing runtime branch selection in a flow process, comprising:

a computer processor; and

a runtime system application executing on the computer processor, the runtime system application implementing a method, comprising;

gathering and storing performance metrics of flow branch behavior for executed flows in a runtime system over a period of time;

using aggregated performance metrics for the flow branch behavior to determine an optimal ordering of branches for a currently running flow, comprising;

identifying at least one branch point in the currently running flow, the branch point having two or more branches;

generating ordering permutations for at least a portion of the branches of the branch point in the currently running flow to identify any permutations that have not been executed;

gathering metrics for at least one permutation of the branch point in the currently running flow;

comparing the metrics to performance metrics of executed flows having substantially similar flow branch behavior; and

identifying optimal branch ordering for the permutation based upon the comparison; and

executing the flow according to the optimal branch ordering.

10. The system of claim 9, wherein the optimal branch ordering is determined by identifying a permutation from the stored performance metrics that, based upon past executions, is determined to execute faster than other permutations from the stored performance metrics or is determined to use fewer resources to complete than other permutations from the stored performance metrics.

11. The system of claim 10, wherein gathering the metrics includes gathering load values that reflect time spent completing a flow branch;

wherein an average load value is calculated by averaging load values for multiple activated flow branches.

12. The system of claim 10, wherein gathering the metrics includes identifying common branches taken in a flow.

13. The system of claim 9, wherein the system runtime application further implements:

updating the stored performance metrics with statistical data reflecting execution of the flow using the optimal branch ordering.

14. The system of claim 9, wherein the permutation indicates a path of the branch point and reflects a particular sequence of tasks in the flow.

15. A computer program product for optimizing runtime branch selection in a flow process, the computer program product comprising a storage medium having computer-readable program code stored thereon, the program code causing a computer to implement a method, the method comprising:

gathering and storing performance metrics of flow branch behavior for executed flows in a runtime system over a period of time;

using aggregated performance metrics for the flow branch behavior to determine an optimal ordering of branches for a currently running flow, comprising;

identifying at least one branch point in the currently running flow, the branch point having two or more branches;

generating ordering permutations for at least a portion of the branches in the branch point for the currently running flow to identify any permutations that have not been executed;

gathering metrics for at least one permutation of the branch point in the currently running flow;

comparing the metrics to performance metrics of executed flows having substantially similar flow branch behavior; and

identifying optimal branch ordering for the permutation based upon the comparison; and

executing the flow according to the optimal branch ordering.

16. The computer program product of claim 15, wherein the optimal branch ordering is determined by identifying a permutation from the stored performance metrics that, based upon past executions, is determined to execute faster than other permutations from the stored performance metrics or is determined to use fewer resources to complete than other permutations from the stored performance metrics.

17. The computer program product of claim 16, wherein gathering the metrics includes gathering load values that reflect time spent completing a flow branch;

wherein an average load value is calculated by averaging load values for multiple activated flow branches.

18. The computer program product of claim 16, wherein gathering the metrics includes identifying common branches taken in a flow.

19. The computer program product of claim 15, further comprising instructions for implementing:

updating the stored performance metrics with statistical data reflecting execution of the flow using the optimal branch ordering.

20. The computer program product of claim 15, wherein the permutation indicates a path of the branch point and reflects a particular sequence of tasks in the flow.