Privatizing transactions for Lee’s algorithm in commercial hardware transactional memory.
Saved in:
| Title: | Privatizing transactions for Lee’s algorithm in commercial hardware transactional memory. |
|---|---|
| Authors: | Quislant, Ricardo1 quislant@uma.es, Gutierrez, Eladio1 eladio@uma.es, Zapata, Emilio L.1 zapata@uma.es, Plata, Oscar1 oplata@uma.es |
| Source: | Journal of Supercomputing. Apr2018, Vol. 74 Issue 4, p1676-1694. 19p. |
| Subjects: | Parallel programs (Computer programs), Transaction systems (Computer systems), IBM computers, Computer architecture, Application program interfaces |
| Abstract: | Lee’s algorithm solves the path-connection problems that arise in logical drawing, wiring diagramming or optimal route finding. Its parallel version has been widely used as a benchmark to test transactional memory systems. It exhibits transactions of large size and duration that stress these systems exposing their limitations. In fact, Lee’s algorithm has been proved to perform similar to sequential in commercial hardware transactional memory systems due to persistent capacity overflows. In this paper, we propose a novel approach to Lee’s algorithm in the context of commercial hardware transactional memory systems. We show how the majority of the computation of the largest transaction, i.e. grid privatization and path calculation, can be executed out of the boundaries of the transaction, thus reducing the size requirements. We leverage the correctness criteria of lazy subscription fallback locks to ensure a correct execution. This novel approach uses transactional memory extensions from commercial processors from a different point of view, not needing either early release or open-nested transaction features that are not yet implemented in these systems. We propose an application programming interface to facilitate the task of the programmer. Experiments are carried out with the Intel Core and IBM Power8 architectures, showing speedups around 3.5× |
| Copyright of Journal of Supercomputing is the property of Springer Nature 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 |
|
Full text is not displayed to guests.
Login for full access.
|
|
| FullText | Links: – Type: pdflink Text: Availability: 1 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 128656646 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: Privatizing transactions for Lee’s algorithm in commercial hardware transactional memory. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Quislant%2C+Ricardo%22">Quislant, Ricardo</searchLink><relatesTo>1</relatesTo><i> quislant@uma.es</i><br /><searchLink fieldCode="AR" term="%22Gutierrez%2C+Eladio%22">Gutierrez, Eladio</searchLink><relatesTo>1</relatesTo><i> eladio@uma.es</i><br /><searchLink fieldCode="AR" term="%22Zapata%2C+Emilio+L%2E%22">Zapata, Emilio L.</searchLink><relatesTo>1</relatesTo><i> zapata@uma.es</i><br /><searchLink fieldCode="AR" term="%22Plata%2C+Oscar%22">Plata, Oscar</searchLink><relatesTo>1</relatesTo><i> oplata@uma.es</i> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22Journal+of+Supercomputing%22">Journal of Supercomputing</searchLink>. Apr2018, Vol. 74 Issue 4, p1676-1694. 19p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Parallel+programs+%28Computer+programs%29%22">Parallel programs (Computer programs)</searchLink><br /><searchLink fieldCode="DE" term="%22Transaction+systems+%28Computer+systems%29%22">Transaction systems (Computer systems)</searchLink><br /><searchLink fieldCode="DE" term="%22IBM+computers%22">IBM computers</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+architecture%22">Computer architecture</searchLink><br /><searchLink fieldCode="DE" term="%22Application+program+interfaces%22">Application program interfaces</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: Lee’s algorithm solves the path-connection problems that arise in logical drawing, wiring diagramming or optimal route finding. Its parallel version has been widely used as a benchmark to test transactional memory systems. It exhibits transactions of large size and duration that stress these systems exposing their limitations. In fact, Lee’s algorithm has been proved to perform similar to sequential in commercial hardware transactional memory systems due to persistent capacity overflows. In this paper, we propose a novel approach to Lee’s algorithm in the context of commercial hardware transactional memory systems. We show how the majority of the computation of the largest transaction, i.e. grid privatization and path calculation, can be executed out of the boundaries of the transaction, thus reducing the size requirements. We leverage the correctness criteria of lazy subscription fallback locks to ensure a correct execution. This novel approach uses transactional memory extensions from commercial processors from a different point of view, not needing either early release or open-nested transaction features that are not yet implemented in these systems. We propose an application programming interface to facilitate the task of the programmer. Experiments are carried out with the Intel Core and IBM Power8 architectures, showing speedups around 3.5×<inline-graphic></inline-graphic> over both the standard transactional version of the algorithm and the sequential for certain grid inputs and four threads. We also compare our proposal with a software transactional memory LeeTM approach. [ABSTRACT FROM AUTHOR] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>Copyright of Journal of Supercomputing is the property of Springer Nature 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=128656646 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1007/s11227-017-2188-2 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 19 StartPage: 1676 Subjects: – SubjectFull: Parallel programs (Computer programs) Type: general – SubjectFull: Transaction systems (Computer systems) Type: general – SubjectFull: IBM computers Type: general – SubjectFull: Computer architecture Type: general – SubjectFull: Application program interfaces Type: general Titles: – TitleFull: Privatizing transactions for Lee’s algorithm in commercial hardware transactional memory. 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: 04 Text: Apr2018 Type: published Y: 2018 Identifiers: – Type: issn-print Value: 09208542 Numbering: – Type: volume Value: 74 – Type: issue Value: 4 Titles: – TitleFull: Journal of Supercomputing Type: main |
| ResultId | 1 |
