著者

武井 康浩 張山 昌論 亀山 充隆

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. RECONF, リコンフィギャラブルシステム (ISSN:09135685)

巻号頁・発行日

vol.114, no.75, pp.79-83, 2014-06-04

---

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