Eliminating dynamic computation redundancy

The traditional method of extracting performance from programs is based on scaling processor resources to execute multiple independent instructions per cycle. In order to enable their cost-effective performance potential, these processors demand that increasing levels of instruction-level parallelism (ILP) be exposed in programs. Current state-of-the-art compilers cannot expose the level of ILP necessary to overcome the diminishing performance returns of high-issue processors. Ultimately performance becomes limited by the dependences of programs, and not the machine resources. Thus, one of the major challenges to increasing processor performance is overcoming the fundamental dataflow limitation imposed by data dependences. By reusing previous computation results, the dataflow limit can be surpassed for sequences of operations that are otherwise redundantly executed. Many traditional compiler techniques eliminate program redundancy and optimize the effectiveness of the program. Currently, compiler techniques have no mechanism for capturing dynamic redundancy, redundancy occurring over a temporal set of definitions. Consequently, the available silicon resources are more effectively allocated to exploiting program redundancy than instruction-level parallelism.;This dissertation proposes and investigates four key architectural and compilation techniques that eliminate dynamic redundancy to improve the resource utilization and performance. The Reusable Computation Region Framework (RCRF) provides a compilation framework to accurately determine the regions, called Reusable Computation Regions (RCRs), of a program in which reuse is likely to occur. The Compiler-directed Computation Reuse (CCR) approach integrates compiler and architecture techniques to exploit execution behavior of these regions. In this approach, the Instruction Set Architecture (ISA) provides a simple interface for the compiler to communicate the run-time execution of each region into a hardware structure. The Dynamic Computation Management System (DCMS) enhances the effectiveness of the compiler-directed computation reuse approach by dynamically activating the statically-selected computation regions according to run-time program behavior. Finally, a class of computation regions formed by the RCRF can be exploited using compiler transformation and existing architecture support. In the compiler-based Value Optimization Framework (VOF), program reformulation and predicated execution-based value transformations are used to exploit the redundancy of regions. By systematically coordinating compiler techniques and hardware technologies significant amounts of the dynamic computation redundancy can be eliminated in program execution.