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
FullText Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 136867738
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: Improving hardware transactional memory parallelization of computational geometry algorithms using privatizing transactions.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Quislant%2C+Ricardo%22">Quislant, Ricardo</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> quislant@uma.es</i><br /><searchLink fieldCode="AR" term="%22Gutierrez%2C+Eladio%22">Gutierrez, Eladio</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> eladio@uma.es</i><br /><searchLink fieldCode="AR" term="%22Zapata%2C+Emilio+L%2E%22">Zapata, Emilio L.</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> zapata@uma.es</i><br /><searchLink fieldCode="AR" term="%22Plata%2C+Oscar%22">Plata, Oscar</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> oplata@uma.es</i>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Journal+of+Parallel+%26+Distributed+Computing%22">Journal of Parallel & Distributed Computing</searchLink>. Sep2019, Vol. 131, p103-119. 17p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Parallel+programming%22">Parallel programming</searchLink><br /><searchLink fieldCode="DE" term="%22Computational+geometry%22">Computational geometry</searchLink><br /><searchLink fieldCode="DE" term="%22Problem+solving%22">Problem solving</searchLink><br /><searchLink fieldCode="DE" term="%22Multiprocessors%22">Multiprocessors</searchLink><br /><searchLink fieldCode="DE" term="%22Algorithms%22">Algorithms</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: 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]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>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.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=136867738
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1016/j.jpdc.2019.04.018
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 17
        StartPage: 103
    Subjects:
      – SubjectFull: Parallel programming
        Type: general
      – SubjectFull: Computational geometry
        Type: general
      – SubjectFull: Problem solving
        Type: general
      – SubjectFull: Multiprocessors
        Type: general
      – SubjectFull: Algorithms
        Type: general
    Titles:
      – TitleFull: Improving hardware transactional memory parallelization of computational geometry algorithms using privatizing transactions.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Quislant, Ricardo
      – PersonEntity:
          Name:
            NameFull: Gutierrez, Eladio
      – PersonEntity:
          Name:
            NameFull: Zapata, Emilio L.
      – PersonEntity:
          Name:
            NameFull: Plata, Oscar
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 09
              Text: Sep2019
              Type: published
              Y: 2019
          Identifiers:
            – Type: issn-print
              Value: 07437315
          Numbering:
            – Type: volume
              Value: 131
          Titles:
            – TitleFull: Journal of Parallel & Distributed Computing
              Type: main
ResultId 1