大規模グラフ上の最短経路探索のためのFPGAアクセラレータの設計

摘要

ノード数，エッジ数が非常に大きいグラフにおける最短経路問題は，様々な分野で応用されている．しかしながら，ダイクストラ法などの最短経路検索アルゴリズムは，複雑な処理が含まれているため，GPUなどのアクセラレータを用いた高速化が難しい．本稿では，FPGAを用いた最短経路検索アルゴリズムのための専用アクセラレータを提案している．大規模グラフを効率的に処理するアーキテクチャを設計するために，タスク並列スケジューリング法，メモリ上のグラフデータ構造について考察している．性能評価の結果から，Altera StratixVに約80万ノードを有するグラフを処理するアーキテクチャを実装することが可能であり，Intel Core i7と比べてサイクル数あたりの効率が良い処理を実現することを確認した．