权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

EAGER: Concurrent Data Structures

EAGER：并发数据结构

基本信息

批准号：
1650596
负责人：
James Aspnes
金额：
$ 26.5万
依托单位：
Yale University
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2016
资助国家：
美国
起止时间：
2016-09-01 至 2020-06-30
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1650596&HistoricalAwards=false
关键词：
EAGER Concurrent Data Structures

项目摘要

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.

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