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资源，从而更快，更节能。该项目的应用方面将产生一系列软件库，可供现代HPC从业人员使用。该项目期间发现和开发的技术将纳入夏威夷大学的CS课程中，以教育未来的学生以更有效的现代平行计算技术进行更有效的技术。当前的大量并行，分布式和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.

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

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