基于硬件事务内存构建并发链表
|
摘要
并发数据结构是并行程序的基本组成部分,其执行效率直接影响到并行程序的执行性能。设计并发数据结构需要解决的一个主要问题是数据同步。传统的基于锁的同步控制策略使用较为普遍,但无法兼顾编程效率和执行性能。事务内存作为一种新兴的并行编程范式被提出。基于Intel处理器所提供的硬件事务内存构建并发链表,并与基于锁和基于硬件同步原语的并发链表展开性能比对,研究Intel硬件事务内存对并发链表执行效率的影响。
Concurrent data structures(CDS)are essential building blocks for parallel programs,and their efficiency significantly affects the overall performance of the programms.Synchronizing concurrent accesses to shared data is a critical challenge for CDS design.Traditionally,lock-based schemes are widely-used.However,lock-based schemes are either error-prone or inefficient.Transactional memory,as a brand new parallel programming paradigm,is proposed.We construct a concurrent linked list upon Intel's hardware transactional memory and compare its performance with a lock-based and a lock-free counterparts.
Concurrent data structures(CDS)are essential building blocks for parallel programs,and their efficiency significantly affects the overall performance of the programms.Synchronizing concurrent accesses to shared data is a critical challenge for CDS design.Traditionally,lock-based schemes are widely-used.However,lock-based schemes are either error-prone or inefficient.Transactional memory,as a brand new parallel programming paradigm,is proposed.We construct a concurrent linked list upon Intel's hardware transactional memory and compare its performance with a lock-based and a lock-free counterparts.
引文
[1]Herlihy M,Eliot J,Moss B.Transactional memory:Architectural support for lock-free data structures[J].AcmSigarch Computer Architecture News,1993,21(2):289-300.
[2]Liu Yu-jie,Zhou T,Spear M.Transactional acceleration of concurrent data structures[C]∥Proc of ACM Symposium on Parallelism in Algorithms and Architectures,2015:244-253.
[3]Meawad F,Iyer K,Schoeberl M,et al.Micro-transactions for concurrent data structures[J].Concurrency&Computation Practice&Experience,2013,25(16):2252-2268.
[4]Yehuda A,Amir L,Adam M.Software-improved hardware lock elision[C]∥Proc of the 2014ACM Symposium on Principles of Distributed Computing(PODC'14),2014:212-221.
[5]Richard M Y.Performance evaluation of Inteltransactional synchronization extensions for high-performance computing[C]∥Proc of the International Conference on High Performance Computing,Networking,Storage and Analysis(SC'13),2014:Article 19.
[6]Le H Q,Guthrie G,Williams D,et al.Transactional memory support in the IBM POWER8processor[J].IBM Journal of Research and Development,2015,59(1):1-14.
[7]Restricted transactional memory overview[EB/OL].[2018-05-28].https:software.intel.com/en-us/node/524025.
[8]Chen Juan.Learning from mistake:Transformation of programming education[J].Education on Computer,2017(12):54-58.(in Chinese)
[9]Concurrent-ll[EB/OL].[2018-08-11].https://github.com/jserv/concurrent-ll.
[10]Harris T L.A pragmatic implementation of non-blocking linked-lists[C]∥Proc of International Conference on Distributed Computing,2001:300-314.
[8]陈娟.从错误中学习:计算机程序设计课程改革实践[J].计算机教育,2017(12):54-58.
[2]Liu Yu-jie,Zhou T,Spear M.Transactional acceleration of concurrent data structures[C]∥Proc of ACM Symposium on Parallelism in Algorithms and Architectures,2015:244-253.
[3]Meawad F,Iyer K,Schoeberl M,et al.Micro-transactions for concurrent data structures[J].Concurrency&Computation Practice&Experience,2013,25(16):2252-2268.
[4]Yehuda A,Amir L,Adam M.Software-improved hardware lock elision[C]∥Proc of the 2014ACM Symposium on Principles of Distributed Computing(PODC'14),2014:212-221.
[5]Richard M Y.Performance evaluation of Inteltransactional synchronization extensions for high-performance computing[C]∥Proc of the International Conference on High Performance Computing,Networking,Storage and Analysis(SC'13),2014:Article 19.
[6]Le H Q,Guthrie G,Williams D,et al.Transactional memory support in the IBM POWER8processor[J].IBM Journal of Research and Development,2015,59(1):1-14.
[7]Restricted transactional memory overview[EB/OL].[2018-05-28].https:software.intel.com/en-us/node/524025.
[8]Chen Juan.Learning from mistake:Transformation of programming education[J].Education on Computer,2017(12):54-58.(in Chinese)
[9]Concurrent-ll[EB/OL].[2018-08-11].https://github.com/jserv/concurrent-ll.
[10]Harris T L.A pragmatic implementation of non-blocking linked-lists[C]∥Proc of International Conference on Distributed Computing,2001:300-314.
[8]陈娟.从错误中学习:计算机程序设计课程改革实践[J].计算机教育,2017(12):54-58.