Paper Info
Title
Online identification of frequently executed acyclic paths by leveraging data stream algorithms
Abstract
Most of the traditional path profilers simply generate a path-frequency table that records the raw frequencies of each path. The compiler is supposed to carry out the herculean task of mining this table for frequently executed paths to drive aggressive profile-guided optimizations. This begs a question: why cannot profilers themselves identify these frequent paths --- produce information that can be consumed directly by the optimizers? The essential theme of this paper is that the sequence of acyclic paths emitted by a classic Ball-Larus profiler can be viewed as a data-stream: this enables an online extraction of any required statistics (like the frequently executed paths) on the profile information without requiring storage and update of the huge path-frequency tables generated by a long-running program. We adapt a classic data stream algorithm for finding majority elements in a stream (by Karp et al.) for our use, essentially by enabling optimizations that exploit the properties of paths generated off a Ball-Larus profiler. We instantiate our ideas by building an efficient path profiler that identifies all acyclic paths frequented above a user-provided threshold percentage of all executed paths.
Year
DOI
Venue
2013
10.1145/2480362.2480680
SAC
Keywords
Field
DocType
classic data stream algorithm,acyclic path,frequent path,enabling optimizations,traditional path,online identification,aggressive profile-guided optimizations,executed path,classic ball-larus profiler,efficient path profiler,ball-larus profiler,reflection,meta data,java
Metadata,Online identification,Data stream,Computer science,Algorithm,Compiler,Exploit,Theoretical computer science,Java
Conference
Citations 
PageRank 
References 
0
0.34
5
Authors
2
Name
Order
Citations
PageRank
G. Kumar141.42
Subhajit Roy24510.84