| 講演名 | 2017-11-06 FPGAを用いたグラフストリーム処理の一検討 松崎 貴之(熊本大), 尼崎 太樹(熊本大), 飯田 全広(熊本大), 久我 守弘(熊本大), 末吉 敏則(熊本大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | グラフ処理は局所性の低いメモリアクセスを行うという特性を持ち，ノード数が数億超えるような大規模なグラフを処理するのは容易ではない．このような不規則なメモリアクセスを避けて処理を行う手法にストリーム処理があり，グラフ処理にストリーム処理を適用することができれば，特有の不規則なメモリアクセスパターンを回避できると考えられる．そこで本稿では，グラフをストリームで表現し処理する手法についての検討を行う．ストリーム形式のPseudo-ZDD データを入力とし，これを主記憶に格納することなく演算することで，メモリアクセスの解消を図る．提案手法によって，グラフのストリームによる処理をFPGA を用いてハードウェア化し，その性能を評価したところ実行時間はCortex A9 CPU に対してノード数16,384 のとき最大で54 倍高速であった．また，リソース使用率に関してはZedboard およびCU105 のいずれの評価ボードでも1%未満で実装できることがわかった． |
| 抄録(英) | Graph processing has memory access with low locality, and it is not easy to process large-scale graphs which have the millions of nodes. Stream processing is a method of large-scale processing and it can avoid such irregular memory access. It is considered that a unique irregular memory access pattern can be avoided if stream processing can be applied to graph processing. In this paper, we examined a method of expressing and processing graphs as streams. We tried to solve memory access by inputting Pseudo-ZDD data in stream form and computing it without storing it in memory. Furthermore, we tried a hardware implementation of the proposed method using FPGA. As a result, the execution time was up to 54 times faster than the Cortex A9 CPU when the number of nodes was 16,384. We also found that resource utilization was less than 1% on either Zedboard or KCU 105 evaluation boards. |
| キーワード(和) | FPGA / グラフ処理 / ZDD / ストリーム処理 |
| キーワード(英) | FPGA / Graph processing / ZDD / Stream processing |
| 資料番号 | RECONF2017-38 |
| 発行日 | 2017-10-30 (RECONF) |
| 研究会情報 | |
| 研究会 | VLD / DC / CPSY / RECONF / CPM / ICD / IE / IPSJ-SLDM / IPSJ-EMB / IPSJ-ARC |
|---|---|
| 開催期間 | 2017/11/6(から3日開催) |
| 開催地（和） | くまもと県民交流館パレア |
| 開催地（英） | Kumamoto-Kenminkouryukan Parea |
| テーマ（和） | デザインガイア2017 -VLSI設計の新しい大地- |
| テーマ（英） | Design Gaia 2017 -New Field of VLSI Design- |
| 委員長氏名（和） | 越智 裕之(立命館大) / 井上 美智子(奈良先端大) / 中野 浩嗣(広島大) / 本村 真人(北大) / 廣瀬 文彦(山形大) / 日高 秀人(ルネサス エレクトロニクス) / 浜本 隆之(東京理科大) / 浜口 清治(島根大) / 渡辺 晴美(東海大) / 五島 正裕(NII) |
| 委員長氏名（英） | Hiroyuki Ochi(Ritsumeikan Univ.) / Michiko Inoue(NAIST) / Koji Nakano(Hiroshima Univ.) / Masato Motomura(Hokkaido Univ.) / Fumihiko Hirose(Yamagata Univ.) / Hideto Hidaka(Renesas) / Takayuki Hamamoto(Tokyo Univ. of Science) / Kiyoharu Hamaguchi(Shimane Univ.) / 渡辺 晴美(東海大) / Masahiro Goshima(NII) |
| 副委員長氏名（和） | 峯岸 孝行(三菱電機) / 福本 聡(首都大東京) / 入江 英嗣(東大) / 三吉 貴史(富士通研) / 柴田 裕一郎(長崎大) / 佐野 健太郎(東北大) / 武山 真弓(北見工大) / 永田 真(神戸大) / 児玉 和也(NII) / 木全 英明(NTT) |
| 副委員長氏名（英） | Noriyuki Minegishi(Mitsubishi Electric) / Satoshi Fukumoto(Tokyo Metropolitan Univ.) / Hidetsugu Irie(Univ. of Tokyo) / Takashi Miyoshi(Fujitsu) / Yuichiro Shibata(Nagasaki Univ.) / Kentaro Sano(Tohoku Univ.) / Mayumi Takeyama(Kitami Inst. of Tech.) / Makoto Nagata(Kobe Univ.) / Kazuya Kodama(NII) / Hideaki Kimata(NTT) |
| 幹事氏名（和） | 永山 忍(広島市大) / 新田 高庸(NTTデバイスイノベーションセンタ) / 吉村 正義(京都産大) / 金子 晴彦(東工大) / 大川 猛(宇都宮大) / 高前田 伸也(北大) / 谷川 一哉(広島市大) / 三好 健文(イーツリーズ・ジャパン) / 岩田 展幸(日大) / 中村 雄一(豊橋技科大) / 高宮 真(東大) / 橋本 隆(パナソニック) / 高橋 桂太(名大) / 河村 圭(KDDI総合研究所) / 許 浩沿(パナソニックセミコンダクタソリューションズ) / 密山 幸男(高知工科大) / 柴田 誠也(NEC) / 岡野 浩三(信州大) / 北村 崇師(産総研) / 早川 栄一(拓殖大) / 福田 浩章(芝浦工大) / 横山 孝典(東京都市大) / 小野 貴継(九大) / 近藤 正章(東大) / 長谷川 揚平(東芝) / 塩谷 亮太(名大) |
| 幹事氏名（英） | Shinobu Nagayama(Hiroshima City Univ.) / Koyo Nitta(NTT) / Masayoshi Yoshimura(Kyoto Sangyo Univ.) / Haruhiko Kaneko(Tokyo Inst. of Tech.) / Takeshi Ohkawa(Utsunomiya Univ.) / Shinya Takameda(Hokkaido Univ.) / Kazuya Tanigawa(Hiroshima City Univ.) / Takefumi Miyoshi(e-trees.Japan) / Nobuyuki Iwata(Nihon Univ.) / Yuichi Nakamura(Toyohashi Univ. of Tech.) / Makoto Takamiya(Univ. of Tokyo) / Takashi Hashimoto(Panasonic) / Keita Takahashi(Nagoya Univ.) / Kei Kawamura(KDDI Research) / Ko Kyo(Panasonic) / Yukio Mitsuyama(Kochi Univ. of Tech.) / Seiya Shibata(NEC) / 岡野 浩三(信州大) / 北村 崇師(産総研) / 早川 栄一(拓殖大) / 福田 浩章(芝浦工大) / 横山 孝典(東京都市大) / Takatsugu Ono(Kyushu Univ.) / Masaaki Kondo(Univ. of Tokyo) / Yohei Hasegawa(Toshiba) / Ryota Shioya(Nagoya Univ.) |
| 幹事補佐氏名（和） | / 新井 雅之(日大) / 伊藤 靖朗(広島大) / 津邑 公暁(名工大) / 小林 悠記(NEC) / 中原 啓貴(東工大) / 赤毛 勇一(NTTデバイスイノベーションセンタ) / 夏井 雅典(東北大) / 柘植 政利(ソシオネクスト) / 伊藤 浩之(東工大) / 範 公可(電通大) / 松尾 康孝(NHK) / 早瀬 和也(NTT) |
| 幹事補佐氏名（英） | / Masayuki Arai(Nihon Univ.) / Yasuaki Ito(Hiroshima Univ.) / Tomoaki Tsumura(Nagoya Inst. of Tech.) / Yuuki Kobayashi(NEC) / Hiroki Nakahara(Tokyo Inst. of Tech.) / Yuichi Akage(NTT) / Masanori Natsui(Tohoku Univ.) / Masatoshi Tsuge(Socionext) / Hiroyuki Ito(Tokyo Inst. of Tech.) / Pham Konkuha(Univ. of Electro-Comm.) / Yasutaka Matsuo(NHK) / Kazuya Hayase(NTT) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on VLSI Design Technologies / Technical Committee on Dependable Computing / Technical Committee on Computer Systems / Technical Committee on Reconfigurable Systems / Technical Committee on Component Parts and Materials / Technical Committee on Integrated Circuits and Devices / Technical Committee on Image Engineering / Special Interest Group on System and LSI Design Methodology / Special Interest Group on Embedded Systems / Special Interest Group on System Architecture |
|---|---|
| 本文の言語 | JPN-ONLY |
| タイトル（和） | FPGAを用いたグラフストリーム処理の一検討 |
| サブタイトル（和） | |
| タイトル（英） | |
| サブタイトル（和） | |
| キーワード(1)（和/英） | FPGA / FPGA |
| キーワード(2)（和/英） | グラフ処理 / Graph processing |
| キーワード(3)（和/英） | ZDD / ZDD |
| キーワード(4)（和/英） | ストリーム処理 / Stream processing |
| 第 1 著者 氏名（和/英） | 松崎 貴之 / Takayuki Matsuzaki |
| 第 1 著者 所属（和/英） | 熊本大学(略称：熊本大) Kumamoto University(略称：Kumamoto Univ.) |
| 第 2 著者 氏名（和/英） | 尼崎 太樹 / Motoki Amagasaki |
| 第 2 著者 所属（和/英） | 熊本大学(略称：熊本大) Kumamoto University(略称：Kumamoto Univ.) |
| 第 3 著者 氏名（和/英） | 飯田 全広 / Masahiro Iida |
| 第 3 著者 所属（和/英） | 熊本大学(略称：熊本大) Kumamoto University(略称：Kumamoto Univ.) |
| 第 4 著者 氏名（和/英） | 久我 守弘 / Morihiro Kuga |
| 第 4 著者 所属（和/英） | 熊本大学(略称：熊本大) Kumamoto University(略称：Kumamoto Univ.) |
| 第 5 著者 氏名（和/英） | 末吉 敏則 / Toshinori Sueyoshi |
| 第 5 著者 所属（和/英） | 熊本大学(略称：熊本大) Kumamoto University(略称：Kumamoto Univ.) |
| 発表年月日 | 2017-11-06 |
| 資料番号 | RECONF2017-38 |
| 巻番号（vol） | vol.117 |
| 号番号（no） | RECONF-279 |
| ページ範囲 | pp.7-12(RECONF), |
| ページ数 | 6 |
| 発行日 | 2017-10-30 (RECONF) |