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

本项目发展了一种理论，用于描述使用并行结构的并行数据结构和并行算法的性能。并行算法的标准度量，如“工作”（总计算量）和“跨度”（关键路径长度），在共享数据上存在争用时不会自然地泛化。此外，当数据结构是并行的时候，分析顺序数据结构的标准方法（如摊销）似乎不能推广，部分原因是性能取决于底层并行任务调度器的属性。具体的研究目标如下：(1)研究一种设计和分析使用数据结构的并行算法的方法，特别是平摊算法。(2)设计并行调度器，改善并行数据结构上的争用。(3)设计并行数据结构，这些数据结构可以很好地使用这些调度器。如今，并行计算无处不在。现代计算平台——从智能手机到网络路由器，从个人电脑到大型集群和云——每一个都包含多个处理器。编写可证明可扩展性良好的并行代码具有挑战性，分析顺序算法和数据结构的技术通常不适用于并行代码。本项目将为描述争夺共享数据访问的并行程序的可伸缩性提供理论基础。

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.