Integrating Speculative Execution to Loop and Task-based Parallelization

Abstract

This proposal brings five contributions to address code parallelization. First, it proposes a tool to measure the loop-carried probability of each component of a loop and to detect loop-carried patterns in the loop extending the OpenMP check clause. Initial experiments shows that loop-carried probability is an effective metric to decide when to use TLS or BDX to parallelize loops, thus, for certain loops, slow-downs can be transformed in 2× speed-ups by quickly selecting the appropriate algorithm. Second, it proposes an annotation approach to separate the (may) sequential components of a given loop based on the loop-carried probability of each component, thus exposing other components to parallelization. Third, it integrates two algorithms (TLS and BDX) into a simple OpenMP clause that enables the programmer to select the best algorithm for each component of a given loop (judicious approach). Fourth, it proposes new OpenMP clauses to implement speculative privatizations (spec private and spec reduction) which are essential to achieve performance in the TLS algorithm. Finally, this proposal also describes a novel speculation technique for the parallel execution of tasks. This technique, called Speculative Task Execution (STE), speculatively executes tasks which have control dependences with previous tasks. However, STE can also be used to speculate data dependences between tasks of different iterations in a loop possibly generated by a taskloop construct. It requires hardware support that can be provided in a similar fashion as that available in Hardware Transactional Memory (HTM) systems. We propose the implementation of a prototype to STE and the design of new speculative constructs and clauses to integrate STE into OpenMP task-based parallelization as: (a) the spec on construct; (b) the tls clause for taskloop construct, and (c) the spec in dependence-type for depend clause.