EAGER: Concurrent Data Structures

大多数计算机编程都描述了由单个处理器核心一个接一个地执行的一系列步骤。随着处理器速度的增长速度放缓，CPU制造商已经通过构建具有多个处理器内核的系统来应对，这些处理器内核可以同时执行多个任务。这些处理器共享一个公共内存，用于各自的计算和与其他处理器的通信。组织这个共享内存，以便处理器可以在不被其他处理器延迟的情况下进行进程，这需要仔细的协调，并设计专门的数据结构和通信协议，以允许在没有冲突的情况下进行有效的合作。该项目将研究如何让处理器随机选择不同的方法来完成相同的任务，以提高这些数据结构使用的效率和内存量，鉴于已知非随机方法的不可能结果，这种方法似乎是必要的。这可能会大大提高我们利用多核机器的能力，同时简化这些机器的程序员的工作。除了对计算机科学和编程实践的影响外，该项目还将直接影响本科生和研究生的研究。由于并发数据结构非常适合本科生实施项目，避免了本科生参与更多理论研究时经常出现的困难，因此该项目将成为招募学生参与尖端、高风险研究的桥梁，包括来自代表性不足群体的学生。在研究生阶段，该项目的成果将直接纳入PI的教学，包括更新PI公开的讲义，这些讲义已经被其他机构的许多学生使用。该项目考虑的主要问题是：我们是否可以使用避免传统并发控制工具（如锁）的数据结构来消除共享内存系统中程序并发执行中的瓶颈？两种看起来很有希望的技术是随机化的使用，它避免了错误的时间总是导致错误的执行，不同的进程相互干扰的操作，以及有限使用假设，其中共享数据结构在设计时假设它们只用于有限数量的操作，允许显著降低成本和复杂性。除了将这些技术单独应用于并发共享内存数据结构的设计之外，该项目还将考虑这些方法如何相互补充，例如，通过使用随机帮助技术将短期有限使用的数据结构转换为长期无限制使用的数据结构。这项工作的一个关键要素是为共享内存数据结构开发改进的成本度量，包括空间复杂性的动态度量，它比在以前的工作中发现的最大内存消耗的最坏情况度量更准确地反映实际内存使用情况。

Most computer programming describes a sequence of steps to be carried out one by one by a single processor core. As the rate of increase in processor speed has slowed, CPU manufacturers have responded by building systems with many processor cores that together carry out multiple tasks simultaneously. These processors share a common memory that they use both for their own individual computations and for communication with other processors. Organizing this shared memory so that the processors can make progress without being delayed by other processors requires careful coordination and the design of specialized data structures and communication protocols to allow efficient cooperation without conflicts. The project will study how letting processors make random choices between different ways to accomplish the same task to improve the efficiency and amount of memory used by these data structures, an approach that appears to be necessary given known impossibility results for non-randomized methods. This may significantly improve our ability to exploit the power of multicore machines, while simplifying the work of programmers of these machines. In addition to this impact on computer science and the practice of programming, the project will directly impact both undergraduate and graduate research. Because concurrent data structures are well-suited to undergraduate implementation projects, which avoid difficulties that often arise with involving undergraduates in more theoretical research, the project will serve as a bridge for recruiting students into cutting-edge, high-stakes research, including students from under-represented groups. At the graduate level, results from the project will feed directly into the PI's teaching, including updates to the PI's publicly-available lecture notes already in use by many students at other institutions.The main question considered by the project is: Can we remove bottlenecks in concurrent executions of programs in shared-memory system using data structures that avoid traditional concurrency control tools like locking? Two techniques that appear promising are the use of randomization, which avoids problems where bad timing consistently produces bad executions in which different processes interfere with each others' operations, and limited-use assumptions, where shared data structures are designed under the assumption that they will only be used for a limited number of operations, allowing for significant reductions in cost and complexity. In addition to applying these techniques individually to the design of concurrent shared-memory data structures, the project will also consider how these methods can complement each other, for example by the use of randomized helping techniques to transform short-lived limited-use data structures into long-lived unlimited-use data structures. A key element of this work will be the development of improved cost measures for shared-memory data structures, including dynamic measures of space complexity that more accurately reflect practical memory usage than the worst-case measures of maximum memory consumption found in previous work.