Technical Reports on Information and
Computer Science from Kochi
Vol. 4 (2012), No. 8
GPGPUを用いた迷路配線の並列アルゴリズムの一手法
A Parallel Algorithm for Maze-Routing on GPGPUSoC
藤井 良弥1,
中井 駿介2,
寺田 翔太2,
村岡 道明3,
豊永 昌彦3
1. 高知大学理学部
2. 高知大学大学院理学専攻
3. 高知大学 情報講座
要旨
本研究は，短TAT設計に向けたVLSIレイアウト設計の自動配線について，並列迷路配線法（1層，多層）の提案とその効果の検証をおこなったものである．提案する並列迷路配線法は，GPGPUにおけるスレッドを，各検索点に割り当てて同時に候補点を検索する．新たな検索点リストの作成においては，並列化したオフセット処理をおこなっている．
実験によりそれらの高速化の効果を調べたところ，並列1層配線法では，サイズ20～100グリッド四方の配線領域で最大8.3倍，並列多層配線法ではサイズ20～40グリッド四方の配線領域で最大12.7倍の高速化が確認された．
(2012年3月31日 受付)
全文(PDF) 1,996,671 bytes