GPUを用いた巡回セールスマン問題に対する蟻コロニー最適化の効果的な実装(GPU・マルチコア,クラウド、ネットワーク及び一般)
スポンサーリンク
概要
- 論文の詳細を見る
本論文では.GPUを用いた蟻コロニー最適化手法の効果的な実装を提案する.提案する実装では,グローバルメモリのコアレッシングアクセスや共有メモリのバンクコンフリクトなど,GPUのアーキテクチャに由来する様々なプログラミング技法を考慮した.また,多数の蟻が次の都市をランダムに選択する際に,少ない計算で高確率に次の都市を見つけることが可能な反復ランダム試行を用いた手法を提案する.実験の結果,1002都市の巡回セールスマン問題に対する蟻コロニー最適化に対し,同様の処理を行うCPU実装で381.95秒かかる処理をNVIDIA社のGeForce GTX 580を用いて我々の実装は8.71秒で実行,つまり,43.47倍の高速化を実現した.
- 2012-10-05
著者
-
中野 浩嗣
広島大学大学院工学研究科
-
伊藤 靖朗
広島大学大学院工学研究科
-
中野 浩嗣
北陸先端科学技術大学院大学情報科学研究科
-
中野 浩嗣
北陸先端科学技術大学院大学
-
内田 晃裕
広島大学大学院工学研究科
関連論文
- 教育用・小規模組込みシステム用の超小型プロセッサと言語処理系
- 教育用・小規模組込みシステム用の超小型プロセッサと言語処理系
- 小型組込みシステムと教育のためのFPGA向けTiny Processing System(応用2)
- COMP2000-24 マルチホップパケット無線ネットワーク上のブロードキャストの確率アルゴリズム
- An efficient implementation of exhaustive verification of the Collatz conjecture using DSP48E blocks of Xilinx Virtex-5 FPGAs (リコンフィギャラブルシステム)
- FPGAのDSPブロックを最大限利用するRSA暗号ハードウェアアルゴリズム (ワイドバンドシステム)
- FPGAのDSPブロックを最大限利用するRSA暗号ハードウェアアルゴリズム (情報セキュリティ)
- FPGAのDSPブロックを最大限利用するRSA暗号ハードウェアアルゴリズム (情報処理)
- FPGAを用いたコラッツ予想の検証(応用3)
- ロジックエレメントを節約したFPGAラベリング(応用1)