US 8,079,020 B2Granted

Preferential path profiling

AssigneeMicrosoft Corporation

InventorsTrishul Amit Madhukar Chilimbi, Kapil Vaswani, Aditya Vithal Nori

Life of this patent

Estimating the term…

Loading patent…

Abstract

This paper describes preferential path profiling, which enables profiling a specified subset of all possible program paths with very low overhead. Preferential path profiling compactly identifies paths of interest using an array. More specifically, PPP assigns a unique and compact path index identifier to all interesting paths that can be used to index into a path array. The path array contains a second path value identifier that is used to distinguish interesting paths from other program paths This path numbering allows the implementation of preferential path profiling to use array-based counters instead of hash table-based counters for identifying paths of interest and gathering path profiles, which significantly reduces execution time and computational resource overhead during profiling.

Claims14

Dependent claims

In a computer profiling environment that typically records a computer program's control transfers through a sequence of executed instructions, each sequence representing a path that defines a characterization of a program's dynamic behavior, a method of reducing the overhead associated with path profiling by constructing an array of values that represent a subset of an

overall number of paths within a control-flow graph for the program, the method comprising:
identifying a subset of paths from a number of control-flow paths, which represent an abstraction of a program's dynamic control-flow behavior, and wherein the subset of paths are chosen based on predefined criteria to limit path selection;
determining a different path index identifier for each of the subset of paths, each index identifier to be associated with an index into an array representing the entire subset of paths;
wherein determining a different path index identifier for each of the subset of paths further comprises:
assigning edge weights to one or more edges within the control-flow graph of the program;
traversing each edge which lies within a particular path, the path comprising one or more edges within the control-flow graph;
and
summing the edge weights having been assigned to the edges within the control-flow graph for the program which are traversed by the path to determine the different path index;
assigning a path value for each of the subset of paths, each of the path values used in distinguishing the subset of paths from at least some of the paths not in the subset;
wherein assigning a path value further comprises:
assigning second edge weights to one or more edges within the control-flow graph of the program;
traversing each edge which lies within a particular path, the path comprising one or more edges within the control-flow graph;
and
summing the second edge weights having been assigned to the edges within the control-flow graph for the program which are traversed by the path to create a path value;
and
for each path within the subset of paths, correlating within the array the determined index identifier and the assigned path value, using the index identifier as the array index into the elements of the array and storing the path value within a corresponding element of the array, such that during a runtime path profiling implementation for the program, the appropriate index identifier and correlated path value can be used to compare a traversed path with a assigned path value in order to determine if the path is within the subset of paths.

13 more elements

In a runtime computer profiling environment that typically records a computer program's control transfers through a sequence of executed instructions, each sequence representing a path that defines a characterization of a program's dynamic behavior, a method of reducing the overhead associated with typical path profiling by identifying paths of interest using a predetermined array that defines a subset of an overall number of paths within a control-flow graph for the program, the method comprising:

determining a path index identifier for a path traversed during execution of a computer program, the path index identifier being part of an array representing a subset of paths from a number of control-flow paths that represent an abstraction of the program's dynamic control-flow behavior, and wherein the subset of paths are chosen based on predefined criteria to limit path selection;
wherein determining a path index for a path further comprises:
assigning first edge weights to one or more edges within the control-flow graph of the program;
traversing each edge which lies within the path, the path comprising one or more edges within the control-flow graph;
and
summing the first edge weights having been assigned to the edges within the control-flow graph for the program which are traversed by the path to determine the path index;
determining a first path value for the traversed path, the path value representing an identifier used in distinguishing the subset of paths from at least some of the paths not in the subset;
wherein determining the first path value for a traversed patch comprises:
assigning second edge weights to one or more edges within the control-flow graph of the program;
traversing each edge which lies within the path, the path comprising one or more edges within the control-flow graph;
and
summing the second edge weights having been assigned to the edges within the control-flow graph for the program which are traversed by the path to determine the first path value;
based on the determined path index identifier, accessing the array using the index identifier as an index into the array elements to retrieve a previously assigned path value therein;
and
comparing the retrieved assigned path value with the determined first path value in order to determine if the path is within the subset of paths.

12 more elements

A computer program product comprising a computer-readable storage medium having encoded thereon computer executable code which, when executed within a suitable computing environment, performs the method comprising:

determining a path index identifier for a path traversed during execution of a computer program, the path index identifier being part of an array representing a subset of paths from a number of control-flow paths that represent an abstraction of the program's dynamic control-flow behavior, and wherein the subset of paths are chosen based on predefined criteria to limit path selection;
wherein determining a path index for a path further comprises:
assigning first edge weights to one or more edges within the control-flow graph of the program;
traversing each edge which lies within the path, the path comprising one or more edges within the control-flow graph;
and
summing the first edge weights having been assigned to the edges within the control-flow graph for the program which are traversed by the path to determine the path index;
determining a first path value for the traversed path, the path value representing an identifier used in distinguishing the subset of paths from at least some of the paths not in the subset;
wherein determining the first path value for a traversed patch comprises:
assigning second edge weights to one or more edges within the control-flow graph of the program;
traversing each edge which lies within the path, the path comprising one or more edges within the control-flow graph;
and
summing the second edge weights having been assigned to the edges within the control-flow graph for the program which are traversed by the path to determine the first path value;
based on the determined path index identifier, accessing the array using the index identifier as an index into the array elements to retrieve a previously assigned path value therein;
and
comparing the retrieved assigned path value with the determined first path value in order to determine if the path is within the subset of paths.

12 more elements

Dependencies are inferred from the claim text.

Facts

Application: 11/682,196Filed 5 Mar 2007
Published: US 2008/0222614 A111 Sep 2008
Granted: 13 Dec 2011
Term ends: Not estimatedThe source records don’t support an estimate.

Classification4 codes

G06F 11/3471
Performance evaluation by tracing or monitoring: address tracing
G06F 11/3447
Recording or statistical evaluation of computer activity, e.g. of down time, of input/output operation ; Recording or statistical evaluation of…:…
G06F 2201/88
Indexing scheme relating to error detection, to error correction, and to monitoring: monitoring involving counting
G06F
Computing and data processing