Speculative Taskloop (STL) is a loop parallelization technique that takes the best of Task-based Parallelism and Thread-Level Speculation to speed up loops with may loop-carried dependencies that were previously difficult for compilers to parallelize. Previous studies show the efficiency of STL when implemented using Hardware Transactional Memory and the advantages it offers compared to a typical DOACROSS technique such as OpenMP ordered. This paper presents a performance comparison between STL and a previously proposed technique that implements Thread-Level Speculation (TLS) in the for worksharing construct (FOR-TLS) over a set of loops from cbench and SPEC2006 benchmarks. The results show interesting insights on how each technique can be more appropriate depending on the characteristics of the evaluated loop. Experimental results reveal that by implementing both techniques on top of HTM, speed-ups of up to 2.41× can be obtained for STL and up to 2× for FOR-TLS.

Although modern compilers implement many loop parallelization techniques, their application is typically restricted to loops that have no loop-carried dependences (DOALL) or that contain well-known structured dependence patterns (e.g. reduction). These restrictions preclude the parallelization of many computational intensive DOACROSS loops. In such loops, either the compiler finds at least one loop-carried dependence or it cannot prove, at compile-time, that the loop is free of such dependences, even though they might never show-up at runtime. In any case, most compilers end-up not parallelizing DOACROSS loops. This paper brings three contributions to address this problem. First, it integrates three algorithms (TLS, DOAX, and BDX) into a simple openMP clause that enables the programmer to select the best algorithm for a given loop. Second, it proposes an annotation approach to separate the sequential components of a loop, thus exposing other components to parallelization. Finally, it shows that loop-carried probability is an effective metric to decide when to use TLS or other non-speculative techniques (e.g. DOAX or BDX) to parallelize DOACROSS loops. Experimental results reveal that, for certain loops, slow-downs can be transformed in 2× speed-ups by quickly selecting the appropriate algorithm.

This paper presents a detailed analysis of the application of Hardware Transactional Memory (HTM) support for loop parallelization with Thread-Level Speculation (TLS) and describes a careful evaluation of the implementation of TLS on the HTM extensions available in such machines. The sample implementation of TLS over HTM described in this paper also provides evidence that the programming effort to implement TLS over HTM support is non-trivial. Thus the paper also describes an extension to OpenMP that both makes TLS more accessible to OpenMP programmers and allows for the easytuning of TLS parameters. As a result, it provides evidence to support several important claims about the performance of TLS over HTM in the Intel Core and the IBM POWER8 architectures. Experimental results reveal that by implementing TLS on top of HTM, speed-ups of up to 3.8x can be obtained for some loops.

This paper presents a detailed analysis of the application of Hardware Transactional Memory (HTM) support for loop parallelization with Thread-Level Speculation (TLS). As a result it provides three contributions: (a) it shows that performance issues well-known to loop parallelism (e.g. false sharing) are exacerbated in the presence of HTM, and that capacity aborts can increase when one tries to overcome them, (b) it reveals that, although modern HTM extensions can provide support for TLS, they are not powerful enough to fully implement TLS, (c) it shows that simple code transformations, such as judicious strip mining and privatization techniques, can overcome such shortcomings, delivering speed-ups for programs that contain loop-carried dependencies. Experimental results reveal that, when these code transformations are used, speed-ups of up to 30% can be achieved for some loops for which previous research had reported slowdowns.