AitF: FULL: Collaborative Research: Provably Efficient GPU Algorithms

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

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.