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.
|
|
| 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×<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] |
|---|---|
| ISSN: | 09208542 |
| DOI: | 10.1007/s11227-017-2188-2 |
