Detecting Variable-Length Phases in Utility Programs Program and hardware adaptation to take advantage of dynamic changes in behavior is becoming increasingly important. A number of recent techniques divide an execution into phases and adapt hardware and/or the program on a per-phase basis. The benefit of the adaptation depends on the accuracy of phase partitioning and behavior prediction. In this work, we consider a class of dynamic programs whose behavior depends strongly on their input. An example is a compiler, in which behavior varies not only from one input to another but also across sections of the same input. Other examples include interpreters, compression and transcoding utilities, and databases. These applications share the common feature that they provide some sort of service: they accept, or can be configured to accept, a sequence of requests, each of which is processed more-or-less independently of the others. Because they are so heavily dependent on their input, utility applications display much less regular behavior than typical scientific programs. Previous phase-detection methods often predict the phase of an upcoming fixed-length time interval based on behavior detected in the preceding interval(s). Because they work on-line, these methods cannot afford sophisticated analysis and have little global information. Recently a wavelet-based method was proposed to find and insert phase markers into a program during profiling [Shen et al., ASPLOS'04]. The phase markers enable more accurate run-time phase prediction with negligible overhead. However, as noted by the authors, the method does not work on utility programs due to their irregular behavior. In this work, we treat the strong input dependence of utility programs as an opportunity for phase detection. We introduce a new technique called active profiling, which uses a sequence of identical requests to induce behavior that is both representative of normal usage and sufficiently regular to identify outermost phases. Active profiling differs from traditional profiling in that its input is specially designed to expose the desired behavior in a program.This process requires only the most high-level knowledge of program behavior, and no access to source code." Through active profiling, we induce perfect behavior repetitions in utility programs. We then employ a novel phase-boundary analysis to mark top-level phase transitions. The technique finds all basic blocks occurring exactly the same times as the number of requests in the regular input, and chooses those that are evenly spaced. Dynamic adaptations use the past instances of a phase to choose the optimal configuration for the coming instance of that phase. Therefore, the consistency across the instances of a phase is critical. Our method finds phases that show significantly more consistent behavior than previous methods. Outermost phases detected by active profiling often correspond to a memory usage cycle. As one use of the phase detection, we monitor and control program memory at phase boundaries. By explicitly invoking garbage collection at phase boundaries, we have been able to improve the performance of Xlisp by 44%.