AF: SMALL: Collaborative Research: Data Structures for Parallel Algorithms

AF：小：协作研究：并行算法的数据结构

• 批准号: 1217708
• 负责人: Michael Bender
• 金额: $ 13.9万
• 依托单位: SUNY at Stony Brook
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2012
• 资助国家: 美国
• 起止时间: 2012-08-01 至 2016-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1217708&HistoricalAwards=false
• 关键词: AF; SMALL; Collaborative; Research; Data; AF; SMALL; Collaborative; Research; Data

This project develops a theory for characterizing the performance of parallel data structures and parallel algorithms that use parallel structures. Standard metrics for parallel algorithms, such as "work" (total amount of computation) and "span" (critical-path length), do not naturally generalize in the presence of contention on shared data. Moreover, standard approaches for analyzing sequential data structures, such as amortization, do not seem to generalize when data structures are parallel, in part because the performance depends on the properties of the underlying parallel task schedulers.The specific research goals are as follows: (1) Investigate a methodology for designing and analyzing parallel algorithms that use data structures, especially amortized ones. (2) Design parallel schedulers that ameliorate the contention on parallel data structures. (3) Design parallel data structures that perform provably well with these schedulers.Today parallel computing is ubiquitous. Modern computation platforms---smartphones to network routers, personal computers to large clusters and clouds---each contain multiple processors. Writing parallel code that provably scales well is challenging and techniques for analyzing sequential algorithms and data structures generally do not apply to parallel code. This project will develop a theoretical foundation for characterizing the scalability of parallel programs that contend for access to shared data.

该项目开发了一种理论，用于表征使用并行结构的并行数据结构和并行算法的性能。 平行算法的标准指标，例如“工作”（计算总量）和“ SPAN”（临界路径长度），在存在共享数据的争论时不会自然地概括。 此外，分析顺序数据结构（例如摊销）的标准方法似乎并没有概括数据结构何时并行，部分原因是性能取决于基础并行任务调度程序的属性。具体的研究目标如下：（1）研究一种方法，用于研究和分析并行算法的方法，这些方法是使用并行算法使用数据结构，尤其是amaliors amalsiors amalsiors amalsiors amalsiors amalistials。 （2）设计平行调度程序，可以改善并行数据结构上的争论。 （3）设计并行数据结构，这些数据结构在这些调度程序中表现出色。图案并行计算无处不在。 现代计算平台 - 网络路由器，个人计算机到大型群集和云的智能手机 - 每个都包含多个处理器。 编写可以很好地扩展的并行代码具有挑战性，并且用于分析顺序算法和数据结构的技术通常不适用于并行代码。 该项目将建立一个理论基础，以表征争夺访问共享数据的并行程序的可扩展性。