Programming frameworks for performance driven speculative parallelization

Effectively utilizing available parallelism is becoming harder and harder as systems evolve to many-core processors with many tens of cores per chip. Automatically extracting parallelism has limitations whereas completely redesigning software using traditional parallel constructs is a daunting task that significantly jeopardizes programmer productivity. On the other hand, many studies have shown that a good amount of parallelism indeed exists in sequential software that remains untapped. How to unravel and utilize it successfully remains an open research question. Speculation fortunately provides a potential answer to this question. Speculation provides a golden bridge for a quick expression of "potential" parallelism in a given program. While speculation at extremely fine granularities has been shown to provide good speed-ups, speculation at larger granularities has only been attempted on a very small scale due to the potentially large overheads that render it useless. The transactional construct used by STMs can be used by programmers to express speculation since it provides atomicity and isolation while writing parallel code. However, it was not designed to deal with the semantics of speculation. This thesis contends that by incorporating the semantics of speculation new solutions can be constructed and speculation can provide a powerful means to the hard problem of efficiently utilizing many-cores with very low programmer efforts. This thesis takes a multi-faceted view of the problem of speculation through a combination of programming models, compiler analysis, scheduling and runtime systems and tackles the semantic issues that surround speculation such as determining the right degree of speculation to maximize performance, reuse of state in rollbacks, providing probabilistic guidance for minimizing conflicts, deterministic execution for debugging and development, and providing very large scale speculations across distributed nodes. First, we present F2C2-STM, a high performance flux-based feedback-driven concurrency control technique which automatically selects and adapts the degree of speculation in transactional applications for best performance. Second, we present the Merge framework which is capable of salvaging useful work performed during an incorrect speculation and incorporates it towards the final commit. Third, we present a framework which has the ability to leverage semantics of data structures and algorithmic properties to guide the scheduling of concurrent speculative transactions to minimize conflicts and performance loss. Fourth, we present DeSTM, a deterministic STM designed to aid the development of speculative transactional applications for repeatability without undue performance loss. These contributions significantly enhance the use of transactional memory as a speculative idiom improving the efficiency of speculative execution as well as simplify the development process. Finally, we focus on a performance oriented view of speculation, namely choose one of many speculative semantics, dubbed as algorithmic speculation. We present, the Multiverse framework which scales algorithmic speculation to a large distributed cluster with thousands of cores while maintaining its simplicity and efficiency. To conclude, speculative algorithms are benefited by the contributions of this thesis due to the enhancements to the transactional and the algorithmic speculative paradigms developed in this work, laying the foundation for the development and tuning of new speculative algorithms.Ph.D