System and method for application migration in a grid computing environment

• US 20080300851A1
• Filed: 06/04/2007
• Published: 12/04/2008
• Est. Priority Date: 06/04/2007
• Status: Active Grant

• Current Assignee: Infosys Limited
• Original Assignee: Infosys Technologies Limited (Infosys Limited)
• Inventors: Chakrabarti, Anirban, Sengupta, Shubhashis, Damodaran, Anish
• Granted Patent: US 8,117,606 B2
• Time in Patent Office: Days
• US Class Current: 703/22
• CPC Class Codes: G06F 8/433 Dependency analysis; Data or control flow analysis

Abstract

A system and method for assessing performance of a software application migrated to a grid infrastructure is provided. The system comprises a grid code analyzer for generating a directed acyclic graph (DAG) corresponding to the software application by performing static and dynamic analysis; a grid task generator for reducing the DAG generated by the grid code analyzer; and a grid simulator for simulating performance of the software application on one or more predetermined grid infrastructures. The grid simulator accepts the reduced DAG as input and produces performance data as output.

Claims

1. A system for assessing performance of a software application migrated to a grid infrastructure, the system comprising:

a grid code analyzer for generating a directed acyclic graph (DAG) corresponding to the software application by performing static and dynamic analysis;

a grid task generator for reducing the DAG generated by the grid code analyzer; and

a grid simulator for simulating performance of the software application on one or more predetermined grid infrastructures, the grid simulator accepting the reduced DAG as input and producing performance data as output.

2. The system as claimed in claim 1 wherein the grid task generator reduces the generated DAG by using one or more node compression algorithms for reducing the number of nodes of the DAG.

3. The system as claimed in claim 1 wherein the grid task generator reduces the generated DAG by clustering two or more nodes of the DAG by using one or more clustering algorithms.

4. The system as claimed in claim 1 wherein the grid simulator implements one or more scheduling algorithms for scheduling the input DAG on the one or more predetermined grid infrastructures.

5. The system as claimed in claim 1 wherein the grid code analyzer comprises:

a static analyzer for statically analyzing the software application, and comprising;

a parser for parsing the software application by analyzing dependencies between two or more sections of the software application and partitioning the software application into virtual blocks for removing dependency loops in the DAG corresponding to the software application, each node of the DAG representing at least one virtual block; and

code instrumentor for inserting instrument strings in the software application for capturing run time and dependency information; and

a dynamic analyzer for dynamically analyzing the software application, and comprising;

a central processing unit (cpu) profiler for determining the cpu time required for processing each virtual block for obtaining node weights corresponding to each node of the DAG, and

a memory profiler for determining an amount of data exchanged between a pair of virtual blocks for obtaining edge weight of an edge linking the two nodes of the DAG corresponding to the pair of virtual blocks.

6. The system as claimed in claim 5 wherein the grid code analyzer further comprises a symbol table for storing information regarding symbols such as types, constants, functions and variables declared in the software application, the symbol table being created during static analysis of the software application and being used for dynamic analysis.

7. The system as claimed in claim 6 wherein the symbol table is implemented as a hash table wherein a scope number, a block number and a variable name are used for generating keys corresponding to each symbol declared in the software application.

8. The system as claimed in claim 5 wherein the grid code analyzer further comprises a memory map for maintaining an updatable record of memory allocated on heap during run time of the software application, the memory map being created and used during dynamic analysis of the software application for determining data exchanged between a pair of virtual blocks.

9. The system as claimed in claim 8 wherein the memory map is a data structure implemented as a balanced binary search tree.

10. The system as claimed in claim 5 wherein the instrument strings are inserted based on dependency relations between two virtual blocks determined during parsing of the software application.

11. The system as claimed in claim 5 wherein instrument strings are inserted before and after each virtual block for capturing the run time information of each virtual block during dynamic analysis of the software application.

12. The system as claimed in claim 5 wherein the memory profiler uses a memory tracking function for determining amount of data exchanged between the pair of virtual blocks by using a programming language operator for determining memory allocated on stack, and by dereferencing a pointer variable for determining memory allocated on heap.

13. A method for assessing performance of a software application migrated to a grid infrastructure, the method comprising the steps of:

generating a directed acyclic graph (DAG) corresponding to the software application by performing static and dynamic analysis;

reducing the generated DAG;

simulating performance of the software application by inputting the reduced DAG to one or more predetermined grid infrastructures and obtaining performance data as output; and

analyzing the performance data for assessing the performance of the software application on the one or more predetermined grid infrastructures.

14. The method as claimed in claim 13 wherein the step of generating a DAG comprises:

statically analyzing the software application by;

parsing the software application by determining dependencies between two or more sections of the software application and partitioning the software application into virtual blocks for removing dependency loops in the DAG, each node of the DAG representing at least one virtual block; and

inserting instrument strings in the software application for capturing run time information by tracking the execution path and the data changes occurring during execution of the software application;

dynamically analyzing the software application by;

determining the cpu time required for processing each virtual block for obtaining node weights corresponding to each node of the DAG, and

determining amount of data exchanged between a pair of virtual blocks for obtaining edge weight of an edge linking the two nodes of the DAG corresponding to the pair of virtual blocks.

15. The method as claimed in claim 14 wherein the step of parsing comprises determining dependencies such as hierarchical dependencies, argument level dependencies, global value dependencies and return value dependencies.

16. The method as claimed in claim 14 wherein the step of inserting instrument strings comprises inserting at least a start block and an end block instrument strings at the commencement and end of a virtual block respectively for profiling the software application and estimating the running time of each virtual block.

17. The method as claimed in claim 13 wherein the step of reducing the generated DAG comprises reducing the number of nodes of the DAG by using one or more node compression algorithms.

18. The method as claimed in claim 13 wherein the step of reducing the generated DAG further comprises clustering two or more nodes of the DAG by using one or more clustering algorithms.

19. The method as claimed in claim 13 wherein the step of simulating performance of the software application on one or more predetermined grid infrastructures comprises implementing one or more scheduling algorithms for scheduling the input DAG on the one or more predetermined grid infrastructures.

20. The method as claimed in claim 13 wherein the DAG is reduced by an α

compression algorithm comprising the steps of;

a. providing a threshold value of α

;

b. traversing a root node of the DAG;

c. determining if the weight of the node being traversed is greater than α

;

d. sorting the one or more child nodes corresponding to the node being traversed based on their node weights and storing the sorted nodes in a list in an ascending order, if the weight of the node being traversed is not greater than α

;

e. combining the node being traversed with the head child node having the least node weight in the list;

f. determining if a DAG triad is formed;

g. determining if the node weight of the combined node is greater than α

, if a DAG triad is not formed;

h. cancelling the combination action performed at step e, if it is determined that the node weight of the combined node obtained is greater than α

or a DAG triad is formed;

i. removing the head child node from the list if the node weight of the combined node is not greater than α

;

j. determining if the list contains other child nodes;

k. Repeating steps e to j, if the list contains other child nodes;

l. determining if all nodes of the DAG have been traversed, if the list does not contain other child nodes; and

m. traversing a next node in the DAG and repeating steps c and onwards iteratively until all nodes of the DAG are traversed, if all nodes of the DAG have not been traversed.

21. The method as claimed in claim 13 wherein the DAG is reduced by a β

compression algorithm comprising the steps of;

a. providing a threshold value of β

;

b. sorting node weights of all nodes in the DAG based on the node weights and storing the sorted nodes in a list in an ascending order;

c. traversing a head node in the list and determining if weight of the node being traversed is less than β

;

d. combining the node being traversed with its predecessor node, if weight of the node being traversed is less than β

;

e. determining if a DAG triad is formed as a result of the combination action;

f. cancelling the combination action if it is determined that a DAG triad is formed as a result of the combination action;

g. determining if all the nodes of the DAG present in the list are traversed;

h. traversing a next node in the list and repeating step b and onwards until all nodes of the DAG are traversed, if it is determined that all the nodes of the DAG in the list are not traversed;

i. determining if a node weight of the combined node obtained at step d is greater than a predetermined threshold value α

, if it is determined at step e that a DAG triad is not formed;

j. re-sorting all nodes in the DAG based on node weights and storing the sorted nodes in a list in an ascending order, if the node weight of the combined node obtained at step d is not greater than α

.

k. repeating step c and onwards until all nodes of the DAG are traversed;

l. repeating step f and onwards until all nodes of the DAG are traversed if the node weight of the combined node obtained at step e is greater than α

.

m. repeating step h and onwards until all nodes of the DAG are traversed if weight of the node being traversed is greater than β

.

22. The method as claimed in claim 20 or 21 wherein the threshold value of α

is approximately 1.5 to 2 times of the maximum value of edge weight associated with the DAG.

23. The method as claimed in claim 21 wherein the threshold value of β

is approximately 0.5 to 0.7 times the maximum value of node weight associated with the DAG.

24. The method as claimed in claims 20 or 21 wherein the threshold values α

and β

are between zero and infinity, such that the value of α

is greater than the value of β

.

25. A computer program product comprising a computer usable medium having a computer readable program code embodied therein for assessing performance of a software application migrated to a grid infrastructure, the computer program product comprising:

program instruction means for generating a directed acyclic graph (DAG) corresponding to the software application by performing static and dynamic analysis;

program instruction means for reducing the generated DAG;

program instruction means for simulating performance of the software application by inputting the reduced DAG to one or more predetermined grid infrastructures and obtaining performance data as output; and

program instruction means for analyzing the performance data for assessing the performance of the software application on the one or more predetermined grid infrastructures.

26. The computer program product as claimed in claim 25 wherein the program instruction means for generating a DAG comprise:

program instruction means for statically analyzing the software application by;

parsing the software application by determining dependencies between two or more sections of the software application and partitioning the software application into virtual blocks for removing dependency loops in the DAG, each node of the DAG representing at least one virtual block; and

inserting instrument strings in the software application for capturing run time information by tracking the execution path and the data changes occurring during execution of the software application;

program instruction means for dynamically analyzing the software application by;

determining the cpu time required for processing each virtual block for obtaining node weights corresponding to each node of the DAG, and

determining amount of data exchanged between a pair of virtual blocks for obtaining edge weight of an edge linking the two nodes of the DAG corresponding to the pair of virtual blocks.

27. The computer program product as claimed in claim 25 wherein the DAG is reduced by an α

compression algorithm comprising program instruction means for;

a. providing a threshold value of α

;

b. traversing a root node of the DAG;

c. determining if the weight of the node being traversed is greater than α

;

d. sorting the one or more child nodes corresponding to the node being traversed based on their node weights and storing the sorted nodes in a list in an ascending order, if the weight of the node being traversed is not greater than α

;

e. combining the node being traversed with the head child node having the least node weight in the list;

f. determining if a DAG triad is formed;

g. determining if the node weight of the combined node is greater than α

, if a DAG triad is not formed;

h. cancelling the combination action performed at step e, if it is determined that the node weight of the combined node obtained is greater than α

or a DAG triad is formed;

i. removing the head child node from the list if the node weight of the combined node is not greater than α

;

j. determining if the list contains other child nodes;

k. Repeating steps e to j, if the list contains other child nodes;

l. determining if all nodes of the DAG have been traversed, if the list does not contain other child nodes; and

m. traversing a next node in the DAG and repeating steps c and onwards iteratively until all nodes of the DAG are traversed, if all nodes of the DAG have not been traversed.

28. The computer program product as claimed in claim 25 wherein the DAG is reduced by a β

compression algorithm comprising program instruction means for;

a. providing a threshold value of β

;

b. sorting node weights of all nodes in the DAG based on the node weights and storing the sorted nodes in a list in an ascending order;

c. traversing a head node in the list and determining if weight of the node being traversed is less than β

;

d. combining the node being traversed with its predecessor node, if weight of the node being traversed is less than β

;

e. determining if a DAG triad is formed as a result of the combination action;

f. cancelling the combination action if it is determined that a DAG triad is formed as a result of the combination action;

g. determining if all the nodes of the DAG present in the list are traversed;

h. traversing a next node in the list and repeating step b and onwards until all nodes of the DAG are traversed, if it is determined that all the nodes of the DAG in the list are not traversed;

i. determining if a node weight of the combined node obtained at step d is greater than a predetermined threshold value α

, if it is determined at step e that a DAG triad is not formed;

j. re-sorting all nodes in the DAG based on node weights and storing the sorted nodes in a list in an ascending order, if the node weight of the combined node obtained at step d is not greater than α

.

k. repeating step c and onwards until all nodes of the DAG are traversed;

l. repeating step f and onwards until all nodes of the DAG are traversed if the node weight of the combined node obtained at step e is greater than α

.

m. repeating step h and onwards until all nodes of the DAG are traversed if weight of the node being traversed is greater than β

.

29. The computer program product as claimed in claim 27 or 28 wherein the threshold value of α

is approximately 1.5 to 2 times of the maximum value of edge weight associated with the DAG.

30. The computer program product as claimed in claim 28 wherein the threshold value of β

is approximately 0.5 to 0.7 times the maximum value of node weight associated with the DAG.

31. The computer program product as claimed in claims 27 or 28 wherein the threshold values α

and β

are between zero and infinity, such that the value of α

is greater than the value of β

.