Keywords: parallelisation, concurrency, thread-level speculation, compiler, multicore, data dependencies.

The computing industry relied on increasing the clock frequency and on uniprocessor architectural enhancements to improve performance. The situation has changed nowadays, power and thermal issues have made this approach no longer feasible. Semiconductor manufacturers continue developing the manufacturing technology and the number of transistors per unit area doubled every few months; processor designers use the additional transistor density to place multiple cores in the same die. This creates a situation in which only multi-threaded applications can take advantage of the newly available resources. But many applications exhibit irregular access to memory, complex control flow and dynamic loop limits which strongly limit the parallelisation of applications.

Normal code parallelization and optimization need to take a pessimistic approach to guarantee correctness of execution due to data and control dependencies. Being able to resolve and remove data dependencies in run-time can dramatically improve parallelization.

Thread-Level Speculation (TLS) is a technique that enables parallel execution of sequential applications on multicore systems. This paper describes how memory-region speculative execution (MRSe) can potentially widen the scope of single threaded applications that can be parallelised by resolving data dependencies at run-time that otherwise would prevent parallelism from being extracted. MRSe is a parallelisation technique that is applied to regions of code that might contain a great amount of parallelism but cannot be statically proven to preserve the sequential behaviour under parallel execution.

The differences between MRSe compared to conventional TLS are a greatly reduced overhead by:

1. Tracking memory changes by regions and no by variables, at the cost of producing false positive data violation detections.
2. Speculative thread rollback checkpoints are only created at the moment the thread starts executing instead on every memory operation, reducing the memory footprint and the cost of the memory read/write operations.

The results of the evaluation of the first implementation of this approach show that the overhead caused by the functions of the library is less than expected and that it is easy to obtain a good performance improvement under the set of described cases in the paper. But the logic of writing speculative code is not trivial and work should be done to be integrated into automatic parallelisation tools. Overall, MRSe is a promising approach for expanding the grade of parallelism inside an application, specially in environments with wide amount of available computing resources.

purchase the full-text of this paper (price £20)

go to the previous paper
go to the next paper
return to the table of contents
return to the book description
purchase this book (price £50 +P&P)