The Research And Applications Of Instruction Criticality In Processors

Modern superscalar processors commonly use radical out-of-order execution technology. Since multiple instructions can execute in processors out-of-order simultaneously, critical path just consists of part of instructions. Identification and optimization for these instructions is one of key technologies which lead to understand and break through the performance bottlenecks of modern processors. With program dependence graph and critical path analysis, our research of instruction criticality can analyze instructions and events that have contributions to program execution time to discover performance bottlenecks and program phases and finally to direct processor design.We analyzed the original program dependence graph model proposed by Fields and extended and improved this model to represent programs behaviors executing in clustered-superscalar processors. Based on program dependence graph, we implement a fixed window based on-line critical path analysis framework and validate it. Then, we extracted instruction criticality information with this framework by critical path analysis, and analyzed the characteristics of instruction criticality quantified by two-value and LoC(likelihood of criticality) metric by information theory and statistics method. The research shows that instruction criticality quantified by two-value metric appears great history-independent randomness, and the instruction criticality quantified by LoC presents characteristics that are architecture-independent and dynamic-invariable. With these characteristics, we proposed a method for design of static LoC criticality predictor, which reload LoC values calculated by Profile to LoC predictor, and then processors can use LoC to optimize instruction execution.Finally, we used instruction criticality prediction to improve performance of clustered-superscalar processors. To mitigate the performance loss induced by inter-cluster communication and intra-cluster resource contention, we applied instruction criticality prediction to focus on instruction scheduling and steering. Experimental results show that criticality prediction based scheduling policy can improve performance effectively. Our static LoC predictor can improve performance as well as dynamic predictor did. Under 2-, 4- and 8-cluster architectures, the average speedup is 2.9%, 4.1% and 5.3% achieved by static LoC predictor. Then, we refined dependency based steering policy with criticality prediction, and proposed a processor execution critical mode based steering over stall method. The results present that within the refined steering policy, our steering over stall can also improve performance effectively. Under 2-, 4- and 8-cluster architectures, our stall over steering can improve performance of integer programs by 2.7%, 3.0% and 4.3% on average when criticality prediction based instruction scheduling was not used, and the performance can be improved further by 3.2%, 4.7% and 7.3% on average while focusing on criticality prediction based instruction scheduling.