The Program Cycle Behavior Of Multi-level Analysis

Phase analysis, which classifies the set of execution intervals with similar performance behavior and resource requirements, has been widely used in a variety of dynamic systems, including dynamic cache reconfiguration, simulation acceleration and race detection. While phase granularity has been a major factor on the accuracy of phase prediction, it has not been well investigated yet and most previous research usually adopts a fine-grained prediction scheme. They record and update the phase ids in a history table when program is running, then predict future phase according to the table. Such a scheme can only take account of recent local phase information and could be frequently interfered by temporary noises due to instant phase changes, which might notably limit the prediction accuracy.In this paper, we make the first investigation on the potential of multi-level phase analysis (MLPA), where fine-grained phase analysis and coarse-grained phase analysis are combined together to improve the overall effectiveness. We observe that:(?) For different fine-grained intervals belonging to the same coarse-grained phase, both the sequences and the distributions of these intervals are very similar and stable;(?) Coarse-grained interval can be accurately identified based on the fine-grained intervals at the beginning of its execution.Based on the observation, we design and implement a MLPA scheme. In such a scheme, a coarse-grained phase is first identified based on the fine-grained intervals at the beginning of its execution. The following fine-grained phases in it are then predicted based on the sequence of fine-grained phases in the coarse-grained phase. The most important advantage of MLPA is that it considers the global historical phase information but not the recent local phase information. Experimental results show such a scheme can notably improve the prediction accuracy. Using Markov fine-grained phase predictor as the baseline, MLPA can improve prediction accuracy by 17%,42%and 32% for next phase, phase change and phase length prediction accordingly, yet incur only about 2% time overhead and 40% space overhead (about 360 bytes).To demonstrate the usefulness of such a scheme, we apply MLPA to a dynamic cache reconfiguration system which dynamic adjust the cache size to reduce data cache's power consumption and access time, and a sampling-based simulation system. Experimental results show that MLPA can further reduce the average cache size by 14% compared to the fine-grained scheme, and achieve a speedup in simulation time of 14.OX (15 hours vs.125 hours) with similar accuracy compared to 10M SimPoint.