Minimizing interaction costs among components of computer programs

• US 7,360,205 B2
• Filed: 02/11/2002
• Issued: 04/15/2008
• Est. Priority Date: 02/09/2001
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Rajan, Vadakkedathu T., Wegman, Mark N., Roth, Tova, Kimelman, Douglas N., Sreedhar, Vugranam C.
• Primary Examiner(s): Zhen; Wei
• Assistant Examiner(s): RAMPURIA, SATISH
• Application Number:
  US10/073,628
• Publication Number:
  US 20020111697A1
• Time in Patent Office: 2,255 Days
• Field of Search: 717/100, 717/158, 717/104, 717129-161, 707/2, 715/514, 716/1, 705/35
• US Class Current: 717/130
• CPC Class Codes: G06F 11/3409 for performance assessment
• CPC Class Codes: G06F 11/3447 Performance evaluation by modeling
• CPC Class Codes: G06F 11/3466 Performance evaluation by tracing or monitoring
• CPC Class Codes: G06F 2201/865 Monitoring of software

Abstract

A system and method for minimizing total cost of interaction among components of a computer program which are each characterized by at least one implementation property. A implementation property may, for example, be a choice of string representation (e.g. ASCII, UNICODE, EBCDIC or choice of data structure (e.g. hash, tree, compressed). The method comprises the steps of: carrying out a run of the program; monitoring that run to measure an amount of interaction between each pair of components; determining a cost of interaction between each pair of interacting components; determining a choice of implementation properties which minimizes total cost of the run; and assigning choices of implementation properties to said components for a future run of the program.

Claims

1. A method for minimizing total cost of interaction among of components of a computer program, each of the components being characterized by one or more data representation properties, structure, the method comprising steps of:

a) carrying out at least a partial run of the program;

b) monitoring the at least partial run of the program to capture information on interaction between each pair of components, wherein the information on interaction comprises information relating to an explicit request from one component of the pair to the other component of the pair for some data, and wherein the monitoring comprises recording a source component, a destination component, and an amount of data;

c) determining a cost of interaction between each pair of interacting components;

d) determining a set of interrelated choices of the data representation properties of each of the components of at least one group of components which minimizes total cost of the at least partial run;

e) assigning the set of interrelated choices of the properties to the components for a subsequent at least partial run of the program; and

wherein the data representation properties comprise a choice of string representation of a component, and the amount of interaction measured in step (b) comprises a frequency of interaction between each pair of interacting components;

the cost of interaction comprising a function of the frequency and a cost of converting any differing string representations of the pair to a common string representation.

2. The method as set forth in claim 1, wherein at least one string representation is selected from ASCII, UNICODE, and EBCDIC.

3. The method as set forth in claim 1, the data representation property comprising a choice of data structure of a component, the amount of interaction measured in step (b) comprising a frequency of interaction between each pair of interacting components;

the cost of interaction comprising a function of the frequency and a cost of converting any differing choices of data structures of the pair to a common choice of data structure.

4. The method as set forth in claim 3, wherein at least one data structure is selected from hash, tree, and compressed data structures.

5. The method as set forth in claim 1, wherein the step (d) of determining the choice is carried out by building a graph with nodes representing program components and edges that join adjacent nodes representing interaction therebetween, each edge being characterized by a cost of each interaction, then using a graph cutting technique to find a minimum cut of the graph.

6. The method of claim 1 wherein the data representation properties comprise string representation.

7. The method of claim 1 wherein the data representation properties comprise data structure.

8. A computer readable storage medium including computer instructions for carrying out a method for minimizing total cost of interaction among components, each of the components being characterized by one or more data representation properties of a computer program running on a computer system, the medium comprising instructions for:

a) carrying out at least a partial run of the program;

b) monitoring the at least partial run of the program to measure an amount of interaction between each pair of components, wherein an interaction comprises an explicit request from one component of the pair to the other component of the pair for some data, and wherein monitoring comprises recording-a source component, a destination component and an amount of data;

c) determining a cost of interaction between each pair of interacting components;

d) determining a set of interrelated choices of the data representation properties of each of the components of at least one group of components which minimizes total cost of the at least partial run;

e) assigning the set of interrelated choices of the properties to the components for a subsequent at least partial run of the program; and

wherein the data representation property comprising a choice of string representation of a component, the amount of interaction measured in instruction

(b) comprising a frequency of interaction between each pair of interacting components;

the cost of interaction comprising a function of the frequency and a cost of converting any differing string representations of the pair to a common string representation.

9. The computer readable storage medium as set forth in claim 8, wherein at least one string representation is selected from ASCII, UNICODE, and EBCDIC.

10. The computer readable storage medium as set forth in claim 8, the data representation property properties comprising a choice of data structure of a component, the amount of interaction measured in step (b) comprising a frequency of interaction between each pair of interacting components;

the cost of interaction comprising a function of the frequency and a cost of converting any differing choices of data structures of the pair to a common choice of data structure.

11. The computer readable storage medium as set forth in claim 10, wherein at least one data structure is selected from hash, tree, and compressed data structures.

12. The computer readable storage medium as set forth in claim 8 wherein the instruction (d) of determining the choice is carried out by building a graph with nodes representing program components and edges that join adjacent nodes representing interaction therebetween, each edge being characterized by a cost of each interaction, then using a graph cutting technique to find a minimum cut of the graph.

13. The method of claim 8 wherein the data representation properties comprise string representation.

14. The method of claim 8 wherein the data representation properties comprise data structure.