一句话：提出面向 GPU 等层次化并行架构的高效线性递推算法，并通过 DSL 代码生成器自动产出优化的 CUDA 代码。
线性递推涵盖前缀和、数字滤波器等基本计算，但结果值之间存在依赖，并行化困难。本文提出一种新的工作与空间高效的线性递推算法，适合自动并行化与 GPU 等层次化大规模并行架构。作者在领域特定代码生成器中实现该方法，自动生成优化的 CUDA 代码。评估表明：对标准前缀和与单级 IIR 滤波器，生成代码在大输入上达到内存拷贝吞吐量，这是理论上限；对高阶前缀和，性能接近文献中最快的手写代码；对基于元组的前缀和与数字滤波器，自动并行化代码优于此前最快的实现。
Linear recurrences encompass many fundamental computations including prefix sums and digital filters. Later result values depend on earlier result values in recurrences, making it a challenge to compute them in parallel. We present a new work- and space-efficient algorithm to compute linear recurrences that is amenable to automatic parallelization and suitable for hierarchical massively-parallel architectures such as GPUs. We implemented our approach in a domain-specific code generator that emits optimized CUDA code. Our evaluation shows that, for standard prefix sums and single-stage IIR filters, the generated code reaches the throughput of memory copy for large inputs, which cannot be surpassed. On higher-order prefix sums, it performs nearly as well as the fastest handwritten code from the literature. On tuple-based prefix sums and digital filters, our automatically parallelized code outperforms the fastest prior implementations.
DOI 原文 ·
@inproceedings{paperbot4264,
title = {Automatic Hierarchical Parallelization of Linear Recurrences},
author = {Sepideh Maleki and Martin Burtscher},
booktitle = {ASPLOS},
year = {2018},
doi = {10.1145/3173162.3173168}
}