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

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