Efficiently Implementing Wait-Free Shared Objects on Multiprocessors

在多处理器上高效实现无等待共享对象

• 批准号: 9803678
• 负责人: Prasad Jayanti
• 金额: $ 18.66万
• 依托单位: Dartmouth College
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1998
• 资助国家: 美国
• 起止时间: 1998-08-01 至 2002-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9803678&HistoricalAwards=false
• 关键词: Efficiently; Implementing; Wait; Free; Shared

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.

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