C2CU : A CUDA C Program Generator for Bulk Execution of a Sequential Algorithm
C2CU : A CUDA C Program Generator for Bulk Execution of a Sequential Algorithm
复制标题
DOI：
10.1007/978-3-319-11194-0_14
复制
发表时间：
2014-08
期刊：
影响因子：
--
通讯作者：
Daisuke Takafuji;K. Nakano;Yasuaki Ito
中科院分区：
文献类型：
--
作者：
Daisuke Takafuji;K. Nakano;Yasuaki Ito
一些重要的任务，包括矩阵计算、信号处理、排序、动态规划、加密和解密，都可以通过不经意的顺序算法来执行。如果每次访问的地址不依赖于输入数据，则顺序算法是不重要的。顺序算法的批量执行是针对许多独立的输入依次或并行地执行它。许多工作致力于为单个输入设计和实现并行算法。然而，这些工作都没有评估这些算法的批量执行性能。本文的第一个贡献是提出了一种用于批量执行不经意顺序算法的时间最优实现。我们的第二个贡献是开发了一个名为 C2CU 的工具，它可以自动生成 CUDA C 程序，用于批量执行不经意的顺序算法。 C2CU 已用于生成 CUDA C 程序，用于批量执行双调排序、Floyd-Warshall 和 Montgomery 模乘算法。与单个 CPU 上的顺序实现相比，上述算法生成的 CUDA C 程序的运行速度分别快了 199 倍、54 倍和 78 倍。
Several important tasks, including matrix computation, signal processing, sorting, dynamic programming, encryption, and decryption, can be performed byoblivioussequential algorithms. A sequential algorithm is oblivious if an address accessed at each time does not depend on the input data. Abulkexecution of a sequential algorithm is to execute it for many independent inputs in turn or in parallel. A number of works have been devoted to design and implement parallel algorithms for a single input. However, none of these works evaluated the bulk execution performance of these algorithms. The first contribution of this paper is to present a time‐optimal implementation for bulk execution of an oblivious sequential algorithm. Our second contribution is to develop a tool, named C2CU, which automatically generates a CUDA C program for a bulk execution of an oblivious sequential algorithm. The C2CU has been used to generate CUDA C programs for the bulk execution of the bitonic sorting, Floyd‐Warshall, and Montgomery modulo multiplication algorithms. Compared to a sequential implementation on a single CPU, the generated CUDA C programs for the above algorithms run, respectively, 199, 54, and 78 times faster.