CSR: Medium: Collaborative Research: Programming Abstractions and Systems Support for GPU-Based Acceleration of Irregular Applications

人们越来越关注使用图形处理单元（GPU）来提高图形域之外的应用程序的性能和能效。GPU特别适合运行执行类似于像素处理的操作的常规程序，并且在该领域的性能，价格和能效方面，它们可以提供比多核CPU更大的优势。GPU越来越多地出现在从手持设备到超级计算机的各种设备中，这并不奇怪。尽管常规算法非常重要，但计算生物学、数据挖掘和社交网络等新问题领域需要非常不同的算法基础：它们需要构建、计算和更新大型图。不幸的是，对于如何在当前的GPU架构上有效地实现不规则应用程序，人们了解得相对较少。 锁步操作等特性以及最小化线程发散和最大化内存合并的需求对高效实现不规则算法提出了特殊的挑战。然而，最近在手工移植不规则代码方面的一些成功表明，困难不在于GPU硬件，而在于由于缺乏通用的、易于理解的优化技术，编写和调整GPU代码的技术还不成熟。这项工作将开发编程符号，编译器优化，和运行时系统支持，这将使程序员能够在高抽象级别上表达他们的算法，但仍然产生良好的性能。预计的任务包括为重要的不规则算法生成高度优化的手写GPU实现，并将其添加到LonestarGPU基准测试套件中，识别高效GPU实现所需的常见优化模式和运行时系统支持，开发编程符号以允许软件开发人员在高抽象级别上指定不规则算法，实现从这些高级规范自动生成高性能GPU代码的合成系统，GPU相对于多核CPU更高的性能和更好的能效，社会效益。这项工作建立在实现这些好处的基础上，促进了GPU的更简单和更广泛的利用，并将更有效的实践纳入未来的编译器和GPU硬件。

There is growing interest in using Graphics Processing Units (GPUs) to increase the performance and the energy efficiency of applications outside the graphics domain. GPUs are particularly suited to run regular programs that perform operations similar to pixel processing, and they can offer a large advantage over multicore CPUs in terms of performance, price, and energy efficiency in this domain. Not surprisingly, GPUs are increasingly appearing in devices ranging from handhelds to supercomputers.Although regular algorithms are very important, new problem domains such as computational biology, data mining, and social networks necessitate very different algorithmic foundations: they require building, computing with, and updating large graphs. Unfortunately, relatively little is understood about how to implement irregular applications efficiently on current GPU architectures. Features such as lockstep operation and the need to minimize thread divergence and maximize memory coalescing pose particular challenges to efficient implementation of irregular algorithms. Nevertheless, some recent successes in hand-porting irregular codes suggest that the difficulties lie not in the GPU hardware but in the immaturity of the state of the art of writing and tuning GPU code due to the lack of general, well-understood optimization techniques.This work will develop programming notations, compiler optimizations, and runtime system support that will enable programmers to express their algorithms at a high level of abstraction but still yield good performance. Projected tasks include producing highly optimized handwritten GPU implementations of important irregular algorithms and adding them to the LonestarGPU benchmark suite, identifying common patterns of optimizations and runtime systems support needed for efficient GPU implementations, developing a programming notation to permit the software developer to specify irregular algorithms at a high level of abstraction, implementing a synthesis system that automatically generates high-performance GPU code from these high-level specifications, and developing course material for teaching GPU programming of irregular codes.The higher performance and better energy efficiency of GPUs relative to multicore CPUs has sincere societal benifits. This work builds on the realization of these benefits by facilitating simpler and more widespread utilization of GPUs and incorporating more effective practices into future compilers and GPU hardware.