AitF: FULL: Collaborative Research: Provably Efficient GPU Algorithms

AitF：完整：协作研究：可证明高效的 GPU 算法

• 批准号: 1533564
• 负责人: Claudio Silva
• 金额: $ 40万
• 依托单位: New York University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-09-01 至 2021-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1533564&HistoricalAwards=false
• 关键词: AitF; FULL; Collaborative; Research; Provably

Graphics processing units (GPUs) were originally developed as specialized hardware exclusively for graphics rendering. In recent years they have become massively parallel systems with hundreds of processing cores supporting thousands of threads. Given their computational potential, they are now used to support general-purpose computation via high-level programming languages. As a result, they have become a standard platform for high-performance computing (HPC) simulations in natural sciences.However, there is still very little understanding of what types of algorithms translate into efficient GPU programs, and many implementations rely on a limited number of design patterns and many rounds of trial-and-error. There is a need for simple but accurate algorithmic models to get a wider algorithmic community involved in GPU computing. The project will develop such a model, intended to have the transformative effect of enabling algorithms researchers to focus their efforts on creating algorithms for GPUs in a way that is currently not possible, increasing the algorithmic knowledgebase in GPU computing. Over time, more efficient algorithms will lead to better utilization of computing resources and reuse of code implemented as libraries. Such a model for GPUs will also enable teaching GPU computing to a wider group of students, similarly to how sequential and PRAM algorithms are currently taught.This project will study the algorithmic aspects of GPU computing and will develop a simple but accurate theoretical model for GPUs, that will define clear guidelines and complexity metrics for algorithm evaluation. The PIs will develop and implement algorithms that will improve the state of the art code base of general purpose computation on GPUs in the areas of combinatorial algorithms, computational geometry, visualization, search algorithms, and data structures.

图形处理单元 (GPU) 最初是作为专门用于图形渲染的专用硬件而开发的。近年来，它们已成为大规模并行系统，拥有数百个处理核心，支持数千个线程。鉴于其计算潜力，它们现在用于通过高级编程语言支持通用计算。 因此，它们已成为自然科学中高性能计算（HPC）模拟的标准平台。然而，对于哪些类型的算法转化为高效的 GPU 程序仍然知之甚少，并且许多实现依赖于有限的数量。设计模式和多轮试错。需要简单但准确的算法模型来让更广泛的算法社区参与 GPU 计算。该项目将开发这样一个模型，旨在产生变革性的效果，使算法研究人员能够集中精力以目前不可能的方式为 GPU 创建算法，从而增加 GPU 计算中的算法知识库。随着时间的推移，更高效的算法将导致更好地利用计算资源和重用作为库实现的代码。这种 GPU 模型还将能够向更广泛的学生群体教授 GPU 计算，类似于目前教授顺序算法和 PRAM 算法的方式。该项目将研究 GPU 计算的算法方面，并将开发一个简单但准确的 GPU 理论模型，这将为算法评估定义明确的指导方针和复杂性指标。 PI 将开发和实施算法，以改进组合算法、计算几何、可视化、搜索算法和数据结构领域 GPU 通用计算的最先进代码库。