講演抄録/キーワード |
講演名 |
2014-11-14 10:15
C2CU : A CUDA C Program Generator for Bulk Execution of a Sequential Algorithm ○Daisuke Takafuji・Koji Nakano・Yasuaki Ito(Hiroshima Univ.) CPSY2014-67 |
抄録 |
(和) |
アルゴリズム実行中の各ステップにおいてアクセスされるアドレスが入力に依存しないシーケンシャルアルゴリズムを,オブリビアスアルゴリズムという.複数の独立した入力に対し,順にまたは並列に実行することを,シーケンシャルアルゴリズムのバルク実行という.本稿では,複数の独立した入力に対し,オブリビアスなシーケンシャルアルゴリズムのバルク実行を行うCUDA Cプログラムを自動生成するツールを開発した.このツールを使うと,オブリビアスなシーケンシャルアルゴリズムのC言語プログラムから,そのバルク実行を行うCUDA Cプログラムに自動で変換することが可能である.生成されたCUDA Cプログラムは,CUDAで動作可能なGPUで実行可能である.我々は,バイトニックソート,フロイド・ワーシャル法,モンゴメリ乗算アルゴリズムに対するバルク実行のCUDA CプログラムをGeForce GTX Titan上に実装し,Intel Xeon CPUでの実装と比較を行なった.その結果,バイトニックソートでは199倍,フロイド・ワーシャル法では54倍,モンゴメリ乗算アルゴリズムでは78倍の高速化を実現した. |
(英) |
A sequential algorithm is oblivious if an address accessed at each time does not depend on input data. Many important tasks including matrix computation, signal processing, sorting, dynamic programming, and encryption/decryption can be performed by oblivious sequential algorithms. Bulk execution of a sequential algorithm is to execute it for many independent inputs in turn or in parallel. The main contribution of this paper is to develop a tool that generates a CUDA C program for the bulk execution of an oblivious sequential algorithm. More specifically, our tool automatically converts a C language program describing an oblivious sequential algorithm into a CUDA C program that performs the bulk execution of the C language program. Generated C programs can be executed in CUDA-enabled GPUs. We have implemented CUDA C programs for the bulk execution of bitonic sorting algorithm, Floyd-Warshall algorithm, and Montgomery modulo multiplication. Our implementations running on GeForce GTX Titan for the bulk execution can be 199 times faster for bitonic sort, 54 times faster for Floyd-Warshall algorithm, and 78 times faster for Montgomery modulo multiplication, over the implementations on a single Intel Xeon CPU. |
キーワード |
(和) |
GPGPU / CUDA / バルク実行 / オブリビアスアルゴリズム / フロイド・ワーシャル法 / モンゴメリ乗算アルゴリズム / / |
(英) |
GPGPU / CUDA / oblivious algorithms / Floyd-Warshall algorithm / Montgomery modulo multiplication / / / |
文献情報 |
信学技報, vol. 114, no. 302, CPSY2014-67, pp. 75-80, 2014年11月. |
資料番号 |
CPSY2014-67 |
発行日 |
2014-11-06 (CPSY) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
CPSY2014-67 |