大規模グラフ処理のための再構成可能カスタムアクセラレータの開発

点击翻译按钮获取中文摘要

本年度の研究実績として、外部ストレージとのデータ転送時間を削減するためのグラフデータ圧縮法、および最短経路検索の計算に必要な中間結果の記憶量の削減手法を提案した。大規模グラフにおける最短経路検索を処理する場合において、入力グラフのデータ量が外部メモリ以上の場合は転送帯域の小さいストレージを使用する必要があり、転送時間が増大する。そのため、コンパクトな記憶量と高効率な処理を両立する簡潔データ構造を入力グラフに適用して、データ伸長のためのハードウェアをFPGAに実装した。アメリカの道路ネットワーク（2395万ノード、5833万エッジ）を簡潔グラフ化した場合のデータ量について、エッジのアドレスを示すIndex情報のデータ量が88%削減されていることが確認された。しかしながら，エッジの重みと接続ノードを示すデータ量が大きいため、グラフ全体のデータ量の削減率が18%にとどまっていることが確認されたため、テキスト圧縮を応用したデータ圧縮法の応用を検討している。最短経路検索における中間結果の記憶量削減について、最短経路問題のアルゴリズムであるダイクストラ法におけるノードアクセスの順序を考慮して、現在ノードにおける距離のデータを専用レジスタに記憶して、新たに現在ノードに隣接した未確定ノードのデータを前の現在ノードデータに上書きできるアクセラレータをFPGAに実装した。格子グラフにおける1 点対全点最短経路問題の処理中にノードメモリに格納されるノードデータ数について、全体のノード数の約1/3 程度であることが確認された。また、 FPGAアクセラレータの処理性能の見積もりをCPUと比較すると，ノード数が4096 のグラフの最短経路検索に対して，CPU の約60 倍の処理速度になる見積もりが得られた。