超並列SIMD型プロセッサMXコアへのアントコロニー最適化法の実装と評価

摘要

著者らは，株式会社ルネサステクノロジが開発したマトリクス構造超並列プロセッサコア（以下MXコア）に注目し，評価，研究を行っている．MXコアはビットシリアル演算器を多数搭載したSIMD (Single Instruction Multiple Data)型のプロセッサである．本研究ではMXコアの高並列処理に注目し，解の探索を独立して行うことが可能な組合せ最適化問題の近似解法であるアントコロニー最適化法(ACO)をMXコアに実装する．ACOでTSP (Traveling Salesman Problem)を解くことで，解の探索における並列度とMXコアの処理能力の評価を行う．その結果，一度に100並列以上で解を導出することができ，MXコアの有効性を確認した．また，Intel Pentium M 1.1GHzと比較した時，同一周波数に換算した場合，最大で1.7倍の速度向上が得られた．