This dissertation proposes a framework for modeling the control flow behavior of a program and the application of this framework to the optimization of speculative threads used for instruction and data prefetch. A novel form of helper threading, prescient instruction prefetch, is introduced in which helper threads are initiated when the main thread encounters a spawn point and prefetch instructions starting at a distant target point. The target identifies a code region tending to incur I-cache misses that the main thread is likely to execute soon;​ even though intervening control flow may be unpredictable. The framework is also applied to the compile time optimization of simple p-threads, which improve performance by reducing data cache misses.

The optimization of speculative threads is enabled by modeling program behavior as a Markov chain based on profile statistics. Execution paths are considered stochastic outcomes, and program behavior is summarized via path expression mappings. Mappings for computing reaching, and posteriori probability;​ path length mean, and variance;​ and expected path footprint are presented. These are used with Tarjan's fast path algorithm to efficiently estimate the benefit of spawn-target pair selections.

Two implementation techniques for prescient instruction prefetch—direct pre-execution, and finite state machine recall—are proposed and evaluated. Further, a hardware mechanism for reducing resource contention in direct pre-execution called the YAT-bit is proposed and evaluated. Finally, a hardware mechanism, called the safe-store, for enabling the inclusion of stores in helper threads is evaluated and extended. Average speedups of 10.0% to 22% (depending upon memory latency) on a set of SPEC CPU 2000 benchmarks that suffer significant I-cache misses are shown on a research Itanium® SMT processor with next line and streaming I-prefetch mechanisms that incurs latencies representative of next generation processors. Prescient instruction prefetch is found to be competitive against even the most aggressive research hardware instruction prefetch technique:​ fetch directed instruction prefetch.

The application of the modeling framework to data prefetch helper threads yields results comparable with simulation based helper thread optimization techniques while remaining amenable to implementation within an optimizing compiler.