Phase Shift Detection: A Problem Classification

Dynamic analysis of a program's execution is an increasingly popular approach to characterizing the semantics of a program. One important aspect of dynamic analysis is the detection of phases, which can help improve program understanding, offer specialization opportunities in a dynamic optimization system, reduce simulation time, and dynamically adapt multi-configuration hardware to program behavior. Although both online and offline phase shift detection algorithms exist, most work has focused on the efficacy of the client, without a detailed study of the various dimensions of the underlying phase shift detection problem. The goal of this paper is to better understand the fundamental problem of phase shift detection. Specifically, we 1) demonstrate that an intuitive notion of a phase is not well-defined; 2) define an abstract problem with two parameters that captures the essence of the phase shift detection problem; 3) show that existing phase shift detection algorithms are instances of this abstract problem; 4) define an intuitive concrete instance of the abstract problem and demonstrate that the concrete problem has a unique solution; and 5) demonstrate for the concrete problem that two intuitive parameters that define a phase are not "well behaved" such that changes in these parameter's value may result in significantly different phases being identified. This last property illustrates the importance of clients choosing appropriate parameter values when employing a phase detection algorithm.