Instruction-Isomorphism in program execution

Abstract

This paper identifies a fundamental runtime program property: Instruction-Isomorphism. An instruction instance is said to be isomorphic if its component - Information derived from the instruction and its backward dynamic data dependence graph - is identical to the component of an instruction executed earlier. By definition an isomorphic instruction will produce exactly the same output with the earlier instruction. This work introduces a taxonomy of isomorphic behavior, describes transformations that can change the isomorphic behavior of an instruction, characterizes empirically various aspects of instruction-isomorphism and suggests directions for improving predictors and performance. The empirical analysis shows that there is very little instruction-isomorphism in the dynamic dependence graph of a program. This is due to programming conventions and architectural semantics that introduce a lot of "overhead" nodes and dependences. However, by transforming the dynamic dependence graph closer to its dataflow form, instruction-isomorphism becomes prominent. The data show that for SPEC benchmarks, depending on the benchmark and dataset, 65 to 99.9% of the dynamic instructions are isomorphic.