著者
武井 康浩 張山 昌論 亀山 充隆
出版者
一般社団法人電子情報通信学会
雑誌
電子情報通信学会技術研究報告. RECONF, リコンフィギャラブルシステム (ISSN:09135685)
巻号頁・発行日
vol.114, no.75, pp.79-83, 2014-06-04

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

知能自動車の知能処理は将来のシステムLSIの応用として期待されている.知能自動車への応用が実現可能となれば,ありとあらゆるリアルワールド応用が可能になる。このようなシステムの実現には,システムLSIのハイレベル階層の開発技術要素を研究する上での好例となる.本研究ではこのような観点から,主に以下の要素技術に関する研究を行った。1.高安全知能自動車用VLSIプロセッサチップファミリの形成高安全知能自動車のための世界最高性能VLSIプロセッサチップファミリの開発を行った。これらは,ステレオビジョンVLSIプロセッサ,オプティカルフロー処理VLSIプロセッサ,軌道計画VLSIプロセッサ,確率推論に基づく軌道予測などであった。これらのVLSIコンピユーティングの計算量減少を目的とした,VLSI向きアルゴリズムレベルも考察した。また,システムLSIの実用化を推進する1つの方策として,現在のFPGAの性能をはるかに超えるフィールドプログラマブルVLSIの開発も行った。2.システムインテグレーションと知能アルゴリズムリアルワールドの環境情報をセンシングし,将来起こるであろう環境の変化を予測することが必要である。計測値にも予測値にも誤差が含まれることを十分考慮したシステムインテグレーションが重要であり,一定サンプル周期毎に同一処理を繰返すリアルワールド信号処理をモデルを構築し,サンプル周期の満たすべき要件を考察した。3.VLSIプロセッサの構成理論メモリと演算部との間の配線による性能ボトルネックを解決するため,記憶と演算を一体化させたロジックインメモリアーキテクチャに基づくVLSIプロセッサの構成法を提案し,その有用性を実証した。リニアアレーやバス構造などの簡単な相互結合回路網を有するロジックインメモリアーキテクチャモデルにおいて,ハードウェア量制約下での処理時間電力最小化問題の解法を考察した。これらも含めた一般化されたVLSIプロセッサのハイレベルシンセシス問題への拡張も行い,高安全知能自動車用VLSIプロセッサの具体例を通して,以下のような最適化問題に対し実用的な段階により近づけることができた。・「チップ面積制約下での,演算遅れ時間最小化」・「演算遅れ時間制約下での,チップ面積最小化」・「チップ面積と処理時間制約下で消費エネルギーの最小化」