| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2014-11-14 09:50 GPU-BOXにおける中規模グラフに適した並列幅優先探索手法 ○三石拓司（慶大）・鈴木 順・林 佑樹・管 真樹（NEC）・天野英晴（慶大）  CPSY2014-66 |
|
| 抄録 | （和） | グラフ探索アルゴリズムの1つである幅優先探索(BFS)は様々な分野で応用されており，マルチGPUシステムを用いた高速化が近年盛んに研究されている．本研究では，bin sortを応用してCUDAスレッド間のタスクバランスを整えることで，頂点数が$2^{15}$～$2^{25}$程度の中規模グラフに有効な並列BFSアルゴリズムを提案し，Ethernetベースのシステム仮想化技術ExpEtherを用いたマルチGPUシステムの試作機であるGPU-BOXを利用して評価を行う．また2つの先行研究のBFSと比較することで本研究で提案するBFSの特徴と課題について分析する．結果としては，提案BFSを2つの先行研究BFSと比較するとそれぞれ最大6.3倍，10倍の性能を達成し，GPU-BOXを用いた評価ではGPU数を増やすことで緩やかではあるが性能向上が見られた． |
| （英） | Breadth First Search(BFS) has been applied in various fields related to big-data processing, and its acceleration with multi-GPU systems has been actively researched in recent years. Our parallel BFS algorithm is designed for middle scale graph so as to distribute tasks to CUDA threads uniformly by the bin sort algorithm. We compared our BFS algorithm with two BFS algorithms in previous researches for a common multi-GPU system with a single node. Our proposed BFS achieved 6.3 and 10 times faster than conventional BFS algorithms. Also, as increasing the number of GPUs, our BFS achieved gradual speed up on GPU-BOX. | |
| キーワード | （和） | GPU / クラスタ / ExpEther / グラフアルゴリズム / スケーラビリティ / / / |
| （英） | GPU / Cluster / ExpEther / Graph Algorithm / Scalability / / / | |
| 文献情報 | 信学技報, vol. 114, no. 302, CPSY2014-66, pp. 69-74, 2014年11月. | |
| 資料番号 | CPSY2014-66 | |
| 発行日 | 2014-11-06 (CPSY) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | CPSY2014-66 |
|
| 研究会情報 | |
| 研究会 | CPSY |
| 開催期間 | 2014-11-13 - 2014-11-14 |
| 開催地（和） | 広島大学 |
| 開催地（英） | Hiroshima University |
| テーマ（和） | クラウドコンピューティングおよび一般 |
| テーマ（英） | Cloud Computing, etc. |
| 講演論文情報の詳細 | |
| 申込み研究会 | CPSY |
| 会議コード | 2014-11-CPSY |
| 本文の言語 | 日本語 |
| タイトル（和） | GPU-BOXにおける中規模グラフに適した並列幅優先探索手法 |
| サブタイトル（和） | |
| タイトル（英） | Parallel Breadth-First Search for Middle Scale Graph on GPU-BOX |
| サブタイトル（英） | |
| キーワード(1)（和/英） | GPU / GPU |
| キーワード(2)（和/英） | クラスタ / Cluster |
| キーワード(3)（和/英） | ExpEther / ExpEther |
| キーワード(4)（和/英） | グラフアルゴリズム / Graph Algorithm |
| キーワード(5)（和/英） | スケーラビリティ / Scalability |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 三石 拓司 / Takuji Mitsuishi / ミツイシ タクジ |
| 第1著者 所属（和/英） | 慶應義塾大学 (略称： 慶大) Keio University (略称： Keio Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 鈴木 順 / Jun Suzuki / スズキ ジュン |
| 第2著者 所属（和/英） | 日本電気株式会社 (略称： NEC) NEC Corporation (略称： NEC) |
| 第3著者 氏名（和/英/ヨミ） | 林 佑樹 / Yuki Hayashi / ハヤシ ユウキ |
| 第3著者 所属（和/英） | 日本電気株式会社 (略称： NEC) NEC Corporation (略称： NEC) |
| 第4著者 氏名（和/英/ヨミ） | 管 真樹 / Masaki Kan / カン マサキ |
| 第4著者 所属（和/英） | 日本電気株式会社 (略称： NEC) NEC Corporation (略称： NEC) |
| 第5著者 氏名（和/英/ヨミ） | 天野 英晴 / Hideharu Amano / アマノ ヒデハル |
| 第5著者 所属（和/英） | 慶應義塾大学 (略称： 慶大) Keio University (略称： Keio Univ.) |
| 第6著者 氏名（和/英/ヨミ） | / / |
| 第6著者 所属（和/英） | (略称： ) (略称： ) |
| 第7著者 氏名（和/英/ヨミ） | / / |
| 第7著者 所属（和/英） | (略称： ) (略称： ) |
| 第8著者 氏名（和/英/ヨミ） | / / |
| 第8著者 所属（和/英） | (略称： ) (略称： ) |
| 第9著者 氏名（和/英/ヨミ） | / / |
| 第9著者 所属（和/英） | (略称： ) (略称： ) |
| 第10著者 氏名（和/英/ヨミ） | / / |
| 第10著者 所属（和/英） | (略称： ) (略称： ) |
| 第11著者 氏名（和/英/ヨミ） | / / |
| 第11著者 所属（和/英） | (略称： ) (略称： ) |
| 第12著者 氏名（和/英/ヨミ） | / / |
| 第12著者 所属（和/英） | (略称： ) (略称： ) |
| 第13著者 氏名（和/英/ヨミ） | / / |
| 第13著者 所属（和/英） | (略称： ) (略称： ) |
| 第14著者 氏名（和/英/ヨミ） | / / |
| 第14著者 所属（和/英） | (略称： ) (略称： ) |
| 第15著者 氏名（和/英/ヨミ） | / / |
| 第15著者 所属（和/英） | (略称： ) (略称： ) |
| 第16著者 氏名（和/英/ヨミ） | / / |
| 第16著者 所属（和/英） | (略称： ) (略称： ) |
| 第17著者 氏名（和/英/ヨミ） | / / |
| 第17著者 所属（和/英） | (略称： ) (略称： ) |
| 第18著者 氏名（和/英/ヨミ） | / / |
| 第18著者 所属（和/英） | (略称： ) (略称： ) |
| 講演者 | 第1著者 |
| 発表日時 | 2014-11-14 09:50:00 |
| 発表時間 | 25分 |
| 申込先研究会 | CPSY |
| 資料番号 | CPSY2014-66 |
| 巻番号（vol） | vol.114 |
| 号番号（no） | no.302 |
| ページ範囲 | pp.69-74 |
| ページ数 | 6 |
| 発行日 | 2014-11-06 (CPSY) |
[研究会発表申込システムのトップページに戻る]