| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 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 |
|
| 研究会情報 | |
| 研究会 | CPSY |
| 開催期間 | 2014-11-13 - 2014-11-14 |
| 開催地（和） | 広島大学 |
| 開催地（英） | Hiroshima University |
| テーマ（和） | クラウドコンピューティングおよび一般 |
| テーマ（英） | Cloud Computing, etc. |
| 講演論文情報の詳細 | |
| 申込み研究会 | CPSY |
| 会議コード | 2014-11-CPSY |
| 本文の言語 | 英語 |
| タイトル（和） | |
| サブタイトル（和） | |
| タイトル（英） | C2CU : A CUDA C Program Generator for Bulk Execution of a Sequential Algorithm |
| サブタイトル（英） | |
| キーワード(1)（和/英） | GPGPU / GPGPU |
| キーワード(2)（和/英） | CUDA / CUDA |
| キーワード(3)（和/英） | バルク実行 / oblivious algorithms |
| キーワード(4)（和/英） | オブリビアスアルゴリズム / Floyd-Warshall algorithm |
| キーワード(5)（和/英） | フロイド・ワーシャル法 / Montgomery modulo multiplication |
| キーワード(6)（和/英） | モンゴメリ乗算アルゴリズム / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 高藤 大介 / Daisuke Takafuji / タカフジ ダイスケ |
| 第1著者 所属（和/英） | 広島大学 (略称： 広島大) Hiroshima University (略称： Hiroshima Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 中野 浩嗣 / Koji Nakano / ナカノ コウジ |
| 第2著者 所属（和/英） | 広島大学 (略称： 広島大) Hiroshima University (略称： Hiroshima Univ.) |
| 第3著者 氏名（和/英/ヨミ） | 伊藤 靖朗 / Yasuaki Ito / イトウ ヤスアキ |
| 第3著者 所属（和/英） | 広島大学 (略称： 広島大) Hiroshima University (略称： Hiroshima Univ.) |
| 講演者 | 第1著者 |
| 発表日時 | 2014-11-14 10:15:00 |
| 発表時間 | 25分 |
| 申込先研究会 | CPSY |
| 資料番号 | CPSY2014-67 |
| 巻番号（vol） | vol.114 |
| 号番号（no） | no.302 |
| ページ範囲 | pp.75-80 |
| ページ数 | 6 |
| 発行日 | 2014-11-06 (CPSY) |
[研究会発表申込システムのトップページに戻る]