Parallel programming using thread-level speculation

As the performance increases of single-threaded processors diminish, consumer desktop processors are moving toward multi-core designs. Thread-level speculation (TLS) increases the space of applications that can benefit from these designs. With TLS, a sequential application is divided into fairly independent tasks that are speculatively executed in parallel, while the hardware dynamically enforces data dependencies to provide the appearance of sequential execution. This thesis demonstrates that support for TLS greatly eases the task of manual parallel programming. Because TLS provides a sequential programming interface to parallel hardware, it enables the programmer to focus only on issues of performance, rather than correctness.; The dissertation starts by demonstrating the parallelization of a microbenchmark to introduce a number of techniques for manual TLS parallelization. Several of the advanced techniques leverage programmer expertise to surpass the capabilities of current advanced, automated parallelizers; the research presented here can provide guidance for the future development of such tools. Following this, the use of these techniques to parallelize seven of the SPEC CPU2000 applications is described. TLS parallelization yielded an average 120% speedup on four floating point applications and 70% speedup on three integer applications, while requiring only approximately 80 programmer hours and 150 lines of non-template code per application. These strong parallel performance results generated with relatively modest programmer effort support the inclusion of TLS in future chip multiprocessor designs.; For each application parallelized, a detailed description is provided of how and where parallelism was located, the impediments to extracting it using TLS, and the code transformations that were required to overcome these impediments. The results on these applications demonstrate that using advanced manual techniques is essential to effectively parallelize integer benchmarks. This leads to a discussion of common hindrances to TLS parallelization, and a subsequent description of methods of programming that help expose the parallelism in applications to TLS systems. These programming guidelines can help uniprocessor programmers create applications that can be easily ported to future TLS systems and yield good performance. In closing, the dissertation reviews the many advantages of manual TLS parallel programming and specifies potential future research areas.