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.

By: Michael J. Hind, Vadakkedathu T. Rajan, Peter F. Sweeney

Published in: RC22887 in 2003


This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.


Questions about this service can be mailed to .