文献

J-GLOBAL ID：201702246458736523   整理番号：17A1942850

FPGAを用いたグラフストリーム処理の一検討

A Study on Graph Processing by Stream Using FPGA

著者 (5件)： 松崎貴之 (熊本大) ,  尼崎太樹 (熊本大) ,  飯田全広 (熊本大) ,  久我守弘 (熊本大) ,  末吉敏則 (熊本大)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 117  号： 279(RECONF2017 37-49)  ページ： 7-12  発行年： 2017年10月30日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： グラフ処理は局所性の低いメモリアクセスを行うという特性を持ち,ノード数が数億超えるような大規模なグラフを処理するのは容易ではない。このような不規則なメモリアクセスを避けて処理を行う手法にストリーム処理があり,グラフ処理にストリーム処理を適用することができれば,特有の不規則なメモリアクセスパターンを回避できると考えられる。そこで本稿では,グラフをストリームで表現し処理する手法についての検討を行う。ストリーム形式のPseudo-ZDDデータを入力とし,これを主記憶に格納することなく演算することで,メモリアクセスの解消を図る。提案手法によって,グラフのストリームによる処理をFPGAを用いてハードウェア化し,その性能を評価したところ実行時間はCortex A9CPUに対してノード数16,384のとき最大で54倍高速であった。また,リソース使用率に関してはZedboardおよびKCU105のいずれの評価ボードでも1%未満で実装できることがわかった。(著者抄録)

シソーラス用語： *FPGA ,  *データ処理 ,  マイクロプロセッサ ,  高速化 ,  資源 ,  アルゴリズム ,  *グラフ理論 ,  二分決定グラフ ,  改変 ,  実験 ,  評価実験
準シソーラス用語： ストリーム処理 ,  計算資源 ,  ZDD ,  ハードウェア化

分類 (2件)： ディジタル計算機ハードウェア一般  (JC04010C) ,  計算機利用技術一般  (JE01000C)

引用文献 (9件)：

• A. Ching, S. Edunov, M. Kabiljo, D. Logothetis, and S. Muthukrishnan, “One trillion edges: Graph processing at facebook-scale,” Proc. VLDB Endow., vol.8, no.12, pp.1804-1815, Aug. 2015.
• O. Mencer, Z. Huang, and L. Huelsbergen, “HAGAR: Efficient multi-context graph processors,” Proceedings of the Reconfigurable Computing Is Going Mainstream, 12th International Conference on Field-Programmable Logic and Applications, pp.915-924, FPL '02, Springer-Verlag, 2002.
• E. Nurvitadhi, G. Weisz, Y. Wang, S. Hurkat, M. Nguyen, J.C. Hoe, J.F. Martinez, and C. Guestrin, “GraphGen: An FPGA framework for vertex-centric graph computation,” 2014 IEEE 22nd Annual International Symposium on Field-Programmable Custom Computing Machines, pp.25-28, May 2014.
• T. Inoue, H. Iwashita, J. Kawahara, and S. Minato, “Graphillion: software library for very large sets of labeled graphs,” International Journal on Software Tools for Technology Transfer, vol.18, no.1, pp.57-66, Feb. 2016.
• S. Minato, “Zero-suppressed BDDs and their applications,” International Journal on Software Tools for Technology Transfer, vol.3, no.2, pp.156-170, May 2001.

タイトルに関連する用語 (3件)： FPGA ,  グラフ ,  ストリーム処理