AF: Small: Toward A Unified Model of Parallelism And Locality

AF：小：走向并行性和局部性的统一模型

• 批准号: 1911245
• 负责人: Nodari Sitchinava
• 金额: $ 20万
• 依托单位: University of Hawaii
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2019
• 资助国家: 美国
• 起止时间: 2019-10-01 至 2024-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1911245&HistoricalAwards=false
• 关键词: AF; Small; Toward; Unified; Model

The project will study the challenges and limitations of combining parallelism and locality in algorithm design for modern many-core architectures. With data transfer being one of the primary bottlenecks in modern high-performance computing (HPC), parallel algorithms with better locality will result in more efficient utilization of the HPC resources, resulting in faster and more energy-efficient implementations. The applied aspect of the project will produce a collection of software libraries that can be used by modern HPC practitioners. The techniques discovered and developed during this project will be incorporated into the CS courses at the University of Hawaii, to educate future generation of students in more efficient techniques for modern parallel computing.The current large number of parallel, distributed and I/O-efficient models of computation, which capture the challenges of utilizing parallelism and locality, is confusing for both theoreticians and practitioners alike. This project will investigate the relationship between all of these models and the possibility of using the Parallel External Memory (PEM) model as a unifying model combining parallelism and locality. The results of this research will expand our collective understanding of the power and limitation of various existing models, answering the question why some fundamental problems are easy in some models, yet are hard in others.The project will develop a number of fully-scalable PEM algorithms, while identifying problems that don't admit full scalability. It will produce a number of new algorithmic techniques for combining parallelism and locality. The experimental aspect of the project will validate the performance and scalability of the produced algorithms by implementing them as software libraries. These libraries will be made publicly available in the form of open-source software.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

该项目将研究在现代众核架构的算法设计中结合并行性和局部性的挑战和限制。随着数据传输成为现代高性能计算（HPC）的主要瓶颈之一，具有更好局部性的并行算法将导致HPC资源的更有效利用，从而导致更快和更节能的实现。该项目的应用方面将产生一个可供现代HPC从业者使用的软件库集合。在这个项目中发现和开发的技术将被纳入计算机科学课程在夏威夷大学，教育未来一代的学生在更有效的技术，现代并行computing.The当前大量的并行，分布式和I/O高效的计算模型，捕捉利用并行性和局部性的挑战，是混淆的理论家和从业者一样。本项目将研究所有这些模型之间的关系，以及使用并行外部存储器（PEM）模型作为结合并行性和局部性的统一模型的可能性。这项研究的结果将扩大我们对各种现有模型的能力和局限性的集体理解，回答为什么一些基本问题在某些模型中很容易，而在其他模型中却很难的问题。该项目将开发一些完全可扩展的PEM算法，同时识别不允许完全可扩展的问题。它将产生许多新的算法技术，用于结合并行性和局部性。该项目的实验方面将通过将其实现为软件库来验证所产生算法的性能和可扩展性。该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

LCP-Aware Parallel String Sorting

LCP 感知并行字符串排序

• DOI: 10.1007/978-3-030-57675-2_21
• 发表时间: 2020
• 期刊: Euro-Par 2020: Parallel Processing
• 作者: Ellert, Jonas;Fischer, Johannes;Sitchinava, Nodari
• 通讯作者: Sitchinava, Nodari

Atomic Power in Forks: A Super-Logarithmic Lower Bound for Implementing Butterfly Networks in the Nonatomic Binary Fork-Join Model

分叉中的原子力：在非原子二元分叉连接模型中实现蝴蝶网络的超对数下界

• DOI: 10.1137/1.9781611976465.128
• 发表时间: 2021
• 期刊: Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA
• 作者: Goodrich, Michael T;Jacob, Riko;Sithinava, Nodari
• 通讯作者: Sithinava, Nodari

Locality-of-Reference Optimality of Cache-Oblivious Algorithms

缓存忽略算法的参考局部性最优性

• 发表时间: 2022
• 期刊: Symposium on Algorithmic Principles of Computer Systems
• 作者: Afshani, P.;Iacono, J.;Jayapaul, V.;Karsin, B.;Sitchinava, N.
• 通讯作者: Sitchinava, N.

Engineering Worst-Case Inputs for Pairwise Merge Sort on GPUs

在 GPU 上设计成对归并排序的最坏情况输入

• DOI: 10.1109/ipdps47924.2020.00119
• 发表时间: 2020
• 期刊: 2020 IEEE International Parallel and Distributed Processing Symposium (IPDPS
• 作者: Berney, Kyle;Sitchinava, Nodari
• 通讯作者: Sitchinava, Nodari

Beyond Binary Search: Parallel In-Place Construction of Implicit Search Tree Layouts

• DOI: 10.1109/tc.2021.3075392
• 发表时间: 2021-04
• 期刊: IEEE Transactions on Computers
• 影响因子: 3.7
• 作者: Kyle Berney;H. Casanova;Ben Karsin;Nodari Sitchinava