View in EDS

Improving hardware transactional memory parallelization of computational geometry algorithms using privatizing transactions.

Saved in:
Bibliographic Details
Title: Improving hardware transactional memory parallelization of computational geometry algorithms using privatizing transactions.
Authors: Quislant, Ricardo1 (AUTHOR) quislant@uma.es, Gutierrez, Eladio1 (AUTHOR) eladio@uma.es, Zapata, Emilio L.1 (AUTHOR) zapata@uma.es, Plata, Oscar1 (AUTHOR) oplata@uma.es
Source: Journal of Parallel & Distributed Computing. Sep2019, Vol. 131, p103-119. 17p.
Subjects: Parallel programming, Computational geometry, Problem solving, Multiprocessors, Algorithms
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 2 × to 3.5 × with four threads. • A new optimized hardware transactional memory (HTM) implementation of Lee's and Ruppert's algorithms using privatizing transactions. • A reduction of the privatizing transaction validation set by a small subset of variables representative of the whole private section read set. • A reduction of the transactional section of privatizing transactions as much as possible to meet the hardware constraints of the HTM system. • A discussion of the programming complexity of the privatizing transaction solutions. [ABSTRACT FROM AUTHOR]
Copyright of Journal of Parallel & Distributed Computing is the property of Academic Press Inc. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
Description
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 2 × to 3.5 × with four threads. • A new optimized hardware transactional memory (HTM) implementation of Lee's and Ruppert's algorithms using privatizing transactions. • A reduction of the privatizing transaction validation set by a small subset of variables representative of the whole private section read set. • A reduction of the transactional section of privatizing transactions as much as possible to meet the hardware constraints of the HTM system. • A discussion of the programming complexity of the privatizing transaction solutions. [ABSTRACT FROM AUTHOR]
ISSN:07437315
DOI:10.1016/j.jpdc.2019.04.018