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开发一个简单但准确的理论模型，为算法评估定义明确的指导方针和复杂性指标。PI将开发和实施算法，以改善组合算法、计算几何、可视化、搜索算法和数据结构领域GPU上通用计算的最新代码库。