Improving Hardware Transactional Memory Parallelization of Computational Geometry Algorithms Using Privatizing Transactions.

Abstract

Hardware transactional memory is a new parallel programming paradigm supported by current commercial multiprocessors. This paradigm provides optimistic concurrency and overcomes some of the problems associated with classical lock-based synchronization, such as deadlock and serialization. Certain algorithms of computational geometry are found to be good candidates for parallelization with this paradigm. However, hardware transactional approaches to these algorithms lead to poor performance as the resulting transactions are too large for the underlying hardware to deal with. Large transactions overflow hardware resources serializing the execution.

In this paper, we propose using privatizing transactions to parallelize two computational geometry algorithms: Lee’s algorithm, which solves the shortest-route problem, and Ruppert’s algorithm for Delaunay/Voronoi mesh refinement. Privatizing transactions are based on commercial hardware transactional memory extensions, and their goal is to reduce transaction footprint by means of a non-transactional private execution section. This results in effective smaller transactions. Our implementation is able to further reduce the transaction size as we propose a reduced validation set for privatizing transactions. Programming complexity of these implementations is discussed.

Results show that our privatizing transaction implementations indeed enhance performance comparing with existing hardware transactional memory versions. Experiments with Intel’s transactional memory extensions yield speedups ranging from 2x to 3.5x with four threads.