P3: Partitioned Path Profiling
Publication Date: 2014-May-23
The IP.com Prior Art Database
Acyclic path profile is an useful abstraction of the program trace which is effectively used for compiler optimization to software engineering. Even though it is proven to be more useful than other profiles such as edge or vertices, the overhead of obtaining such profile is prohibitabily high for its in-field usage. Starting from its introduction by Ball-Larus, various methods have addressed this problem. In this work we present a technique called Partitioned Path Profiling or P3 which instruments multiple copies of the program which are run parallely. The final profile can be obtained by combining the partial profiles obtained by parallel execution. To our knowledge, P3 is the first parallel algorithm for path profiling.
Page 01 of 6
P3: Partitioned Path Profiling
Path profiles are an abstraction of programs control path behavior at run-time. They are effectively used in the fields of compiler optimization [DE02], testing [JHS02], debugging, and software maintenance [ECG99]. Path profiling, as introduced by Ball-Larus in their seminal work [BL96], is a frequency measurement of acyclic execution paths in a program. This
profiling subsumes the other profiling such as edge and vertex profiling. Various tools already incorporates some form of path profiling information.
Ball-Larus presented a solution in [BL96] where it performs CFG edge-labelling in such a way that uniquely identifies each acyclic path in a CFG by a number (pathid). It inserts instrumentation such that after execution of each acyclic path, its pathid is computed as the sum of the edge labels in the acyclic path, and the count corresponding to the pathid is incremented in an array. The overall edge labelling is targeted towards efficient collection of path profiles. After its introduction, various works have focussed on increasing the efficiency [AH02,VNC07,CNV07], variations [MR99,DD13,PCC05], and utility [JBZ04,BM05] of the
One important problem which restricts the widespread use of path profiling in field use is the overhead of collecting path profiles.
There are two kinds of overhead related to collection of path profiles. The memory overhead comes as the frequency of paths are stored in an array and size of the array is equal to the number of static acyclic paths in the program which tend to be large. Hashtables replaced array and are used to capture only the frequency of the excutable paths without the storage overhead, but use of Hashtable suffers from the time overhead. This problem is addressed in various works ([VNC07,CNV07]). The problem of time-overhead is more critical. Vaswani et al. [VNC07] reported an average overhead of 50% with worst case overhead of 132%. Other studies (e.g. [BM05]) reports similar overhead. As profiling paths is expensive, basic block and edge profiles are still prefered over path profile for many applications even though edge profiles can determine only 48% of the paths [BM05].
Ball-Larus' algorithm [BL96] uses a spanning tree based technique to reduce the time overhead of collection. Various other techniques have addressed the time overhead collection problem by reducing the amount of information to be collected. For example, Apiwattanapong et al. [AH02]
presents an algorithm, called Selective path profiling (SPP), to profile only selected set of paths thereby using probes less than that is required for full acyclic path profiles. Vaswani et al. developed Preferential Path Profiling - to compactly number set of interesting paths such that the overhead due to hashtable can be minimized. Chouhan et al. introduced Pertinent path profiling [BRC13] where they are interested on profiling the set of paths passing through a give set of