Efficiently Implementing Wait-Free Shared Objects on Multiprocessors

这项研究的目标是使运行在异步共享内存多处理器上的并行程序能够灵活、高效和可靠地共享数据。具体地说，该研究试图开发用于构建系统软件的算法，这些算法(1)使实现任何共享数据结构变得容易，(2)确保对实现的共享数据结构的访问是快速的，以及(3)确保实现的共享数据结构是容错的。共享数据结构的无等待实现确保即使系统中的某些进程崩溃，数据结构仍可供正确的进程访问。通用结构是一种算法，它使设计任何共享数据结构的无等待实现变得容易。为了实现上一段中所述的目标，本研究寻求一种具有低最坏情况时间复杂度和强并行性的通用结构：并发操作即使访问数据结构的公共部分也是并行运行的，前提是经常访问的部分只被读取，而不是被修改。通用结构通常需要强大的同步操作，例如比较和互换。将这些构造移植到不支持此类操作的较弱体系结构是本研究的另一个目标。最终的目标是理解普遍结构的内在局限性。

The goal of this research is to make it possible for parallel programs, running on asynchronous shared-memory multiprocessors, to share data flexibly, efficiently, and reliably. Specifically, the research seeks to develop algorithms for building system software that (1) make it easy to implement any shared data structure, (2) ensure that accesses to implemented shared data structures are fast, and (3) ensure that the implemented shared data structures are fault-tolerant. A wait-free implementation of a shared data structure ensures that the data structure remains accessible to correct processes even if some processes in the system crash. A universal construction is an algorithm that makes it easy to design a wait-free implementation of any shared data structure. To realize the goal stated in the previous paragraph, this research seeks a universal construction with low worst-case time complexity and strong parallelism: concurrent operations run in parallel even if they access common parts of the data structure, provided that the commonly accessed parts are only read, and not modified. Universal constructions often require strong synchronization operations, such as compare & swap. Porting these constructions to weaker architectures that do not support such operations is another objective of this research. A final objective is to understand the intrinsic limitations of universal constructions.