SI2-SSE: TLDS: Transactional Lock-Free Data Structures

利用多处理器系统的并行性是计算机科学中的一个重大挑战。多核编程要求我们改变设计和使用基本数据结构的方式。非阻塞数据结构允许不受约束地访问共享数据；但是，必须小心，以免错误地覆盖数据。设计和使用非阻塞数据结构的一个主要障碍是缺乏一种通用的方法来允许高效的事务性和可组合操作。该项目由高级网络基础设施办公室和计算与通信基础部支持，将探索和定义设计和使用事务性多处理器算法的基本技术。在这项工作中产生的软件元素将显著改善现有并发容器的功能和重用，并将加速多处理器应用程序的性能，超越当前编程库的能力。在这个项目中创建的编程元素将通过一个软件库的开源发布来传播。该项目还将有助于培养受过系统编程培训的劳动力。为了实现该项目的目标，PI将探索解决方案，以克服支持高性能数据结构事务的两个关键挑战：1)如何有效地缓冲写操作，使其修改对事务范围外的操作不可见，以及2)如何在中止部分执行的事务时最小化回滚的代价。将创建六个事务性无锁容器的代表性集合，包括：链表、集合、跳跃列表、多维列表、优先级队列和字典。这项工作将大大提高对多处理器软件设计的认识和实践。据PI所知，无锁事务转换是为数据结构事务提供无锁进程和语义冲突检测的第一种方法。为了实现这一点，PI将在事务执行中创建新的冲突检测和恢复技术。本文将介绍一种基于节点的冲突检测方案，该方案不依赖于软件事务性内存，也不需要使用额外的数据结构。基于节点逻辑状态的解释，将设计一种新的有效的冲突恢复策略，而不是显式地撤销中止事务中已执行的操作。本研究将介绍跨多个数据结构高效执行可组合非阻塞事务的第一种方法。作为这项工作的一部分的软件组件和数据结构本身将是重要的研究工件。

Exploiting the parallelism in multiprocessor systems is a major challenge in computer science. Multicore programming demands a change in the way we design and use fundamental data structures. Non-blocking data structures allow un-constrained access to shared data; however, care must be taken so that data is not overwritten incorrectly. A main obstacle to the design and use of non-blocking data structures is the lack of a generic methodology for allowing efficient transactional and composable operations. This project, supported by the Office of Advanced Cyberinfrastructure, and the Division of Computing and Communication Foundations, will explore and define the fundamental techniques for the design and use of transactional multiprocessor algorithms. The software elements produced in this work will significantly improve the functionality and reuse of the existing concurrent containers and will accelerate the performance of multiprocessor applications beyond what is possible with current programming libraries. The programming elements created in this project will be disseminated through the open-source release of a software library. The project will also help contribute to a workforce trained in systems programming.To achieve the project's goals, the PI will explore solutions to overcome two key challenges for supporting high-performance data structure transactions: 1) how to efficiently buffer write operations so that their modifications are invisible to operations outside the transaction's scope, and 2) how to minimize the penalty of rollbacks when aborting partially executed transactions. A representative collection of six transactional lock-free containers will be created including: a linked-list, a set, a skiplist, a multi-dimensional list, a priority queue, and a dictionary. This work will substantially advance the knowledge and practice in multiprocessor software design. To the best of the PI's knowledge, lock-free transactional transformation is the first methodology that provides both lock-free progress and semantic conflict detection for data structure transactions. To achieve this, the PI will create new techniques for conflict detection and recovery in the execution of transactions. A node-based conflict detection scheme that does not rely on Software Transactional Memory nor require the use of an additional data structure will be introduced. A new and efficient conflict recovery strategy will be designed, based on the interpretation of the logical status of nodes instead of explicitly revoking executed operations in an aborted transaction. This research will introduce the first approach for the efficient execution of composable non- blocking transactions across multiple data structures. The software components and data structures engineered as part of this work will be significant research artifacts themselves.