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.