SHF: Small: Multicore Data-Structures: Relaxed, Flat, and Randomized

SHF：小型：多核数据结构：宽松、扁平和随机

• 批准号: 1217921
• 负责人: Nir Shavit
• 金额: $ 50万
• 依托单位: Massachusetts Institute of Technology
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2012
• 资助国家: 美国
• 起止时间: 2012-08-01 至 2016-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1217921&HistoricalAwards=false
• 关键词: SHF; Small; Multicore; Data; Structures

Most multicore data structures being designed and used in parallel software today are concurrent versions of the sequential data structures of years past. They continue to work reasonably well because the level of parallelism offered by mainstream multicore machines is still low. As machines grow in size, however, the limitations of these traditional structures will become clear: they have inherent sequential bottlenecks, require tight synchronization, and are not easily distributed. This project will develop new classes of parallel data structures that combine relaxed specifications with highly decentralized randomized implementations, overcoming the drawbacks of existing structures and providing a better fit with tomorrow's massively parallel many-core machine designs. This research will combine theoretical algorithmic work with empirical evaluation on real machines and applications, and will result in a library of concurrent data structures and a collection of design approaches and specification methodologies. Commercial software developers are in desperate need of data structures that scale while still remaining easy to understand and modify. Making this project's developed structures widely available will greatly help in making tomorrow's applications, whether they run on a cell phone or on a server in the cloud, make full use of the parallelism offered by multicore technology.

目前并行软件中设计和使用的大多数多核数据结构都是过去顺序数据结构的并发版本。因为主流多核机器提供的并行性水平仍然很低，所以它们仍然运行得相当好。然而，随着机器规模的增长，这些传统结构的局限性将变得越来越明显：它们具有固有的顺序瓶颈，需要严格的同步，并且不容易分布。该项目将开发新的并行数据结构类，将宽松的规范与高度分散的随机实现相结合，克服现有结构的缺点，并更好地适应未来的大规模并行多核机器设计。这项研究将理论算法工作与实际机器和应用的经验评估相结合，并将产生并发数据结构库和设计方法和规范方法的集合。商业软件开发人员迫切需要既可扩展又易于理解和修改的数据结构。使这个项目开发的结构广泛可用，将极大地有助于使未来的应用程序，无论是在手机上还是在云中的服务器上运行，充分利用多核技术提供的并行性。