Branch optimizations and instruction-level parallelism exploitation for dynamic superscalar and VLIW processors.

摘要

Wide issue superscalar and VLIW processors benefit from the utilization of instruction-level parallelism (ILP) to achieve high performance. However, if insufficient ILP is found, the performance potential of these processors reduces drastically. Branch instructions are one of the main problems towards not achieving high ILP. Branch instructions pose strict ordering constraints in a program which impedes any effort to achieve a desired overlap of instruction execution with them. To effectively exploit ILP in the presence of branches, the parallelism extraction phases require efficient handling of branch instructions and reduce any ill-effects that they impose.; This dissertation investigates two techniques, namely speculative execution and predicated execution to extract (and enhance) ILP in the presence of branch instructions. Speculative execution is a technique by which instructions are executed before the branch condition that controls them is evaluated (or known). This can increase the performance if some of the idle cpu cycles are now used to execute speculative instructions from the taken path. If instructions are speculated from the wrong path(s), the performance can suffer.; Speculative execution, by itself, is not enough to achieve high ILP. The fundamental limitation due to the presence of branch instructions in the instruction stream can still have detrimental effects. This motivates us to investigate the other technique, predicated execution. Predicated execution is an architectural technique which eliminates the branch instruction (and its associated penalty) at the expense of extra instructions which get dynamically executed. The predicated (or guarded) instruction executes conditionally depending on the value of an extra predicate operand which satisfies the condition that originally controls the execution of the branch instruction.; Excessive application of speculative and/or guarded execution can hurt ILP. The thesis aims at describing new techniques to combine the individual merits of speculative and guarded execution and improves ILP beyond existing techniques. New profile guided branch optimizations are proposed which help reduce branch overhead costs. Finally, we provide an experimental evaluation of predicated execution on dynamic superscalar architectures and propose different predication models as cost-effective alternatives to the full-predication approach.