Speculative Parallelization on Multicore Processors

With the advent of multicore processors, extracting thread level parallelism from a sequential program has become crucial for improving performance. However, many sequential programs cannot be easily parallelized due to the presence of dependences. To solve this problem this dissertation presents a thread-based execution model, called Copy-or-Discard (CorD), that supports speculative parallelization. In CorD, the state of speculative threads is maintained separately from the non-speculative computation state. If speculation is successful, the results of the speculative computation are committed by copying them into the non-speculative state. If a misspeculation is detected, no costly recovery mechanisms are needed as the speculative state can be simply discarded.To illustrate the applicability of CorD, this dissertation first shows how to apply it to streaming applications. Optimizations are proposed to reduce data copying overhead. A lightweight scheme based on version comparison is also presented to detect misspeculations. It is observed that when misspeculation rate becomes high, the benefits of parallelism are usually nullified. To address this problem two techniques, Multiple Speculations and Incremental Recovery, are proposed. The first technique creates multiple versions of speculatively-executed code using different value predictions. If any one of these versions is found to be correct, the speculation is successful. The second technique focuses on reducing misspeculation cost. Instead of discarding all results, it allows saving and reuse of the results that are not affected by the variables that cause the misspeculation. Finally, this dissertation shows the applicability of CorD in the presence of dynamic data structures. Such data structures pose many new challenges. The copying of data structures from non-speculative to speculative state is expensive due to the large sizes of data structures. The copying of updated data structures from speculative state to non-speculative state are complex due to the changes in the shape of dynamic data structures. In addition, translating pointers internal to dynamic data structures between their non-speculative and speculative memory addresses has to be addressed. This dissertation proposes an augmented design for the representation of dynamic data structures such that all of the above operations are performed efficiently