Reducing the penalty of branch and load hazards in pipelined microprocessors.

Pipelined microprocessors allow the simultaneous execution of several machine instructions at a time, increasing the total throughput of instructions. Because an instruction being executed by a pipelined microprocessor may depend on the results of another instruction that is being executed simultaneously, data and control hazards can reduce the efficiency of pipelined microprocessors. This dissertation examines data hazards caused by memory load instructions and branch hazards caused by conditional branch instructions. Load instructions can be particularly difficult to execute efficiently because computer memory systems are often significantly slower than contemporary microprocessors. The load target buffer is a microarchitectural feature that predicts the address that will be needed by a memory load instruction before the actual address is computed. Simulations of the SPEC89 benchmarks on single-issue in-order-execution pipelines determine that an effective load target buffer needs to include at least 1024 entries. When branch prediction is accurate, delaying the pipeline stage that performs ALU operations improves the ability of processors to tolerate a slow memory system. Branch instructions can reduce the ability of a processor to exploit instruction-level parallelism, even when the processor has accurate branch prediction. Predicated instructions are machine instructions with an extra operand that acts as a logical predicate to the execution of the instruction. Compilers can replace code that contains conditional branches with code that contains predicated instructions, reducing the number of branches. The dissertation describes DecisionScanner, a tool that instruments C source code and traces the decisions made by conditional branches as the instrumented program executes. Experiments on five of the SPEC92 C benchmarks, the UNIX word count utility, and an MPEG video player show significant performance improvement for machines that support out-of-order execution that can issue eight or more instructions per cycle. Machines that issue fewer instructions per cycle realize a moderate improvement in performance. Processors achieve most of the benefits of full predication when only conditional moves are available.PhDApplied SciencesComputer scienceUniversity of Michigan, Horace H. Rackham School of Graduate Studieshttp://deepblue.lib.umich.edu/bitstream/2027.42/129692/2/9610132.pd